熊 磊,姚冬萍,陳 霞

(北京交通大學軌道交通控制與安全國家重點實驗室,北京100044)

1962年Gallager提出的低密度奇偶校驗(Lowdensity Parity-Check,LDPC)碼是一種具有逼近Shannon容量限和相對較低譯碼復雜度的優(yōu)異信道編碼,近年來得到了廣泛關注[1-2].Chung S.Y.等人采用離散密度進化算法搜索LDPC碼的最佳次數(shù)分布對,在采用置信傳播(Belief Propagation,BP)譯碼算法下獲得了距Shannon容量限僅0.004 5 dB的優(yōu)異性能[3],然而這一性能是在假定碼長無限長且Tanner圖中不存在環(huán)的情況下得出的.當存在環(huán)時,譯碼時將發(fā)生信息的自反饋,破壞了信息傳播的獨立性,導致譯碼性能的降低.最短環(huán)長(即圍長)越小,短環(huán)的數(shù)量越多,碼字性能的惡化就越明顯.構造具有較大圍長和較少短環(huán)的碼字是當前LDPC碼研究的重要問題之一.

Kim J.L.等人提出了不包含環(huán)長為4的環(huán)(4線循環(huán))LDPC碼的構造方法[4];Yu Kou等人提出的有限幾何構造法,可以按圍長要求進行碼字的構造[5];Campello J.和Modha D.S.提出的比特填充(Bit Filling,BF)構造方法,在給定的圍長約束條件下,向校驗矩陣逐個添加‘1'元素,可以獲得具有較大圍長的碼字,但構造復雜度與碼長的3次方呈正比[6-7].Hu X.Y.提出的漸進邊增長(Progressive Edge-Grow th,PEG)構造法由無環(huán)的Tanner圖開始,逐條增加邊,每次增加時都使得新增邊所形成的環(huán)盡可能地長,從而以較低的復雜度(與碼長的平方呈正比)實現(xiàn)了較大的圍長,被普遍認為是當前性能最好的 LDPC碼構造方法[8-9].Lin Yi-Kai和 Wei Zhan等人將PEG構造法應用于結構化LDPC碼的構造也獲得極佳的性能[10-11].Dejan Vukobratovi等人提出了優(yōu)化環(huán)的外信息度[12],Richter G.則提出停止集(Stopping Sets)的概念來改善PEG構造法的性能[13].

針對現(xiàn)有PEG構造法忽視最短環(huán)數(shù)量所造成的性能惡化,本文作者提出了環(huán)多項式的概念,并在此基礎上提出了基于環(huán)多項式的漸進邊增長(Progressive Edge Growth based on Polynomial of Cycle,PEGPC)構造法.該構造法借助環(huán)多項式,優(yōu)化了新增邊的選擇,不僅可以實現(xiàn)較大的圍長,而且有效地減少了最短環(huán)的數(shù)量,改善了LDPC碼的性能.

1 樹型圖與環(huán)多項式

如圖1所示,假定PEG構造法要為比特節(jié)點si增加一條邊,則以其為頂點,將Tanner圖逐層展開,直到樹型圖包含的校驗節(jié)點數(shù)達到最大為止.假定某校驗節(jié)點cj首次出現(xiàn)于樹型圖中的第l層,如果在si和cj之間增加一條邊,該新增邊所形成的最短環(huán)長為2(l+1).顯然,PEG構造法盡可能選擇處于樹型圖底部(即 l值較大)的校驗節(jié)點.由于新增邊所形成的環(huán)相對較長,從而盡力而為(Best-Effort)地避免了短環(huán)的出現(xiàn),以較低的復雜度實現(xiàn)較大的圍長.然而PEG構造法沒有考慮減少短環(huán)的數(shù)量.為了更全面地表征新增邊對Tanner圖的影響,本文提出了環(huán)多項式的概念.

如圖1所示,假定樹型圖中某校驗節(jié)點cv是由比特節(jié)點su擴展而來,則稱節(jié)點su為cv的父節(jié)點,而cv則為su的子節(jié)點.父節(jié)點與子節(jié)點是相對的,且一個節(jié)點的父節(jié)點和子節(jié)點可能不只一個.

圖1 樹型Tanner圖Fig.1 Tree-like Tanner graph

節(jié)點的環(huán)多項式的計算方法如下:①令頂點的環(huán)多項式為1,如圖1中,f(si)=1;②子節(jié)點的環(huán)多項式為其父節(jié)點環(huán)多項式的冪次加1,即乘以 x ,如cv的多項式f(cv)=xf(su);當父節(jié)點不唯一時,則先對其各父節(jié)點的環(huán)多項式求和,然后冪次再加1;③未在樹型圖中出現(xiàn)節(jié)點的環(huán)多項式為0.

