基于BIBD的多進制準循環(huán)LDPC碼構造

劉 冰，吳東偉，崔 潔，張用宇

(中國人民解放軍91469部隊，北京 100841)

0 引 言

多進制低密度奇偶校驗碼(low-density parity-check，LDPC)及其迭代譯碼算法(q-ary sum-product algorithm，QSPA)由Davey和Mackay于1998年首次提出[1]，相比于二進制LDPC碼，其具有更好的差錯性能優(yōu)勢，但這卻是以更高的譯碼復雜度為代價換取來的，正是這種譯碼的高復雜度制約了多進制LDPC碼構造的發(fā)展。基于FFT的QSPA譯碼算法(FFT-QSPA)的提出[2]有效解決了多進制LDPC碼譯碼高復雜度的弊端，同時也促進了多進制LDPC碼構造方法的研究。

多進制LDPC碼的性能與校驗矩陣H的結構密切相關。對于構造H方法，大體可以分為基于計算機搜尋的隨機構造法[3]和基于代數(shù)和幾何的結構化方法[4-7]兩大類。構造多進制LDPC碼的校驗矩陣時，需要確定2個重要的參數(shù)，即非零值的位置和非零值的取值。只有當構造的校驗矩陣中非零值的位置和取值都具有一定結構時，其矩陣才認為具有結構化的特性。一般而言，對二進制隨機構造的LDPC長碼比等長的結構化LDPC碼性能更好，然而也正因為其校驗矩陣的隨機性，使得人們難以找到簡單的編碼方法；相反，結構化LDPC碼在碼的構造、編譯碼復雜度以及存儲空間等方面較隨機LDPC碼有明顯優(yōu)勢。而多進制LDPC碼在短幀時具有接近Shannon限的能力，表現(xiàn)出了其在短碼和中長碼上所具有的優(yōu)勢，并且多進制LDPC碼具有很好的糾錯能力和較強的抗突發(fā)錯誤能力。因此，如同構造BCH碼和RS碼那樣，尋找系統(tǒng)的、綜合性能較好的多進制LDPC碼的構造方法成為當前研究的熱點。

準循環(huán)(qusic-cyclic，QC)作為一類非常重要的結構化LDPC碼結構，其特殊的循環(huán)結構使得編碼可以采用移位寄存器在線性時間內(nèi)完成，譯碼可以采用計數(shù)器尋址，并且可以并行實現(xiàn)。Yu Kou[8]基于有限幾何理論首次提出了一種代數(shù)的、系統(tǒng)的二進制LDPC碼構造方法。L.Zeng[4-5]在二進制QC構造的基礎上首次提出了基于有限幾何和有限域的多進制準循環(huán)LDPC碼的系統(tǒng)化構造方法。相比于RS碼而言，其構造的碼字在加性高斯白噪聲(additive white Gaussian noise，AWGN)信道下可以取得很大的編碼增益。上述方法都是準循環(huán)LDPC碼的經(jīng)典構造。組合設計是組合數(shù)學中的一個重要問題，其中一種特殊的組合設計被稱為均衡不完全區(qū)組設計(balanced incomplete block design，BIBD)[9-10]。Bassem Ammar[9]將BIBD的一種特殊子類首次運用于二進制LDPC碼的設計中，而目前尚無將BIBD法應用于構造多進制LDPC碼的相關文獻。

本文在BIBD構造和廣義二維擴展的基礎上提出三類基于BIBD的多進制QC LDPC碼的構造方法，該方法可以取得girth至少為6的規(guī)則多進制QC-BIBD-LDPC碼。由于基于BIBD構造多進制校驗矩陣時，其所構造的伽羅華域值q是素數(shù)或是素數(shù)的冪，而采用低復雜度的FFT-QSPA譯碼時，只能對2的冪次域階數(shù)構造的碼字進行譯碼，因此在考慮到譯碼復雜度的前提下，采用BIBD構造多進制LDPC碼時會涉及到2個不同的高階域，需要進行適當?shù)奶幚怼?/p>

1 BIBD多進制準循環(huán)LDPC碼

1.1 基本概念及構造方法

令GF(q)為具有q個元素的有限域。多進制規(guī)則LDPC碼C由多進制稀疏校驗矩陣H的零空間所定義，其具有以下結構化性質(zhì)：

