5G通信算法：LDPC譯碼算法詳解

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

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

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

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

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

一切算法研究，需要從腦海理論到落地實(shí)踐，通過仿真驗(yàn)證，再到工程應(yīng)用，才能將知識(shí)轉(zhuǎn)變?yōu)樨?cái)富。

01

MP譯碼算法

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

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

考慮下面的奇偶校驗(yàn)矩陣:

對(duì)于上面的奇偶校驗(yàn)矩陣，我們得到:

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

02

BF譯碼算法

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

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

03

BP(SP)算法

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

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

也就是bit ci為1時(shí)奇偶校驗(yàn)方程滿足的概率。bit ci為0時(shí)滿足奇偶校驗(yàn)方程的概率為

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

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

當(dāng)需要將概率相乘時(shí)，只需要加LLR，從而降低和積譯碼器的復(fù)雜性。這使得概率的對(duì)數(shù)表示有了好處。從校驗(yàn)節(jié)點(diǎn)j到比特節(jié)點(diǎn)i的外部信息表示為L(zhǎng)LR：

從而有：

其中：

運(yùn)用關(guān)系式

于是得到：

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

則有

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

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

于是有

然后我們可以得到：

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

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

對(duì)于所有的j,i，有Hj,i=1。因此，yi代表實(shí)際接收到的信道值，即不是有效值。對(duì)于不同的信道，Li可以計(jì)算：

BEC：

BSE：

BI-AWGNC:

瑞利信道：

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

04

Min-Sum算法

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

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

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

審核編輯：劉清