BIBD 循環(huán)置換矩陣的多進制LDPC碼構造?

劉冰，陶偉，竇高奇，高俊

（1.解放軍91469部隊，北京100841；2.海軍裝備研究院，北京100161；3.海軍工程大學電子工程學院，武漢430033）

BIBD 循環(huán)置換矩陣的多進制LDPC碼構造?

劉冰1，3，陶偉2，3，竇高奇3，高俊3

（1.解放軍91469部隊，北京100841；2.海軍裝備研究院，北京100161；3.海軍工程大學電子工程學院，武漢430033）

提出了基于均衡不完全區(qū)組設計（Balanced Incomplete Block Design，BIBD）的多進制準循環(huán)LDPC（Low-Density Parity-Check）碼代數構造方法。在該構造方法中提出了廣義多進制位置向量的概念，并根據廣義多進制位置向量和BIBD法對指數矩陣進行廣義二維擴展，構造出具有循環(huán)置換子矩陣的多進制校驗矩陣，由此得到girth不小于6的多進制LDPC碼。仿真結果表明，采用FFT-QSPA（基于快速傅里葉變換的多進制和積算法）對構造出的LDPC碼進行譯碼，在AWGN信道下相比于同參數的RS碼來說可以取得明顯的編碼增益，并且優(yōu)于多進制Mackay碼。

多進制低密度奇偶校驗碼；準循環(huán)；均衡不完全區(qū)組；廣義多進制位置向量；二維擴展

1 引言

均衡不完全區(qū)組設計（Balanced Incomplete Block Design，BIBD）［1-2］可用于構造多進制低密度奇偶校驗（Low-Density Parity-Check，LDPC）碼，其是組合數學中組合設計的一個重要問題。BIBD構造法屬結構化構造法［3-6］，相比于隨機化構造法［7，8］，具有特定的結構，尤其是循環(huán)或準循環(huán)（Qusic-Cyclic，QC）結構，優(yōu)勢在于編碼實現簡單，僅用簡單的移位寄存器就可實現線性化的編碼復雜度［9］，這對工程的實際應用具有重要的作用和意義。將二進制LDPC碼擴展到高階伽羅華域上形成多進制LDPC碼［10］，一般來說，精心設計的多進制LDPC碼具有較二進制更好的性能，特別是在中短幀長度。但是多進制LDPC碼面臨著兩大難題：編碼和譯碼的復雜度過高。對于編碼來說，可以采用準循環(huán)結構的LDPC碼，達到線性化編碼的目的［9］；而對于譯碼來說，基于快速傅里葉變換的多進制和積算法（Fast Fourier Transform based q-ary Sum-Product Algorithm，FFT-QSPA）［11］在取得優(yōu)越性能的同時，有效地降低了多進制LDPC碼的譯碼復雜度。

準循環(huán)LDPC碼作為一類非常重要的LDPC碼分支，其構造方法汲取和借鑒了代數、幾何等領域的數學理論，多角度迅速發(fā)展。Shu Lin課題研究小組首次提出了基于有限幾何［12］、有限域［13］、循環(huán)置換矩陣［14］和BIBD［3，15］等理論的系統化二進制LDPC碼構造方法。之后在二進制構造的基礎上首次提出了基于有限幾何［16］和有限域［17］的多進制準循環(huán)LDPC碼的系統化構造方法，相比于RS碼而言，構造出的碼字在AWGN信道下可以取得很大的編碼增益。Bassem Ammar將BIBD的一種特殊子類首次運用于二進制LDPC碼的設計中［2］，該LDPC碼校驗矩陣的構造方法采用的是BIBD關聯矩陣。BIBD構造多進制校驗矩陣時，其元素取自GF（pm），其中p是素數，m為正整數，但是低復雜度的FFT-QSPA只能對GF（2l）域上構造的碼字進行譯碼［11，18］，因此在采用BIBD循環(huán)置換矩陣構造多進制LDPC碼時，兩者的適用前提條件是有所區(qū)別的。針對這一問題，本文提出了基于廣義多進制位置向量的廣義二維擴展方法以及兩類基于BIBD廣義循環(huán)置換矩陣（Circulant Permutation Matrix，CPM）的多進制QC LDPC碼的構造方法，該方法可取得girth至少為6的規(guī)則多進制QC LDPC碼。通過對指數矩陣進行基于廣義多進制位置向量的水平擴展和基于部分周期循環(huán)特性的垂直擴展，使得構造校驗矩陣非零元素的位置和數值分別取自GF（pm）和GF（2l）域。提出的廣義二維擴展優(yōu)勢在于：可適用于非2冪次大小循環(huán)置換子矩陣的構造和2的冪次大小循環(huán)置換子矩陣的拓展；構造出的多進制LDPC碼可采用低復雜度高性能的FFT-QSPA譯碼算法。

