LDPC

LDPC簡(jiǎn)介

　　LDPC碼最早在20世紀(jì)60年代由Gallager在他的博士論文中提出，但限于當(dāng)時(shí)的技術(shù)條件，缺乏可行的譯碼算法，此后的35年間基本上被人們忽略，其間由Tanner在1981年推廣了LDPC碼并給出了LDPC碼的圖表示，即后來所稱的Tanner圖。1993年Berrou等人發(fā)現(xiàn)了Turbo碼，在此基礎(chǔ)上，1995年前后MacKay和Neal等人對(duì)LDPC碼重新進(jìn)行了研究，提出了可行的譯碼算法，從而進(jìn)一步發(fā)現(xiàn)了LDPC碼所具有的良好性能，迅速引起強(qiáng)烈反響和極大關(guān)注。經(jīng)過十幾年來的研究和發(fā)展，研究人員在各方面都取得了突破性的進(jìn)展，LDPC碼的相關(guān)技術(shù)也日趨成熟，甚至已經(jīng)開始有了商業(yè)化的應(yīng)用成果，并進(jìn)入了無線通信等相關(guān)領(lǐng)域的標(biāo)準(zhǔn)。LDPC碼是通過校驗(yàn)矩陣定義的一類線性碼，為使譯碼可行，在碼長(zhǎng)較長(zhǎng)時(shí)需要校驗(yàn)矩陣滿足“稀疏性”，即校驗(yàn)矩陣中1的密度比較低，也就是要求校驗(yàn)矩陣中1的個(gè)數(shù)遠(yuǎn)小于0的個(gè)數(shù)，并且碼長(zhǎng)越長(zhǎng)，密度就要越低。

LDPC百科

　　LDPC是Low Density Parity Check Code英文縮寫，意思是低密度奇偶校驗(yàn)碼，最早在20世紀(jì)60年代由Gallager在他的博士論文中提出。

　　發(fā)展歷史

　　LDPC碼最早在20世紀(jì)60年代由Gallager在他的博士論文中提出，但限于當(dāng)時(shí)的技術(shù)條件，缺乏可行的譯碼算法，此后的35年間基本上被人們忽略，其間由Tanner在1981年推廣了LDPC碼并給出了LDPC碼的圖表示，即后來所稱的Tanner圖。1993年Berrou等人發(fā)現(xiàn)了Turbo碼，在此基礎(chǔ)上，1995年前后MacKay和Neal等人對(duì)LDPC碼重新進(jìn)行了研究，提出了可行的譯碼算法，從而進(jìn)一步發(fā)現(xiàn)了LDPC碼所具有的良好性能，迅速引起強(qiáng)烈反響和極大關(guān)注。經(jīng)過十幾年來的研究和發(fā)展，研究人員在各方面都取得了突破性的進(jìn)展，LDPC碼的相關(guān)技術(shù)也日趨成熟，甚至已經(jīng)開始有了商業(yè)化的應(yīng)用成果，并進(jìn)入了無線通信等相關(guān)領(lǐng)域的標(biāo)準(zhǔn)。LDPC碼是通過校驗(yàn)矩陣定義的一類線性碼，為使譯碼可行，在碼長(zhǎng)較長(zhǎng)時(shí)需要校驗(yàn)矩陣滿足“稀疏性”，即校驗(yàn)矩陣中1的密度比較低，也就是要求校驗(yàn)矩陣中1的個(gè)數(shù)遠(yuǎn)小于0的個(gè)數(shù)，并且碼長(zhǎng)越長(zhǎng)，密度就要越低。

　　應(yīng)用熱點(diǎn)

　　LDPC碼即低密度奇偶校驗(yàn)碼（Low Density Parity Check Code，LDPC），它由Robert G.Gallager博士于1963年提出的一類具有稀疏校驗(yàn)矩陣的線性分組碼，不僅有逼近Shannon限的良好性能，而且譯碼復(fù)雜度較低， 結(jié)構(gòu)靈活，是近年信道編碼領(lǐng)域的研究熱點(diǎn)，目前已廣泛應(yīng)用于深空通信、光纖通信、衛(wèi)星數(shù)字視頻和音頻廣播等領(lǐng)域。LDPC碼已成為第四代通信系統(tǒng)（4G）強(qiáng)有力的競(jìng)爭(zhēng)者，而基于LDPC碼的編碼方案已經(jīng)被下一代衛(wèi)星數(shù)字視頻廣播標(biāo)準(zhǔn)DVB-S2采納。

