低密度奇偶檢查碼
低密度奇偶檢查碼（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 } $。