LDPC碼置信傳播譯碼時(shí)序研究

南京信息工程大學(xué)電子與信息工程學(xué)院 周 華 李誠謙 余嘉昊

LDPC碼置信傳播譯碼時(shí)序研究

南京信息工程大學(xué)電子與信息工程學(xué)院 周 華 李誠謙 余嘉昊

本文對低密度奇偶校驗(yàn)（LDPC）碼置信傳播譯碼的三種基本時(shí)序安排進(jìn)行詳細(xì)介紹，包括洪泛譯碼、串行譯碼、動(dòng)態(tài)譯碼。對各譯碼時(shí)序的原理、收斂速度、誤碼率等進(jìn)行闡述和比較，并提出一些可行性改進(jìn)措施來提高LDPC碼的譯碼性能。

LDPC碼；置信傳播；譯碼時(shí)序

1. 低密度奇偶校驗(yàn)碼介紹

低密度奇偶校驗(yàn)碼（LDPC碼） 由二進(jìn)制稀疏矩陣定義，矩陣中大部分元素是 0，剩余部分元素為 1。LDPC碼的一個(gè)重要研究成果是1981年著名學(xué)者Tanner提出了用圖模型來表述LDPC碼的理念。該模型根據(jù)LDPC碼的校驗(yàn)矩陣中1的位置提出雙向二分圖。通過二分圖可構(gòu)造性能良好的 LDPC 碼，支持并行譯碼，大大降低譯碼復(fù)雜度。Mackay 和 Neal 利用二分圖對 LDPC 碼性能進(jìn)行了深入研究，發(fā)現(xiàn)采用置信傳播（belief propagation）譯碼算法的 LDPC碼譯碼性能逼近香濃極限。

2. LDPC碼置信傳播譯碼算法

假設(shè)一個(gè)（N,K）的LDPC碼，校驗(yàn)位數(shù)量為M=N-K，則校驗(yàn)矩陣H是一個(gè)M*N的矩陣。矩陣H的二分圖如圖1所示。圖1下方的N個(gè)圓圈節(jié)點(diǎn)表示N個(gè)碼字符號(hào)，稱作變量節(jié)點(diǎn)；上邊的M個(gè)方形節(jié)點(diǎn)表示M個(gè)校驗(yàn)方程，稱作校驗(yàn)節(jié)點(diǎn)。當(dāng)變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)存在于同一個(gè)校驗(yàn)方程時(shí)，就用邊將兩者連接。和每個(gè)節(jié)點(diǎn)相連的邊的個(gè)數(shù)稱作該節(jié)點(diǎn)的度。從某個(gè)節(jié)點(diǎn)出發(fā)再次回到該節(jié)點(diǎn)所經(jīng)歷邊的個(gè)數(shù)即為環(huán)的長度，其中最短環(huán)所經(jīng)過的邊的數(shù)量構(gòu)成二分圖的圍長。如圖1，黑色加粗的邊構(gòu)成了一個(gè)圍長等于4的短環(huán)。我們構(gòu)造矩陣的時(shí)候尤其關(guān)注最小圍長，因?yàn)樗苯雨P(guān)系到LDPC碼的譯碼性能。

圖1 LDPC碼的校驗(yàn)矩陣和二分圖

3. 置信傳播的調(diào)度安排

LDPC碼最常用的譯碼算法是置信傳播。理論分析表明，如果與其校驗(yàn)矩陣對應(yīng)的二分圖無環(huán)路存在，則BP算法會(huì)收斂于全部比特的后驗(yàn)概率，也是LDPC碼具有良好性能的原因之一。

通常評(píng)估一種譯碼算法有三個(gè)指標(biāo)：譯碼速率、譯碼復(fù)雜度和譯碼性能。譯碼器通過迭代算法更新消息，直到滿足停止條件。迭代算法的本質(zhì)是對二分圖中的信息進(jìn)行調(diào)度。調(diào)度是指置信傳播過程中變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間的消息更新次序。下面介紹幾種常見的時(shí)序調(diào)度譯碼算法：

第一，洪泛機(jī)制是標(biāo)準(zhǔn)置信傳播算法釆取的調(diào)度策略，屬于并行消息傳遞機(jī)制，也是最普遍最基本的調(diào)度策略。它的做法是：在每一輪迭代過程中，所有校驗(yàn)節(jié)點(diǎn)同時(shí)收集從相鄰變量節(jié)點(diǎn)傳來的消息，更新完畢后，再利用已更新過的所有校驗(yàn)節(jié)點(diǎn)的消息同時(shí)去更新所有變量節(jié)點(diǎn)的消息，最后每個(gè)變量節(jié)點(diǎn)根據(jù)判決條件進(jìn)行判決，如此反復(fù)，直到滿足停止條件。這種消息傳遞機(jī)制最為簡單，譯碼速率也很高，但性能并不是最優(yōu)的。研究標(biāo)明，洪泛往往需要較大的迭代次數(shù)才能收斂，從而引起高運(yùn)算量以及很長的譯碼時(shí)延。泛洪的置信傳播調(diào)度方式如圖2所示。

