LDPC碼在 AWGN信道中的性能研究

邵麗娜,史 萍,駱 超

(中國傳媒大學(xué) 信息工程學(xué)院,北京 100024)

1 引言

伴隨著通信技術(shù)的飛速發(fā)展以及各種傳輸方式對可靠性要求的不斷提高,差錯控制編碼技術(shù)作為抗干擾技術(shù)的一種重要手段,在數(shù)字通信領(lǐng)域和數(shù)字傳輸系統(tǒng)中顯示出越來越重要的作用。自從Shannon提出信道編碼定理[1]以來,編碼研究者們一直致力于尋找性能上盡可能接近 Shannon極限而復(fù)雜度又較低的信道編碼方案?？上У氖?從上世紀(jì) 50年代以來研究的傳統(tǒng)糾錯碼都不是實(shí)用好碼[2]。1993年,Berrou等人提出的 Turbo碼[3]通過采用軟輸出迭代譯碼來逼近最大似然譯碼,取得了超乎尋常的優(yōu)異性能,被看作信道編碼理論研究的重要里程碑。在對 Turbo碼的基于圖模型的編譯碼和迭代譯碼研究過程中,David J.C.Mackay,M.Neal和 N.Wiberg等人發(fā)現(xiàn)[4],早在 1962年 Robert G.Gallager提出的低密度奇偶校驗(yàn)碼[5](Low Density Parity Check Codes,LDPC Codes)也是一種實(shí)用好碼,其在 AWGN信道下的性能接近 Shannon極限且實(shí)現(xiàn)復(fù)雜度低。1996年 Mackay教授等人重新發(fā)現(xiàn)了 LDPC碼后,便轟動了編碼界,成為自信息論提出以來最重大的研究進(jìn)展之一。理論研究表明:1/2碼率的 LDPC碼在 BPSK調(diào)制下的性能距信息論中的 Shannon限僅差 0.0045dB[6],是目前距 Shannon限最近的糾錯碼。LDPC碼與高效調(diào)制相結(jié)合,能夠滿足下一代移動通信高速數(shù)據(jù)大容量傳輸?shù)钠惹幸?它的迭代譯碼思想現(xiàn)已廣泛用于通信技術(shù)的很多領(lǐng)域,為實(shí)現(xiàn)迭代信道估計(jì)、迭代均衡以及信號檢測提供了新的思路。

2 LDPC碼編碼原理

對 LDPC碼編碼方法的研究主要分兩步進(jìn)行,首先是奇偶校驗(yàn)矩陣的構(gòu)造,然后是基于奇偶校驗(yàn)矩陣的編碼算法。

2.1 碼字構(gòu)造

LDPC碼校驗(yàn)矩陣的構(gòu)造方法可分為兩大類:一類是隨機(jī)構(gòu)造法,其校驗(yàn)矩陣不規(guī)則,雖然糾錯性能好,但由于校驗(yàn)矩陣的隨機(jī)性使得編碼復(fù)雜度高。下文中介紹的Gallager構(gòu)造法和PEG構(gòu)造法屬于此類;另一類是結(jié)構(gòu)化構(gòu)造法,它由幾何、代數(shù)和組合設(shè)計(jì)等方法構(gòu)造,其校驗(yàn)矩陣具有某種特殊的結(jié)構(gòu),因而其硬件實(shí)現(xiàn)比隨機(jī)結(jié)構(gòu)的碼容易,而且可以通過設(shè)計(jì) girth較大的碼,使其性能達(dá)到隨機(jī)校驗(yàn)矩陣生成的碼字,下文中介紹的準(zhǔn)循環(huán)構(gòu)造法即屬于此類。

2.1.1 Gallager構(gòu)造法

Gallager構(gòu)造的 LDPC碼[7]具有如下特點(diǎn):校驗(yàn)矩陣 H的列重和行重固定,且列重 dv≥3;H中的元素隨機(jī)生成,行重和列重均勻分布;矩陣按行劃分成dv個水平子矩陣,子矩陣中每列只有一個“1”,第一個子矩陣中第 i行只有從第(i-1)dc+1列到第 idc列的元素為“1”,其余子矩陣是第一個子矩陣的隨機(jī)列變換。該類碼的碼集合是由H中下面dv-1個子矩陣的列等概率隨機(jī)分配所得碼的集合。Gallager方法構(gòu)造的碼字對于給定列重 dv,對足夠低的信噪比和足夠長的碼長,最佳譯碼器的錯誤概率隨碼長指數(shù)下降;碼的最小距離隨碼長線性增加。

