一種具有較大圍長的正則LDPC碼構(gòu)造方法

摘 要:提出一種新的具有較大圍長的正則LDPC碼構(gòu)造方法。首先介紹以矩陣分裂技術(shù)為基礎(chǔ)的高圍長正則LDPC碼的構(gòu)造方法，并在此基礎(chǔ)上分析了設(shè)計(jì)圍長時(shí)參數(shù)的選取方法。仿真表明，用這種方法構(gòu)造的正則LDPC碼圍長可以達(dá)到12，并且在AWGN信道下的性能不差于相同參數(shù)、隨機(jī)構(gòu)造的LDPC碼，在高信噪比時(shí)甚至優(yōu)于相同參數(shù)的隨機(jī)碼。

關(guān)鍵詞:低密度奇偶校驗(yàn)碼;高圍長;矩陣分裂;正則LDPC碼

中圖分類號(hào):TN911.72 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2010)03-087-03

Method for Construction of Regular LDPC Code with Large Girth

HUANG Xiang，Senbai Dalabaev

(School of Information Science Engineering，Xinjiang University，Urumqi，830046，China)

Abstract:A construction method of strucred regular Low-Density Parity-Check(LDPC)code with large girth based on matrix dividing is proposed.The parameter option about girth accuting is analysed.Simulation results show that these codes′ girth can achieve 12 based on this method，besides that，its performance is not worse than randomly constructed LDPC code in the same parameter under AWGN channel.Even better than the same parameter random code at high SNR situation.

Keywords:low-desity parity-check codes;large gith;matrix dividing;regular LDPC code

1962年Gallager提出低密度校驗(yàn)(Low Density Parity Check，LDPC)碼[1]，后來Tanner對(duì)它進(jìn)行了很有價(jià)值的補(bǔ)充[2]，直到1995年又被Mackey重新提出[3]。如果采用和積迭代譯碼算法，LDPC碼具有非常接近香農(nóng)限的性能。如果在LDPC碼的Tanner圖中存在環(huán)，在迭代譯碼的過程中錯(cuò)誤信息將會(huì)膨脹，對(duì)于LDPC的譯碼性能相當(dāng)有害，尤其是較短環(huán)的存在，所產(chǎn)生的危害尤為嚴(yán)重。所以，在構(gòu)造LDPC的過程當(dāng)中，要盡量避免短環(huán)的出現(xiàn)。為了盡量減小Tanner圖中環(huán)的存在對(duì)相應(yīng)LDPC碼在和積譯碼算法下所得性能的影響，一些研究學(xué)者基于代數(shù)方法和啟發(fā)式搜索方法，提出了一些具有較大圍長的LDPC碼構(gòu)造方法。研究表明，通過增大LDPC碼的圍長，在一定程度上可以改善碼的糾錯(cuò)性能。本文構(gòu)造了正則LDPC碼，在構(gòu)造過程中討論了設(shè)計(jì)圍長的參數(shù)選舉，使得滿足一定的條件就可以避免校驗(yàn)矩陣的小圍長出現(xiàn)，使得所構(gòu)造的矩陣具有較大圍長。

1 LDPC碼的構(gòu)造理論[3，4]

考慮長為16的(2，4)正則LDPC碼對(duì)應(yīng)的Tanner，如圖1所示。

圖1 (16，2，4)LDPC碼的Tanner圖表示

從圖1中很顯然可以看出，該Tanner中環(huán)的最小長度為8，因此對(duì)應(yīng)LDPC碼的圍長也為8。

按圖1將其中的變量結(jié)點(diǎn)和校驗(yàn)結(jié)點(diǎn)依次編號(hào)，可以得到對(duì)應(yīng)LDPC碼的校驗(yàn)矩陣，如圖2所示。

圖2 (16，2，4)LDPC碼的校驗(yàn)矩陣表示

圖2矩陣很有規(guī)律，可以看作是由兩個(gè)行重為2、維數(shù)為8×8的循環(huán)方陣拼接而成。因此可以猜想，采用某些有規(guī)律的矩陣合并成校驗(yàn)矩陣，這樣生成的LDPC碼很可能會(huì)具有較大的圍長。或者說，將LDPC碼的校驗(yàn)矩陣分裂為若干個(gè)子矩陣，然后每個(gè)子矩陣再按照某種規(guī)律構(gòu)造，就有可能避免小環(huán)的出現(xiàn)。