　　譯碼算法

　　對(duì)同樣的LDPC碼來說，采用不同的譯碼算法可以獲得不同的誤碼性能。優(yōu)秀的譯碼算法可以獲得很好的誤碼性能，反之，采用普通的譯碼算法，誤碼性能則表現(xiàn)一般。LDPC碼的譯碼算法包括以下三大類：硬判決譯碼，軟判決譯碼和混合譯碼。1. 硬判決譯碼將接收的實(shí)數(shù)序列先通過解調(diào)器進(jìn)行解調(diào)，再進(jìn)行硬判決，得到硬判決0，1序列，最后將得到的硬判決序列輸送到硬判決譯碼器進(jìn)行譯碼。這種方式的計(jì)算復(fù)雜度固然很低，但是硬判決操作會(huì)損失掉大部分的信道信息，導(dǎo)致信道信息利用率很低，硬判決譯碼的信道信息利用率和譯碼復(fù)雜度是三大類譯碼中最低的。常見的硬判決譯碼算法有比特翻轉(zhuǎn)（bit-flipping， BF）算法、一步大數(shù)邏輯（one-step majority-logic， OSMLG）譯碼算法。2. 軟判決譯碼可以看成是無窮比特量化譯碼，它充分利用接收的信道信息（軟信息），信道信息利用率得到了極大的提高，軟判決譯碼利用的信道信息不僅包括信道信息的符號(hào)，也包括信道信息的幅度值。信道信息的充分利用，極大地提高了譯碼性能，使得譯碼可以迭代進(jìn)行，充分挖掘接收的信道信息，最終獲得出色的誤碼性能。軟判決譯碼的信道信息利用率和譯碼復(fù)雜度是三大類譯碼中最高的。最常用的軟判決譯碼算法是和積譯碼算法，又稱置信傳播 （belief propagation， BP）算法。3. 與上述的硬判決譯碼和軟判決譯碼相比，混合譯碼結(jié)合了軟判決譯碼和硬判決譯碼的特點(diǎn)，是一類基于可靠度的譯碼算法，它在硬判決譯碼的基礎(chǔ)上，利用部分信道信息進(jìn)行可靠度的計(jì)算。常用的混合譯碼算法有、加權(quán)比特翻轉(zhuǎn)（weighted BF， WBF）算法、加權(quán)OSMLG（weighted OSMLG， WMLG）譯碼算法。

　　LDPC初級(jí)之Decoder基礎(chǔ)

　　LDPC （Low-Density Parity-Check，低密度奇偶校驗(yàn)） 強(qiáng)大的糾錯(cuò)能力使其應(yīng)用范圍越來越廣。LDPC可以簡(jiǎn)單的分成編碼器（Encoder），信道模型（Channel model），解碼器（Decoder）三部分。其中Decoder在這三部分中最為簡(jiǎn)單，為此，初級(jí)系列先介紹decoder，便于大家對(duì)LDPC有一個(gè)初步的了解。

　　如今LDPC的Decoder多采用sum-product decoding。而在介紹sum-product之前，有必要先介紹message-passing和bit-flipping decoding，了解它們對(duì)于了解sum-product，以及后續(xù)深入學(xué)習(xí)LDPC有很大的幫助。

　　Tanner Graph

　　直觀認(rèn)識(shí)message-passing工作原理的最佳工具是Tanner Graph。每個(gè)parity-check matrix H都有一個(gè)對(duì)應(yīng)的Tanner Graph。以一個(gè)例子說明Tanner Graph的構(gòu)造原理，如下H矩陣：

　　（1）

　　H陣的每一行對(duì)應(yīng)的都是一個(gè)parity-check，將第m行中每個(gè)“1”所處的第n列，即bit cn，歸納成一個(gè)組合

　　比如， ， .因此，第m行的parity-check可以表述成：

　　其中是第m行中元素。

　　同時(shí)，定義

　　為第m行中除了第n列，其它元素為“1”的列。比如， ， .

　　除了組合每行中的元素“1”的列位置，還需組合每列中元素“1”所處的行位置。定義：

　　為第n列（bit cn）所處元素為“1”的行。比如， ， .

　　定義：

