EE6101-Digital-Comm-Systems-Part2-LPDC

基础介绍

Low Density Parity Check Codes （LDPC）码是一种特殊的线性块码。4G和5G都使用了LPDC码。

Tanner 图

下面是一个普通的线性块码的校验矩阵示例（它不是LDPC码，因为里面1的个数太多了，不是低密度，只是因为用这个例子来讲Tanner图非常简单，所以用它）

$$H = \begin{bmatrix} \overset{v_1}{1} & \overset{v_2}{0} & \overset{v_3}{0} & \overset{v_4}{1} & \overset{v_5}{0} & \overset{v_6}{1} \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{bmatrix} \begin{array}{c} c_1\\ c_2\\ c_3\\ \end{array}$$

每一行代表 1 个校验节点c₁/c₂/c₃（c的意思是Check），每一列代表 1 个变量节点v₁~v₆（v的意思是variable）。

如同前面介绍的线性快码一样，在信道上传输的是$V=[v_1,v_2…v_n]$，传输完成后，使用$S=VH^T$进行Syndrome test，如果S结果不为0，则有误。

而所谓Tanner图，就是把校验矩阵H给画出来，如下图所示。$c_1$里面，在$v_1,v_4,v_6$的地方有1，因此$c_1$与他们相连。$c_2$里面，$v_2,v_4,v_5$的地方有1，因此$c_2$与他们相连…

其中：

• 边（edge）：连接v节点和c节点的线被称为edge
• 环（cycle）：某个节点出发，沿着边走一圈又回到起点的路径（比如v₄→c₂→v₅→c₃→v₆→c₁→v₄）
• 围长（Girth）：最小的环的长度。例如上图，最小的环是v₄→c₂→v₅→c₃→v₆→c₁→v₄，因此围长就是6。（在LDPC码中，围长越长，查/纠错能力越强）

LDPC码

正则LDPC码

LDPC码是通过校验矩阵定义的。如果一个LDPC码的校验矩阵每一列的 “1” 的个数相同，每一行的 “1” 的个数也相同，则称其为正则（regular）LDPC码

在正则LDPC码中：

• $w_c$表示列重：一列里面有几个1
• $w_r$表示行重：一行里面有几个1

$$H = \begin{bmatrix} h_{1,1} & h_{1,2} & \dots & h_{1,n} \\ h_{2,1} & h_{2,2} & \dots & h_{2,n} \\ & \vdots & & \\ h_{m,1} & h_{m,2} & \dots & h_{m,n} \\ \end{bmatrix}$$

对于一个n列m行的校验矩阵，称其为$(n,k)$ code，其中$k=n-m$。

在n列m行的校验矩阵中所有 “1” 的数量：$w_c\times n=w_r\times m$。

而若一个LDPC有n列，则代表其在信道中传输由n个码字；而有m行，则代表能恢复出m个原始数据。那么：由此可以得到编码效率$\frac{m}{n}=\frac{w_c}{w_r}$。$k=n-m$就是冗余度。因此编码率：

$$Code\ Rate=\frac{k}{n}=\frac{n-m}{n}=1-\frac{m}{n}=1-\frac{w_c}{w_r}$$

“度” 的定义：节点的度 = 该节点在Tanner图中连的边数（对应校验矩阵里 “1” 的个数）

对于任意LDPC码，v-node 和 c-node 的度数至少是 2。

对于规则 LDPC 码，所有变量节点（v）的度都相同（等于列重(w_c)），所有校验节点（c）的度也都相同（等于行重(w_r)）。

例如下面这个例子：

$$H = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ \end{bmatrix}$$

在这个例子中，每一行的1的数量（$w_r=4$），每一列的1的数量$w_c=2$。校验矩阵$n=8,m=4$。

• 这是一个$(4,4)$编码，冗余度为4。
• $w_r=4$，$w_c=2$
• 矩阵内共有$w_r\times m= w_c \times n = 16$个1
• 编码率：$\frac{k}{n}=\frac{4}{8}=1-\frac{w_c}{w_r}=1-\frac{1}{2}=\frac{1}{2}$