由于Tanner圖是二分圖,所以校驗節(jié)點的環(huán)多項式的冪次必為奇數(shù),而比特節(jié)點的環(huán)多項式的冪次則必為偶數(shù).假設校驗節(jié)點cj的環(huán)多項式為

式中:f(cj)表示新增邊(si,cj)將給整個Tanner圖添加hk條長度為2k的環(huán);hk+1條長度為2(k+1)的環(huán),依此類推.

校驗節(jié)點環(huán)多項式的冪次表示新增邊所形成的環(huán)長,而系數(shù)則為所對應環(huán)長的數(shù)量.如果 cj的多項式為0,則表明cj未曾在樹型圖中出現(xiàn),那么增加邊(si,cj)不會導致任何環(huán)長小于2(l+2)環(huán),其中l(wèi)為樹型圖擴展的最大層數(shù).

需要注意的是,cj的環(huán)多項式反映的是由于增加邊(si,cj)而形成的環(huán),且只有校驗節(jié)點的環(huán)多項式才具有實際的意義.

環(huán)多項式以多項式的形式實現(xiàn)了對環(huán)的長度和數(shù)量精確的數(shù)學刻畫,可用于碼字分析和構造等領域.

2 PEGPC構造法

PEGPC構造法采用比較各校驗節(jié)點的環(huán)多項式進行新增邊的選擇,比較過程包括如下兩步:

步驟1:比較各校驗節(jié)點的多項式的最低冪次,選擇最低冪次最大的校驗節(jié)點.最低冪次越大,則表明選擇該校驗節(jié)點所形成的最短環(huán)的環(huán)長也就越大.當結果不唯一時,則繼續(xù)進行第2步.

步驟2:比較最低冪次的系數(shù)值,選取系數(shù)值較小的校驗節(jié)點.冪次的系數(shù)值越小,選擇該節(jié)點所形成最短環(huán)也就越少.如果選擇結果仍不唯一,則回到第1步比較冪次較高的項,也可以從中隨機選擇一個.

在實際構造中,為了簡化比較過程,通常給 x賦一個值(如令x=0.1),將環(huán)多項式簡化為一個代數(shù)值,從而將比較環(huán)多項式的冪次和系數(shù)值簡化為比較環(huán)多項式的值,將兩步比較大大簡化一步比較.與PEG構造法相比,簡化后的PEGPC構造法的復雜度沒有明顯增加,而且只要滿足0＜x?1,其構造性能基本不會發(fā)生惡化.

假定要構造一個碼長為N,包含m個校驗式的LDPC碼,PEGPC構造法步驟如下所示:

對每一個比特節(jié)點si,

1)添加與si相連的第1條邊,選擇當前節(jié)點度最小校驗節(jié)點的cj,添加第1條邊,即.

2)初始化:

①比特節(jié)點環(huán)多項式初始化

②校驗節(jié)點環(huán)多項式初始化

3)如圖1所示以si為頂點擴展樹型圖,每擴展一層對各節(jié)點的環(huán)多項式進行以下更新:

①校驗節(jié)點環(huán)多項式更新,若校驗節(jié)點cv由比特節(jié)點su擴展而來,則

②比特節(jié)點環(huán)多項式更新,若比特節(jié)點sq由校驗節(jié)點cp擴展而來

4)新增邊,選擇環(huán)多項式的值最小的校驗節(jié)點cj,即

其中 Vc為可選校驗節(jié)點的集合.

為si增加第k條邊,即Eksi=(si,cj).

返回步驟2),繼續(xù)為 si增加邊,直至與 si相連全部邊增加完畢.

3 仿真結果

本節(jié)在高斯白噪聲(AWGN)信道下,對PEGPC的性能進行仿真.仿真采用(N=504,R=1/2,dv=3,dc=6)正規(guī) LDPC碼;在 PEGPC構造法中,令 x=0.1;采用BPSK調(diào)制,歸一化BP譯碼算法,歸一化常數(shù)α=1.15,最大迭代譯碼次數(shù)設定為100,在每個信噪比點至少收集50個錯誤碼字.

圖2 本地圍長分布圖Fig.2 Girth histograms of PEGPC code,PEG code and a random code

