基于位置矢量構(gòu)造準(zhǔn)循環(huán)LDPC碼

周景芝，宋玉連

（連云港師范高等專科學(xué)校數(shù)學(xué)系，江蘇連云港 222006）

1 引言

低密度奇偶校驗(yàn)（LDPC）碼由于具有非常優(yōu)良的性能而受到人們廣泛的關(guān)注.準(zhǔn)循環(huán)LDPC碼是LDPC碼的一類非常重要的分支.Yu Kou等人提出了利用有限域里的歐氏幾何和投影幾何來(lái)構(gòu)造LDPC碼［1］，這種方法構(gòu)造出的碼字具有循環(huán)或者準(zhǔn)循環(huán)特性，但是產(chǎn)生了許多長(zhǎng)度為6的環(huán).LDPC碼的Tanner圖中長(zhǎng)度為4的環(huán)會(huì)造成譯碼性能的降低.Shu Lin課題研究小組指出利用平衡不完全區(qū)組設(shè)計(jì)［2］（BIBD）構(gòu)造LDPC碼是一個(gè)很好的方向.BIBD構(gòu)造法和隨機(jī)化構(gòu)造法相比，具有循環(huán)或準(zhǔn)循環(huán)結(jié)構(gòu)，編碼實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單.為了進(jìn)一步研究LDPC碼的構(gòu)造并考慮它的實(shí)用性，利用 Bose構(gòu)造的BIBD，基于位置矢量構(gòu)造出譯碼性能非常好的準(zhǔn)循環(huán)LDPC碼，用此設(shè)計(jì)構(gòu)造的LDPC碼最小環(huán)長(zhǎng)大于等于6.

2 Bose－BIBD的關(guān)聯(lián)矩陣的結(jié)構(gòu)特性

以 （m，q，ρ，γ，λ） 為參數(shù)的基于 BIBD 的 LDPC碼校驗(yàn)矩陣構(gòu)造過(guò)程為［3］:（1）建立集合X=（x1，x2，…，xq），獲取其n個(gè)分組Q1，Q2，…，Qn，其中Qi為X的子集，包含γ個(gè)元素;要求集合X的任意一個(gè)元素xi需在ρ個(gè)分組中出現(xiàn);且集合X的任意兩個(gè)元素xi，xj在n個(gè)分組中同時(shí)出現(xiàn)的次數(shù)相同，均為 λ;（2）所有參數(shù)間需滿足qρ=nλ和λ（q－1）=ρ=（λ－1） 條件.實(shí)際上，以（n，q，ρ，γ，λ） 為參數(shù)的基于平衡不完全區(qū)組設(shè)計(jì)過(guò)程都可用一個(gè)q×n的關(guān)聯(lián)矩陣H=（hij）q×n表示.如果X中的第i個(gè)元素落在Qj分組中，令hij=1，否則hij=0.相關(guān)矩陣H成為行重為ρ，列重為γ，任意兩列重復(fù)為1的次數(shù)至多為1的矩陣，符合規(guī)則LDPC碼的校驗(yàn)矩陣定義.

Bose在有限域上構(gòu)造了下面這類BIBD.令t是一個(gè)使得12t+1為素?cái)?shù)的正整數(shù)，從而GF（12t+1）={0，1，2，…，12t} 是一個(gè)有12t+1 個(gè)元素的有限域.令α是有限域GF（12t+1）上的一個(gè)本原元，滿足α4t－1=αc，其中c是一個(gè)小于12t+1的奇整數(shù)，則GF（12t+1）的元素可由0，α0=1，α，α2，…，αq－2來(lái)表示，其中 αq－1=1.于是，存在一個(gè)參數(shù)為q=12t+1，n=t（12t+1），ρ=4t，γ=4 和 λ=1的BIBD.該BIBD的t個(gè)基礎(chǔ)區(qū)組是:Bi={0，α2i，α2i+4t，α2i+8t}，其中 0 ≤i＜t.我們將有限域GF（12t+1）的12t+1個(gè)元素依次加到每一個(gè)基礎(chǔ)區(qū)組Bi得到了t（12t+1）個(gè)區(qū)組，每個(gè)區(qū)組中有γ=4個(gè)元素組成，每個(gè)元素恰好在ρ=4t個(gè)區(qū)組中出現(xiàn)，每個(gè)元素對(duì)恰好在λ=1個(gè)區(qū)組中出現(xiàn).這t（12t+1）個(gè)分組構(gòu)成的BIBD稱為（t（12t+1），12t+1，4t，4，1） －Bose－BIBD，其關(guān)聯(lián)矩陣H是一個(gè)（12t+1）×t（12t+1）矩陣，列重是4，行重是4t，這樣可以得到一個(gè)長(zhǎng)度為n=t（12t+1）的 LDPC碼，其Tanner圖中沒(méi)有長(zhǎng)度為4的環(huán).

