低密度奇偶檢查碼

在1962年，低密度奇偶檢查碼(LDPC code)即被羅伯特·加拉格提出[1]，並被證明其錯誤校正能力非常接近理論最大值，香農極限(Shannon Limit)；不過受限於當時技術，低密度奇偶檢查碼並無法實作。最近幾年，低密度奇偶檢查碼被重新發現[2]，並隨著積體電路的技術演進，低密度奇偶檢查碼的實作逐漸可行，而成為各種先進通訊系統的頻道編碼標準。

低密度奇偶檢查碼是基於具有稀疏矩陣性質的奇偶檢驗矩陣建構而成。對(n, k)的低密度奇偶檢查碼而言，每k位元資料會使用n位元的碼字(codeword)編碼。以下是一個被(16, 8)的低密度奇偶檢查碼使用的奇偶檢驗矩陣H。當中可以見得矩陣內的元素1數量遠少於元素0數量，所以具有稀疏矩陣性質，也就是低密度的由來。

${\displaystyle 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]}$

總和-乘積演算法

假設在一通訊系統的頻道有AWGN屬性，而傳送訊號為${\displaystyle \mathbf {U} \left(u_{1},u_{2},\dots ,u_{n}\right)}$，接收訊號是${\displaystyle \mathbf {Y} \left(y_{1},y_{2},\dots ,y_{n}\right)}$，bit node有n個，check node有m個。而總和-乘積演算法在解碼流程如下：

• 初始化：假設AWGN的方差(variance)是${\displaystyle \sigma ^{2}}$。
  • bit node n會被初始化成：

${\displaystyle \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會被初始化成：

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

• check node更新：
  • check node m更新為：

${\displaystyle \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\}}$； 其中${\displaystyle n'\in N\left(m\right)\backslash n}$是連接到check node m的bit node組合，但不包含第n個bit node。

• bit node更新：
  • bit node n更新為：

${\displaystyle \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)}$；其中${\displaystyle m'\in M\left(n\right)\backslash m}$是連接到bit node n的check node組合，但不包含第m個check node。

• 終止：
  • 解碼位元計算：假設解碼後訊號為${\displaystyle {\hat {\mathbf {U} }}\left({\hat {u}}_{1},{\hat {u}}_{2},\dots ,{\hat {u}}_{n}\right)}$。Hard-decision解碼位元可由下列兩式求出：

${\displaystyle \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)}$ ${\displaystyle {\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}}}$

• • 只要解碼後的碼字${\displaystyle \mathbf {v} }$在恆等式${\displaystyle \mathbf {H} \mathbf {v} ^{T}=0}$成立，即終止疊代計算。

最小值-總和演算法

最小值-總和演算，大抵上和總和-乘積演算法類似，除了於「check node更新」做不一樣的計算方式。而改變的計算式如下：

${\displaystyle \sigma _{m}=XOR\left\{sgn\left(\lambda _{n'\to m}\right)|n'\in N\left(m\right)\backslash n\right\}}$， ${\displaystyle \mu _{m,min}=min\left\{|\lambda _{n'\to m}||n'\in N\left(m\right)\backslash n\right\}}$， ${\displaystyle \Lambda _{m\to n}\left(u_{n}\right)=\sigma _{m}\cdot \mu _{m,min}}$。

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.