文章的組織結構如下：第2節(jié)提出了基于廣義多進制位置向量的廣義二維擴展方法，第3節(jié)由上述擴展方法構造出了兩類BIBD循環(huán)置換矩陣的多進制LDPC碼，第4節(jié)通過仿真結果比較了構造出多進制LDPC碼的性能，最后是結束語。

2 BIBD與多進制準循環(huán)LDPC碼構造

多進制規(guī)則LDPC碼C由多進制稀疏校驗矩陣H的零空間所定義，其具有以下結構化性質：每行的重量（非零元素的個數）為dc；每列的重量為dv；行列（RC）約束，即任何兩行（或兩列）之間位置相同的非零元素個數不大于1。這樣構造出來的校驗矩陣是規(guī)則的，由其零空間給出的碼C稱為（dv，dc）規(guī)則LDPC碼。RC約束保證了兩點：由H的零空間給出的LDPC碼C的Tanner圖girth至少為6；碼的最小距離至少為dv+1。如果H的行與（或）列具有不同的重量，那么H的零空間將給出一個非規(guī)則LDPC碼。LDPC碼的誤碼性能由碼結構特性的諸多因素共同決定，主要因素有Tanner圖的girth、短環(huán)的結構、處于某一碼字上短環(huán)的數量、校驗矩陣的選擇和碼字的最小距離等。目前只能通過仿真和基本的分析來考查這些起決定作用的因素，它們之間還沒有明確的結論性關系，有待進一步研究。最影響碼字性能的短環(huán)是長度為4的環(huán)，所以這類短環(huán)在校驗矩陣的構造時應予以避免，這是目前絕大多數LDPC碼構造時首要考慮的問題，同時也滿足了定義中的行列約束性質。

具有q個元素的阿貝爾群G的一個BIBD是指G的n個r子集，記為B1，B2，…，Bn，稱為區(qū)組（Blocks），它們滿足如下條件［1］：每個元素恰好在n個區(qū)組中的k個出現；任一元素對恰好在n個區(qū)組中的λ個出現；每個區(qū)組中元素的個數r與X中的元素總數q相比非常小。于是，一個BIBD由n，v=q，r，k和λ5個參數來刻畫。除了用區(qū)組的表示方式外，一個BIBD可以用一個GF（q）域上的q×n關聯矩陣H=［hi，j］來描述：其行對應著X的q個元素；其列對應著該設計的n個區(qū)組；當且僅當第i個元素xi

屬于第j個區(qū)組Bj時，hi，j≠0且hi，j∈GF（q），否則，hi，j=0。這個矩陣被稱為設計的關聯矩陣H，H的列重和行重分別是r和k。根據BIBD的第2個條件，H的兩個行向量具有λ個公共的1分量。如果λ=1，H就滿足了LDPC碼定義的所有性質，于是H的零空間給出了一個長度為n的（dv，dc）規(guī)則LDPC碼，其Tanner圖中沒有長度為4的環(huán)。這是基于BIBD最直接構造LDPC碼的方法。對于（n，v，r，k，1）BIBD素域構造方法可查閱相關文獻［1-3，15］。而本文構造的多進制校驗矩陣的基矩陣是基于Bose BIBD理論，首先闡述下面一個定理［1］。

定理：令G=｛x（1），x（2），…，x（q）｝是具有q個元素的阿貝爾群。對于G中的每一個元素x（i），重復f次，并記為x（i）1，x（i）2，…，x（i）f，這樣通過群G可以得到具有fq個元素的集合X。將fq個元素分為q組，X的s個r子集，記為B1，B2，…，Bs，稱為區(qū)組（Blocks），它們滿足如下條件：在s個區(qū)組中的sr個元素中，k個元素屬于q組中的一組；s個區(qū)組中元素的差是對稱重復的，且每一個出現λ次。