非正则LDPC码

度 (Degree) 范围： 对于不规则LDPC码，变量节点 (v-nodes) 和 校验节点 (c-nodes) 的度数可以有一个范围，而不是像规则LDPC码那样固定。它们的度数是根据度分布多项式随机选择的。

最小度要求： 一个c-node（校验节点）或v-node（变量节点）的度数必须至少为二。

度分布多项式

• $\lambda(x)$：关于变量节点 (v-node) 的度分布多项式。
• $\rho(x)$：关于校验节点 (c-node) 的度分布多项式。

这些多项式描述了从边（edges） 视角看到的度分布。

举个例子：(\lambda(x)=0.2x + 0.8x^2)（v-node 度数分布）、(\rho(x)=0.5x^4 + 0.5x^5)（c-node 度数分布）

$\lambda(x)=0.2x + 0.8x^2$的0.2代20% 的连边连接到度为 $2$ 的变量节点上；0.8代表80% 的连边连接到度为 $3$ 的变量节点（v-node）上。

$\rho(x)=0.5x^4 + 0.5x^5$的0.5代表50%的连边连接到了度为 $4$ 的和度为5的校验节点（c-node）上

进一步地，如果我们知道总边数N，则可以计算：

• v-node 总数：(n = N \int_0^1 \lambda(x)dx)
• c-node 总数：(m = N \int_0^1 \rho(x)dx)

进一步根据编码率的公式，可以推出：$CR=1-\frac{m}{n}=1-\frac{\int_0^1 \lambda(x)dx}{\int_0^1 \rho(x)dx}$

还是看到前面的例子：在$\lambda(x)=0.2x + 0.8x^2$和$\rho(x)=0.5x^4 + 0.5x^5$下：（1）求编码率R，（2）求度数为 2 的变量节点（v-node）的比例，（3）求度数为 5 的校验节点（c-node）的比例

编码率：$R = 1 - \frac{\int_0^1 \rho(x) dx}{\int_0^1 \lambda(x) dx}$

$$\int_0^1 \lambda(x) dx = \int_0^1 (0.2x + 0.8x^2) dx= \left[ 0.2 \frac{x^2}{2} + 0.8 \frac{x^3}{3} \right]_0^1=\frac{1.1}{3}$$ $$\int_0^1 \rho(x) dx = \int_0^1 (0.5x^4 + 0.5x^5) dx= \left[ 0.5 \frac{x^5}{5} + 0.5 \frac{x^6}{6} \right]_0^1=\frac{1.1}{6}$$ $$R=1-\frac{\frac{1.1}{3}}{\frac{1.1}{6}}=\frac{1}{2}$$

度数为2的v的比例：根据$\lambda$可知，有20%的边连接度数为2的v节点，有80%的边连接度数为3的v节点。

根据定义，度为 $i$ 的节点连接的边数占 $E$ 的比例是 $\lambda_i$，所以：

$$\text{度为 } i \text{ 的节点连接的边数} = E \cdot \lambda_i$$

又因为每个度为 $i$ 的节点都贡献了 $i$ 条边，所以度为 $i$ 的节点总数 $N_i$ 为：

$$N_i = \frac{\text{度为 } i \text{ 的节点连接的边数}}{i} = \frac{E \cdot \lambda_i}{i}$$

那么，度数为2的节点在总的v节点中的比例，就是

$$\overline \lambda_2 = \frac{N_2}{N_2+N_3}=\frac{\frac{\lambda_2}{2}}{\frac{\lambda_2}{2}+\frac{\lambda_3}{3}}=\frac{3}{11}$$

同理可得：

$$\rho_5=\frac{\frac{\rho_5}{5}}{\frac{\rho_5}{5}+\frac{\rho_6}{6}}=\frac{6}{11}$$