圖2 泛洪算法節(jié)點(diǎn)間消息傳播的過程

第二，串行調(diào)度按照一定的次序，依次對各節(jié)點(diǎn)進(jìn)行更新。直到所有的校驗(yàn)節(jié)點(diǎn)（或變量節(jié)點(diǎn)）更新完畢，一次迭代過程才算結(jié)束。串行的消息傳遞機(jī)制，與洪泛機(jī)制相比，具有收斂速度快，復(fù)雜度低，且實(shí)際占用硬件資源少的特點(diǎn)。分層置信傳播是一種典型的串行調(diào)度策略。研究表明，LBP譯碼的收斂速度大概是洪泛的兩倍，且復(fù)雜度與洪泛保持一致。這是一種相對理想的，幾乎不增加復(fù)雜度代價(jià)的更新策略。但是無論是洪泛還是LBP，其更新節(jié)點(diǎn)的順序是不變的，稱其為非動(dòng)態(tài)消息更新策略。LBP的置信傳播調(diào)度方式如圖3所示。

圖3. 泛洪算法節(jié)點(diǎn)間消息傳播的過程

第三，動(dòng)態(tài)調(diào)度動(dòng)態(tài)選擇節(jié)點(diǎn)進(jìn)行更新，使得譯碼達(dá)到最優(yōu)的性能和最大的收斂速率。其中殘差置信傳播策略能較大提高譯碼收斂速率。RBP為一種動(dòng)態(tài)消息調(diào)度策略，每次需要對所有的消息計(jì)算更新前后的差值，然后進(jìn)行排序。篩選出最大殘差值所在的邊，對其優(yōu)先更新。其原理是，當(dāng)譯碼收斂的時(shí)候，節(jié)點(diǎn)前后兩次消息的殘差值會(huì)趨向于0，也就是說，如果節(jié)點(diǎn)間消息殘差值越大，則可以認(rèn)為該消息在迭代譯碼中還未收斂，更新該消息對整個(gè)算法收斂具有較大貢獻(xiàn)。因此優(yōu)先對該節(jié)點(diǎn)進(jìn)行處理，能有效的加快譯碼的整體收斂速率。RBP在高性噪比區(qū)可能存在誤碼平層現(xiàn)象，因而大大限制了譯碼性能。繼而一種面向節(jié)點(diǎn)的RBP的動(dòng)態(tài)策略(NWRBP)被提出，在一定程度上有效克服誤碼平層現(xiàn)象。NW-RBP在原有的算法上做了改進(jìn)，與RBP不同，NW-RBP在選中最大殘差值之后，讓更多的變量節(jié)點(diǎn)參與更新。仿真結(jié)果表明, NW-RBP不僅提高了譯碼收斂速率，而且改善了RBP的譯碼性能，但是相對復(fù)雜度比較高。RBP和NW-RBP的置信傳播調(diào)度方式如圖4所示。

圖4 RBP（左）和NW-RBP（右）算法節(jié)點(diǎn)間消息傳播的過程

為比較以上三種調(diào)度方式的效果，采用（1944,972）碼在AWGN信道下進(jìn)行以上幾種置信調(diào)度機(jī)制仿真，仿真結(jié)果如圖5所示。當(dāng)?shù)螖?shù)較小的時(shí)候，RBP性能要顯著優(yōu)于其他三種算法。但隨著迭代次數(shù)繼續(xù)增大，RBP的FER曲線開始變得平緩，不再隨著迭代次數(shù)的增加而降低，曲線出現(xiàn)了誤碼平層現(xiàn)象。尤其，在RBP迭代4次時(shí)候的FER與LBP在迭代次13的時(shí)候的FER相同，而且兩種算法的FER曲線在迭代次數(shù)19次的時(shí)候相交，這說明了在RBP譯碼過程中，雖然迭代次數(shù)增大，仍然有些錯(cuò)誤無法正確譯出。當(dāng)?shù)螖?shù)較小，NW-RBP的性能并不如RBP，然后在迭代次數(shù)為10次的時(shí)候，RBP的性能曲線出現(xiàn)了瓶頸，而NW-RBP的FER繼續(xù)得到改善而降低，這說明NW-RBP能較好得克服錯(cuò)誤平臺(tái)現(xiàn)象而使得譯碼的性能更好。此外，NW-RBP在迭代15次的時(shí)候的FER與LBP在迭代50次的時(shí)候的FER相同，且在迭代10次之后，NW-RBP相比RBP和LBP分別有1dB和0.8dB的FER增益，這說明NW-RBP能有效克服誤碼平層現(xiàn)象。

圖5 信噪比Eb/N0=1.75dB時(shí)，（1944,972）碼的FER隨迭代次數(shù)變化的情況

4. 改進(jìn)措施展望