　　為第n列中除了第m行，其它對(duì)應(yīng)元素為”1”的行。如：， .

　　了解這些，除了對(duì)創(chuàng)建Tanner Graph有幫助外，還對(duì)了解后續(xù)的bit-flipping， sum-product等幫助。

　　Tanner Graph由三種元素構(gòu)成：

　　- bit nodes：代表H陣中的列，也就是codeword的每個(gè)bit；

　　- check nodes：代表H陣中的行，也就是parity-check約束；

　　- edge：如果Hmn=1，則第n個(gè)bit node和第m個(gè)check node之間會(huì)互連，即一條edge。

　　根據(jù)以上的H矩陣，其對(duì)應(yīng)的Tanner Graph如下圖：

　　因?yàn)?img alt="N_{1}=\left\{ 1,2,4\right\} " border="0" height="30" src="https://www.zhihu.com/equation?tex=N_%7B1%7D%3D%5Cleft%5C%7B+1%2C2%2C4%5Cright%5C%7D+" width="203" />， 則check node z1與c1， c2， c4之間有edge。因?yàn)?，則bit node c1與z1， z3之間有edge。

　　Message-Passing

　　Message-passing是指信息在相連的check nodes和bit nodes間傳遞。Bit-flipping和sum-product decoding都屬于message-passing，所不同的是，二者傳遞的信息不一樣。下面以BEC（Bit Erasure Channel）為例，介紹message-passing的工作原理，讓大家對(duì)其有一個(gè)直觀的了解。

　　所謂BEC，是指在其通道中傳輸?shù)男盘?hào)要么被接收器正確的接收，要么被通道erase掉，使得接收器沒有接收到此信號(hào)。由于接收到的信號(hào)都是正確的，因此Decoder只需要處理那些沒有接收到的未知信號(hào)即可。

　　回想Decoder判斷接收信號(hào)為codeword的基本原理，

　　以H陣的z1為例，則需滿足如下關(guān)系

　　假設(shè)bit c1=r1=”0”，c2=r2=”1”，c4在經(jīng)過BEC通道時(shí)出錯(cuò)，導(dǎo)致r4未知：r4=”x”，則可以推斷出c4=“1”，由此完成對(duì)c4在糾錯(cuò)。因此，BEC的message-passingdecoding可以簡(jiǎn)化如下：

　　1. 初始化：接收到信號(hào)（”x”代表對(duì)應(yīng)bit被BEC erase）視為由bit nodes傳遞給相連check nodes的初始信息。

　　2. check nodes update： 如果傳遞到check node zm的信息中沒有”x”，則check nodes無需生成新信息；如果只有cn=”x”，則需根據(jù)

　　其中為mod 2求和， 為check node zm生成的信息，并將其傳遞給bit cn。如果有兩個(gè)及以上的bit node為”x”，則zm無法糾錯(cuò)，.

　　3. bit nodes update： 如果bit nodes的狀態(tài)為”x”，則將其更新為接收到的信息。

　　4. 如果bit nodes沒有了”x”，則decoding結(jié)束；否則從步驟2處開始，繼續(xù)迭代。

　　Example：

　　由方程（1）中的H矩陣，編碼得到一個(gè)codeword c=［0 0 1 0 1 1］。經(jīng)過BEC通道后，接收到的信號(hào)r=［0 0 1 x x x］。 Message-passing decoding的糾錯(cuò)過程如下：

　　1. 初始化：bit nodes傳遞給check nodes的初始信息M=［0 0 1 x x x］。

　　2. Check nodes update：

　　由H矩陣及其Tanner Graph可知，z1與c1， c2， c4相連，其中M4=”x”，則check nodez1生成信息

　　z2與c2， c3， c5相連，其中M5=”x”，則check nodez2生成信息

　　z3與c1， c5， c6相連，其中M5=”x”，M6=”x”。因?yàn)橛袃蓚€(gè)未知信息，所以check nodez3無法糾錯(cuò)，因此z3生成信息

　　z4與c3， c4， c6相連，其中M4=”x”，M6=”x”。則

　　3. Bit nodes update

　　因?yàn)镸4=”x”，，則Bit node c4=”0”。

　　因?yàn)镸5=”x”，， 則Bit node c5=”1”。

　　因?yàn)镸6=”x”， ，，則Bit node c6=”x”。