圖2給出了PEGPC碼、PEG碼和刪除了4線循環(huán)的隨機碼的本地圍長(即各比特所參與的最短環(huán)長)分布圖.隨機碼的圍長僅為6,本地圍長均值為6.43,而PEGPC和PEG碼的圍長均達到了8,本地圍長均值則分別為8.079和8.004(見表1).與隨機碼相比,PEGPC和PEG碼的圍長和本地圍長均值都有了明顯提高.相比于PEG碼,PEGPC碼的圍長和本地圍長均值雖然沒有明顯提高,但最短環(huán)(即長度為8的環(huán))的數(shù)量卻有了明顯的下降,如圖3所示.PEG碼共包含844個最短環(huán),而PEGPC碼則減少為398個,下降約52.8%.

表1 圍長、本地圍長和最短環(huán)數(shù)量比較Tab.1 Comparison of girth,local girth and number of shortest cycles

圖3 最短環(huán)數(shù)量分布圖Fig.3 Histograms of number of the shortest cycles

圖4為PEGPC碼、PEG碼和隨機碼的誤比特率(Bit Error Rate,BER)曲線對比圖.隨著的增大,PEGPC碼在性能上的優(yōu)勢逐漸明顯,在=3.5 dB時,PEGPC碼的BER只有約PEG碼的1/3,而比隨機碼則要低近兩個數(shù)量級,在BER=10-5時,PEGPC碼要優(yōu)于PEG碼約0.1 dB,優(yōu)于隨機碼約0.45 dB.

圖4 PEGPC碼、PEG碼和隨機碼的 BER性能Fig.4 BER curves for PEGPC code,PEG code and random code

4 結論

本文作者提出了環(huán)多項式的概念,并在此基礎上提出了基于環(huán)多項式的漸進邊增長構造法,在選擇新增邊時,利用環(huán)多項式,不僅保證了新增邊形成的環(huán)盡可能長,而且短環(huán)的數(shù)量盡可能少,優(yōu)化了碼字構造.仿真結果表明,該方法在保證較大圍長的同時,短環(huán)數(shù)量可以降低約52.8%.短環(huán)數(shù)量的減少降低了信息自反饋對譯碼性能的影響,明顯改善了LDPC碼的性能,且構造靈活,構造復雜度低.

[1]Gallager R G.Low-Density Parity-Check Codes[J].IRE Transactions on Information Theoryy,1962,IT-18,:21-28.

[2]Gallager R G.Low-Density Parity-Check Codes.Cambridge[M].MA:MIT Press,1963.

[3]CHUNG Saeyoung,Forney G D,Richardson T J,et al.On the Design of Low-Density Parity-Check Codes with in 0.0045 dB of the Shannon Limit[J].IEEE Communications Letters,2001,5(2):58-60.

[4]Kim Jonlark,Peled U N,Perepelitsa I,et al.Explicit Construction of Families of LDPC Codes with no 4-Cycles[J].IEEE Transactions on Information Theory,2004,50(10):2378-2388.

[5]Kou Y,Lin S,Fossorier M.Low-Density Parity-Check Codes Based on Finite Geometries:A Rediscovery and New Results[J].IEEE Transactions on Information Theory,2001,47(7):2711-2736.

[6]Campello J,Modha D S.Designing LDPC Codes Using Bit-Filling[C]∥IEEE ICC 01',2001:55-59.

[7]Campello J,Modha D S.Extended Bit-Filling and LDPC Code Design[C]∥IEEE Globecom 01',2001:985-989.

[8]HU Xiaoyu,Eleftheriou E,Arnold D M.Progressive Edge-Growth Tanner Graphs[C]∥IEEE Globecom 01',2001:995-1001.

[9]Hu Xiaoyu,Eleftheriou E,Arnold D M.Irregular Progressive Edge-Growth(PEG)Tanner graphs[C]∥IEEE Internation Symposium on Information Theory(ISIT 02'),2002:480.

[10]Lin Yikai,Chen Chinlung,Liao Yenchin,et al.Structured LDPC Codes with Low Error Floor Based on PEG Tanner Graphs[C]∥IEEE Internation Symposium on Circuits and Systems(ISCAS 08'),2008:1846-1849.

[11]Zhan Wei,Zhu Guangxi,Li Peng,et al.Quasi-Cyclic LDPC Codes Based on D and Q Matrices Through Progressive Edge Growth[C]∥IEEE Internation Symposium on Intelligent Signal Processing and Communication System(ISPACS 07'),2007:12-15.

[12]Vukobratovic D,Senk V.Generalized ACE Constrained Progressive Edge-Growth LDPC Code Design[J].IEEE Communication Letters,2008,12(1):32-34.

[13]Richter G,Hof A.On A Construction Method of Irregular LDPC Codes Without SmallStopping Sets[C]∥IEEE Internation Conference on Communication(ICC 06'),2006:1119-1124.