LPDC码的编码规则

LDPC 码的核心是构造稀疏校验矩阵 H（已知码长 n、码率 R），H 需要满足以下条件：

1. 行列约束（RC 约束）
   • 要求：任意两行 / 列的非零元素（即 “1”）重叠位置不超过 1 个。
   • 作用：保证对应的 Tanner 图没有 4 环（围长 girth=4）。
   • 反面影响：如果不满足，迭代译码中消息会在 2 次迭代后关联，严重恶化译码性能。
2. 围长（Girth）
   • 要求：围长至少为 6（必须避免 girth=4）。
   • 作用：围长越大，迭代次数增加时译码性能越好。
3. 列重（Column Weight）
   • 对于正则 LDPC 码，最小码距至少为 “列重 + 1”（列重较大时这个下界很紧）。
   • 作用：列重越大，通常错误平层越低、收敛速度越快。（错误平层指的是不可纠正的错误图案，列重越大→每个变量节点连接的校验节点越多→错误图案同时满足多个校验方程的概率越低→“不可纠正的错误” 越难出现→错误平层被压低）
4. 围长与列重的矛盾
   • 难点：列重增大（H 中 “1” 变多）时，围长很难超过 6（尤其是高码率码，H 会更密）。
5. 实际选择
   • 通常 girth=6 的码性能足够好；低 - 中码率场景下，围长可以做到更大（比如 12）。

Majority-Logic解码法（MLG）

MLG方法的决策依据是：每个比特的最终取值，选 “出现次数最多的那个值”（少数服从多数）。

考虑一个例子，一个LPDC码的解码矩阵如下：

$$H = \begin{bmatrix} \overset{v_1}{1} & \overset{v_2}{0} & \overset{v_3}{0} & \overset{v_4}{1} & \overset{v_5}{0} & \overset{v_6}{1} \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{bmatrix} \begin{array}{c} c_1\\ c_2\\ c_3\\ \end{array}$$

假设发送码字是$U=[1, 1,0,1,0,0]$，经过信道传输，变成了$V=[1, 1,0,0,0,0]$，bit4发生了翻转。

根据这个校验矩阵的Tanner图：

$C_1=v_1+v_4+v_6$，这个结果本来应该是0，但是由于信道传输发生了错误，现在它是1。

由于模2运算的性质（加法与减法等价），$v_1+v_4+v_6=0$，移项可得：$v_1=v_4+v_6,v_4=v_1+v_6,v_6=v_1+v_4$。现在我们把接收到的数据代入：

• $v_1=v_4+v_6=0+0=0$
• $v_4=v_1+v_6=1+0=1$
• $v_6=v_1+v_4=1+0=1$

对于$C_2=v_2+v_4+v_5$，也重复这个步骤：

• $v_2=v_4+v_5=0+0=0$
• $v_4=v_2+v_5=1+0=1$
• $v_5=v_2+v_4=1+0=1$

对于$C_3=v_3+v_5+v_6$，同理：

• $v_3=v_5+v_6=0+0=0$
• $v_5=v_3+v_6=0+0=0$
• $v_6=v_3+v_5=0+0=0$

现在，我们拿到了所有$v$节点对各自应该是多少的“投票”，这被称为候选值。将其列成表，例如下表第一行就表示，通过$C_1$的校验方程，$C_1$投$v_1=0,v_4=1,v_6=1$。表的最后一行是我们接收到的$v$

校验方程	(v_1)	(v_2)	(v_3)	(v_4)	(v_5)	(v_6)
(C_1)	0	0	-	1	-	1
(C_2)	-	0	-	1	1	-
(C_3)	-	-	0	-	0	0
Detected $v$	1	1	0	0	0	0

根据这张表，我们遵循：如果v之间相互投票的票数相较于接受有优势，则选择相互投票的结果。否则选择接收的结果。例如，相互投票有两个以上1，接收是0，则最终选择1。若相互投票是一个1，接收是0，则最终该选择0。