通過將G中每個元素逐個加到每一個區(qū)組B1，B2，…，Bs上，可以得到一個具有參數v=fq，n=sq，r，k和λ的BIBD，這里，區(qū)組B1，B2，…，Bs被稱為基本區(qū)組。本文校驗矩陣指數矩陣的構造則是建立在基本區(qū)組上。

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

其中，l∈Z Z；rt為GF（2l）域中所有非零元素重復的周期數，不足一個周期的，記為一個周期，并計入rt中；rc是重復周期的帶分數表示，整數部分表示重復的整數周期數，分數中分母表示一個周期的長度，分子表示不足一個周期的周期長度。l的取值與pm的值關系如下：

式中，l∈Z Z，「·表示向上取整。

令β是GF（2l）域的本原元。β-∞=0，β0=1，β，β2，…，β2l-2表示GF（2l）域中的所有元素，并且β2l-1=1。將基于BIBD區(qū)組的廣義多進制位置向量定義為z（i）=（z0，z1，…，zpm-1），其向量取值對應的是GF（2l）域中的pm個非零元素，其中zi= βimod（2l-1），i∈Bi，而其它所有分量為0。Bi中的元素稱為循環(huán)置換矩陣的位置數，決定著校驗矩陣非零值的位置。因此，z（i）是GF（2l）域上的pm重向量，其重量為1。

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

二維pm重擴展是由垂直擴展和水平擴展兩部分組成，對于某個元素δ，dispv（δ）=［δ，δ+1，…，δ+pm-1］T為該元素的垂直擴展，而disph（δ）=z（δ）為該元素的水平擴展。根據上述基本概念和提出規(guī)則，可以對基本區(qū)組Bi中所有元素進行廣義二維pm重擴展得到廣義多進制準循環(huán)矩陣。由于多進制校驗矩陣非零值位置和數值的選取分別是建立在GF（pm）和GF（2l）這兩個不同域中，構造出的二維pm重矩陣非零元素的分布具有兩種情形：當rt=1時，在GF（2l）域上只具有部分域元素循環(huán)（rc＜1）或循環(huán)（rc=1）的特性；當rt≥2時，所有GF（2l）域非零元素個數一般在矩陣中分布不均，但是當2l-1=rcpm時，非零元素分布將是均勻的。

下面將闡述通過BIBD構造的基矩陣擴展到GF（2l）域多進制準循環(huán)校驗矩陣的一般方法。假設通過BIBD方法構造出n×r的GF（pm）域下指數矩陣：

式中，ei，j∈GF（pm），E中的每一行是一個BIBD的基本區(qū)組。

Ei具有如下的結構特性：每一列都是GF（pm）中循環(huán)順序的pm個元素；任意兩列所有位置的元素各不相同；任意兩行所有位置的元素各不相同。根據這三點特性可知，來自不同兩行垂直擴展的矩陣Ei和Ej不會在同一位置上具有相同的元素，這就保證了RC約束條件。然后將Ei進行水平擴展，就可構造出一個n×r陣列pm×pm循環(huán)置換矩陣Q：

二維pm重擴展disp（ei，j）可以理解為將E中的一個元素ei，j擴展成一個循環(huán)置換矩陣Qi，j，對于任一整數對（dv，dc），其中1≤dv≤n，1≤dc≤r，令Q（dv，dc）是Q的dv×dc子陣列，則Q（dv，dc）就是一個GF（2l）域上的dvpm×dcpm矩陣，同時也滿足RC約束，其零空間給出的就是長度為dcpm的多進制CPM-BIBD-LDPC碼。其碼率至少為1-dv／dc，girth至少為6。令H=QT，則H是一個r×n陣列pm×pm循環(huán)置換矩陣。對于任一整數對（dv，dc），其中1≤dv≤r，1≤dc≤n，令H（dv，dc）是H的dv×dc子陣列，則H（dv，dc）同樣可表述為一個GF（2l）域上的dvpm×dcpm矩陣，同時也滿足RC約束，其零空間給出的就是長度為dcpm的多進制CPM -BIBD-LDPC碼。其行重為dc，列重為dv，碼率至少為1-dv／dc，H滿足RC約束，因此，girth至少也為6。

3 BIBD循環(huán)置換矩陣多進制LDPC碼

3.1 第1類CPM-BIBD-LDPC碼

