低密度校驗碼（LDPC）
2.1 LDPC的産生與發展
| 2.2 LDPC 碼的基本原理 |
2.2.1 Gallager 碼
LDPC 碼是一種分組校驗碼，由 Gallager 于 1963 年提出 [1-2]。在其博士論 文 [2] 中，除了對性能界的詳盡分析之外，Gallager 還建議了兩種解碼方法：一 種是簡單的代數法解碼；另一種是基于機率論的解碼。
論文 [1-2] 所想表達的一個思想是，盡管 LDPC 的“低重”特性從碼距的角 度不具有很強的優勢，但稀疏陣結構可以降低解碼的計算量，在性能與工程實 現複雜度之間提供一個折中。在之後的近 40 多年，LDPC 經曆了一段相對沉寂 的時期。部分的原因是基于機率論解碼的複雜度要比代數法解碼高很多，即使 采用稀疏權重的設計，對于當時的硬體，其成本還是難以接受。
另一個原因是對機率論解碼的認識本身，包括其性能潛力。傳統信道編碼 理論評判一個碼的性能大多是基于碼距分析的，通過最小碼距及碼距的分布， 得到性能界的解析表達式，進而比較“嚴格”地推斷出該信道編碼的糾錯能力。 這類方法對較短碼長且基于代數法解碼的分組碼十分有效，但當碼長較長且采 用機率論的解碼，就顯得不那麼有力。LDPC 碼的優勢在于長碼和運用機率方 法解碼。是以在很長的一段時間中，它的潛力并沒有被學術界和工業界所廣泛認識。
1993 年 Turbo 碼 [7] 的出現掀起了業界對機率法解碼的熱潮。所謂機率法 解碼，即采用軟的資訊比特，而不是代數式譯碼中的“對”或“錯”的硬判決。“軟”展現在每個比特位的置信度是一個機率分布，即一個實數，相當于“對” 與“錯”之間漸變的“灰階”。機率法解碼一般需要與疊代譯碼相結合，才會 展現其優勢。仿照 Turbo 譯碼原理，大家又重新發現最初 Gallager 所提的 LDPC 的機率法解碼就是采用疊代譯碼的。而且 Turbo 和 LDPC 都可以用因子 圖（Factor Graph）[16] 的分析手段統一起來，所用的解碼方法也可以歸類為人 工智能當中的置信傳播（Belief Propagation）算法 [17] 或者資訊傳遞（Message Passing）[18]。
經典的 LDPC 編碼器可以按如下描述。一個長度為 k 的二進制的資訊比特序 列 u，引入 m 個校驗比特後，生成 n 個編碼比特的序列 t，此 時碼率為 k/n。因 為是線性碼，碼字 t 可以用 u 乘以一個生成矩陣 GT 來表示：
生成矩陣 GT 包含兩部分：
如果采用硬判決的代數法譯碼，相應的校驗矩陣可以寫成：
當碼字在傳輸中沒有錯誤時，奇偶校驗通過，即，
其中，第一個值為t的估值。需要指出的是，LDPC校驗矩陣有時不一定寫成右邊為機關矩陣的形式，尤其當采用機率譯碼（如軟資訊的置信度傳播）方式。此時需要對校驗矩陣做一些線性代數的變換，求出生成矩陣以便編碼。
LDPC的特點在于行數為m，列數為n的校驗矩陣A具有稀疏性，即多數的元素為0，矩陣A的産生方法有随機生成、結構化設計或者窮舉尋找，詳細請見後述（第2.3節和第2.5.3節）。
一個LDPC編碼後的碼塊通過AWGN信道的框圖如圖2-2所示：
在圖2-2中，資訊比特流u先進行編碼。編碼後的比特流t經過AWGN信道，輸出為觀測到的序列 y。LDPC 解碼器進行變量節點和校驗節點之間的反 複疊代交換軟資訊，若幹次疊代後，解碼器輸出硬判決結果，即解碼後的資訊 比特序列u的估計值。
LDPC 校驗矩陣 A 的稀疏性的必要性在于：
- LDPC 采用的是“加和乘”（Sum-product）的譯碼算法。該算法隻有當二 分圖（Bipartite）中沒有環（Cycle-free），或者沒有短環（Short Cycle）時才能 達到較好的性能。而稀疏性可以大大降低短環出現的可能性；
- 稀疏性意味着變量節點和校驗節點之間的連接配接密度不高，這樣在做“加和 乘”的譯碼時可以減少累加和相乘的運算，降低譯碼的複雜度；
- 當校驗矩陣 A 是稀疏陣時，其相應的生成矩陣 GT 通常不具有稀疏性，這說明産生的編碼序列t的編碼權重有可能較高，進而具有較好的編碼矩陣。
2.2.2 規則 LDPC 和非規則 LDPC
LDPC編碼可以用二分圖的方法表述，根據圖2-3所示的LDPC二分圖（Bipartite）。規則LDPC，每個變量節點（Yi,i=1,2,3,…,9，為列的編号；有 9 個輸入變量節點）連接配接q=2個校驗節點（Ai,i=1,2,3,…,6；行的編号；有 6 行 參與校驗；q 為列重—這一列中“1”的個數），每個檢驗節點連接配接r=3個變量節點（r 為行重，即等于這一行中“1”的個數）。
從圖 2-3 中可以看出，節點分成兩大類型：變量節點（Variable Nodes）和校驗節點（Check Nodes）。同一類型的節點不能直接彼此相連，不能直接互 通資訊，但可以通過另一個類型的節點傳遞資訊。這種互聯結構展現于網狀的 連線，也稱“邊”（Edge），可以完全由校驗矩陣決定。
LDPC 可以分為規則（Regular）和非規則（Irregular）[8] 兩種。規則的 LDPC 是指同一種類型的節點具有相同的自由度。這裡的自由度是與各節點類 型的邊數目，即對于 LDPC 碼來說，相當于校驗矩陣中每行或者每列上的非零 元素數目。圖 2-3 就是一個規則 LDPC 的例子，其中每個校驗節點與 3 個變量節 點相連，而每個變量節點與 2 個校驗節點相連。對應到校驗矩陣，即每行有 3 個非 零元素，dc = 3。每列有 2 個非零元素，dv = 2。與 6×9 的整個校驗矩陣來看，還 是比較“稀疏”的。當 LDPC 碼非常大時，其稀疏性就更為明顯。
非規則 LDPC 的變量節點或者校驗節點的自由度可以不一樣，隻要服從某 種分布即可。用一對參數（λ, ρ）式子表示非規則 LDPC，其中
代表了變量節點的自由度分布。而
代表了校驗節點的自由度分布。更精确的講，系數λi和ρi分别表示自由度為i的從變量節點和校驗節點發出的邊數所占的比例。上面的兩個公式也可以用來描述規則的LDPC，例如，圖2-3的LDPC就可以寫成
λ（x）:=x^1
和
ρ(x):=x^2
。
相比規則LDPC，非規則LDPC有更大的靈活性和優化空間。無論從理論分析還是仿真驗證，非規則LDPC的性能更優。是以在工程上所考慮的LDPC都是非規則的LDPC。
2.2.3 置信度傳播的基本原理及其應用
置信度傳播（Belief Propagation）也被稱為資訊傳送（Message Passing），是機率論中的一種基本算法，guangfanyingyongza廣泛應用在數字通信、人工智能、計算機科學、運籌管理等領域。
我們把圖2-4一般化成一個因子圖（Factor Graph），由變量節點（Variable Notes）和因子節點（Factor Notes）組成。
一般地置信度傳播或者資訊傳送算法的本質就是根據因子圖中變量節點和因子節點的連接配接關系，計算變量節點取值的邊緣機率分布。這裡有一個基本假設，即變量節點之間、因子節點之間都是不相關的，它們的聯合機率分布可 以表示成邊緣機率的乘積。邊緣機率的求解可以用樹狀結構圖表示。因子圖展 開成樹狀圖之後（這裡假設不存在環狀結構），可以更直覺地看出疊代譯碼的過程，如圖 2-5 所示。
從因子節點a到變量節點i的資訊mga i(x； ) 可以解釋成因子節點a有多大的可能性認為節點i會處于狀态x；c而對于變量節點i，它處于狀态x，的聯合置信度正比于與它相連的因子節點認為變量節點會處于狀态x；的機率的乘積，即
對于任意一個因子節點A，它的置信度等價于與它相連的所有變量節點的聯合置信度。用式(2-12)表示
注意這裡的L是個集合的概念。那麼根據式(2-11)，變量節點集合L中的每一個節點的置信度都是由正比于與它相連的因子節點認為變量節點會處于狀态x，的機率的乘積，是以這個聯合機率可以寫成：
一個節點上的置信度，也就是邊緣機率，就等于除了它自己，對所有相連的因子節點的聯合置信度求和，即：
式(2-15)可以寫成疊代形式。對于能夠展成樹形圖的結構，而且不存在局部的環狀結構，可以證明：置信度傳播算法能夠在有限的疊代次數内(兩倍的樹形結構的最大深度)收斂到邊緣機率。
在實際的因子圖展開當中， 局部可能會出現迂回環狀結構(LoopyGraph) ， 如圖2-6所示。當有環結構存在時， 置信度傳播算法有可能不收斂，或者即使收斂，也不一定收斂到邊緣機率分布。解決環結構不收斂的方法有好幾種，對環結構的研究具有更多的理論意義，對工程設計的指導有限，這裡不再贅述。
在信道解碼方面，置信度傳播被用在多種編碼當中。這裡我們介紹在 LDPC 中的應用。LDPC 校驗矩陣的每一行代表一個奇偶校驗，傳統的代數譯 碼隻考察相對應的比特節點上的值相加之和是否為 0，如果是，奇偶校驗通過； 反之，校驗不通過。在機率譯碼當中，校驗節點，也就是一般的因子圖中的因 子節點，需要計算的是該校驗通過的機率。而這個計算是假定某一個相連的變 量比特是 1（或者 0），并且其他變量節點的值符合某種先驗的機率分布。變量 節點需要計算的是一個比特是 1（或者 0）的機率，這個計算是基于所有相連的校驗節點上的校驗通過機率。
用 rij 代表由校驗節點确定的資訊機率，更具體的，用 rij0 代表當資訊比特 ti 為 0 時，校驗節點j能夠校驗通過的機率。同理，用rij1 代表當資訊比特ti 為 1 時， 校驗節點 j 能夠校驗通過的機率。那麼，根據置信度傳播算法的原理，這兩個 資訊機率可以用式（2-17）來計算：
在式(2-17) 中， 表達式ie row[j] /(表示在第j行的所有為1的比特索引，除去目前的比特索引i。機率qy由變量節點來計算。q，表示在給定所有的校驗節點的資訊(除去校驗節點j)的條件下，t；=0的機率。同理，q；表示在給定所有的校驗節點的資訊(除去校驗節點j)的條件下，t；=1的機率。根據置信度傳播的算法原理，機率q；可以表達成：
在式(2-18) 中， j ecol[i] /(j) 表示在第i列的所有為1的校驗節點索引，除去目前的校驗節點索引j。系數aiy是用來歸一化的， 以保證q； +q； =1。式子中的p?和pi是相對于目前一輪疊代譯碼的第i個資訊比特的先驗機率，由以前的疊代過程得到。外部資訊(Extrinsic Information) e； 和e， 的計算公式為：