檢視低密度奇偶檢查碼的原始碼

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

==歷史==

佇一九六二年，低密度奇偶檢查碼 ( LDPC code ) 即予羅伯特 ・ 加拉格提出，並且予證明其錯誤學校正能力非常接近理論上大值，香農盡磅（Shannon Limit）； 猶毋過因為彼當陣技術，低密度奇偶檢查碼並無法度實作。最近幾年，低密度奇偶檢查碼被重新發現，閣隨著積體電路的技術演進，低密度奇偶檢查碼的實作漸漸會當行，成做各種先進通訊系統的信道編碼標準。

==運作==

低密度奇偶檢查碼是因為有疏疏矩陣性質奇偶檢驗矩陣建構才成做。著 ( _ n , k _ ) 的低密度奇偶檢查碼來講，逐 _ k _ 位元資料會使用 _ n _ 位元的碼字 ( codeword ) 編碼。以下是一个被 ( _ 十六 , 八 _ ) 的低密度奇偶檢查碼使用的奇偶檢驗矩陣 _ H _。當中會當看著矩陣內的元素一數量真少元素零數量，所以有疏矩陣性質，也就是低密度的由來。

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

===解碼===

低密度奇偶檢查碼的解碼，會當對應做二分圖 ( bipartite graph ) 作表示。下跤的二分圖是按照描述奇偶檢驗矩陣 _ H _ 建置，其中 _ H _ 的行 ( row ) 對應至'''check node'''，而且 _ H _ 的列 ( column ) 對應至'''bit node'''。'''check node'''和'''bit node'''之間的連線，由 _ H _ 內的元素一決定；可比 _ H _ 中第一途 ( row ) 佮第一列 ( column ) 元素一，使'''check node'''和'''bit node'''兩者上倒手爿的第一个互相連接。



低密度奇尪仔檢查碼的解碼演算法，主要是因為有疊代性 ( iterative ) 的放批傳播 ( belief propagation )；規个解碼的流程是下跤所示：

一 . 做接收的資料'''R'''對通訊頻道 ( channel ) 進入低密度奇偶檢查碼的解碼器，解碼器會對訊息作初始化 ( initialization )。
二 .'''check node'''根據互相連接的濟个'''bit node'''內的資料做更新運算 ( update )。
三 .'''bit node'''著相連紲的濟个'''check node'''內的資料做更新運算。
四 . 觀察終止 ( termination ) 條件，來決定敢是繼續疊代計算。

詳細的解碼演算法，捷看有兩種：'''總和-乘積演算法 ( Sum-Product Algorithm )'''和'''上細漢值-總和演算法 ( Min-Sum Algorithm )'''。'''總和-乘積演算法'''有較好的錯誤閣較正能力，煞有較懸的計算複雜度；反之，'''上細漢值-總和演算法'''佇小可仔減低的錯誤閣較正能力下，換較低的計算複雜度。

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

假使佇咧一通訊系統的頻道有 AWGN 屬性，傳送訊號做 $ \ mathbf { U } \ left ( u _ { 一 } , u _ { 二 } , \ dots , u _ { n } \ right ) $，接收訊號是 $ \ mathbf { Y } \ left ( y _ { 一 } , y _ { 二 } , \ dots , y _ { n } \ right ) $，'''bit node'''有 _ n _ 個，'''check node'''有 _ m _ 個。而且'''總和-乘積演算法'''佇解碼的流程如下：

* 初初化：準講 AWGN 的方差 ( variance ) 是 $ \ sigma ^ { 二 } $。
*'''bit node'''_ n _ 會予初初化做：

$ \ lambda _ { n \ to m } \ left ( u _ { n } \ right )=\ log { \ frac { P ( u _ { n }=零 / y _ { n } ) } { P ( u _ { n }=一 / y _ { n } ) } }={ \ frac { 二 y _ { n } } { \ sigma ^ { 二 } } } $。

* *'''check node'''_ m _ 會予初初化做：

$ \ Lambda _ { m \ to n } \ left ( u _ { n } \ right )=零 $。

*'''check node'''更新：
*'''check node'''_ m _ 更新為：

$ \ Lambda _ { m \ to n } \ left ( u _ { n } \ right )=二 \ tanh ^ { 影一 } \ left \ { \ prod _ { n'\ in N \ left ( m \ right ) \ backslash n } \ tanh \ left [{ \ frac { \ lambda _ { n'\ to m } \ left ( u _ { n'} \ right ) } { 二 } } \ 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 { 二 y _ { n } } { \ sigma ^ { 二 } } } + \ 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 } } _ { 一 } , { \ hat { u } } _ { 二 } , \ dots , { \ hat { u } } _ { n } \ right ) $。'''Hard-decision'''解碼位元會當由下列兩式求出：

$ \ lambda _ { n } \ left ( u _ { n } \ right )={ \ frac { 二 y _ { n } } { \ sigma ^ { 二 } } } + \ sum _ { m \ in M \ left ( n \ right ) } \ Lambda _ { m \ to n } \ left ( u _ { n } \ right ) $
$ { \ hat { u } } _ { i }={ \ begin { cases } 零 , & { \ mbox { if } } \ lambda _ { i } \ left ( u _ { i } \ right ) \ geq 零 ~ \ forall i \ in \ left \ { 一 , 二 , \ dots , n \ right \ } \ \ 一 , & { \ mbox { if } } \ lambda _ { i } \ left ( u _ { i } \ right ) \ leq 零 ~ \ forall i \ in \ left \ { 一 , 二 , \ dots , n \ right \ } \ end { cases } } $

* * 干焦解碼了的碼字 $ \ mathbf { v } $ 佇恆等式 $ \ mathbf { H } \ mathbf { v } ^ { T }=零 $ 成立，即終止疊代計算。

====上細漢值-總和演算法====

'''上細漢值-總和演算'''，拄著佮'''總和-乘積演算法'''類似，除了是講「'''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 } $。

==參考文獻==

[[分類: 待校正]]