低密度奇偶检查码

低密度奇偶检查码（Low-density parity-check code，LDPC code），是线性分组码（linear block code）的一种，用于更正传输过程中发生错误的编码方式。

历史

在1962年，低密度奇偶检查码(LDPC code)即被罗伯特·加拉格提出^[1]，并被证明其错误校正能力非常接近理论最大值，香农极限（Shannon Limit）；不过受限于当时技术，低密度奇偶检查码并无法实现。最近几年，低密度奇偶检查码被重新发现^[2]，并随着集成电路的技术演进，低密度奇偶检查码的实现逐渐可行，而成为各种先进通信系统的信道编码标准。

运作

低密度奇偶检查码是基于具有稀疏矩阵性质的奇偶检验矩阵建构而成。对(n, k)的低密度奇偶检查码而言，每k比特资料会使用n比特的码字(codeword)编码。以下是一个被(16, 8)的低密度奇偶检查码使用的奇偶检验矩阵H。当中可以见得矩阵内的元素1数量远少于元素0数量，所以具有稀疏矩阵性质，也就是低密度的由来。

$H=\left[{\begin{matrix}1&1&1&1&0&0&0&0&0&0\\0&0&0&0&1&1&1&1&0&0\\0&0&0&0&0&0&0&0&1&1\\0&0&0&0&0&0&0&0&0&0\\1&0&0&0&0&0&0&1&0&0\\0&1&0&0&1&0&0&0&0&0\\0&0&1&0&0&1&0&0&1&0\\0&0&0&1&0&0&1&0&0&1\end{matrix}}\quad \!{\begin{matrix}0&0&0&0&0&0\\0&0&0&0&0&0\\1&1&0&0&0&0\\0&0&1&1&1&1\\1&0&0&1&0&0\\0&1&0&0&1&0\\0&0&0&0&0&1\\0&0&1&0&0&0\end{matrix}}\right]$

解码

低密度奇偶检查码的解码，可对应成二分图(bipartite graph)作表示。下方的二分图是依照上述奇偶检验矩阵H建置，其中H的行(row)对应至check node，而H的列(column)对应至bit node。check node和bit node之间的连线，由H内的元素1决定；好比H中第一行(row)和第一列(column)的元素1，使check node和bit node两者各自最左手边的第一个彼此连接。

低密度奇偶检查码的解码算法，主要基于有迭代性(iterative)的置信传播(belief propagation)；整个解码流程如下方所示：

当接收资料R从通信频道(channel)进入低密度奇偶检查码的解码器，解码器会对消息作初始化(initialization)。
check node根据互相连接的多个bit node内的资料做更新运算(update)。
bit node对相连接的多个check node内的资料做更新运算。
观察终止(termination)条件，来决定是否继续迭代计算。

详细的解码算法，常见有两种：总和-乘积算法(Sum-Product Algorithm)^[3]^[4]和最小值-总和算法(Min-Sum Algorithm)^[5]^[6]。总和-乘积算法具有较佳的错误更正能力，却具较高的计算复杂度；反之，最小值-总和算法在稍微减低的错误更正能力下，换取较低的计算复杂度。

总和-乘积算法

假设在一通信系统的频道有AWGN属性，而发送信号为 $\mathbf {U} \left(u_{1},u_{2},\dots ,u_{n}\right)$ ，接收信号是 $\mathbf {Y} \left(y_{1},y_{2},\dots ,y_{n}\right)$ ，bit node有n个，check node有m个。而总和-乘积算法在解码流程如下：

初始化：假设AWGN的方差(variance)是 $\sigma ^{2}$ 。
- bit node n会被初始化成：

\lambda _{n\to m}\left(u_{n}\right)=\log {\frac {P(u_{n}=0/y_{n})}{P(u_{n}=1/y_{n})}}={\frac {2y_{n}}{\sigma ^{2}}}

。

- check node m会被初始化成：

\Lambda _{m\to n}\left(u_{n}\right)=0

。

check node更新：
- check node m更新为：