這里采用矩陣分裂[5-7]的思想。設(shè)要構(gòu)造一個(gè)長為n(n=ρUU∈N)的(λ，ρ)正則LDPC碼，將該碼的校驗(yàn)矩陣分裂為(λ，ρ)個(gè)U×U的子矩陣。

H=H0H1Hλ-1=H0，0H0，1…H0，ρ-1H1，0H1，1…H1，ρ-1Hλ-1，0Hλ-1，1…Hλ-1，ρ-1

(1)

式中:每個(gè)子矩陣Hi，j=I(ai，j)(0≤i<λ，0≤j<ρ)均為一個(gè)單位陣或者單位陣的循環(huán)移位;ai，j表示該單位陣的各行循環(huán)右移的位數(shù)。顯然，這樣構(gòu)造的校驗(yàn)矩陣也不可能為滿秩，至多為λρ-λ-1。

為便于描述，用A=(ai，j)表示由各個(gè)子方陣的循環(huán)移位參數(shù)組成的矩陣，用(I，J，i，j)表示校驗(yàn)矩陣中的元素，其中(I，J)為該元素所屬的子矩陣的坐標(biāo)，(i，j)為該元素在它所屬的子矩陣中的坐標(biāo)。稱Tanner圖中每個(gè)變量結(jié)點(diǎn)參與的所有環(huán)的最小長度為該變量結(jié)點(diǎn)的環(huán)長，則顯然相應(yīng)LDPC碼的圍長就等于各個(gè)變量結(jié)點(diǎn)環(huán)長的最小值。將n個(gè)變量結(jié)點(diǎn)分為P組，每一組變量結(jié)點(diǎn)對(duì)應(yīng)一列子矩陣，則考慮到各個(gè)子矩陣的循環(huán)特性，有如下定理成立。

定理1 屬于同組的變量結(jié)點(diǎn)具有相同的環(huán)長。

證明:設(shè)任意兩個(gè)同組的變量結(jié)點(diǎn)x和y，分別對(duì)應(yīng)一列子矩陣的第x列和第y列，且y-x=dmod U，其環(huán)長分別為C(x)和C(y)，并設(shè)變量結(jié)點(diǎn)x的最小環(huán)路徑如圖3所示。

圖3 變量節(jié)點(diǎn)x的環(huán)路示意圖(一)

根據(jù)各個(gè)子矩陣的循環(huán)特性，可以找到另一個(gè)環(huán)的路徑如圖4所示。

圖4 變量節(jié)點(diǎn)x的環(huán)路示意圖(二)

顯然該環(huán)路長度為C(x)且經(jīng)過變量節(jié)點(diǎn)y，故有:

C(x)≥C(y)

(2)

同理可得:

C(x)≤C(y)

(3)

綜合上面兩式，有C(x)=C(y)即對(duì)任意兩個(gè)同組的變量節(jié)點(diǎn)，它們的環(huán)長均相等，證畢。

由定理1可知，按照上述方法構(gòu)造的校驗(yàn)矩陣所對(duì)應(yīng)的LDPC碼，所有變量節(jié)點(diǎn)的環(huán)長至多有ρ種情況，因此對(duì)這樣構(gòu)造的矩陣只需要分別從各組中抽取一個(gè)變量節(jié)點(diǎn)，然后只對(duì)這ρ個(gè)變量節(jié)點(diǎn)進(jìn)行檢測(cè)，即可確定整個(gè)碼的圍長。

2 校驗(yàn)矩陣中循環(huán)移位參數(shù)的選取

下面討論4環(huán)的情況。如果一個(gè)LDPC碼含有4環(huán)，則它所對(duì)應(yīng)的校驗(yàn)矩陣中必然有4個(gè)“1”處于某個(gè)矩形的四個(gè)頂點(diǎn)，該環(huán)路路徑可表示為:

顯然，應(yīng)有:

i+aI1J1=i+aI1J2-aI2J2+aI2J1mod U

(4)

化簡(jiǎn)后得:

aI1J1+aI1J2-aI2J2+aI2J1=0 mod U

(5)

至此，可以得到如下定理。