令t是滿足12t+1=pm的一個正整數，其中p是一個素數，m是一個正整數，也就是說，12t+1是一個素數的冪。假設GF（12t+1）域有一個本原元α滿足α4t-1=αc，其中c是一個小于pm的正奇數，表1給出了部分t、12t+1及所對應的全部α和c的取值表，以使在素域GF（12t+1）中存在滿足α4t-1=αc的本原元α，其中本原元α是用實數來表示的。

表1 在素域GF（12t+1）中本原元α滿足α4t-1=αc時參數的取值Table 1 A listof parameters that the prime field GF（12t+1）has a primitive elementαsuch that the conditionα4t-1=αcholds

于是，對于具有q=12 t+1個元素集合G中每個元素重復f=1次得到集合X，存在一個BIBD，它具有n=t（12 t+1）個區(qū)組，每個區(qū)組由r=4個元素組成，每個元素恰好在k=4 t個區(qū)組中出現，每個元素對恰好在λ=1個區(qū)組中出現。用GF（12 t+1）域的元素α-∞=0，α0=1，α，α2，…，α12t-1來表示集合X的12 t+1=pm個元素。于是，X的BIBD可由下述t個基本區(qū)組完全確定：

式中，0≤i＜t。

對于給定的第1類BIBD的每一個基本區(qū)組，可形成一個t×4的基矩陣E（1）：

通過廣義二維12t+1重擴展后可得多進制的（12t+1）×（12t+1）廣義循環(huán)置換矩陣的t×4陣列：

可以很清楚地看出，Q（1）和H（1）分別是具有（12 t+1）×（12 t+1）的多進制循環(huán)置換矩陣的t×4

和4×t陣列，對于每一個子矩陣Qj，i（Hi，j）都是（12 t+1）×（12 t+1）的多進制循環(huán)置換矩陣，行重（列重）和列重（行重）分別為4和t。由于對Q（1）（dv，dc）和H（1）（dv，dc）的分析是一致的，只是dv和dc的取值范圍不同。下面以H（1）為例，對于1≤dv≤4，1≤dc≤t，令H（1）（dv，dc）是H（1）的dv×dc

子陣列，則H（1）（dv，dc）是dv（12 t+1）×dc（12 t+1）的多進制矩陣，dv、dc恰為矩陣的列重和行重，H（1）

（dv，dc）的零空間給出了一個（dv，dc）的規(guī)則多進制CPM-BIBD-LDPC碼。碼長為N=dc（12 t+1），最小距離至少為dv+1，碼率至少為1-dv／dc。

3.2 第2類CPM-BIBD-LDPC碼

令t是滿足20 t+1=pm的一個正整數，其中p是一個素數。假設GF（20 t+1）域有一個本原元α滿足α4t+1=αc，其中c是一個小于pm的正奇數。表2給出了部分t、20 t+1及所對應的全部α和c的取值表，以使在素域GF（20 t+1）中存在滿足α4t-1=αc的本原元α。

表2 在素域GF（20t+1）中本原元α滿足α4t+1=αc時參數的取值Table 2 A list of parameters that the prime field GF（20 t+1）has a primitive elementαsuch that the conditionα4t+1=αcholds

于是，對于具有q=20 t+1個元素的集合X，存在一個BIBD，它有n=t（20 t+1）個區(qū)組，每個區(qū)組由r=5個元素組成，每個元素恰好在k=5 t個區(qū)組中出現，每個元素對恰好在λ=1區(qū)組中出現。用GF（20 t+1）域的元素α-∞=0，α0=1，α，α2，…，α20t-1來表示集合X的20 t+1=pm個元素。于是，X的BIBD由下述t個基本區(qū)組完全確定：

式中，0≤i＜t。

對于給定的第2類BIBD的每一個基本區(qū)組，可形成一個t×4的基矩陣E（2）：

E（2）的垂直擴展其實是通過將GF（pm）中的每個元素逐個加到這t個基本區(qū)組的每一個上而得到BIBD的所有n=t（20 t+1）個區(qū)組。通過廣義二維20 t+1重擴展后可得到具有（20 t+1）×（20 t+1）廣義多進制循環(huán)置換矩陣的t×5陣列Q（2），令H（2）=