由于H可以寫(xiě)成H=［G0，G1，…，Gt－1］，所以，H的零空間就給出了一個(gè)準(zhǔn)循環(huán)LDPC碼，其長(zhǎng)度為n=t（12t+1）.我們也可以選擇其中k個(gè)循環(huán)陣G0，G1，…，Gk－1來(lái)構(gòu)造矩陣H（k）:H（k）=［G0，G1，…，Gk－1］，其中 1 ≤k≤t.H（k） 是一個(gè)（12t+1）×k（12t+1）矩陣，其列重和行重分別為4和4k.這樣可以得到一個(gè)長(zhǎng)度為n=k（12t+1）的準(zhǔn)循環(huán)LDPC碼，其Tanner圖中沒(méi)有長(zhǎng)度為4的環(huán).

3 基于位置矢量的準(zhǔn)循環(huán)BIBD－LDPC碼

定義1［4］令p為素?cái)?shù)，在模p的加法和乘法下構(gòu)成有限域GF（p）.我們對(duì)GF（p）上的元素定義一個(gè)p－元位置矢量.當(dāng)i∈GF（p）時(shí)，i位置矢量記為:

其中l(wèi)i∈GF（2），即L（i）中除分量li=1，其它分量均為0.

定理1 若i，j∈GF（p），且i≠j，則L（i） ≠L（j）.

定理2 若i∈GF（p），則L（i+1）是L（i）的右循環(huán)移位向量.

顯然A，是一個(gè)在GF（2）上的p×p的循環(huán)置換方陣.

Bose－BIBD在有限域GF（12t+1）中有t個(gè)基礎(chǔ)區(qū)組:Bi={0，α2i，α2i+4t，α2i+8t}，其中0 ≤i＜t.令矩陣Qi是將GF（12t+1）的各個(gè)元素依次加到Bi構(gòu)成的一個(gè)（12t+1）×4矩陣.

Qi具有以下結(jié)構(gòu)特性［5］:

（l）各列的12t+1個(gè)元素互不相同，分別為GF（12t+1）的12t+1個(gè)元素;

（2）任意兩列或兩行在同一位置都沒(méi)有相同的元素;

Qi的每一行都是（t（12t+1），12t+1，4t，4，1）－Bose－BIBD的一個(gè)區(qū)組，Qi的行標(biāo)記從0到12t，每一列標(biāo)記從0到3.用位置矢量替換Qi的每一個(gè)元素，從而得到一個(gè)在GF（2）域上的（12t+1）×4（12t+1）矩陣Mi，它是由4個(gè)（12t+1）×（12t+1）循環(huán)置換矩陣組成:

其中0≤i＜t，Ai，j是由Qi的第j列所有元素的位置矢量組成的（12t+1）×（12t+1）方陣，其中0≤j≤3.對(duì)于Bose－BIBD所有的t個(gè)基礎(chǔ)區(qū)組，可以構(gòu)造一個(gè)由t×4個(gè)（12t+1）×（12t+1）循環(huán)置換矩陣構(gòu)成的矩陣Z:

令H=ZT，因此H是由4×t個(gè)（12t+1）×（12t+1）的循環(huán)置換矩陣構(gòu)成的，在GF（2）上的一個(gè)4（12t+1）×t（12t+1）的矩陣，它的列重為4，行重為t.H的零空間給出了一個(gè)（4，t）－正則準(zhǔn)循環(huán)的BIBD－LDPC碼，其碼長(zhǎng)為n=t（12t+1）.

若γ和ρ均為正整數(shù)，且滿足1≤γ≤4和1≤ρ≤t，令H（γ，ρ）是H的一個(gè) γ（12t+1）×ρ（12t+1）的子矩陣，即H（γ，ρ）由 γ×ρ個(gè)（12t+1）×（12t+1）的循環(huán)置換矩陣構(gòu)成的，其列重和行重分別為 γ和 ρ.于是，H（γ，ρ）的零空間給出了一個(gè)（γ，ρ）－正則準(zhǔn)循環(huán)LDPC碼，其碼長(zhǎng)為ρ（12t+1），并且該碼的Tanner圖中沒(méi)有長(zhǎng)度為4的環(huán)，環(huán)長(zhǎng)至少為6.

:

［1］KOU Y，LIN S，F(xiàn)OSSORIER M P.Low － density parity － check codes based on finite geometries:a rediscovery and new results［J］.IEEE Trans Inform Theory，2001，47（7）:2711 －2736.

［2］Bose R C.On the construction of balanced incomplete design［J］.Annals of Eugenics，1939，9（1）:353 －399.

［3］Lan L，Ying Y T，Shu L，Memari B，and Honary B.New constructions of quasi－ cyclic LDPC codes based on special classed of BIBD＇s for the AWGN and binary erasure channels［J］.IEEE Transactions on Communication，2007，55（12）:2381.

［4］Djurdjev I，Xu J，and Lin S.Construction of low － density parity－ check codes based on shortened Reed － Solomon codes with two informations symbols［J］.IEEE Transactions on Communication，2003，17（7）:317 － 319.

［5］Lan L，Ying Y T.Constructions of quasi－ cyclic LDPC codes for the AWGN and binary erasure channels:a finite field approach［J］.IEEE Trans Inform Theory，2007，53（7）:2429 －2458.