1)每行的重量為dc；

2)每列的重量為dv。無論是二進制還是多進制，LDPC碼的構造都還需要增加一條性質(zhì)；

3)任何2行(或2列)之間位置相同的非零值的個數(shù)不大于1。

這樣構造出來的校驗矩陣規(guī)則，由其零空間給出的碼C稱為(dv,dc)規(guī)則LDPC碼。性質(zhì)3稱為RC約束，其保證了H的零空間給出的LDPC碼C的Tanner圖girth至少為6。如果H的行與(或)列具有不同的重量，那么H的零空間將給出一個非規(guī)則LDPC碼。

令G={x(1),x(2),…,x(q)}是具有q個元素的Abelian群。G的一個BIBD是指G的n個dv子集，記為B1,B2,…,Bn，稱為區(qū)組(Blocks)，它們滿足如下條件：

1)每個元素恰好在n個區(qū)組中的dc個出現(xiàn)；

2)任一元素對恰好在n個區(qū)組中的λ個出現(xiàn)；

3)每個區(qū)組中元素的個數(shù)dv與X中的元素總數(shù)q相比非常小。

1)其行對應X的q個元素；

2)其列對應該設計的n個區(qū)組；

3)當且僅當?shù)趇個元素xi屬于第j個區(qū)組Bj時，hij≠0且hij∈GF(q)，否則，hij=0。 這個矩陣被稱為基于GF(q)域設計的關聯(lián)矩陣H，H的列重和行重分別是dv和dc。

根據(jù)BIBD的第2個條件，H的2個行向量具有λ個公共的1分量。如果λ=1，H就滿足了LDPC碼所有定義的結構化性質(zhì)，于是H的零空間給出了一個長度為n的(dv,dc)規(guī)則LDPC碼，其Tanner圖中沒有長度為4的環(huán)，這是基于BIBD最直接構造LDPC碼的方法。

1)在s個區(qū)組中的sdv個元素中，dc個元素屬于q組中的一組；

2)s個區(qū)組中元素的差對稱重復，且每一個出現(xiàn)λ次。通過將G中每個元素逐個加到每一個區(qū)組B1,B2,…,Bs上，可以得到一個具有參數(shù)M=kq，N=sq，dc，dv和λ的BIBD。

由于采用BIBD構造校驗矩陣中的循環(huán)陣大小都是素數(shù)的冪pm，將BIBD構造的校驗矩陣擴展到多進制上，可直接在GF(pm)域上進行，即在BIBD決定的位置上隨機或有規(guī)律地填入GF(pm)域中的非零值。但這種方法構造出的多進制LDPC碼只能采用QSPA算法或其衍生算法來譯碼，而不能采用低復雜度的FFT-QSPA譯碼算法，采用QSPA算法存在的缺陷是復雜度較高，不利于工程實現(xiàn)。應用FFT-QSPA的前提是域的階數(shù)必須為2的冪次，因此，構造基于BIBD多進制LDPC碼時需要綜合考慮編譯碼復雜度等實際情況。此時會涉及到GF(pm)和GF(2l)兩個域，多進制LDPC碼校驗矩陣非零值的位置由GF(pm)域上的BIBD設計決定，而非零值的取值由GF(2l)域決定。這2個域的具體關系如下：(2l-1)·(rt-1)

其中[·]表示向上取整。

令β是GF(2l)域的本原元。將BIBD區(qū)組的多進制位置向量定義為z(Bi)=(z0,z1,…,zpm-1)， 其向量取值對應的是GF(2l)域中的pm個元素，其中zi=βimod(2l-1)，i∈Bi，其他所有分量為0。Bi中的元素稱為位置數(shù)，決定著校驗矩陣中非零值的位置。因此，z(Bi)是GF(2l)域上的pm重向量，其重量為區(qū)組Bi中所包含元素的個數(shù)。

多進制位置向量z(Bi+1)定義為位置向量z(Bi)向右循環(huán)移一位，第1列至第pm-1列的元素右移后乘以β得到第2列至第pm列的元素，而最后1列元素右移后乘以βrt(2l-1)-(pm-1)后得到第1列元素。多進制位置向量z(Bi+j)定義為區(qū)組Bi中元素依次加非零值j∈GF(pm)后得到取值在GF(2l)域的多進制位置向量。這樣，在GF(2l)域上可形成以Bi，Bi+1，…，Bi+pm-1的位置向量為行的多進制pm×pm大小的循環(huán)陣Q。所以，Q是根據(jù)區(qū)組Bi的廣義二維pm重擴展：