［Q（2）］T，Q（2）和H（2）都可作為多進制LDPC碼的校驗矩陣。同樣，對于H（2），1≤dv≤5，1≤dc≤t，而對于Q（2），1≤dv≤t，1≤dc≤5，H（2）（dv，dc）和Q（2）（dv，dc）分別是H（2）和Q（2）中dv×dc大小的子陣列，其零空間也給出了一個（dv，dc）的規(guī)則多進制CPM-BIBD-LDPC碼。碼長為N=dc（20 t+1），最小距離至少為dv+1，碼率至少為1-dv／dc。

4 仿真結果及性能分析

本節(jié)給出兩類由BIBD構造出的多進制CPMBIBD-LDPC碼采用FFT-QSPA譯碼時的性能，并與相同比特長度的RS碼和多進制Mackay LDPC碼進行比較。所有仿真中的信號均采用BPSK調制，且在雙邊功率譜密度為N0／2的加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道中傳輸。FFT-QSPA算法的最大迭代次數設置為50。

對于第1類多進制CPM-BIBD-LDPC碼，取t =6，該設計具有如下參數：v=q=73，n=438，r= 4，k=48和λ=1，這樣可以得到一個6×4的基矩陣E（1）。為了設計一列重dv=3、行重dc=6的多進制LDPC碼，首先只取E（1）中的前6×3矩陣作為構造多進制CPM-BIBD-LDPC碼的基矩陣E（1）（3，6）：

對E（1）（3，6）進行廣義二維擴展的矩陣經轉置后可得H（1）（3，6），它是一個由3×6的73×73的廣義循環(huán)置換矩陣所構成校驗矩陣，其非零值的位置和數值分別建立在GF（73）和GF（27）域上。由構造出的H（1）（3，6）的零空間將給出一個碼率為0.504 6

的128-ary（438，221）CPM-BIBD-LDPC碼。采用FFT-QSPA譯碼算法，該碼的性能如圖1所示。為了便于比較，我們也給出了同比特長度RS碼的BM算法的誤碼性能。在FER為10-4處，相對于GF（29）

域上采用BM算法的（340，172）RS碼來說，取得了大約3.80 dB的編碼增益。

圖1 采用FFT-QSPA譯碼的128-ary（438，221）CPM-BIBDLDPC碼和采用BM算法GF（29）域的（340，172）RS碼的誤碼性能Fig.1 Error performances of the 128-ary（438，221）BIBD-QCLDPC code decoded with the FFT-QSPA and the（340，172）RS code over GF（29）decoded with the BM algorithm

為了構造出不同的2l進制的LDPC碼，根據式。因此，可以據此構造出128-ary、64-ary、32-ary CPM-BIBD -LDPC碼。如圖2所示，首先我們將128-ary CPM -BIBD-LDPC碼與幾乎同碼率的128-ary Mackay LDPC碼作一比較，相比于Mackay LDPC碼，在FER為10-4處取得了大約0.14 dB的編碼增益，因而本文提出的多進制CPM-BIBD-LDPC碼具有更好的誤碼性能。通過對不同進制的LDPC碼比較可以看出，隨著進制數的減少，誤碼性能也相對變好，但是這種性能的差距不大，進制數的減少同時也能降低譯碼的復雜度。這種現象Mackay也曾指出［19］：隨著域階數的增加，其誤碼性能并不總是單調提升，這一現象的產生與校驗矩陣的構造密切相關。

圖2不同進制數下的（438，221）CPM-BIBD-LDPC碼和128-ary Mackay LDPC碼的性能比較Fig.2 Performances comparison of（438，221）CPM-BIBD-LDPC codes over different Galois fields and a 128-ary Mackay LDPC code

圖3 給出了4種LDPC碼的平均迭代次數曲線圖，其反映了如下3點：構造出的多進制LDPC碼具有很好的收斂特性；隨著進制數的減少，其收斂越快，但是之間的差距并不大；相比于Mackay LDPC碼，本文構造的LDPC碼誤碼性能和收斂特性更為優(yōu)越。

圖3 采用FFT-QSPA譯碼不同進制數下CPM-BIBDLDPC碼和Mackay LDPC碼的平均迭代次數Fig.3 Average numbers of iterations for decoding CPM-BIBD-LDPC codes over different Galois fields and a Mackay LDPC code with the FFT-QSPA

對于第2類多進制CPM-BIBD-LDPC碼，取t =3，這樣可以得到一個3×5的基矩陣E（2）：