• (v_1)：候选值只有 1 个 0，接收值是 1 → 选接收值 1
• (v_2)：候选值只有 1 个 0，接收值是 1 → 选接收值 1
• (v_3)：候选值全是 0 → 选 0
• (v_4)：候选值是 2 个 1 ，相较于接受的0有优势→ 选 1（修正了错误）
• (v_5)：候选值是 1 个 1、1 个 0 → 选接收值 0
• (v_6)：候选值是 1 个 1、1 个 0 → 选接收值 0

MLG译码法也可以转化为BF译码法，BF译码法的核心原理是：当某一个c出现错误为1时，为给这个c贡献的v节点的“错误可能性”+1，最后把错误可能性最高的$v$翻转。如此往复，直到校验通过。

从这个地方可以试着反向理解一下为什么最小度数要求至少为2：在上面这个例子中，$v_1$的度数仅为1（因为这只是一个方便演示，简化了的普通线性块码，而非标准LDPC码），这时候，在投票过程中$v_1$就只有一票，这是不科学的。如果度数至少为2，那每个节点都至少有2票+一个观测值。这样才能区分优劣。

Believe Propagation解码法

之前的MLG 是 “硬判决”：解调器直接输出 “0/1” 比特，译码器也输出 “0/1”—— 但这样会丢掉噪声里的细节信息。例如下图在解码器这一步，原本的模拟信号被转换为了数字信号。例如使用最大似然接收机之类，直接进行硬裁决，因此说解调器破坏了噪声信息。

而BP 是 “软判决”（软输入软输出，SISO）：解调器输出的不是 “0/1”，而是 “这个比特是 0/1 的概率”；译码器也用概率做迭代，能保留噪声信息，最终性能更好。因此，BP解码法也更常用。

BP 的本质是在 Tanner 图的 “变量节点（比特）” 和 “校验节点” 之间，迭代传递 “概率消息”，逐步优化每个比特是 0/1 的置信度。

BP是基于贝叶斯思想的，根据先验概率去优化后验概率。总体流程如下

1. 根据接收到的v和比特0 1分布的先验概率，拿到每一个v节点是0或是1的概率
2. 进行Syndrome test
3. 如果Syndrome test 结果有误，则现有的v的概率，和对c的错误情况，对v是0或是1的概率进行迭代。
4. 如此往复，直到校验通过

在这之中，涉及到两个消息传递：

• $q_{m,n}(b)$（比特 $\to$ 校验）： 比特v告诉校验节点c：“根据我收到的信号以及其他校验节点的反馈，我认为我是 $b$（0或1）的概率是这么多” 。

• $r_{m,n}(b)$（校验 $\to$ 比特）： 校验节点c告诉比特v：“根据其他几个连接到我的比特的情况，为了让校验成立，你必须是 $b$ 的概率是这么多” 。

• 

Step0：初始化每个bit的概率

这个步骤仅根据信道接收到的模拟信号 $Y$计算出每个$v$最初的概率。

下面这张图是前面学习过的二元信号（即，只有0和1）下，接收端收AWGN影响的条件PDF分布图。现在我们假设比特 ‘1’ 映射为 +1V，比特 ‘0’ 映射为 -1V。0和1出现的概率相等（即 $P(v_n=1) = P(v_n=0) = 0.5$。）

那么接收信号$y_n = x_n + w_n$，$w_n$ 是高斯白噪声，服从正态分布 $\mathcal{N}(0, \sigma^2)$。

现在我们单看我收到了信号$y_n$，在这个条件下，$v_n=1$的概率。根据贝叶斯定理：

$$P(v_n=1 | y_n) = \frac{p(y_n | v_n=1)P(v_n=1)}{p(y_n)}$$

其中分母 $p(y_n)$ 是全概率公式（归一化因子）：

$$p(y_n) = p(y_n | v_n=1)P(v_n=1) + p(y_n | v_n=0)P(v_n=0)$$

