2.2.1 基本概念

LDPC碼的特征是校驗矩陣為稀疏矩陣，即1的個數很少，0的個數很多。Gallager最早設計的 LDPC 碼是一種規則編碼。給定碼率，碼長N=10的(3,6)規則LDPC碼，其校驗矩陣如式（2-1）所示。

這里，校驗矩陣H包含5行10列，每一行對應一個校驗關系，稱為校驗節點，每一列對應一個編碼比特，稱為變量節點。(3,6)是指校驗矩陣H的每一列含有3個1，每一行含有6個1，即列重為3，行重為6，行重與列重的分布相同，只是1的位置不同。只要碼長充分長，則行重與列重顯著小于碼長N與信息位長度K，因此 H具有稀疏性。需要指出的是LDPC碼構造具有隨機性，只要在校驗矩陣中隨機分布的1的位置滿足行重與列重要求即可，這樣得到的是一組碼字集合，而并非單個編碼約束關系，并且，校驗矩陣不嚴格要求滿秩。

上述(3,6)規則LDPC碼的校驗矩陣可表示為Tanner圖，如圖2-1所示。

圖2-1中含有10個變量節點，分別對應校驗矩陣的一列；含有5個校驗節點，分別對應校驗矩陣的一行。集合 表示第i個變量節點連接的校驗節點集合，集合表示第 j個校驗節點連接的變量節點集合。例如，對應式（2-1）所示校驗矩陣的第一列，對應校驗矩陣的第2行。

校驗矩陣的行重對應變量節點的連邊數，稱為變量節點度分布；列重對應校驗節點度分布。對比式（2-1）與圖2-1的Tanner圖，可以發現二者是一一對應的。Tanner圖中的環與式（2-1）中的1構成的連接關系完全對應。例如，圖2-1中虛線構成了長度為4的環（v2→c3→v4→c1→v2）對應式（2-1）中含有4個1的虛線環。

定義2.1 Tanner 圖中一條閉環路徑的長度定義為環長，在所有閉環中，長度最小的環長稱為Tanner圖的圍長。

一般地，對于(N,K)規則的LDPC碼，行重與列重分別為dc 與dv，我們通常稱這樣的LDPC碼為(dv,dc)碼，它的行重與列重滿足關系式（2-2）。

這樣，對應的 Tanner 圖可表示為，其中，V是變量節點集合，節點數滿足;C是校驗節點集合，節點數滿足;ε是邊集合，邊數滿足。進一步地，(dv,dc)碼的碼率可表示為

上述概念可以進一步推廣到不規則 LDPC 碼，其中，dc 為最大行重，dv為最大列重。

定義2.2 Tanner圖的變量節點與校驗節點的度分布生成函數為

其中，λi與ρi為度分布系數，表示度為i的節點連邊數占總邊數的比例。進一步地，可以定義變量節點與校驗節點的度分布倒數的均值分別為

由于總邊數相等，因此有

由此，給定度分布(λ, )ρ，非規則LDPC碼的碼率為

本質上，LDPC碼的設計符合信道編碼定理中隨機編碼的思想。Tanner圖中變量節點與校驗節點之間的連接關系具有隨機性，我們可以把度分布系數λi與ρj看作變量節點與校驗節點連邊的概率。因此，Tanner圖實際上是符合度分布要求的隨機圖，變量節點與校驗節點之間的連邊關系也可以看作一種交織操作。只要碼長充分長，Tanner圖的規模充分大，這種隨機連接就可以反映隨機編碼特征，暗合了信道編碼定理證明的假設：（1）碼長無限長；（2）隨機化編碼。因此，LDPC碼與Turbo碼在結構設計上，具有類似的偽隨機編碼特征。