　　Bit nodes update結(jié)束后，各Bit node的信息更新為M=［0 0 1 0 1 x］。因此重復(fù)Check nodes update，繼續(xù)迭代。

　　4. Check nodes update

　　z3與c1， c5， c6相連，其中M6=”x”。則

　　z4與c3， c4， c6相連，其中M6=”x”。則

　　5. Bit nodes update

　　目前只有M6=”x”， ， 則Bit node c6的信息更新為1，M=［0 0 1 0 1 1］。

　　6. End

　　至此，所有bit nodes的信息都為0/1，不再有”x”，糾錯(cuò)結(jié)束。

　　通過以上的分析，想必大家對(duì)message-passing decoding中的message和passing有了直觀的了解。BEC的特性決定了接收到的信息一定是正確的，所以其decoding的方法只是syndrome decoding。但是在BSC （Binary Symmetric Channel）和AWGN （Additive White Gaussian Noise）通道中，由于接收到的數(shù)據(jù)并不能明確知道其對(duì)錯(cuò)，導(dǎo)致decoding的方法會(huì)與BEC有所不同。

　　盡管BEC的message-passing decoding方法非常簡(jiǎn)單，但是其中也存在缺陷。請(qǐng)大家思考一個(gè)問題：什么情況下，無論進(jìn)行多少次的迭代計(jì)算，BEC的message-passing decoding依然無法糾錯(cuò)成功？后續(xù)的文章中會(huì)對(duì)此做專題分析。

　　Bit-Flipping Decoding

　　Bit-flipping是message-passing中的hard-decision算法，在bit nodes 和check nodes中，傳遞的信息是0/1。Check node依然利用syndrome decoding的方法來生成信息。與BEC中的message-passing decoding不同的是，由于每個(gè)接收到的bit信息都存在出錯(cuò)的可能性，所以check nodes需要針對(duì)每個(gè)與之相連的bit node生成信息。具體decoding步驟如下：

　　1. 初始化：接收到信號(hào)視為由bit nodes傳遞給相連check nodes的初始信息。

　　2. check nodes update： check node zm根據(jù)接收到的信息，針對(duì)每個(gè)與之相連的bit node生成信息

　　其中 為mod 2求和。

　　3. bit nodes update： bit node接收與之相連的check nodes傳遞來的信息。如果接收到的大部分信息與原bit node值不同，則bit node值翻轉(zhuǎn)。

　　4. 如果bit nodes的值滿足syndrome decoding，則decoding成功；否則從2開始繼續(xù)迭代。

　　Example：

　　由方程（1）中的H矩陣，編碼得到一個(gè)codeword c=［0 0 1 0 1 1］。經(jīng)過BSC通道后，接收到的信號(hào)r=［1 0 1 0 1 1］。 Bit-flipping decoding的糾錯(cuò)過程如下：

　　1. 初始化：bit nodes傳遞給check nodes的初始信息M=［1 0 1 0 1 1］。

　　2. Check nodes update： check node z1接收來自bit node c1， c2， c4的信息，則

　　即反饋給c1的信息， 如下圖所示。

　　反饋給c2的信息

　　反饋給c4的信息

　　同理，依次計(jì)算出：

　　3. Bit nodes update：

　　bit node c1與check nodes z1，z3相連，如下圖所示。， 而。根據(jù)服從大多數(shù)的原則，c1的信息要翻轉(zhuǎn)，則 ；

　　bit node c2與check nodes z1，z2相連，

　　不滿足大多數(shù)的原則，保持不變；

　　bit node c3與check nodes z2，z4相連，

　　則保持不變；

　　bit node c4與check nodes z1，z4相連，

　　保持不變；

　　bit node c5與check nodes z2，z3相連，

　　保持不變；

　　bit node c6與check nodes z3，z4相連，

　　保持不變。

　　Bit nodes update完成后，M=［0 0 1 0 1 1］。

　　4. 驗(yàn)證M是否滿足syndrome decoding.

　　同理，。因此糾錯(cuò)成功，c=［0 0 1 0 1 1］為發(fā)送codeword.

　　通過對(duì)BEC中的Message-passing decoding，以及Bit-flipping decoding的介紹，了解各decoding方法中的message和passing后，對(duì)于message-passing的工作過程及基本原理會(huì)有一個(gè)直觀的影響。這對(duì)于掌握sum-product decoding會(huì)有很好的幫助。