(2)

根據(jù)上述基本概念和提出的規(guī)則，可以由基本區(qū)組Bi進行廣義二維pm重擴展得到多進制準循環(huán)矩陣。由于多進制校驗矩陣非零值的位置和數(shù)值的選取分別是建立在GF(pm)和GF(2l)兩個不同域上，元素的位置由GF(pm)域來確定，而元素的數(shù)值在GF(2l)域內(nèi)選取。因而構造出的二維pm重矩陣Q在GF(2l)域上一般具有域元素分布不均的特性。上述廣義二維擴展方法充分考慮了編碼和譯碼的復雜度，從工程的角度出發(fā)更有利于實際應用。

1.2 I類QC-BIBD-LDPC碼

1)I-A類設計

令t是滿足12t+1=pm的1個正整數(shù)，其中p是1個素數(shù)，m是1個正整數(shù)。假設GF(pm)域有1個本原元α滿足α4t-1=αc，其中c是一個小于pm的正奇數(shù)。于是，對于具有kq=12t+1個元素的集合X，存在一個BIBD，它有N=t(12t+1)個區(qū)組，每個區(qū)組由dv=4個元素組成，每個元素恰好在dc=4t個區(qū)組中出現(xiàn)，每個元素對恰好在λ=1個區(qū)組中出現(xiàn)。用GF(pm)域的元素α-∞=0,α0=1,α,α2,…,α12t-1來表示集合X的12t+1=pm個元素。于是，X的BIBD可由下述t個基本區(qū)組完全確定：

Bi={0,α2i,α2i+4t,α2i+8t}。

(3)

其中0≤i

H=[Q0,Q1,…,Qt-1]。

(4)

由于λ=1，并且H具有廣義循環(huán)形式，因此，H的零空間給出了一個長度為N=t(12t+1)的QC-BIBD-LDPC碼，其girth至少為6。對于1≤v≤t，可以靈活地選擇v個循環(huán)陣Q0，Q1，…，Qv-1來構造如下矩陣：

(5)

表1在素域GF(12t+1)中本原元α滿足α4t-1=αc時參數(shù)的取值

Tab.1 A list parameters that the prime field CF(12t+1) has a primitive elementαsuch that the conditionα4t-1=αcholds

t12t+1(α，c)113(2，1)673(5，33)897(5，27)

2)I-B類設計

與I-A類設計相似，令t是滿足20t+1=pm的1個正整數(shù)，其中p是1個素數(shù)。假設GF(pm)域有1個本原元α滿足α4t+1=αc，其中c是1個小于pm的正奇數(shù)。X的BIBD由下述t個基本區(qū)組完全確定：

Bi={α2i,α2i+4t,α2i+8t,α2i+12t,α2i+16t}。

(6)

表2在素域GF(20t+1)中本原元α滿足α4t+1=αc時參數(shù)的取值

Tab.2 A list of parameters that the prime field GF(20t+1)has a primitive elementαsuch that the conditionα4t+1=αcholds

t20t+1(α，c)241(6，3)361(2，23)12241(7，179)14281(3，173)21421(2，227)

1.3 Ⅱ類QC-BIBD-LDPC碼

令t是滿足4t+1=pm的1個正整數(shù)，即4t+1是1個素數(shù)的冪。令k=3，GF(pm)域中的每個元素重復3次，可得到具有kq=3(4t+1)個元素的集合X。 假設GF(pm)域有一個本原元α滿足(αc+1)/(αc-1)=αd， 其中c和d是2個正奇數(shù)。于是，對于具有kq=3(4t+1)個元素的集合X， 存在1個BIBD，它的參數(shù)如下：M=3(4t+1)，N=3t(4t+1)，dv=4，dc=4t，λ=1。 于是，X的BIBD由下述基本區(qū)組完全確定：

其中0≤i

Ⅱ類BIBD設計的廣義多進制循環(huán)矩陣H具有如下形式：

(8)

其中，

M=[M1,M2,…,Mt]，

(9)

C=[C1,C2,…,Ct]。

(10)

