message-passing | Brack's Blog

Tutorial—LDPC part I

August 8, 2011 Leave a comment

我最近的project是关于LDPC的，所以读了一些关于LDPC的资料，只敢说略有了解。想想当初对LDPC的一片茫然，只想通过这几篇blog对一些需要帮助的朋友提供一些帮助。其实网上的LDPC的介绍，tutorial，多如牛毛，但是多是关于介绍LDPC的历史，decoding算法的描述。往往读完了之后一片茫然，也许这个算法是很棒，能够很好的进行decoding，但是这个算法是如何设计的，以及面对有特殊要求的code的时候，如何设计我们自己的LDPC，并没有一个很好的阐述，甚至不明白为什么算法会设计成这个样子。

我想通过这几篇blog来说明我对LDPC的认知，希望对大家有所帮助。这里强力推荐《modern coding theory》 by Tom Richardson and Rüdiger Urbanke，大师级的著作。的确很难读懂，但是这本书对coding的阐述非常系统，强烈建议读一下。

这篇post，我想先介绍一下LDPC最简单的问题，decoding algorithm。（如果你连什么是linear code，为什么有variable nodes和check nodes也不知道，请先wikipedia一下基础知识）

1.Message-Passing Rules

1.1 函数分解（factorizations）

学过概率的都知道如何求边缘分布（marginal distribution）， $p(x)=\sum_y p(x,y)$ , 对于任何函数来说，求marginal都是一样的方法。

例如，有一个函数 $f(x_1,x_2,x_3,x_4,x_5,x_6)=f_1(x_1,x_2,x_3)f_2(x_1,x_4,x_6)f_3(x_4)f_4(x_4,x_5)$

我们想求对于 $x_1$ 的marginal function，我们可以得到

$f(x_1)=\sum_{x_2,x_3,x_4,x_5,x_6}f(x_1,x_2,x_3,x_4,x_5,x_6)=\sum_{\sim x_1}f(x_1,x_2,x_3,x_4,x_5,x_6)$ ,

其中， $\sum_{\sim x_1}$ 表示除 $x_1$ 之外所有变量（variables）的和。

这里有一个很有意思的现象，假设每个变量的都有X个取值。那么如果直接计算出 $f(x_1)$ 的 $x_1$ 的所有取值需要 $O(X^6)$ 次计算。但是我们可以减少计算量，通过 $f(x)$ 的分解形式。

$f(x_1)=[\sum_{x_2,x_3}f_1(x_1,x_2,x_3)][\sum_{x_4}f_3(x_4)(\sum_{x_6}f_2(x_1,x_4,x_6))(\sum_{x_5}f_4(x_4,x_5))]$

第一个因式需要 $O(X^2)$ 次计算，第二个因式需要 $O(X)$ 次计算，相乘之后计算量还是 $O(X^2)$ , 因为 $x_1$ 还有X个值，所以总共的计算量 $O(X^3)$ 。相比较前一个方法的计算量，这个方法把复杂度大大降低了。

我们可以用树形图来表示刚才的例子。

其中，圆圈代表variable nodes，方块代表factor nodes。variable node总是与factor node相连接的。注意这里没有循环（cycle），也就是说，连接两个nodes只有一条边（edge）。

1.2 Recursive Determination of marginals

下面我们来讨论如何计算marginal。

如果我们想计算 $g(z)=\sum_{\sim z}g(z,\dots)$ ，并且g可以分解成树形图，那么我们可以计算

$g(z,\dots)=\prod_{k=1}^K[g_k(z,\dots)]$

其中，z出现在每个因式（factor） $g_k$ ，但是所有其他的变量（variables）只出现在一个因式中。

例如，前面的一个例子， $f(x_1,\dots)=[f_1(x_1,x_2,x_3)][f_2(x_1,x_4,x_6)f_3(x_4)f_4(x_4,x_5)]$

所以，K＝2。并且如下图所示：

下面，我们再来分析 $g_k$ ，由于树的结构（永远是variable node与factor node相连）我们可以观察出

$g_k(z,\dots)=h(z,z_1,\dots,z_J)\prod_{j=1}^J[h_j(z_j,\dots)],$

其中，z只出现在核心函数（kernel） $h(z,z_1,\dots,z_J)$ 中，每一个 $z_j$ 最多只出现两次，可能在核心函数，或者其中一个因式（factor） $h_j(z_j,\dots)$ 中。

我们前面的那个例子， $f_2(x_1,x_4,x_6)f_3(x_4)f_4(x_4,x_5)=f_2(x_1,x_4,x_6)[f_3(x_4)f_4(x_4,x_5)][1]$ 。

1.3 Message-passing

其中， $f_2$ 是核心函数。如下图所示：

因此，我们可以计算 $\sum_{\sim z}g_k(z,\dots)=\sum_{\sim z}h(z,z_1,\dots,z_J)\prod_{j=1}^J[h_j(z_j,\dots)]=\sum_{\sim z}h(z,z_1,\dots,z_J)\prod_{j=1}^J[\sum_{\sim z_j}h_j(z_j,\dots)]$