定理2 按照式(1)所示矩陣分裂方法構(gòu)造的矩陣所對(duì)應(yīng)的LDPC碼不含長為4的環(huán)的充要條件有式(6)成立:

aI1J1+aI1J2-aI2J2+aI2J1≠0 mod U，

I1≠I2∈{0，1，…，λ-1}，J1≠J2∈{0，1，…，ρ-1}

(6)

該定理的正確性從前面的描述中即可得知，這里不再贅述。

由定理2很容易得到下面推論:

推論1:按照式(1)所示矩陣分裂構(gòu)造方法構(gòu)造的矩陣所對(duì)應(yīng)的LDPC碼不含長為2l的環(huán)的充要條件為:

∑l-1k=0(aIkJk-aIkJ(k+1)mod U)≠0mod U，

Ik≠I(K+1)mod l∈{0，1，…，λ-1}，

Jk≠J(k+1)mod l∈{0，1，…，ρ-1}

在編碼設(shè)計(jì)時(shí)，可以首先確定所構(gòu)造LDPC碼設(shè)計(jì)圍長，然后根據(jù)上面的定理和推論列出相應(yīng)的不等約束，進(jìn)而尋找滿足這些不等約束的參數(shù)即可。

在進(jìn)行參數(shù)選擇時(shí)，可以根據(jù)上面分析和設(shè)計(jì)的圍長列出各參數(shù)所對(duì)應(yīng)滿足的約束方程，然后尋找滿足這些約束方程的參數(shù)取值。然而，由于這些約束方程均為不等約束，因而無法采用一般的方程組求解法;如果采用窮舉的方法去遍歷各個(gè)參數(shù)的所有可能組合，繼而從中找出滿足約束的一組，搜索的范圍將有U(λ-1)(ρ-1)，這樣即使U的取值范圍很小(如102)，總的搜索范圍也將很大，因而無法實(shí)現(xiàn)。

為了實(shí)現(xiàn)參數(shù)的快速選取可以采用下述逐參試探算法:

(1) 令ai，0=0(i=0，1，…，λ-1)及a0，j=0(j=1，2，…，ρ-1);

(2) 隨機(jī)在{0，1，…，U-1}中選取a1，1的取值，然后判斷a1，1是否滿足給定的不等約束，若滿足則確定取值，否則重新執(zhí)行(2)

(3) 按照(2)的方法一次確定剩余子矩陣的循環(huán)移位參數(shù)。

按照上面算法，每個(gè)參數(shù)至多需要U次試探，這樣總共的試探次數(shù)至多為(λ-1)(ρ-1)U，遠(yuǎn)遠(yuǎn)小于整個(gè)搜索空間U(λ-1)(ρ-1)。

由于該算法采用逐個(gè)確定參數(shù)的方法，顯然最后確定的參數(shù)受到的約束是最多的，定義N(l)為考慮消除Tanner圖中長度為2l的環(huán)時(shí)最后一個(gè)參數(shù)受到的約束方程個(gè)數(shù)，則有:

N(2)=C15×C12=10

(7)

N(3)=C15×C12×C14=40

(8)

N(4)=C15×C12×C15×C12×C14=400

(9)

由于各個(gè)約束方程均為不等約束，每個(gè)約束只能限制參數(shù)不能取某個(gè)特定的值，因此所有不等約束限制參數(shù)所不能取的值的個(gè)數(shù)至多為約束方程數(shù)目的兩倍。考慮到所要構(gòu)造的LDPC碼的碼長，U的取值一般在100左右，因此消除六環(huán)一般都可行。

3 仿真及性能分析

取U=168，按照上面的方法構(gòu)造長度為1 008的(3，6)正則LDPC碼，通過計(jì)算機(jī)搜索檢測(cè)發(fā)現(xiàn)，得到子方陣的循環(huán)參數(shù)為:

A=000000

06912291980

0955465859

檢測(cè)發(fā)現(xiàn)LDPC碼的圍長為10，為了保證所構(gòu)造碼的碼率嚴(yán)格等于0.5，可以從生成的檢驗(yàn)矩陣中刪去2個(gè)“1”。該碼在AWGN信道下的糾錯(cuò)性能如圖5所示，圖中的另外兩條曲線分別為相同長度、隨即構(gòu)造、不消除4環(huán)的(3，6)正則LDPC碼的性能曲線。其中，girth表示圍長;ave表示所有變量節(jié)點(diǎn)的平均環(huán)長。

