一種具有最小距離下界的正則LDPC碼的構(gòu)造

王 娟，王中訓(xùn)，朱方強(qiáng)，劉 麗

(煙臺(tái)大學(xué)，光電信息科學(xué)技術(shù)學(xué)院，山東 煙臺(tái) 264005)

低密度校驗(yàn)碼(LDPC碼)是一種逼近香農(nóng)限的好碼[1]。PEG 算法是構(gòu)造中短長 LDPC 碼的最優(yōu)方法[2]，該算法可以得到較大的圍長和較大的最小距離下界[3]。本文提出一種通過不斷改善獨(dú)立樹基礎(chǔ)的最小距離下界的構(gòu)造LDPC碼的新方法。與用PEG方法構(gòu)造的LDPC碼相比，獨(dú)立樹基礎(chǔ)LDPC碼改進(jìn)了圍長和最小距離下界，得到了更低的誤碼率性能。

1 背景介紹

1.1 LDPC碼的表示

LDPC碼可以由其稀疏校驗(yàn)矩陣H唯一定義。矩陣中的行對(duì)應(yīng)校驗(yàn)方程，列對(duì)應(yīng)碼字的比特。LDPC碼還可以用變量節(jié)點(diǎn)(矩陣中的列)校驗(yàn)節(jié)點(diǎn)(矩陣中的行)組成的Tanner圖來表示[4]，當(dāng)校驗(yàn)矩陣元素非零時(shí)，Tanner圖中的變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間有一條邊相連。在Tanner圖最短的循環(huán)長度稱為LDPC的圍長[5]。

1.2 經(jīng)典PEG方法和改進(jìn)的PEG方法

PEG方法是不斷往開始只有校驗(yàn)節(jié)點(diǎn)的Tanner圖中添加特點(diǎn)度數(shù)的變量節(jié)點(diǎn)去構(gòu)造具有大圍長的LDPC碼。每往Tanner圖中添加1條邊，添加的邊的環(huán)長是目前可獲得的最大環(huán)長。此過程直到添加的比特節(jié)點(diǎn)的數(shù)目達(dá)到要求的個(gè)數(shù)。

經(jīng)典的PEG方法構(gòu)造出來的LDPC碼的矩陣不能滿足校驗(yàn)節(jié)點(diǎn)度分布的約束[3]。校驗(yàn)節(jié)點(diǎn)的規(guī)則性對(duì)譯碼收斂速度和硬件實(shí)現(xiàn)都是有利的[6]。變量節(jié)點(diǎn)從合法的校驗(yàn)節(jié)點(diǎn)的集合中選取，每增加一條邊都需要檢驗(yàn)新增加邊的校驗(yàn)節(jié)點(diǎn)的度是否達(dá)到了預(yù)設(shè)值dc，直到選取到達(dá)到預(yù)設(shè)值的校驗(yàn)節(jié)點(diǎn)。對(duì)PEG方法做這樣小的改動(dòng)能增加校驗(yàn)節(jié)點(diǎn)的規(guī)則性，卻對(duì)LDPC碼的圍長性能幾乎沒有影響。

碼的圍長可用來求最小距離下界[3]。對(duì)規(guī)則LDPC碼，當(dāng)是奇數(shù)，則

在第2章將提出用獨(dú)立樹得到新的下界，這個(gè)界比式(1)，(2)中的圍長為基礎(chǔ)的下界都要緊。

1.3 獨(dú)立樹的構(gòu)造

獨(dú)立樹是Tanner圖的一個(gè)聯(lián)通子圖，為的是最大化根節(jié)點(diǎn)與葉節(jié)點(diǎn)之間的距離。獨(dú)立樹的每個(gè)變量節(jié)點(diǎn)都連接了Tanner圖中它的一部分鄰居節(jié)點(diǎn)。每個(gè)校驗(yàn)節(jié)點(diǎn)也和Tanner圖中的同樣的鄰居節(jié)點(diǎn)相連。這種對(duì)變量節(jié)點(diǎn)的安排，既能滿足Tanner圖的校驗(yàn)節(jié)點(diǎn)的約束，也能滿足獨(dú)立樹對(duì)每個(gè)校驗(yàn)節(jié)點(diǎn)的約束。

