LDPC

LDPC簡介

　　LDPC碼最早在20世紀(jì)60年代由Gallager在他的博士論文中提出，但限于當(dāng)時的技術(shù)條件，缺乏可行的譯碼算法，此后的35年間基本上被人們忽略，其間由Tanner在1981年推廣了LDPC碼并給出了LDPC碼的圖表示，即后來所稱的Tanner圖。1993年Berrou等人發(fā)現(xiàn)了Turbo碼，在此基礎(chǔ)上，1995年前后MacKay和Neal等人對LDPC碼重新進(jìn)行了研究，提出了可行的譯碼算法，從而進(jìn)一步發(fā)現(xiàn)了LDPC碼所具有的良好性能，迅速引起強烈反響和極大關(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碼是通過校驗矩陣定義的一類線性碼，為使譯碼可行，在碼長較長時需要校驗矩陣滿足“稀疏性”，即校驗矩陣中1的密度比較低，也就是要求校驗矩陣中1的個數(shù)遠(yuǎn)小于0的個數(shù)，并且碼長越長，密度就要越低。

LDPC百科

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

　　發(fā)展歷史

　　LDPC碼最早在20世紀(jì)60年代由Gallager在他的博士論文中提出，但限于當(dāng)時的技術(shù)條件，缺乏可行的譯碼算法，此后的35年間基本上被人們忽略，其間由Tanner在1981年推廣了LDPC碼并給出了LDPC碼的圖表示，即后來所稱的Tanner圖。1993年Berrou等人發(fā)現(xiàn)了Turbo碼，在此基礎(chǔ)上，1995年前后MacKay和Neal等人對LDPC碼重新進(jìn)行了研究，提出了可行的譯碼算法，從而進(jìn)一步發(fā)現(xiàn)了LDPC碼所具有的良好性能，迅速引起強烈反響和極大關(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碼是通過校驗矩陣定義的一類線性碼，為使譯碼可行，在碼長較長時需要校驗矩陣滿足“稀疏性”，即校驗矩陣中1的密度比較低，也就是要求校驗矩陣中1的個數(shù)遠(yuǎn)小于0的個數(shù)，并且碼長越長，密度就要越低。

　　應(yīng)用熱點

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

　　譯碼算法

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

　　LDPC初級之Decoder基礎(chǔ)

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

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

　　Tanner Graph

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

　　（1）

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

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

　　其中是第m行中元素。

　　同時，定義

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

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

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

　　定義：

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

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

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

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

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

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

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

　　因為， 則check node z1與c1， c2， c4之間有edge。因為 ，則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的工作原理，讓大家對其有一個直觀的了解。

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

　　回想Decoder判斷接收信號為codeword的基本原理，

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

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

　　1. 初始化：接收到信號（”x”代表對應(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。如果有兩個及以上的bit node為”x”，則zm無法糾錯，.

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

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

　　Example：

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

　　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”。因為有兩個未知信息，所以check nodez3無法糾錯，因此z3生成信息

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

　　3. Bit nodes update

　　因為M4=”x”，，則Bit node c4=”0”。

　　因為M5=”x”，， 則Bit node c5=”1”。

　　因為M6=”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”，糾錯結(jié)束。

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

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

　　Bit-Flipping Decoding

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

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

　　2. check nodes update： check node zm根據(jù)接收到的信息，針對每個與之相連的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矩陣，編碼得到一個codeword c=［0 0 1 0 1 1］。經(jīng)過BSC通道后，接收到的信號r=［1 0 1 0 1 1］。 Bit-flipping decoding的糾錯過程如下：

　　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的信息

　　同理，依次計算出：

　　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. 驗證M是否滿足syndrome decoding.

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

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