利用第2節(jié)提出的二維擴展方法可設計出一個183×305的多進制校驗矩陣Q（2）（3，5），其列重和行重分別是3和5。Q（2）（3，5）的零空間給出一個碼率為0.406 6的64-ary（305，124）CPM-BIBD-LDPC碼。該LDPC碼的FFT-QSPA和RS碼的BM算法的誤碼性能和迭代性能如圖4所示。與上述分析類似，在BER為10-4處，相對于GF（28）上采用BM算法的（229，93）RS碼來說，取得了大約3.90 dB的編碼增益。

5 結束語

多進制碼的優(yōu)勢在于應對突發(fā)噪聲和混合類型噪聲比二進制碼更為有效，多進制碼中的RS碼廣泛應用于隨機噪聲、突發(fā)噪聲和干擾同時存在的通信系統或數據存儲系統中，而目前多進制LDPC碼的研究呈現上升趨勢，表現出了具有替代RS碼的潛能。本文提出了基于BIBD循環(huán)置換矩陣的多進制LDPC碼構造方法，多進制校驗矩陣中非零元素位置的確定源于對基本區(qū)組的選擇，而非零元素數值的選取則是建立在提出的廣義多進制位置向量的基礎上。在這種規(guī)則下構造出的多進制LDPC碼具有QC特性，編譯碼復雜度低，其Tanner圖沒有長度為4的環(huán)路，提出的構造方法可適用于所有素數大小的循環(huán)置換子矩陣組成的多進制校驗矩陣，具有很大的靈活性和可擴展性。仿真結果表明，在采用低復雜度FFT-QSPA譯碼時具有很好的糾錯性能和良好的收斂特性，在幾乎相同的比特長度上，本文構造的多進制LDPC碼比RS碼和多進制Mackay LDPC碼具有更好的性能。

［1］Bose RC.On the construction of balanced incomplete design［J］.Annals of Eugenics，1939，9（1）：353-399.

［2］Ammar B，Honary B，Kou Y，et al.Construction of lowdensity parity-check codes based on balanced incomplete block designs［J］.IEEE Transactions on Information Theory，2004，50（6）：1257-1268.

［3］Lan L，Tai Y Y，Lin S，et al.New constructions of quasicyclic 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.

［4］Zhou B，Kang J，Song S，etal.Construction of non-binary quasi-cyclic LDPC codes by arrays and array dispersions［J］.IEEE Transactions on Communications，2009，57（6）：1652-1662.

［5］Chen C，Bai B，Wang X.Construction of nonbinary quasicyclic LDPC cycle codes based on singer perfect difference set［J］.IEEECommunications Letters，2010，14（2）：181-183.

［6］Kang J，Huang Q，Zhang L，et al.Quasi-cyclic LDPC codes：An algebraic construction［J］.IEEE Transactions on Communications，2010，58（5）：1383-1396.

［7］Chen X，Men A，Yang B，etal.Construction of LDPC codes over GF（q）withmodified progressive edge growth［J］.Journal of China Universities of Posts and Telecommunications，2009，16（5）：103-106.

［8］Shebl S，El-Fishawy N，Elazm A A，etal.A random construction of LDPC codes using a sub-optimal search algorithm［C］／／Proceedings of2009 National Conference on National Radio Science.New Cairo，Egypt：IEEE，2009：1-10.

［9］Li Z，Chen L，Zeng L，et al.Efficient encoding of quasicyclic low-density parity-check codes［J］.IEEE Transactions on Communications，2006，54（1）：71-81.

［10］Song S，Zhou B，Lin S，et al.A unified approach to the construction of binary and nonbinary quasi-cyclic LDPC codes based on finite fields［J］.IEEE Transactions on Communications，2009，57（1）：84-93.

［11］Barnault L，Declercq D.Fast decoding algorithm for LDPC over GF（2q）［C］／／Proceedings of 2003 IEEE Information TheoryWorkshop.Paris，France：IEEE，2003：70-73.

［12］Kou Y，Lin S，Fossorier M P C.Low-density paritycheck codes based on finite geometries：A rediscovery and new results［J］.IEEE Transactions on Information Theory，2001，47（7）：2711-2736.

［13］Lan L，Zeng L，Tai Y Y，et al.Construction of quasicyclic LDPC codes for AWGN and binary erasure channels： A finite field approach［J］.IEEE Transactions on Information Theory，2007，53（7）：2429-2458.