\Lambda _{m\to n}\left(u_{n}\right)=2\tanh ^{-1}\left\{\prod _{n'\in N\left(m\right)\backslash n}\tanh \left[{\frac {\lambda _{n'\to m}\left(u_{n'}\right)}{2}}\right]\right\}

；其中

n'\in N\left(m\right)\backslash n

是连接到check node m的bit node组合，但不包含第n个bit node。

bit node更新：
- bit node n更新为：

\lambda _{n\to m}\left(u_{n}\right)={\frac {2y_{n}}{\sigma ^{2}}}+\sum _{m'\in M\left(n\right)\backslash m}\Lambda _{m'\to n}\left(u_{n}\right)

；其中

m'\in M\left(n\right)\backslash m

是连接到bit node n的check node组合，但不包含第m个check node。

终止：
- 解码比特计算：假设解码后信号为 ${\hat {\mathbf {U} }}\left({\hat {u}}_{1},{\hat {u}}_{2},\dots ,{\hat {u}}_{n}\right)$ 。Hard-decision解码比特可由下列两式求出：

\lambda _{n}\left(u_{n}\right)={\frac {2y_{n}}{\sigma ^{2}}}+\sum _{m\in M\left(n\right)}\Lambda _{m\to n}\left(u_{n}\right)

{\hat {u}}_{i}={\begin{cases}0,&{\mbox{if }}\lambda _{i}\left(u_{i}\right)\geq 0~\forall i\in \left\{1,2,\dots ,n\right\}\\1,&{\mbox{if }}\lambda _{i}\left(u_{i}\right)\leq 0~\forall i\in \left\{1,2,\dots ,n\right\}\end{cases}}

- 只要解码后的码字 $\mathbf {v}$ 在恒等式 $\mathbf {H} \mathbf {v} ^{T}=0$ 成立，即终止迭代计算。

最小值-总和算法

最小值-总和演算，大抵上和总和-乘积算法类似，除了于“check node更新”做不一样的计算方式。而改变的计算式如下：

\sigma _{m}=\mathrm {XOR} \left\{\operatorname {sgn} \left(\lambda _{n'\to m}\right)|n'\in N\left(m\right)\backslash n\right\}

，

\mu _{m,\min }=\min \left\{|\lambda _{n'\to m}||n'\in N\left(m\right)\backslash n\right\}

，

\Lambda _{m\to n}\left(u_{n}\right)=\sigma _{m}\cdot \mu _{m,\min }

。

参考文献

^ R. Gallager, “Low-Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. 7, pp. 21–28, Jan. 1962.
^ David J.C. MacKay and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996
^ R. M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Trans. Inform. Theory, Vol. IT-27, no. 5, pp. 399–431, Sep. 1981.
^ F. R. Kschischang, B. J. Frey and H. A. Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Trans. Info. Theory, Vol. 47, pp. 498–519, Feb. 2001.
^ M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced Complexity Iterative Decoding of Low-density Parity Check Codes Based on Belief Propagation,” IEEE Trans. Commun., vol. 47, no. 5, pp. 673–680, May, 1999.
^ J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X. Y. Hu, “Reduced-complexity Decoding of LDPC Codes,” IEEE Trans. Commun., vol. 53, no. 8, pp. 1288–1299, Aug. 2005.

[1] R. Gallager, “Low-Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. 7, pp. 21–28, Jan. 1962.

[2] David J.C. MacKay and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996

[3] R. M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Trans. Inform. Theory, Vol. IT-27, no. 5, pp. 399–431, Sep. 1981.

[4] F. R. Kschischang, B. J. Frey and H. A. Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Trans. Info. Theory, Vol. 47, pp. 498–519, Feb. 2001.

[5] M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced Complexity Iterative Decoding of Low-density Parity Check Codes Based on Belief Propagation,” IEEE Trans. Commun., vol. 47, no. 5, pp. 673–680, May, 1999.

[6] J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X. Y. Hu, “Reduced-complexity Decoding of LDPC Codes,” IEEE Trans. Commun., vol. 53, no. 8, pp. 1288–1299, Aug. 2005.

[1]

[2]

[3]

[4]

[5]

[6]