以上介紹的串行、動(dòng)態(tài)調(diào)度置信傳播，雖然取得了快速收斂的效果。然而，在迭代次數(shù)較多的情況下，現(xiàn)有的一些改進(jìn)方案并不能較大提高NW-RBP的誤碼率。由香濃極限所得，當(dāng)LDPC碼碼長足夠長時(shí)，迭代置信譯碼算法可以無限接近香濃極限。由此可見，LDPC碼中的短環(huán)結(jié)構(gòu)的存在，是導(dǎo)致譯碼算法無法收斂的重要原因?；谶@一點(diǎn)，本文提出兩點(diǎn)可行性改進(jìn)措施：第一，統(tǒng)計(jì)LDPC碼Tanner圖中的短環(huán)分布情況。短環(huán)分布不僅要計(jì)算出短環(huán)的數(shù)量，還要統(tǒng)計(jì)出具體哪些變量節(jié)點(diǎn)參與組成短環(huán)，即短環(huán)結(jié)構(gòu)。第二，在完成短環(huán)分布統(tǒng)計(jì)的基礎(chǔ)上，分析短環(huán)對置信迭代算法的影響，研究殘差值隨迭代次數(shù)增加的變化趨勢，從以下幾個(gè)方面嘗試設(shè)計(jì)新的快速收斂調(diào)度方法：（1）賦予參與組成較多短環(huán)的變量節(jié)點(diǎn)優(yōu)先調(diào)度權(quán)；（2）與比特反轉(zhuǎn)算法相結(jié)合，當(dāng)置信算法無法收斂時(shí)，反轉(zhuǎn)短環(huán)中的某些變量節(jié)點(diǎn)的符號(hào)，從而達(dá)到提高收斂速度和譯碼正確率的目的；（3）參考RBP算法，首先依據(jù)參與短環(huán)數(shù)對變量節(jié)點(diǎn)進(jìn)行歸類，對參與短環(huán)較多者并且殘差最大者優(yōu)先調(diào)度。以上幾種方法的有效性，將在今后的研究中予以驗(yàn)證。

5. 總結(jié)

本文對低密度奇偶校驗(yàn)碼的三種置信傳播譯碼時(shí)序進(jìn)行詳細(xì)介紹。這三種譯碼時(shí)序分別是洪泛譯碼、串行譯碼、動(dòng)態(tài)譯碼。通過展示LDPC碼二分圖中信息的傳遞順序和各譯碼時(shí)序的仿真案例，對各譯碼時(shí)序的譯碼原理、收斂速度、譯碼誤碼率等進(jìn)行闡述和比較，并提出一些可行性改進(jìn)措施，以期望提高LDPC碼的譯碼性能。

[1]R.Gallager.Low density parity check codes.IET Transactions on Informaiton Theory.1962.

[2]F.Kschischang,B.J.R.Frey,and H.A.Loeliger.Factor graphs and the sum-product algorithm. IET Transactions on Informaiton Theory. 2001.

[3]A.I.V.Casado,M.Griot,and R.D.Wesel.LDPC decoders with informed dynamic scheduling.IEEE Transactions on Communications. 2010.

結(jié)束語

通過對微控制器的嵌入式低功耗應(yīng)用方面相關(guān)內(nèi)容的探討，可知嵌入式系統(tǒng)低功耗設(shè)計(jì)目標(biāo)的實(shí)現(xiàn)，需要加強(qiáng)微控制器的合理運(yùn)用。在具體的設(shè)計(jì)過程中，應(yīng)提高對微控制器結(jié)構(gòu)特點(diǎn)的全面認(rèn)識(shí)，確保其在嵌入式低功耗應(yīng)用中能夠達(dá)到預(yù)期的效果，并在可靠的低功耗模式支持下，提高相關(guān)資源利用效率的同時(shí)完善系統(tǒng)的服務(wù)功能，實(shí)現(xiàn)對系統(tǒng)功耗的有效控制。

參考文獻(xiàn)

[1]邵貝貝.單片機(jī)嵌入式應(yīng)用的在線開發(fā)方法 .清華大學(xué)出版社,2004.

[2]林東寧,張強(qiáng).墨盒芯片,實(shí)用新型專利,專利號(hào)ZL 200620060165.9.

[3]劉長龍,嚴(yán)新文.嵌入式低功耗8位微控制器的設(shè)計(jì)[J].天津大學(xué)學(xué)報(bào),2010,(12).

[4]李多,葉樺.一種基于STM32的嵌入式低功耗無線手持控制器設(shè)計(jì)[J].電子設(shè)計(jì)工程,2014,(18).

[5]劉偉偉.嵌入式系統(tǒng)低功耗技術(shù)的研究和應(yīng)用[D].鄭州大學(xué),2012,(05).

項(xiàng)目資助：江蘇省級(jí)大學(xué)生實(shí)踐創(chuàng)新訓(xùn)練計(jì)劃項(xiàng)目（201610300049），江蘇高校品牌專業(yè)建設(shè)工程資助項(xiàng)目，江蘇高校優(yōu)勢學(xué)科Ⅱ期建設(shè)工程資助項(xiàng)目。