邵麗娜,史 萍,駱 超

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

1 引言

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

2 LDPC碼編碼原理

對 LDPC碼編碼方法的研究主要分兩步進行,首先是奇偶校驗矩陣的構造,然后是基于奇偶校驗矩陣的編碼算法。

2.1 碼字構造

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

2.1.1 Gallager構造法

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

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

2.1.2 PEG構造法

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

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

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

2.1.3 準循環(huán)構造方法

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

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

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

2.2 編碼算法

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

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

圖 1 奇偶校驗矩陣的近似下三角形式

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

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

3 LDPC碼譯碼原理

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

3.1 BP譯碼

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

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

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

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

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

圖 2 置信傳播算法示意圖

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

3.2 硬判決位翻轉譯碼

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

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

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

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

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

4 LDPC碼在 AWGN信道中的仿真實驗

4.1 仿真模型

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

4.2 仿真結果

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

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

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

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

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

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

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

5 結論

LDPC碼這種新穎的信道糾錯編碼技術,繼Turbo碼之后向逼近 Shannon限的目標又跨進了一步。從本文的實驗當中我們可以總結出以下結論:在信噪比較大時,LDPC碼的性能要優(yōu)于 Turbo碼,并且其譯碼速率要高于 Turbo碼;譯碼迭代次數(shù)是影響 LDPC碼譯碼性能的一個重要因素,增加譯碼迭代次數(shù)可以提高譯碼性能,但同時復雜度消耗也在增大,所以采用 LDPC碼作為信道編碼的時候我們要綜合實際情況選擇合適的譯碼迭代次數(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部分:廣播信道幀結構、信道編碼和調制,中華人民共和國廣播電影電視行業(yè)標準[S].2006.

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