此種方法下,校驗(yàn)矩陣構(gòu)造簡單,而且校驗(yàn)矩陣的行重列重容易控制,只需先根據(jù)碼長和行重構(gòu)造一個子矩陣,校驗(yàn)矩陣就可以利用此子矩陣得到。但是由于是隨機(jī)構(gòu)造的原因,在碼長較短時 Tanner圖中經(jīng)常容易出現(xiàn)短環(huán),影響了碼的性能,但是隨著碼長的增加,短環(huán)出現(xiàn)的概率會變小。

2.1.2 PEG構(gòu)造法

Xiao-Yu Hu提出了一種使得變量節(jié)點(diǎn)的局部圍長最大的構(gòu)造方法,即 PEG(progressive edge grown)方法[8],PEG方法構(gòu)造的中、短碼長的 LDPC碼是當(dāng)前所知具有相同參數(shù)的最好的低密度奇偶校驗(yàn)碼之一[8]。

PEG算法是構(gòu)造具有大環(huán) Tanner圖的一種次優(yōu)方法,算法在圖上每增加節(jié)點(diǎn)的一條邊都使得該節(jié)點(diǎn)局部環(huán)長最大。假如已構(gòu)造圖 G′中 j個節(jié)點(diǎn)的邊集合為 Ev0∪Ev1∪ …Evj-1,g′是圖 G′的圍長,g′=min{gv0,gv1,…ggvj-1},若在圖中增加 Evj,使新得到的圖的最小環(huán)小于 g′,那么這個新產(chǎn)生的最小環(huán)必須通過點(diǎn) Vj,構(gòu)造最大圍長 Tanner圖就是優(yōu)化Evj中dvj條邊,使該節(jié)點(diǎn)的局部環(huán)長最大。

由于短環(huán)的存在對譯碼性能存在很大的影響,利用 PEG方法構(gòu)造的校驗(yàn)矩陣使得最小環(huán)長最大,因而一般來說,利用 PEG方法構(gòu)造的校驗(yàn)矩陣比利用 Gallager等方法構(gòu)造的校驗(yàn)矩陣性能好。但此種方法要對邊的分布進(jìn)行優(yōu)化,其復(fù)雜度隨之增加。

2.1.3 準(zhǔn)循環(huán)構(gòu)造方法

準(zhǔn)循環(huán)的 LDPC碼的校驗(yàn)矩陣 H由一系列的 m×m小循環(huán)方陣組成[9][10],這些小循環(huán)方陣可以是置換矩陣或是基于有限幾何的矩陣等。

式(1)中 p代表 m×m單位陣,上標(biāo) a表示平移的數(shù)。選用不同的 a可形成不同的編碼方法。由于準(zhǔn)循環(huán)碼的準(zhǔn)循環(huán)特性,可以得到系統(tǒng)形式又具有準(zhǔn)循環(huán)特性的生成矩陣,只需要采用移位寄存器即可實(shí)現(xiàn)輸入碼字和生成矩陣的相乘。

準(zhǔn)循環(huán) LDPC碼具有循環(huán)碼的一些特性,也可以采用一維寄存器完成編碼,硬件實(shí)現(xiàn)復(fù)雜度低。在標(biāo)準(zhǔn) CCSDS131.1-0-2(EX-PERIMENTAL SPECIFICATION)[11]中針對近地業(yè)務(wù)和深空業(yè)務(wù)提出的 LDPC碼方案都是準(zhǔn)循環(huán) LDPC碼,由此也可見其良好的應(yīng)用前景。

2.2 編碼算法

在傳統(tǒng)的編碼過程中,一般生成矩陣是必需的。然而針對 LDPC編碼,盡管碼字的奇偶校驗(yàn)矩陣是非常稀疏的,但其生成矩陣的稀疏性卻無法保證,這樣就可能會導(dǎo)致編碼的運(yùn)算和存儲復(fù)雜性大大增加,不具有實(shí)用性,因此出現(xiàn)了一些新的編碼方法,不再產(chǎn)生生成矩陣,直接利用校驗(yàn)矩陣進(jìn)行編碼,以期獲得較低的編碼復(fù)雜度。下面就主要介紹一種使用比較廣泛的 RU算法。