［14］FossorierM PC.Quasi-cyclic low-density parity-check codes from circulant permutationmatrices［J］.IEEE Transactions on Information Theory，2004，50（8）：1788-1793.

［15］Djordjevic IB.Quantum LDPC codes from balanced incomplete block designs［J］.IEEE Communications Letters，2008，12（5）：389-391.

［16］Zeng L，Lan L，Tai Y Y，et al.Construction of nonbinary cyclic，quasi-cyclic and regular LDPC codes：A finite geometry approach［J］.IEEE Transactions on Communications，2008，56（3）：378-387.

［17］Zeng L，Lan L，Tai Y Y，et al.Constructions of nonbinary quasi-cyclic LDPC codes：A finite field approach［J］.IEEE Transactions on Communications，2008，56（4）：545-554.

［18］Voicila A，Declercq D，Verdier F，et al.Low-complexity decoding for non-binary LDPC codes in high order fields［J］.IEEE Transactionson Communications，2010，58（5）：1365-1375.

［19］Davey M C，MacKay D.Low-density parity check codes overGF（q）［J］.IEEE Communications Letters，1998，2（6）：165-167.

LIUBing was born in Nanchang，Jiangxi Province，in 1984. He is now an engineer with the Ph.D.degree.His research interests include error control coding and signal processing for digital communications.

Email：liubing5275093＠hotmail.com

陶偉（1974—），男，黑龍江哈爾濱人，博士研究生，工程師，主要研究方向為差錯控制編碼和無線數據傳輸；

TAO Wei was born in Harbin，Heilongjiang Province，in 1974.He is now an engineer and currently working toward the Ph.D.degree.His research interests include error control coding and wireless data transmission.

Email：alantao0451＠yahoo.com.cn

竇高奇（1981—），男，山西長治人，博士，講師，主要研究方向為差錯控制編碼和數字通信信號處理；

DOU Gao-qi was born in Changzhi，Shanxi Province，in 1981.He is now a lecturer with the Ph.D.degree.His research interests include error control coding and signal processing for digital communications.

Email：gqdou0917＠163.com

高?。?957—），男，江蘇泰興人，1989年獲博士學位，現為教授、博士生導師，主要研究方向為信道編碼和數字通信。

GAO Jun wasborn in Taixing，Jiangsu Province，in 1957.He received the Ph.D.degree from Beijing Institute of Technology in 1989. He is now a professor and also the Ph.D.supervisor.His research interests include error control coding and digital communications.

Email：gaojunnj＠163.com

Construction of Nonbinary LDPC Codes Based on BIBD Circulant Perm utation M atrices

LIU Bing1，3，TAOWei2，3，DOU Gao-qi3，GAO Jun3
（1.Unit91469 of PLA，Beijing 100841，China；2.Naval Academy of Armament，Beijing 100161，China；3.College of Electronic Engineering，Naval University of Engineering，Wuhan 430033，China）

The algebraic method for constructing nonbinary quasi-cyclic（QC）low-density parity-check（LDPC）codes based on balanced incomplete block designs（BIBD）is presented.The generalized nonbinary location vector is proposed on constructions.A nonbinary matrix，which consists of nonbinary circulant submatrices，is formed by generalized two-dimensionalmatrix dispersion considering the generalized nonbinary location vector and BIBDmethod.The codes constructed by thismethod have girths at least6.Experimental results show that significant coding gains are achieved over Reed-Solomon codes of the same parameters under the AdditiveWhite Gaussian Noise（AWGN）channel with iterative decoding Fast Fourier Transform based q-ary Sum-Product Algorithm（FFT-QSPA）.And a good performance is also achieved over nonbinary Mackay LDPC codes with almost the same conditions.

nonbinary low-density parity-check（LDPC）codes；quasi-cyclic；balanced incomplete block design；generalized nonbinary location vector；two-dimensional dispersion

The National High-tech R＆D Program of China（863 Program）（2009AAJ128，2010AA7010422）；The National Science Foundation for Post-doctoral Scientists of China（200902671）

TN911.22

A

10.3969／j.issn.1001-893x.2011.09.006

劉冰（1984—），男，江西南昌人，博士，工程師，主要研究方向為差錯控制編碼和數字通信信號處理；

1001-893X（2011）09-0027-08

2011-02-18；

2011-08-30

國家高技術研究發(fā)展計劃（863計劃）項目（2009AAJ128，2010AA7010422）；國家博士后科學基金（200902671）