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

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

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

1 背景介紹

1.1 LDPC碼的表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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