我们将分子分母同时除以分子 $p(y_n | v_n=1)$

$$P(v_n=1 | y_n) = \frac{1}{1 + \frac{p(y_n | v_n=0)}{p(y_n | v_n=1)}}$$

现在问题就变成了求似然比 $L=\frac{p(y_n | v_n=0)}{p(y_n | v_n=1)}$

当 $v_n=1$ 时（发送信号为 $+1$）：$y_n$ 服从均值为 $+1$，方差为 $\sigma^2$ 的高斯分布。

$$p(y_n | v_n=1) = \frac{1}{\sqrt{2\pi}\sigma} \exp\left( -\frac{(y_n - 1)^2}{2\sigma^2} \right)$$

当 $v_n=0$ 时（发送信号为 $-1$）：$y_n$ 服从均值为 $-1$，方差为 $\sigma^2$ 的高斯分布。

$$p(y_n | v_n=0) = \frac{1}{\sqrt{2\pi}\sigma} \exp\left( -\frac{(y_n - (-1))^2}{2\sigma^2} \right) = \frac{1}{\sqrt{2\pi}\sigma} \exp\left( -\frac{(y_n + 1)^2}{2\sigma^2} \right)$$

那么似然比就是：

$$L=\frac{p(y_n | v_n=0)}{p(y_n | v_n=1)}= \exp\left( -\frac{(y_n + 1)^2}{2\sigma^2} +\frac{(y_n - 1)^2}{2\sigma^2} \right)$$ $$= \exp\left( \frac{1}{2\sigma^2} (-4y_n) \right) = \exp\left( -\frac{2y_n}{\sigma^2} \right)$$

将似然比代入贝叶斯公式：

$$P(v_n=1 | y_n) = \frac{1}{1 + \exp\left( -\frac{2y_n}{\sigma^2} \right)}$$

这就是在接收$y_n$时，裁决为1的概率。裁决为0的概率与它互补。这就是在AWGN+（+1，-1）极性码的信道下的初始化函数，不同信道和噪声模型下初始化函数不一样。

这个初始化的概率（通常只传递1的概率，记为$q_{m,n}(1)$，因为是0和是1的概率互补。也可以用LLR来传递，但不在本课讨论范围内，本课以传递1的概率为例），就是第一次向检查节点C传递的$q_{m,n}$，其中$m$是Check Node Index，表示消息是发往这个校验节点 $C_m$ 的。n是Variable Node Index，表示消息是源自这个变量节点 $v_n$ 的。

举个例子，还是考虑下图这个校验矩阵。假设原始传输数据$U=[1,1,0,1,0,0]$。假设现在接收端的采样器采样到$y_n=[0.55, 0.38, -0.35, -0.10, -0.55, -0.2]$(bit4受到了干扰，采样值为-0.1，原本是1但会被决策为0),已知噪声方差$\sigma^2=0.5$

将其代入公式$P(v_n=1 | y_n) = \frac{1}{1 + \exp\left( -\frac{2y_n}{\sigma^2} \right)}$即可算出$q_{m,n}(1)$。

例如$q_{1,1}=\frac{1}{1 + \exp\left( -\frac{2\times 0.55}{0.5} \right)}=0.9$。照此步骤算出下表：

	v₁	v₂	v₃	v₄	v₅	v₆
C₁	0.90			0.40		0.30
C₂		0.82		0.40	0.10
C₃			0.20		0.10	0.30

Step1：校验节点处理

现在校验节点收到了初始的$q$，每个校验节点都要综合自己手上的信息，给变量节点一个反馈$r_{m,n}$

计算 $r_{m,n}(1)$ 的公式为：