式中：Mi和Ci為(4t+1)×(4t+1)的廣義循環(huán)矩陣；O為一個(4t+1)×t(4t+1)零矩陣；循環(huán)陣Mi和Ci分別是通過將GF(pm)域中的每個元素逐個加到第i個基本區(qū)組Bi中的前2個元素和后2個元素上而得到部分塊的廣義二維pm重擴展。Mi和Ci的行重和列重都為2。

表3 在素域GF(4t+1)中本原元α滿足(αc+1)/(αc-1)=αd時參數(shù)的取值

對于2≤v≤t，可以分別刪除矩陣M，C和O中的后t-v個循環(huán)陣，這樣可以得到3個新的矩陣去替代原來的M，C和O，其形式如式(8)所示。H(2)的零空間給出的是II類多進制QC-BIBD-LDPC碼，碼長為N=v(4t+1)， 最小距離至少為5。表3給出了部分t， 4t+1，α和c的取值表，以使在素域GF(4t+1)中存在滿足(αc+1)/(αc-1)=αd的本原元α。

1.4 Ⅲ類QC-BIBD-LDPC碼

令t是滿足4t+1=pm的1個正整數(shù)，其中p是1個素數(shù)。令k=5，GF(pm)域中的每個元素重復5次，可得到具有kq=5(4t+1)個元素的集合X。 假設GF(pm)域有一個本原元α滿足(αc+1)/(αc-1)=αd， 其中c和d是2個正奇數(shù)。于是，對于具有kq=5(4t+1)個元素的集合X， 存在一個BIBD，它的參數(shù)如下：M=5(4t+1)，N=5t(4t+1)，dv=5，dc=5t，λ=1，X的BIBD由下述基本區(qū)組完全確定：

(11)

其中，0≤i

Ⅲ類BIBD設計的廣義多進制循環(huán)矩陣H具有如下形式：

其中M和C如式(9)和式(10)所示，D=[D1,D2,…,Dt]， 具有與M和C相同的形式。循環(huán)陣Mi，Ci，Di分別是通過將GF(pm)中的每個元素逐個加到第i個基本區(qū)組Bi中的前2個元素、接著的中間2個元素、最后1個元素0上而得到部分塊的廣義二維pm重擴展。通過刪除后t-v個循環(huán)陣得到H(3)，其零空間給出的是Ⅲ類多進制QC-BIBD-LDPC碼，碼長為N=5v(4t+1)，最小距離至少為6。

2 仿真結果及性能分析

本節(jié)給出上述由BIBD構造出的多進制QC-BIBD-LDPC碼采用FFT-QSPA譯碼時的性能，并與相同比特長度的RS碼進行比較。所有仿真中的信號均采用BPSK調(diào)制，且在雙邊功率譜密度為N0/2的AWGN信道中傳輸。譯碼采用FFT-QSPA算法且最大迭代次數(shù)設置為50。

圖1 采用FFT-QSPA譯碼的128-ary (146,74) QC- BIBD-LDPC碼和采用BM算法GF(28)域上的 (128,64) RS碼的誤碼和收斂性能Fig.1 Error performances and rate of decoding convergence of the 128-ary(146,74)QC-BIBD-LDPC code decoded with the FFT-QSPA and the(128,64)RS code over GF(28) decoded with the BM algorithm

對于Ⅱ類多進制QC-BIBD-LDPC碼，取t=9，v=9，rt=13，可設計出1個111×999的多進制校驗矩陣H(2)， 其列重和行重分別是4和8。H(2)的零空間給出1個碼率為0.8919的4-ary (999,891) QC-BIBD-LDPC碼。為了與其他方法構造的多進制和二進制LDPC碼比較，給出了同比特長度的4-ary (999,888) Mackay LDPC碼、二進制(1998,1776) Mackay LDPC碼以及GF(28)域上(250,222)RS碼的誤碼和迭代性能比較。可以看出,相比于二進制LDPC碼來說構造出的多進制LDPC碼在誤碼和迭代性能上所具有的優(yōu)勢。對于不同構造方法相同參數(shù)的多進制LDPC碼，采用FFT-QSPA譯碼復雜度是相同的(復雜度為O(qlog2q))，且低于QSPA譯碼算法(復雜度為O(q2))，高于二進制信度傳播(belief propagation，BP)譯碼算法(復雜度為O(1))。對于Ⅲ類多進制QC-BIBD-LDPC碼，取t=3，v=2，rt=1， 可設計出碼率為0.5的16-ary (130,65) QC-BIBD-LDPC碼。這類LDPC碼的FFT-QSPA和RS碼BM算法的誤碼性能和迭代性能如圖3所示，可以得出與Ⅰ類和Ⅱ類多進制BIBD-LDPC碼相似的結論。

