低密度奇偶檢查碼

低密度奇偶檢查碼（Low-density parity-check code，LDPC code），是線性分組碼（linear block code）的一種，用於更正傳輸過程中發生錯誤的編碼方式。

歷史

在1962年，低密度奇偶檢查碼(LDPC code)即被羅伯特·加拉格提出^[1]，並被證明其錯誤校正能力非常接近理論最大值，香農極限。但受限於當時技術，低密度奇偶檢查碼並無法實作。近年，低密度奇偶檢查碼被重新發現^[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]}$ 

解碼

低密度奇偶檢查碼的解碼，可對應成二分圖(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)；整個解碼流程如下方所示：

 

1. 當接收資料R從通訊頻道(channel)進入低密度奇偶檢查碼的解碼器，解碼器會對訊息作初始化(initialization)。
2. check node根據互相連接的多個bit node內的資料做更新運算(update)。
3. bit node對相連接的多個check node內的資料做更新運算。
4. 觀察終止(termination)條件，來決定是否繼續疊代計算。

詳細的解碼演算法，常見有兩種：總和-乘積演算法(Sum-Product Algorithm)^[3][4]和最小值-總和演算法(Min-Sum Algorithm)^[5][6]。總和-乘積演算法具有較佳的錯誤更正能力，卻具較高的計算複雜度；反之，最小值-總和演算法在稍微減低的錯誤更正能力下，換取較低的計算複雜度。

總和-乘積演算法

假設在一通訊系統的頻道有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}=\mathrm {XOR} \left\{\operatorname {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.