可以看到，我们可以计算marginal $\sum_{\sim z}g_k(z,\dots)$ 通过kernel函数 $h(z,z_1,\dots,z_J)$ 和单个的marginals $\sum_{\sim z_j}h_j(z_j,\dots)$ 的乘积。

注意，这时我们应该能发现，每个 $h_j(z_j,\dots)$ 的结构与我们要计算的 $g(z,\dots)$ 是完全一样的。我们可以利用recursive进行求解，直到到达树的叶子（leaves）。

初始化：如果是函数，那么就是函数本身。如果是variable node，就初始化为1。

我们还是通过前面那个例子，说明信息如何传递（message-passing）：

$f(x_1,x_2,x_3,x_4,x_5,x_6)=f_1(x_1,x_2,x_3)f_2(x_1,x_4,x_6)f_3(x_4)f_4(x_4,x_5)$

在叶子（leaves）node， $x_2,x_3,x_5,x_6$ 初始化为1， $f_3$ 初始化为$f_3$。在factor node，利用前面提到的“通过kernel函数 $h(z,z_1,\dots,z_J)$ 和单个的marginals $\sum_{\sim z_j}h_j(z_j,\dots)$ 的乘积”来计算，在variable node就进行乘法运算。我们总结一下Message-passing rules，如下图：

最后一个是最后一步（final step）。我们标注 $\mu$ 为信息（message）。

2. Decoding algorithm for BEC

我们之所以要先讨论BEC，是因为BEC信道是最为简单，易于分析。

我们发出的信号为｛0，1｝，接受到的信号｛0，e，1｝，e为erasure，概率为 $\epsilon$ 。

因为BEC不会引入错误，所以对于variable node，如果incoming message全是erasure，那么outgoing message就是erasure。否则，incoming message 应该会统一是0或1。而对于check node，如果有一个incoming message是erasure，那么outgoing message就是erasure。否则，outgoing message为所有incoming message模2加的结果。

3. Decoding algorithm for BMC

BMC包括BSC和BSAWGN信道。Decoding algorithm会用到section1中提到的概念。对于BMC，信息就代表了概率或者置信度（belief），所以这个算法也叫做 belief propagation(BP) algorithm。

在BMC中，假设发出的信号｛－1，1｝。 $\mu(1), \mu(-1)$ 分别代表了1和－1的置信度。初始化， $\mu(1)=p(y_i|1), \mu(-1)=p(y_i|-1)$ 。在degree为K+1的variable node中，message-passing 规则是

$\mu(1)=\prod_{k=1}^K\mu_k(1), \mu(-1)=\prod_{k=1}^K\mu_k(-1)$ ,

我们引入比率（ratio）r， $r_k=\mu_k(1)/\mu_k(-1)$ . 因此，

$r=\frac{\mu(1)}{\mu(-1)}=\frac{\prod_{k=1}^K\mu_k(1)}{\prod_{k=1}^K\mu_k(-1)}=\prod_{k=1}^Kr_k$ ，

为了简化计算，我们定义 $l_k=\ln(r_k)$ , 所以 $l=\sum_{k=1}^K l_k$

下面我们考虑check node。每一个check node都有一个kernel function， $f(x,x_1,\dots,x_J)=\mathbf{1}_{\prod_{j=1}^J x_j=x}$ , 这是每个check node的constraint function。

所以，对于degree 是 J+1的check node来说，

$r=\frac{\mu(1)}{\mu(-1)}$

$=\frac{\sum_{x_1,\dots,x_J}f(1,x_1,\dots,x_J)\prod_{j=1}^J\mu_j(x_j)}{\sum_{x_1,\dots,x_J}f(-1,x_1,\dots,x_J)\prod_{j=1}^J\mu_j(x_j)}$

$=\frac{\sum_{x_1,\dots,x_J:\{\prod_{j=1}^J x_j=1\}}\prod_{j=1}^J\mu_j(x_j)}{\sum_{x_1,\dots,x_J:\{\prod_{j=1}^J x_j=-1\}}\prod_{j=1}^J\mu_j(x_j)}$

$=\frac{\sum_{x_1,\dots,x_J:\{\prod_{j=1}^J x_j=1\}}\prod_{j=1}^J\frac{\mu_j(x_j)}{\mu_j(-1)}}{\sum_{x_1,\dots,x_J:\{\prod_{j=1}^J x_j=-1\}}\prod_{j=1}^J\frac{\mu_j(x_j)}{\mu_j(-1)}}$

$=\frac{\sum_{x_1,\dots,x_J:\{\prod_{j=1}^J x_j=1\}}\prod_{j=1}^J r_j^{\frac{1+x_j}{2}}}{\sum_{x_1,\dots,x_J:\{\prod_{j=1}^J x_j=-1\}}\prod_{j=1}^J r_j^{\frac{1+x_j}{2}}}$