圖2 4-ary (999,891) QC-BIBD-LDPC碼、4-ary (999,888) Mackay LDPC碼和GF(28)域上的 (250,222)縮短RS碼的誤碼和迭代性能比較Fig.2 Error performances and average numbers of iterations for the 4-ary(999,891)QC-BIBD-LDPC code,4-ary(999,888) Mackay LDPC code and the(250,222)shortened RS code over GF(28)

圖3 采用FFT-QSPA譯碼的16-ary (130,65) QC- BIBD-LDPC碼和采用BM算法GF(27)域上的 (74,38)縮短RS碼的誤碼和迭代性能Fig.3 Error performances and average numbers of iterations of the 16-ary(130,65)QC-BIBD-LDPC code,decoded with the FFT-QSPA and the(74,38)shortened RS code over GF (27)decoded with the BM algorithm

3 結 語

在應對突發(fā)噪聲和混合類型噪聲上，多進制碼比二進制碼更為有效。對于隨機噪聲以及突發(fā)噪聲和干擾同時存在的通信系統(tǒng)或數(shù)據(jù)存儲系統(tǒng)來說，多進制LDPC碼是一種現(xiàn)代高效糾錯碼。本文提出的基于BIBD的多進制LDPC碼的構造方法，首先在素域GF(pm)上構造出基本區(qū)組，然后對這些區(qū)組在GF(2l)域進行廣義二維pm重擴展得到相應的多進制校驗矩陣。在提出規(guī)則的框架下構造出的多進制LDPC碼具有廣義QC特性，編碼和譯碼復雜度低，其Tanner圖沒有長度為4的環(huán)路，采用低復雜度FFT-QSPA譯碼時具有很好的性能。仿真結果表明，構造出的多進制QC-BIBD-LDPC碼具有快速收斂的特性，在性能上相比于同比特長度的RS來說具有明顯的編碼增益。所以，在通信和存儲應用領域本文提出的多進制LDPC碼具有替代RS碼的潛能。

[1] DAVEY M C,MACKAY D J C.Low-density parity check codes over GF(q)[J].IEEE Communications Letters,1998,2(6):165-167.

[2] BARNAULT L,DECLERCQ D.Fast decoding algorithm for LDPC over GF(2q)[C]//IEEE Information Theory Workshop.Paris,France:IEEE,2003:70-73.

[3] MACKAY D J C.Good error-correcting codes based on very sparse matrices[J].IEEE Transactions on Information Theory,1999,45(2):399-431.

[4] DIAO Q,ZHOU W,LIN S,et al.A transform approach for constructing quasi-cyclic Euclidean geometry LDPC codes[C]//2012 Information Theory and Applications Workshop.San Diego,USA:IEEE,2012:204-211.

[5] ZENG L,LAN L,TAI Y Y,et al.Constructions of non-binary quasi-cyclic LDPC codes:A finite field approach[J].IEEE Transactions on Communications,2008,56(4):545-554.

[6] HUANG Q,DIAO Q,LIN S,et al.Cyclic and quasi-cyclic LDPC codes on constrained parity-check matrices and their trapping sets[J].IEEE Transactions on Information Theory,2012,58(5):2648-2671.

[7]CHEN C,BAI B,WANG X.Construction of nonbinary quasi-cyclic LDPC cycle codes based on singer perfect difference set[J].IEEE Communications Letters,2010,14(2):181-183.

[8] KOU Y,LIN S,FOSORIER M P C.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.

[9] AMMAR B,HONARY B,KOU Y,et al.Construction of low-density parity-check codes based on balanced incomplete block designs[J].IEEE Transactions on Information Theory,2004,50(6):1257-1269.

[10] LAN L,TAI Y Y,LIN S,et al.New constructions of quasi-cyclic LDPC codes based on special classes of BIBD′s for the AWGN and binary erasure channels[J].IEEE Transactions on Communications,2008,56(1):39-48.