Richardson和 Urbanke在文獻(xiàn)[12]中提出的RU算法通過行列置換將一般的低密度奇偶校驗(yàn)矩陣化為一個近似下三角矩陣(圖 1),可以使編碼復(fù)雜度從高斯消元法的 o(m2)降為 o(n+g2),其中 g為近似下三角矩陣與下三角矩陣的差距,并且在最惡劣的情況下,它只是與碼長的一小部分成比例。

圖 1 奇偶校驗(yàn)矩陣的近似下三角形式

由于原矩陣 H非常稀疏,而且在矩陣變換中只有行列交換,因此變換后得到的近似下三角矩陣仍然是稀疏矩陣。長度為 k的信源向量 s被編碼成一個碼字向量 x=(s,p1,p2),其中 s代表系統(tǒng)比特。p1與 p2代表校驗(yàn)比特,長度分別為 g和 m-g。通過式(2)可以分別遞推出兩部分校驗(yàn)比特[12]。

這六個分塊陣是通過對原有稀疏矩陣的行列做重排獲得的,所以這些分塊陣依然滿足稀疏性,通過進(jìn)一步的分析即可得到和的運(yùn)算量分別為和。由此可以看出,要進(jìn)一步簡化 LDPC碼的編碼運(yùn)算量,需要在重排校驗(yàn)矩陣的時候使得盡量小,運(yùn)算量就可以控制在線性復(fù)雜度附近。

3 LDPC碼譯碼原理

LDPC碼具有良好性能的重要原因之一是:LDPC碼采用了基于置信傳播的迭代譯碼算法,這是一種迭代概率譯碼方法,是 LDPC碼與傳統(tǒng)糾錯碼的重要區(qū)別所在。另外,Gallager在 1962年的文章中還提出了一種基于置信傳播的硬判決翻轉(zhuǎn)譯碼算法。下面分別介紹基于置信傳播的迭代概率譯碼方法和位翻轉(zhuǎn)譯碼方法。

3.1 BP譯碼

基于因子圖的置信傳播譯碼算法(BP Algorithm)是 LDPC碼常用的譯碼算法。對于二元LDPC碼的譯碼,信道模型采用二元輸入連續(xù)輸出平穩(wěn)無記憶 AWGN信道模型,假設(shè)采用 BPSK調(diào)制方式,噪聲服從高斯分布 N(0,)。設(shè)一個 N長LDPC碼的校驗(yàn)矩陣 H=(Hij)M×N,碼字 X={…xN}表示為一組信息節(jié)點(diǎn),Z={z1,z2,…,zM}表示為一組校驗(yàn)節(jié)點(diǎn),觀測的信道信息給出關(guān)于發(fā)送碼字的初始化信息向量 ?a={…,}。用 M(j)表示與變量節(jié)點(diǎn) xj相連的所有校驗(yàn)節(jié)點(diǎn)所構(gòu)成的集合,相對應(yīng)于校驗(yàn)矩陣 H中第 j列為 1的位置,用 N(i)表示與校驗(yàn)節(jié)點(diǎn) zi相連的所有變量節(jié)點(diǎn)構(gòu)成的集合,相對應(yīng)于校驗(yàn)矩陣 H中第 i行為 1的位置。M(j)i表示 m(j)中除去其中的校驗(yàn)節(jié)點(diǎn) zi后剩下的集合,N(i)j表示 N(i)中除去其中的變量節(jié)點(diǎn) xj后剩下的集合。校驗(yàn)節(jié)點(diǎn) zi向變量節(jié)點(diǎn) xj傳遞的校驗(yàn)信息定義為變量節(jié)點(diǎn) xj向校驗(yàn)節(jié)點(diǎn) zi傳遞的變量消息定義為

圖 2顯示了校驗(yàn)信息和變量消息的傳遞方向,基于因子圖模型和和積算法,置信傳播算法執(zhí)行的操作如下:

2.迭代消息傳遞和修正;

(1)各因子節(jié)點(diǎn) fj向其父節(jié)點(diǎn) xj傳遞消息校驗(yàn)節(jié)點(diǎn) zi向其所有父節(jié)點(diǎn) xj分別傳遞消息,各節(jié)點(diǎn) xj根據(jù)接收消息修正

(2)各變量節(jié)點(diǎn) xj向其所有子節(jié)點(diǎn) zi傳遞已更新的消息各節(jié)點(diǎn) zi根據(jù)接收消息修正

圖 2 置信傳播算法示意圖