構(gòu)造獨(dú)立樹的具體步驟是:以vi為根節(jié)點(diǎn)建造樹，對(duì)每一級(jí)中的每個(gè)變量節(jié)點(diǎn)vk進(jìn)行構(gòu)造，即當(dāng)校驗(yàn)節(jié)點(diǎn)cj∈A(vk)但不是vk的根節(jié)點(diǎn)時(shí)，則將cj連接到vk上，將除vk外屬于A(vk)的變量節(jié)點(diǎn)即vl∈N(cj)vk置于下一級(jí)中;對(duì)每個(gè)變量節(jié)點(diǎn)vi都用這種方法去構(gòu)造獨(dú)立樹。

圖1給出N=7，K=3的LDPC碼Tanner圖，圖2為構(gòu)造的該LDPC碼的變量節(jié)點(diǎn)v1為根節(jié)點(diǎn)的獨(dú)立樹，所有碼字在Tanner圖上的構(gòu)造與獨(dú)立樹上的有效構(gòu)造是一致的，而且獨(dú)立樹上關(guān)于最小重量的有效構(gòu)造不能超過碼字的最小距離。

2 獨(dú)立樹基礎(chǔ)LDPC碼的構(gòu)造與其最小距離下界

由Tanner圖的構(gòu)造與獨(dú)立樹構(gòu)造的關(guān)系，使得從獨(dú)立樹去改善碼的性能成為可能。為了得到獨(dú)立樹根節(jié)點(diǎn)的最小距離下界，必須計(jì)算獨(dú)立樹上的最小距離偏差。通過獨(dú)立樹計(jì)算最小距離偏差的方式是去將所有變量節(jié)點(diǎn)的對(duì)數(shù)似然比賦值為1，然后從葉節(jié)點(diǎn)到根節(jié)點(diǎn)用最小和算法(MS)進(jìn)行譯碼[7]。MS算法在根節(jié)點(diǎn)vi的結(jié)果就是獨(dú)立樹的最小重量偏差的重量，記作DITB，i。下面給出計(jì)算 DITB，i的方法。

定理1:LDPC碼的最小距離下界滿足

定理2:以獨(dú)立樹基礎(chǔ)構(gòu)造的LDPC碼的下界都不小于以圍長為基礎(chǔ)構(gòu)造的LDPC碼的最小距離下界DGmin。

由定理1、定理2，很容易可以看出DITB，min也不小于式(1)，(2)中給出的界。以下給出了用獨(dú)立樹方法構(gòu)造規(guī)則LDPC碼的方法。

從含有N個(gè)變量節(jié)點(diǎn)，M個(gè)校驗(yàn)節(jié)點(diǎn)，校驗(yàn)節(jié)點(diǎn)度數(shù)為dC、變量節(jié)點(diǎn)為dV的任意規(guī)則LDPC碼開始進(jìn)行構(gòu)造。

1)用以上介紹的構(gòu)造獨(dú)立樹的方法以碼的N個(gè)變量節(jié)點(diǎn)為根節(jié)點(diǎn)構(gòu)造N個(gè)獨(dú)立樹。

2)所有成對(duì)的邊，與它們相連的變量節(jié)點(diǎn)不與任何常規(guī)校驗(yàn)節(jié)點(diǎn)的相鄰;初始化設(shè) DITB－min=DITB，1，對(duì)任意的 i均有 DITB－min=DITB，i。

3)轉(zhuǎn)換已經(jīng)連接了校驗(yàn)節(jié)點(diǎn)的邊ei和ej。

4)DITB－min減小時(shí)，或者 DITB－min沒有減小，但是滿足DITB－min=DITB，i的 i的數(shù)目減小，或者 DITB－min沒有變，但是滿足 DITB－min=DITB，i的 i的數(shù)目也沒有變，相對(duì)所有的 i來說，DITB，i的平均值減小了，均保持步驟3)的轉(zhuǎn)換。

5)否則取消這種轉(zhuǎn)換。

