本文針對LDPC譯碼算法進行總結(jié)，附帶詳細的推導過程。由于筆者不是這方面的專家，充其量略知一二，許多不懂的地方，還請讀者們多多指教。

LDPC碼在IEEE802.16e、IEEE802.11n、IEEE802.11ac、IEEE802.11ad以及5G等高吞吐量系統(tǒng)中得到了廣泛的應用。

信道編解碼作為整個通信系統(tǒng)中最難實現(xiàn)的一部分，眾多高校、研究院所、企業(yè)，投入了大量的人力資源進行研究與實現(xiàn)。

在信道編解碼技術(shù)中，譯碼主要分為硬判決譯碼和軟判決譯碼。

LDPC硬判決譯碼算法主要分為：消息傳遞（Message-Passing，MP）算法、比特翻轉(zhuǎn)（Bit Flipping, BF）算法和Gallager A、B算法。比特翻轉(zhuǎn)算法中，先求取HC^T，如果為0則停止譯碼，否則翻轉(zhuǎn)參與校驗失敗校驗方程最多的變量節(jié)點對應的比特，再計算HC^T，如此迭代直到HC^T=0或達到設(shè)定迭代次數(shù)。Gallager A、B算法算法過程參考其博士論文。硬判決譯碼性能較差，使用軟判決可顯著提高譯碼性能。

LDPC軟判決譯碼基于置信度傳播（BP）算法（或叫做和積SP算法），通過在變量節(jié)點VN和校驗節(jié)點CN之間傳播和更新置信度信息來達到譯碼收斂的效果。通過BP算法，又衍生出最小和算法，以及歸一化最小和算法，偏置最小和算法。

一切算法研究，需要從腦海理論到落地實踐，通過仿真驗證，再到工程應用，才能將知識轉(zhuǎn)變?yōu)樨敻弧?/span>

01

MP譯碼算法

消息傳遞(MP)算法是迭代解碼算法，在VN和CN之間來回傳遞消息，直到進程停止。消息標記的M_i表示已知bit值為0或1,e表示已刪除位。

在LDPC譯碼中，用B_j符號表示H的奇偶校驗方程中的bit集合(每一行中1的位置集合)，用A_i符號表示碼的第i位的奇偶校驗方程（每一列中1的位置集合）。

考慮下面的奇偶校驗矩陣:

對于上面的奇偶校驗矩陣，我們得到:

基于(Binary Erasure Channel,BEC)的LDPC譯碼處理過程如下：

02

BF譯碼算法

收到符號硬解碼成1和0組成一個二進制向量y。在每個迭代中,計算所有檢查和,以及涉及每一個n bit向量y不滿足奇偶檢驗的數(shù)量。接下來，如果y的比特包含最大數(shù)量的未滿足奇偶校驗，則將其翻轉(zhuǎn)。該過程將重復進行，直到所有校驗和都滿足或達到預定的迭代次數(shù)。

比特翻轉(zhuǎn)譯碼算法的步驟如下：

03

BP(SP)算法

和積算法類似于前一節(jié)中描述的比特翻轉(zhuǎn)算法，但表示每個判決(無論位值是1還是0)的消息現(xiàn)在都是概率。比特翻轉(zhuǎn)譯碼接受接收比特的初始硬判定作為輸入，和積算法是接受接收位的概率作為輸入的軟判定消息傳遞算法。在LDPC譯碼器操作之前，輸入信道或接收比特的概率是已知的，因此它們也被稱為接收比特的先驗概率。在和積解碼器中，節(jié)點之間傳遞的外部信息也是概率。校驗節(jié)點j與比特節(jié)點i之間的外部信息用E_ji表示; E_ji給出了bit c_i為1時使奇偶校驗方程j滿足的概率。如果第i位不包含在j中，則無法定義E_ji，因為在檢查節(jié)點j和第i bit之間沒有外部信息。

奇偶校驗方程中奇數(shù)個bit 是1的概率是：

也就是bit c_i為1時奇偶校驗方程滿足的概率。bit c_i為0時滿足奇偶校驗方程的概率為

二元變量的度量用以下對數(shù)似然比(LLR)表示：

其中，log就是log_e，L(x)符號提供了x的硬判決，并且模|L(x)|決定了判決的可靠性。將LLR轉(zhuǎn)化為概率：

當需要將概率相乘時，只需要加LLR，從而降低和積譯碼器的復雜性。這使得概率的對數(shù)表示有了好處。從校驗節(jié)點j到比特節(jié)點i的外部信息表示為LLR：

從而有：

其中：

運用關(guān)系式

于是得到：

或者，運用關(guān)系式

則有

由于存在tanh和tanh^-1函數(shù)的乘積，上述方程在數(shù)值上具有挑戰(zhàn)性。

考慮Mj,i^'其符號和大小(或bit值和bit可靠性):

于是有

然后我們可以得到：

上式產(chǎn)生了一種新的形式：

每個比特節(jié)點都可以連接輸入LLR，Li，以及每個連接的檢查節(jié)點的LLR。第i位的總LLR就是這些LLR的和：

對于所有的j,i，有H_j,i=1。因此，y_i代表實際接收到的信道值，即不是有效值。對于不同的信道，Li可以計算：

BEC：

BSE：

BI-AWGNC:

瑞利信道：

對數(shù)域和積譯碼算法總結(jié)如下：

04

Min-Sum算法

Min-Sum算法是對數(shù)域和積譯碼算法的簡化，主要考慮到和積譯碼算法在硬件實現(xiàn)上的復雜性，進而采用了一種近似算法。

歸一化最小和譯碼算法的實現(xiàn)采用分層置信傳播算法，是對上式（4-26）的修正，乘一個取值范圍0~1的縮放因子。

偏置最小和譯碼算法，則是在歸一化最小和譯碼算法的基礎(chǔ)上，減去一個偏置因子。

本次關(guān)于LDPC譯碼算法的推導和總結(jié)，到此結(jié)束。