4.迭代或終止:計(jì)算 xHT是否為全零向量。如果是,則本次譯碼結(jié)束;若不是,判斷是否達(dá)到最大迭代次數(shù)。如果已達(dá)到最大迭代次數(shù),結(jié)束譯碼,以最后的結(jié)果作為輸出;若沒有達(dá)到最大迭代次數(shù),則進(jìn)入下一次迭代,直到滿足 xHT為零為止。

3.2 硬判決位翻轉(zhuǎn)譯碼

比特翻轉(zhuǎn)譯碼方法由 Gallager教授在其論文中首先提出,這種算法僅適用于 BSC信道,可看成是置信傳播算法的簡化形式。設(shè)碼字向量經(jīng)過 BSC信道接收的硬判決值為 z,s為伴隨子向量,比特翻轉(zhuǎn)(BF)算法可簡單描述為:

1.首先計(jì)算方程 s=zHT,統(tǒng)計(jì)每位接收值 yi不滿足校驗(yàn)方程的個數(shù)。

2.找出不滿足校驗(yàn)方程的個數(shù)最多的 zj,如不滿足的個數(shù)大于某設(shè)定值,將其翻轉(zhuǎn),得到新的向量 z′。

3.判決條件:由向量 z′代替 z計(jì)算方程 s=zHT,如 s=0則正確譯碼輸出,否則重復(fù)第 1-3步。反復(fù)迭代,直到迭代至最大迭代次數(shù)。

由于校驗(yàn)矩陣為稀疏矩陣,而且一般為隨機(jī)構(gòu)成,所以參與每個校驗(yàn)方程的比特很少,且這些比特在碼字上分布很分散,那么任意一個校驗(yàn)方程所含的比特要么無錯,要么以很高的概率只發(fā)生一個比特的錯誤,因此 BF算法就可以有效的進(jìn)行糾錯。

4 LDPC碼在 AWGN信道中的仿真實(shí)驗(yàn)

4.1 仿真模型

實(shí)驗(yàn)采用二進(jìn)制的偽隨機(jī)序列作為輸入信號,幀長為 4608比特。LDPC編碼中的校驗(yàn)矩陣采用CMMB標(biāo)準(zhǔn)[13]中的規(guī)則校驗(yàn)矩陣 H(9216,3,6),碼長為 9216,行重為固定值 6,列重為固定值 3。經(jīng)過LDPC編碼后的信號再進(jìn)行 BPSK調(diào)制,然后進(jìn)入高斯白噪聲信道。信道的輸出信號首先進(jìn)行 BPSK解調(diào),然后進(jìn)行 LDPC信道譯碼,采用和積譯碼算法,譯碼后的結(jié)果進(jìn)行判決并統(tǒng)計(jì)誤碼率。圖 3為實(shí)驗(yàn)采用的仿真模型。

4.2 仿真結(jié)果

4.2.1 LDPC碼和 Turbo碼在 AWGN信道中的性能比較

圖 4給出了 LDPC碼和 Turbo碼在 AWGN信道中的仿真性能曲線圖。實(shí)驗(yàn)在 CPU為 Intel core2 E7300,主頻 2.66GHz,內(nèi)存為 2.00GB的計(jì)算機(jī)上用 C語言編程完成,其中 LDPC碼的校驗(yàn)矩陣采用CMMB標(biāo)準(zhǔn)中的規(guī)則校驗(yàn)矩陣 H(9216,3,6),碼率1/2,譯碼采用 BP譯碼算法;Turbo碼的碼率為 1/2,譯碼算法采用 MAP譯碼算法[14]。

圖 3 LDPC碼在AWGN信道中的信真模型

由仿真結(jié)果我們看到在信噪比較低的時候,Turbo碼的性能比 LDPC碼的性能好很多,可是當(dāng)信噪比增大后,尤其是在信噪比達(dá)到 1.5dB以后,Turbo碼的性能呈現(xiàn)錯誤平層,出現(xiàn)無法糾正的錯誤,而 LDPC碼在信噪比到 1.5dB以后誤碼率下降非?？?從仿真 10000次的時候來看,在信噪比達(dá)到1.6dB時幾乎已經(jīng)完全糾正錯誤,表現(xiàn)了優(yōu)良的糾錯性能;另一方面,在本實(shí)驗(yàn)采用 BP基本譯碼算法的情況下,LDPC碼的譯碼速度遠(yuǎn)遠(yuǎn)大于 Turbo碼的譯碼速度。由仿真結(jié)果我們看到當(dāng)采用 LDPC碼作為信道編碼方案時,譯碼采用 10次迭代仿真的時間大概只是 Turbo碼仿真時間的 1/2,即使是 LDPC碼譯碼采用 30次迭代的仿真時間也要比 Turbo碼作為信道編碼譯碼迭代 10次的時間短很多,這反映了LDPC的譯碼速率比 Turbo碼高,譯碼的復(fù)雜度低于Turbo碼的譯碼復(fù)雜度。