文獻(xiàn)[8，9]采用PEG算法所構(gòu)造的長度為1 008的(3，6)正則LDPC碼的圍長為8，平均環(huán)長為9.66，稍劣于上面構(gòu)造的LDPC碼，因此該方法用于正則LDPC碼的構(gòu)造時(shí)要優(yōu)于其他的構(gòu)造方法。

通過分析發(fā)現(xiàn)，采用該方法構(gòu)造的正則LDPC碼與文獻(xiàn)[10]所述方法一樣，其圍長存在一個(gè)上限，下面進(jìn)行詳細(xì)介紹。考慮一個(gè)維素為2U×3U的矩陣，將其分裂成6個(gè)維素為U×U的子方陣，每個(gè)方陣均為單位陣或單位陣的行循環(huán)移位，則可以得到一個(gè)行重為3、列重為2的矩陣。不失一般性，令第一行子方陣均為單位陣，其余兩個(gè)方陣的行右循環(huán)移位參數(shù)分別為a1，1和a1，2，則不論a1，1和a1，2如何取值，該矩陣始終存在如圖6所示的12環(huán)。

圖5 長為1 008的(3，6)正則LDPC碼的性能圖

圖6 12環(huán)在矩陣上的環(huán)路示意圖

將圖6環(huán)上各個(gè)的非零元素依次編號(hào)，并令編號(hào)為1的元素坐標(biāo)為(0，0，x，x)，則環(huán)上各節(jié)點(diǎn)的坐標(biāo)如圖7所示。

圖7 12環(huán)上非零元素的坐標(biāo)

因此，若采用上面的方法構(gòu)造(λ，ρ)正則LDPC碼，只要λ≥2，ρ≥2且λ+ρ≥5，相應(yīng)的校驗(yàn)矩陣中也就必然包含圖所示的字矩陣或其轉(zhuǎn)置矩陣，于是得到的LDPC碼的圍長也就必然不可能超過12。

4 結(jié) 語

給出了一種高圍長的正則LDPC碼的構(gòu)造方法，具體分析了去環(huán)方法和循環(huán)移位參數(shù)的選取。用這種方法構(gòu)造的LDPC 碼的H矩陣具有很好的結(jié)構(gòu)。仿真表明，用該方法構(gòu)造的碼在AWGN信道下性能要優(yōu)于隨機(jī)構(gòu)造的碼。

參考文獻(xiàn)

[1]Gallager R G.Low-density Parity Check Codes[J].IRETrans.on Infor.Theory，1962，8:21-28.

[2]Tanner R M.A Recursive Approach to Low-complexity Codes[J].IEEE Trans.on Infor.Theory，1981，IT-27:533-547.

[3]Mackay D J C，Neal R M.Good Codes Based on Very Sparse Matrices[A].Cryptography and Coding，5th IMA Conference in Lecture Notes in Computer Science[C].1995，1025:100-111.

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

[5]趙旦峰，陳艷，高敬鵬，等.基于單位陣的循環(huán)移位構(gòu)造LDPC碼的研究[J].應(yīng)用技術(shù)，2007，34(5):8-10.

[6]劉建權(quán).基于循環(huán)轉(zhuǎn)置單位矩陣條件填充的LDPC 碼構(gòu)造方法[J].電子與信息學(xué)報(bào)，2007，29(12):107.

[7]Tanner R M.A Class of Group-Structured LDPC Codes[A].ICSTA 2001 Proceedings[C].Ambleside，2001.

[8]Xiao Yuhu.Progressive Edge-Growth Tanner Graphs[J].IEEE Trans.on Inform.Theory，2001:995-1001.

[9]雷菁，王建輝，唐朝京.基于PEG 算法的準(zhǔn)循環(huán)擴(kuò)展LDPC 碼構(gòu)造[J].通信學(xué)報(bào)，2008，29(9):104-107.

[10]喬華，管武.一種基于循環(huán)移位矩陣的LDPC碼構(gòu)造方法[J].電子與信息學(xué)報(bào)，2008，30(10):2 385-2 386.