August | 2011 | Brack's Blog

Shannon limit

August 25, 2011 Leave a comment

其实，根本用不着写这篇blog，只是因为本科的时候没学好，所以这个问题缠绕了我一下午(也算是报应吧)。现在有点理解了，希望对一些朋友有用。

Shannon 定理是这样定义的

$C=B\times\log_2(1+\frac S N)$

其中，C是channel capacity，单位bits/s

B是带宽，单位hertz

S是信号功率，单位watt

N是在B带宽下的噪声功率，单位watt。

现在，我们用数字信号表示shannon定理。

$C=B\times\log_2(1+\frac {E_b}{N_o}\frac C B)$

其中我们用了替换 $\frac {E_b}{N_o}\frac C B=\frac S N$ , E_b代表了energy/bit, N_o代表了noise power spectral density。因此 C=E_b*S，N=N_o*B。

可以得到

$\frac {E_b}{N_o}=\frac S N/\frac C B=(2^{\frac C B}-1)/(\frac C B)$

这个时候，我们可以看到，当C/B=1时， $\frac {E_b}{N_o}=1$ ，即0 dB。当C/B减小时（带宽增大）， $\frac {E_b}{N_o}$ 的值会随着C/B的减小而减小，那么极限 $\frac {E_b}{N_o}\geq\lim_{\frac C B\rightarrow0}(2^{\frac C B}-1)/(\frac C B)=\lim_{\frac C B\rightarrow0}\frac{2^{\frac C B}\ln2}1=\ln2$ 。因此我们求到了shannon limit，即ln2，-1.6dB。这是在带宽趋于无穷大的情况下得到的。这当然是一个理论值，是无法做到的。

shannon定理就是说明，当给定R（rate）， $\frac {E_b}{N_o}\geq\frac S N/\frac R B=(2^{\frac R B}-1)/(\frac R B)$ 才能保证可靠的信道传输。

Filed under coding theory Tagged with digital communication, shannon limit

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}}}$

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

$=\frac{\prod_{j=1}^J(r_j+1)+\prod_{j=1}^J(r_j-1)}{\prod_{j=1}^J(r_j+1)-\prod_{j=1}^J(r_j-1)}$

$=\frac{1+\prod_{j=1}^J\frac{r_j-1}{r_j+1}}{1-\prod_{j=1}^J\frac{r_j-1}{r_j+1}}$

$=\frac{1+\prod_{j=1}^J\tanh(l_j/2)}{1-\prod_{j=1}^J\tanh(l_j/2)}$

同时， $l=\ln r, \tanh(l/2)=\frac{r-1}{r+1}=\prod_{j=1}^J\tanh(l_j/2)$

因此， $l=2\tanh^{-1}(\prod_{j=1}^J\tanh(l_j/2))$ 。

综上，在variable node的规则是， $l=\sum_{k=1}^K l_k$

在check node的规则是， $l=2\tanh^{-1}(\prod_{j=1}^J\tanh(l_j/2))$

这就是Message-passing algorithm 的来历。

Filed under coding theory Tagged with decoding, LDPC, message-passing

Hello world!

August 4, 2011 Leave a comment

Welcome to WordPress.com. After you read this, you should delete and write your own post, with a new title above. Or hit Add New on the left (of the admin dashboard) to start a fresh post.

Here are some suggestions for your first post.

You can find new ideas for what to blog about by reading the Daily Post.
Add PressThis to your browser. It creates a new blog post for you about any interesting page you read on the web.
Make some changes to this page, and then hit preview on the right. You can always preview any post or edit it before you share it to the world.

Filed under Uncategorized

Brack's Blog

Shannon limit

Tutorial—LDPC part I

1.Message-Passing Rules

1.1 函数分解（factorizations）

1.2 Recursive Determination of marginals

1.3 Message-passing

2. Decoding algorithm for BEC

3. Decoding algorithm for BMC

Hello world!

Categories

Recent Posts

Archives

Blogroll

Meta