圖 4 LDPC碼與 Turbo碼在 AWGN信道中的性能曲線圖

4.2.2 譯碼迭代次數(shù)對 LDPC碼性能的影響。

圖 5給出了當(dāng)譯碼迭代次數(shù)不同時,同樣的LDPC碼字在 AWGN信道中的性能曲線。由仿真結(jié)果我們清楚地看到隨著迭代次數(shù)的增加,曲線的趨勢也表現(xiàn)出越來越好的性能;同時,隨著迭代次數(shù)的增加,從仿真所需要的時間來看,譯碼所需的時間也在增加?？梢钥闯鐾ㄟ^迭代次數(shù)來提高 LDPC編碼的誤碼性能是以譯碼速率為代價的,所以在選擇適合的迭代次數(shù)的時候我們要綜合實(shí)際需要尋找一個性能和速率的平衡點(diǎn)。

5 結(jié)論

LDPC碼這種新穎的信道糾錯編碼技術(shù),繼Turbo碼之后向逼近 Shannon限的目標(biāo)又跨進(jìn)了一步。從本文的實(shí)驗(yàn)當(dāng)中我們可以總結(jié)出以下結(jié)論:在信噪比較大時,LDPC碼的性能要優(yōu)于 Turbo碼,并且其譯碼速率要高于 Turbo碼;譯碼迭代次數(shù)是影響 LDPC碼譯碼性能的一個重要因素,增加譯碼迭代次數(shù)可以提高譯碼性能,但同時復(fù)雜度消耗也在增大,所以采用 LDPC碼作為信道編碼的時候我們要綜合實(shí)際情況選擇合適的譯碼迭代次數(shù)。

圖 5 不同迭代次數(shù)的LDPC碼性能曲線

[1] Shannon C E.A Mathematical Theory of Communication[J].Bell System Tech J,1950,29:147-160.

[2] R udiger Urbanke.Modern Coding Thoery[M].Cambridge:Cambridge University Press,2008.

[3] Berrou C,Glavieux A,Thitimajshima P.Near Shannon limit error—correcting coding and decoding:turbo-codes[C].In Proc of ICC,Geneva,1993,1064-1070.

[4] DJ CMackay.Good Error-Correcting Codes Based on Very Sparse Matrices[J].IEEETrans info Theory,1999,45(2):399-431.

[5] RG Gallager.Low-Density Parity-Check Codes[J].IRE Transactions on Information Theory,1962,8:21-28.

[6] Sae-Young Chung,G.David Forney,Thomas J.Richardson.On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit[J].IEEE Comm Letters,2001,5(2):58-60.

[7] Gallager R G.Low-Density Parity Check Codes[M].Cambridge,M A:MI T Press,1963.

[8] Xiao-Yu Hu,Evangelos Eleftheriou,Dieter-Michael Arnold.Regular and irregular progressive edge-growth Tanner graphs[C].Global Telecommunications Conference,2001:995-1001.

[9] Tanner R M,Sridharan D,etal.LDPC Block and Convolutional Codes Based on Circulant Matrices[J].IEEE Trans Inform Theory,2004,50(12):2966-2984.

[10] Fossorier M.Quasi-Cyclic Low-Density Parity-Check Codes From Circulant Permutation Matrices[J].IEEE Transactions on Information Theory,2004,50(8).

[11] CCSDS131.1-0-2.LOW density parity check codes for use in near–Earth and deep space application[S].CCSDS,2007.

[12] Richardson T,Urbanke R L.Efficient Encoding of Low-Density Parity-check Codes[J].IEEE Transactions on Information Thoery,2001,47(2):638-656.

[13] GYT220.1-2006,移動多媒體廣播 第 1部分:廣播信道幀結(jié)構(gòu)、信道編碼和調(diào)制,中華人民共和國廣播電影電視行業(yè)標(biāo)準(zhǔn)[S].2006.

[14] 侯銘睿,史萍.非二進(jìn)制 RS-Turbo級聯(lián)碼性能研究[J].中國傳媒大學(xué)學(xué)報(自然科學(xué)版),2008,15(1):64– 68.