查看“︁低密度奇偶檢查碼”︁的源代码

{{Request translation|time=2021-06-02T08:24:02+00:00}}
{{noteTA
|G1=IT
}}
'''低密度奇偶檢查碼'''（Low-density parity-check code，LDPC code），是線性[[分組碼]]（linear block code）的一種，用於更正傳輸過程中發生錯誤的編碼方式。

==歷史==
在1962年，低密度奇偶檢查碼(LDPC code)即被[[羅伯特·加拉格]]提出<ref>R. Gallager, “Low-Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. 7, pp. 21–28, Jan. 1962.</ref>，並被證明其錯誤校正能力非常接近理論最大值，[[香農極限]]。但受限於當時技術，低密度奇偶檢查碼並無法實作。近年，低密度奇偶檢查碼被重新發現<ref> David J.C. MacKay and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996</ref>，並隨著[[積體電路]]的技術演進，低密度奇偶檢查碼的實作逐漸可行，而成為各種先進[[通訊系統]]的[[信道編碼]]標準。

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

<math>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]</math>

===解碼===

低密度奇偶檢查碼的解碼，可對應成[[二分圖]](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兩者各自最左侧的第一個彼此連接。


[[file:Lpdc bipartite graph.PNG|400px]]

低密度奇偶檢查碼的解碼演算法，主要基於有疊代性(iterative)的[[置信傳播]](belief propagation)；整個解碼流程如下方所示：

[[file:Lpdc decode flow.png|400px]]

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

詳細的解碼演算法，常見有兩種：總和-乘積演算法(Sum-Product Algorithm)<ref>R. M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Trans. Inform. Theory, Vol. IT-27, no. 5, pp. 399–431, Sep. 1981.</ref><ref>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.</ref>和最小值-總和演算法(Min-Sum Algorithm)<ref>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.</ref><ref>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.</ref>。總和-乘積演算法具有較佳的錯誤更正能力，卻具較高的計算複雜度；反之，最小值-總和演算法在稍微減低的錯誤更正能力下，換取較低的計算複雜度。

====總和-乘積演算法====

假設在一通訊系統的頻道有[[AWGN]]屬性，而傳送訊號為<math>\mathbf{U} \left ( u_1, u_2, \dots , u_n\right )</math>，接收訊號是<math>\mathbf{Y} \left ( y_1, y_2, \dots , y_n\right )</math>，'''bit node'''有''n''個，'''check node'''有''m''個。而總和-乘積演算法在解碼流程如下：
*初始化：假設AWGN的方差(variance)是<math>\sigma^2</math>。
**bit node n會被初始化成：
<center><math>\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}</math>。</center>
**check node m會被初始化成：
<center><math>\Lambda_{m \to n} \left(u_n\right ) = 0</math>。</center>
*check node更新：
**check node m更新為：
<center><math>\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 \}</math>；</center>
<center>其中<math>n'\in N\left( m \right )\backslash n </math>是連接到check node m的bit node組合，但不包含第n個bit node。</center>
*bit node更新：
**bit node n更新為：
<center><math>\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 )</math>；</center><center>其中<math>m'\in M\left( n \right )\backslash m </math>是連接到bit node n的check node組合，但不包含第m個check node。</center>
*終止：
**解碼位元計算：假設解碼後訊號為<math>\hat{\mathbf{U}} \left ( \hat u_1, \hat u_2, \dots , \hat u_n\right )</math>。Hard-decision解碼位元可由下列兩式求出：
<center><math>\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 )</math></center>
<center><math>\hat u_i = \begin{cases} 
0, & \mbox{if } \lambda_i \left ( u_i\right )\ge 0 ~ \forall i \in \left \{ 1, 2, \dots, n\right \}\\
1, & \mbox{if } \lambda_i \left ( u_i\right )\le 0 ~ \forall i \in \left \{ 1, 2, \dots, n\right \}
\end{cases} </math></center>
**只要解碼後的碼字<math>\mathbf{v}</math>在恆等式<math>\mathbf{H}\mathbf{v}^T=0</math>成立，即終止疊代計算。

====最小值-總和演算法====
最小值-總和演算，大至和總和-乘積演算法類似，除了於「check node更新」做不一樣的計算方式。而改變的計算式如下：
<center><math>\sigma_m = \mathrm{XOR} \left \{ \sgn \left ( \lambda_{n' \to m} \right )|n'\in N\left( m \right )\backslash n\right \}</math>，</center>
<center><math>\mu_{m, \min} = \min \left \{ | \lambda_{n' \to m}| |n'\in N\left( m \right )\backslash n\right \}</math>，</center>
<center><math>\Lambda_{m \to n} \left ( u_n\right ) = \sigma_m \cdot \mu_{m, \min}</math>。</center>


==參考文獻==
<references />
[[Category:錯誤檢測與校正]]
[[Category:编码理论]]