必須說明，獨(dú)立樹LDPC碼構(gòu)造方法比PEG方法計(jì)算復(fù)雜度要高。PEG方法是在確立Tanner圖上的最小環(huán)長之后添加一條邊;而獨(dú)立樹LDPC構(gòu)造用更精確的標(biāo)準(zhǔn)，從總體上估計(jì)每條可能的邊的轉(zhuǎn)換影響，這使得該算法需要進(jìn)一步改進(jìn)。

3 比較獨(dú)立樹和PEG法構(gòu)造的LDPC碼

從碼的性能和仿真結(jié)果上將獨(dú)立樹構(gòu)造的LDPC碼分別與隨機(jī)構(gòu)造的、PEG構(gòu)造的LDPC碼進(jìn)行比較。

表1將碼長分別為N=1008，1512的3種方法構(gòu)造的LDPC碼的圍長進(jìn)行了比較。對(duì)N=504的碼來說，獨(dú)立樹與PEG有同樣的環(huán)長。N=1008和N=1512時(shí)獨(dú)立樹構(gòu)造比其他兩種方法圍長要大，獨(dú)立樹構(gòu)造方法在得到最大化最小距離下界的過程中得到了大的圍長。

表1 幾種LDPC碼的構(gòu)造方法性能比較

圖3、圖4是用BP算法在最大迭代次數(shù)為60次時(shí)的誤碼率仿真結(jié)果。

圖3 N=1008時(shí)仿真結(jié)果

由以上仿真圖可以看出當(dāng)信噪比增加時(shí)，獨(dú)立樹構(gòu)造碼的誤碼率最低，并且會(huì)低于10－5。這是因?yàn)樵谛旁氡仍黾訒r(shí)，圍長和最小距離對(duì)性能有非常重要的影響。每種碼長的碼的仿真結(jié)果與表1給出的性能是一致的，最小距離下界越大誤碼率性能則越低。

4 結(jié)論

圖4 N=1512時(shí)的仿真結(jié)果

本文給出一種新的獨(dú)立樹結(jié)構(gòu)基礎(chǔ)上的最小距離下界的構(gòu)造規(guī)則LDPC碼的方法，新方法的最小距離下界比以圍長為基礎(chǔ)的用PEG方法構(gòu)造的規(guī)則LDPC碼最小距離下界要大。而且這種方法構(gòu)造的規(guī)則LDPC碼得到了更長的圍長、更大的最小距離下界以及更低的誤碼率性能。通過使用BP算法在AWGN信道下仿真的性能比較可知，隨著信噪比的增加，該方法的誤碼率性能越明顯優(yōu)異于隨機(jī)構(gòu)造方法和PEG構(gòu)造方法。

[1]MACKAY D J C，NEAL R M.Near shannon limit performance of lowdensity parity check codes[J].IEEE Elctron.Lett，1996，32(18):1645.

[2]雷偉龍，錢辰，王昭誠，等.基于PEG算法的QC－LDPC碼構(gòu)造[J].電視技術(shù)，2011，35(5):1－4.

[3]HU Xiaoyu，ELEFTHERIOU E，ARNOLD D M.Progressive edgegrowth tanner graphs[C]//Proc.Global Telecommunications Conference.San Antonio，TX，USA:IEEE Press，2001，2:995－1001.

[4]WIBERG N，LOELIGER H A，KOTTER R.Codes and iterative decoding on general graphs[J].Transctions Telecomm，1995，6(5):513－525.

[5]袁東風(fēng)，張海剛.LDPC碼理論與應(yīng)用[M].北京:人民郵電出版社，2008.

[6]CHEN H，CAO Zhicang.A modified PEG algorithm for construction of LDPC codes with strictly concentrated check－node degree distributions[C]//Proc.IEEE Wireless Communications and Networking Conference(WCNC 2007).[S.l.]:IEEE Press，2007:564－568.

[7]李千玲，陳偉，樊豐.基于DVB－S2標(biāo)準(zhǔn)的LDPC碼最小和譯碼算法的改進(jìn)[J]. 電視技術(shù)，2011，33(5):8－9.