$$r_{m,n}(1) = \sum_{v_{n'}} P(S_{m,n} | v_n=1, \{v_{n'}\}) \prod_{n' \in \mathcal{L}(m)\setminus n} q_{m,n'}(v_{n'})$$

其中

• $r_{m,n}(1)$：在假定比特 $v_n=1$ 的前提下，校验节点 $m$ 被满足（即奇偶校验成立）的概率。
• $\mathcal{L}(m)\setminus n$：参与校验的是除 $v_n$ 以外的所有其他变量集合（即，在计算反馈给自己的消息中，不包含自己递上去的概率）。
• $q_{m,n’}(v_{n’})$：其他比特告诉校验节点它们取特定值的概率。
• $P(S_{m,n} | v_n=1, \{v_{n’}\})$：校验成立的条件这是一个指示器：如果 $v_n=1$ 并且其他比特 $\{v_{n’}\}$ 也是这样取值时，则它为1。即，如果一个比特组合让校验成立，这个概率就是 1；如果不成立，概率就是 0 。

用人话翻译这个公式：如果一个检查节点$C_n=v_x+v_y+v_z$，只考虑校验成立的时候，$v_x,v_y,v_z$形成这样组合的概率。

我们接着上面的例子来看，现在节点侧收到了这个表格：

	v₁	v₂	v₃	v₄	v₅	v₆
C₁	0.90			0.40		0.30
C₂		0.82		0.40	0.10
C₃			0.20		0.10	0.30

对于$c_2$节点，它受到$v_2+v_4+v_5$的反馈。因此它也需要再反馈给这些节点。以计算$r_{2,4}$（即，反馈给$v_4$节点的数值）为例子。

如果$v_4$等于1，那么这个校验节点要是0，必须满足$v_2+v_5=1$。即，公式筛选出的校验位成立的情况仅$(v_2=1,v_5=0)$和$(v_2=0,v_5=1)$两种。

那么

$$r_{2,4}(1) = P(\mathbf{v_2=1, v_5=0}) + P(\mathbf{v_2=0, v_5=1})$$ $$= [q_{2,2}(1) \cdot q_{2,5}(0)] + [q_{2,2}(0) \cdot q_{2,5}(1)] \quad \text{}$$ $$= (0.82 \cdot 0.90) + (0.18 \cdot 0.10)\approx0.76$$

这就表示，在 $C_2$ 看来，它的大多数邻居（$v_2$ 和 $v_5$）的消息支持 $v_4$ 应该为 1的概率是$0.76$，这样才能满足校验方程。

这个消息传播给$v_4$后，会强制把$q_{2,4}$更新成$0.76$。将所有的$r$都计算出，更新完成后结果如下表：

	v₁	v₂	v₃	v₄	v₅	v₆
C₁	0.46			0.66		0.58
C₂		0.42		0.76	0.56
C₃			0.34		0.38	0.26

Step2：再次计算q，传播给校验节点

在这个例子中，使用Step1迭代出的结果就已经能完成正确解码了。所以，实际上迭代会在Step1就终止。这个地方只是为了展示反复迭代的步骤，进行了一次计算。

下一次，我们使用下面公式进行$q_{m,n}$的计算：

$$q_{m,n}(b) = K_n \cdot P(v_n=b|y_n) \cdot \prod_{m' \in \mathcal{M}(n)\setminus m} r_{m',n}(b)$$

其中：

• $q_{m,n}(b)$：比特节点 $v_n$ 告诉校验节点 $C_m$ 自己取值 $b$ 的概率。
• $P(v_n=b|y_n)$：该比特自己收到的原始信息（来自信道 $Y$）的概率（即 Step 0 的结果）。
• $r_{m’,n}(b)$：除 $C_m$ 以外，所有其他连接到 $v_n$ 的校验节点 $C_{m’}$ 传回来的反馈信息。
• $\mathcal{M}(n)\setminus m$：连接到 $v_n$ 的除 $C_m$ 以外的所有校验节点的集合。
• $K_n$：一个归一化常数（Normalization Constant），用于确保 $q_{m,n}(0) + q_{m,n}(1) = 1$。

这个公式用人话翻译就是：

现在各个检查节点回传的table如下：

	v₁	v₂	v₃	v₄	v₅	v₆
C₁	0.46			0.66		0.58
C₂		0.42		0.76	0.56
C₃			0.34		0.38	0.26

以计算$q_{2,4}$为例，这个节点收到了$c_1$和$c_2$两个节点的反馈，但是因为$q_{2,4}$是发给$c_2$的，所以$c_2$的反馈被从计算中剔除了。根据$r_{1,4}(1)=0.66$，自己的初始采样$P(v_4=1|y_4)=0.4$

$$q_{2,4}(1)=K_{2,4}\times 0.4\times 0.66 =0.264K_{2,4}$$ $$q_{2,4}(0)=K_{2,4}\times 0.6\times 0.34 =0.204K_{2,4}$$

由于$q_{2,4}(1)+q_{2,4}(0)=1$，解得归一化常数$K_{2,4}=2.137$，代回算出$q_{2,4}(1)$：

$$q_{2,4}(1)=0.264\times 2.137=0.56$$

经过这一轮计算，各家上报给c节点的值如下表：

	v₁	v₂	v₃	v₄	v₅	v₆
C₁	0.46			0.68		0.13
C₂		0.42		0.56	0.06
C₃			0.34		0.13	0.37

由于这个例子并非标准LDPC码（有节点度数不小于2），因此现在$v_1,v_2,v_3$都只有一个反馈了。这在标准LDPC情况中不存在。这里为继续讲解这个例子，不动$v_1,v_2,v_3$的值了。

Step3：计算变量节点的最终概率 (Q_n(1))

如果我们还要再继续迭代，重复上述步骤就好了。但是在这里，使用Step1迭代出的结果就已经能完成正确解码了。所以，实际上迭代会在Step1就终止。

最终候选码字的比特概率 (Q_n(1))，是综合信道初始概率和所有校验节点反馈后的归一化结果，公式为：

$$Q_n(1) = K_n \cdot P(v_n=1|y_n) \cdot \prod_{m \in \mathcal{M}(n)} r_{m,n}(1)$$ $$Q_n(0) = K_n \cdot P(v_n=0|y_n) \cdot \prod_{m \in \mathcal{M}(n)} r_{m,n}(0)$$

其中 (K_n) 是归一化常数（保证 (Q_n(1) + Q_n(0) = 1)）。

继续看前面的例子，Step1的$r_{m,n}$概率是下表：

	v₁	v₂	v₃	v₄	v₅	v₆
C₁	0.46			0.66		0.58
C₂		0.42		0.76	0.56
C₃			0.34		0.38	0.26

初始采样表如下：

	v₁	v₂	v₃	v₄	v₅	v₆
C₁	0.90			0.40		0.30
C₂		0.82		0.40	0.10
C₃			0.20		0.10	0.30

以计算$Q_4$为例子，$P(v_4=1|y_n)=0.4$，Step1回传的$r_{1,4}=0.66, r_{2,4}=0.76$

$$Q_4(1)=K_4\times0.4\times 0.66\times 0.76=0.2006K_4$$ $$Q_4(0)=K_4\times0.6\times 0.34\times 0.24=0.0490K_4$$

接得$k_4=4.0054$，最终算得它是1的概率为$0.2006\times 4.0052=0.8010$。概率大于0.5，判决为1。

同理，最后算出这6位数为1的概率分别为：

$$Q(1)=(0.8852,\ 0.7688,\ 0.1132,\ 0.8010,\ 0.0806,\ 0.1712)$$

因此，最终判决为：1 1 0 1 0 0。原始传输数据$U=[1,1,0,1,0,0]$，与解码结果一致。这样就纠正了bit4发生的错误。

在实际应用中，传递$q_{m,n}(1)$的计算量非常大，就像上面这样。所以实际应用中都是传递的对数似然比（LLR）来简化计算。但是这并不在这门课中涉足。因为老师”do not want to make this part too long in the course”