劉 冰 任席闖 崔 潔

（中國(guó)人民解放軍91469部隊(duì) 北京 100841）

1 引言

1998年，Davey和Mackay重新發(fā)現(xiàn)了多進(jìn)制LDPC（Low-DensityParity-Check）碼［1］，并提出了用于譯碼的多進(jìn)制和積算法（Q-arySum-ProductAlgorithm，QSPA），相比于二進(jìn)制LDPC碼來說取得了明顯的編碼增益，多進(jìn)制LDPC碼的出現(xiàn)為L(zhǎng)DPC碼的研究開拓了一個(gè)新的領(lǐng)域，也有許多關(guān)鍵問題亟待進(jìn)一步研究。多進(jìn)制LDPC碼除了具備二進(jìn)制LDPC碼的一般特性外，還具有獨(dú)特的優(yōu)勢(shì)，如當(dāng)碼長(zhǎng)較短時(shí)具有更好的糾錯(cuò)能力，更強(qiáng)的抗突發(fā)錯(cuò)誤能力，且適合高速率傳輸系統(tǒng)。

Tanner圖中環(huán)的大小和分布是影響多進(jìn)制LDPC碼性能的重要因素之一，特別是短環(huán)的存在會(huì)破壞變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)信息傳遞的獨(dú)立性假設(shè)，使相關(guān)信息在兩類節(jié)點(diǎn)之間傳遞，影響碼字的迭代收斂過程，造成譯碼性能急劇下降。一般構(gòu)造碼字之初就會(huì)考慮消除4環(huán)，而且此類研究成果已經(jīng)非常豐富［2～5］。Tanner圖中最短環(huán)的長(zhǎng)度稱之為 girth（圍長(zhǎng)）。小girth（最小環(huán)）會(huì)對(duì)低碼率、長(zhǎng)度較短的碼字影響較大，消除這類碼的短環(huán)或減少其分布可以帶來明顯的性能改善。另一方面，Tanner圖的girth還與碼的最小距離有關(guān)，一般girth越大，最小距離也將隨之增大，但最小距離并不隨girth增大而無限增大，一味地增大girth并不能提高碼字的性能［6］。因此，構(gòu)造大girth（girth≥8）的多進(jìn)制LDPC碼是多進(jìn)制LDPC碼的一個(gè)研究方向。

對(duì)于迭代譯碼的準(zhǔn)循環(huán)（Quasi-Cyclic，QC）LDPC碼來說，短環(huán)的存在不利于算法的收斂，性能損失的一部分原因歸咎于小girth的存在。目前，大多數(shù)構(gòu)造方法都考慮了消除4環(huán)，即girth至少為6。構(gòu)造出girth為8，甚至更大girth且具備低復(fù)雜度的多進(jìn)制QCLDPC碼是當(dāng)前的研究熱點(diǎn)之一［7～10］。構(gòu)造大girth的主要方法有直接構(gòu)造法和短環(huán)刪除法，其中直接構(gòu)造法是根據(jù)設(shè)計(jì)的規(guī)則使得校驗(yàn)矩陣達(dá)到大girth的特性。本文從大girth指數(shù)矩陣出發(fā)，提出了在不同域上廣義多進(jìn)制位置向量和廣義二維擴(kuò)展方法，采用直接構(gòu)造法確定短環(huán)線性約束方程，與大girth陣列碼結(jié)合構(gòu)造出了大girth多進(jìn)制陣列LDPC碼。

2 大girth多進(jìn)制準(zhǔn)循環(huán)LDPC碼

2.1 大girth指數(shù)矩陣構(gòu)造

陣列碼是一種準(zhǔn)循環(huán)的LDPC碼，其校驗(yàn)矩陣是由許多個(gè)的循環(huán)置換矩陣陣列所組成，形式為

其中，P是大小為 p×p的循環(huán)置換陣，p為素?cái)?shù)，陣列行序號(hào) a0，a1，…，ar-1是取值范圍為 [0，p-1]的不同整數(shù)。H的指數(shù)矩陣定義為

其中，ei，j=ai·j，0≤i≤r-1，0≤j≤n-1，W 表示校驗(yàn)矩陣H 的基矩陣。如果序列a0，a1，…，ar-1形成 等 差 數(shù) 列 ，即 對(duì) 于 i=0，1，…，r-2 ，ai+1-ai=d≠0，稱對(duì)應(yīng)的碼為等差陣列碼。如序列a0，a1，…，ar-1未形成等差數(shù)列，則稱之為非等差數(shù)列碼。

校驗(yàn)矩陣girth的控制主要放在指數(shù)矩陣層面上。任何奇偶校驗(yàn)矩陣H中長(zhǎng)度為2i的閉環(huán)可形成陣列行和陣列列的序號(hào)對(duì)(r0，n0)，(r0，n1)，(r1，n1)，(r1，n2)， …，(ri-1，n0) ， 其 中 ，rk≠rk+1，nk≠nk+1，ri-1≠r0， ni-1≠n0，k=0，1，…，i-1。通過閉環(huán)可得到一個(gè)重要的定理。

定理1［4］：矩陣 H 對(duì)應(yīng)的Tanner圖的girth至少為2(i+1)充要條件是

其中，2≤j≤i，0≤rk，rk+1≤m-1，0≤nk≤n-1，且r0=rr，rk≠rk+1，nk≠nk+1。 可 見 ，要 使 得girth≥2(i+1)，必須消除Tanner圖中環(huán)長(zhǎng)小于或等于2i的環(huán)。對(duì)于陣列碼來說，由于存在r0，r1，n0，n1，r0≠r1，n0≠n1，則 (ar0-ar1)(n0-n1)≠0 ，進(jìn)而得，根據(jù)定理1可知陣列碼的girth至少為6。

考慮校驗(yàn)矩陣girth為8和10的兩種情況，列重分別選取3和4。對(duì)于等差陣列碼，由式（3）可化為

為了得到大girth，要盡量消除短環(huán)或減少短環(huán)的數(shù)量。首先對(duì)等差陣列碼進(jìn)行分析，考慮girth為8的情況，由于陣列碼不存在4環(huán)的情況，只需從去除6環(huán)開始考慮。首先確定6環(huán)存在的條件。如果行重 r=3 ，陣列行序號(hào) r0，r1，r2∈{0，1，2} ，由于r0，r1，r2，n0，n1，n2互不相等，存在6環(huán)的陣列列選擇必定位于不同陣列列的序號(hào)上。不失一般性，取r0=0，r1=1，r2=2，由定理1可得如表1所示第一行存在6環(huán)的約束方程，只要在校驗(yàn)矩陣H選取的序列中，避免存在滿足約束方程的序列即可消除相應(yīng)的環(huán)長(zhǎng)。

圖1 存在8環(huán)的示例

對(duì)于表1中約束方程的計(jì)算，以存在8環(huán)，行重為 3 的 情 況 為 例 ，由 于 r0，r1，r2，r3∈{0，1，2} ，n0≠n1，n1≠n2，n2≠n3，n3≠n0，n0，n1，n2，n3是兩兩不相同的，因而矩陣中存在的環(huán)路需分3種情況：列號(hào)取值范圍分別為2列、3列和4列。對(duì)應(yīng)的示例圖如圖1所示。

表1 6環(huán)和8環(huán)存在的約束方程和避免6環(huán)和8環(huán)的列序列

對(duì)于2列的情況，假設(shè)n0=n2，n1=n3，存在8環(huán)的約束方程為

由于n0≠n1，滿足約束方程的充要條件是r0-r1+r2-r3=0。當(dāng) r0=0，r1=1，r2=2，r3=1時(shí)，其充要條件r0-r1+r2-r3=0總是會(huì)滿足的。在2列的情況下，這種8環(huán)是無法避免的。

對(duì)于3列的情況，可假設(shè)n0=n2或n1=n3，不失一般性，這里僅考慮n0=n2。存在8環(huán)的約束方程為

n0(r0-r1+r2-r3)-n1(r1-r2)+n3(r3-r0)=0（6）

由于陣列行序號(hào) r0，r1，r2，r3∈{0，1，2}，表2給出了3列情況下存在8環(huán)不重復(fù)的約束方程。

表2 列數(shù)為3存在8環(huán)的約束方程

對(duì)于4列的情況，存在8環(huán)的約束方程為n0(r0-r1)+n1(r1-r2)+n2(r2-r3)+n3(r3-r0)=0（7）

由于陣列行序號(hào) r0，r1，r2，r3∈{0，1，2}，表3給出了4列情況下存在8環(huán)不重復(fù)的約束方程。

表3 列數(shù)為4存在8環(huán)的約束方程

對(duì)于其他情況，分析方法與存在8環(huán)，行重為3的情況是類似的。具體的環(huán)約束方程和避免相應(yīng)環(huán)的部分可選取序列如表1所示。

從上述分析可知，等差陣列碼的girth不會(huì)大于8，在兩個(gè)陣列列中，當(dāng)r0=0，r1=1，r2=2，r3=1時(shí)，8環(huán)是不可避免的。而采用非等差數(shù)列碼可以在兩個(gè)不同的陣列列中避免這種8環(huán)的存在。

對(duì)于非等差數(shù)列碼，式（3）變?yōu)?/p>

如同等差數(shù)列碼的分析，對(duì)于2列的情況，假設(shè)n0=n2，n1=n3，存在8環(huán)的約束方程為

由于 ar0，ar1，ar2，ar3的集合域不在等差數(shù)列范圍內(nèi)選取，因而會(huì)帶來一些優(yōu)勢(shì)和問題：選擇的范圍擴(kuò)大，環(huán)約束的方程相應(yīng)增多，搜索序列的復(fù)雜度會(huì)相應(yīng)增加；可得到girth為10或12這樣更大girth的碼字。其分析與大girth等差陣列碼中尋求陣列序列方式相同，如表4所示給出了列重為3、陣列行序號(hào) ar0，ar1，ar2，ar3∈{0，1，3}、環(huán)長(zhǎng)為 6和 8的約束方程以及避免相應(yīng)環(huán)的列序列。

表4 非等差數(shù)列碼6環(huán)和8環(huán)存在的約束方程和避免6環(huán)和8環(huán)的列序列

2.2 大girth多進(jìn)制陣列碼

根據(jù)上節(jié)約束關(guān)系選出的指數(shù)矩陣E(W)，可以保證多進(jìn)制奇偶校驗(yàn)矩陣H的girth都為8和10，分別避免了環(huán)長(zhǎng)6和8。也可產(chǎn)生出更大girth的校驗(yàn)矩陣，只是選取列序列受控的約束方程會(huì)更多，搜索的難度增大。無限增大girth最終對(duì)性能的提高也不會(huì)太大，并且陣列碼無法避免長(zhǎng)度為12的環(huán)［11］。

對(duì)于多進(jìn)制陣列LDPC碼校驗(yàn)矩陣的構(gòu)造將從指數(shù)矩陣E(W)出發(fā)進(jìn)行擴(kuò)展，且循環(huán)陣中不存在零陣。廣義多進(jìn)制擴(kuò)展方法基于兩個(gè)不同域：GF(p)和GF(2l)。多進(jìn)制LDPC碼校驗(yàn)矩陣非零值的位置由GF(p)域決定，非零值的數(shù)值由GF(2l)域決定。這兩個(gè)域的具體關(guān)系如下：(2l-1)·(rt-1)＜p＜(2l-1)·rt，其中，l∈Z，rt=

為GF(2

l

)域中所有非零元素重復(fù)的周期數(shù)，不足一個(gè)周期的，記為一個(gè)周期，并計(jì)入r

t

中，r

c

是重復(fù)周期的帶分?jǐn)?shù)表示，整數(shù)部分表示的是重復(fù)的整數(shù)周期數(shù)，分?jǐn)?shù)中分母表示一個(gè)周期的長(zhǎng)度，分子表示不足一個(gè)周期的剩余長(zhǎng)度。l與 p值的具體關(guān)系由下式表示：

其中，

表示向上取整。

廣義二維擴(kuò)展包括水平擴(kuò)展和垂直擴(kuò)展。首先給出水平擴(kuò)展的方式，即為提出的廣義多進(jìn)制位置向量。令 β是GF(2l)域的本原元。將基于GF(p)和GF(2l)域的廣義多進(jìn)制位置向量定義為z(I)=(z0，z1，…，zp-1)，其中 zi=βimod(2l-1)，i∈I ，其它所有分量為0。集合I是廣義多進(jìn)制位置向量中非零值所在的位置序號(hào)，多進(jìn)制位置向量的重量等于集合I的勢(shì)Card(I)。定義向量的數(shù)值取值范圍是GF(2l)域中的2l-1個(gè)非零元素。當(dāng) z(I)是GF(2l)域上重量為1的 p重向量時(shí)，構(gòu)造出校驗(yàn)矩陣的子陣列為廣義循環(huán)置換矩陣，此時(shí)矩陣的非零位置數(shù)由指數(shù)矩陣決定；當(dāng)z(I)是GF(2l)域上重量不為1的 p重向量時(shí)，構(gòu)造出校驗(yàn)矩陣的子陣列為廣義循環(huán)矩陣，此時(shí)非零位置數(shù)將由一個(gè)集合來決定。接著給出垂直擴(kuò)展方式。令I(lǐng)是任一由GF(p)域中的元素組成的集合，廣義多進(jìn)制位置向量z(I+1)定義為位置向量z(I)向右循環(huán)移一位，移位后第1列至第 pm-1列的元素乘以β分別得到第2列至第 p列元素，而第 p列元素則乘以βrt(2l-1)-(p-1)后得到第1列元素。根據(jù)廣義多進(jìn)制位置向量的擴(kuò)展規(guī)則，多進(jìn)制位置向量z(I+γ)定義為集合I中元素依次加γ∈GF(p)后擴(kuò)展得到的廣義多進(jìn)制位置向量，在GF(2l)域上可形成以I，I+1，…，I+p-1的廣義位置向量為行的多進(jìn)制p×p大小的循環(huán)矩陣PI。

二維 p重?cái)U(kuò)展可由上述垂直擴(kuò)展和水平擴(kuò)展兩部分組成，對(duì)于任一集合 I，dispv(I)=[I，I+1，…，I+p-1]T為該集合的垂直擴(kuò)展，而disph(I)=z(I)為該集合的水平擴(kuò)展，其中無論集合I中元素取GF(p)域內(nèi)何值，循環(huán)矩陣PI都不會(huì)為全零矩陣。集合I與循環(huán)置換矩陣PI是一一對(duì)應(yīng)的關(guān)系：

通過式（11）可從指數(shù)矩陣（對(duì)應(yīng)于廣義循環(huán)置換矩陣）或相應(yīng)集合（對(duì)應(yīng)于廣義循環(huán)矩陣）構(gòu)造出具有廣義循環(huán)特性的多進(jìn)制校驗(yàn)矩陣H。由于多進(jìn)制校驗(yàn)矩陣非零值位置和數(shù)值的選取分別建立在GF(p)和GF(2l)兩個(gè)不同的域上，構(gòu)造出的二維 p重矩陣PI非零元素的分布具有兩種情形：1）當(dāng)rt=1時(shí)，在GF(2l)域上只具有部分域元素循環(huán)（rc＜1）或循環(huán)（rc=1）的特性；2）當(dāng) rt≥2時(shí)，所有GF(2l)域非零元素個(gè)數(shù)一般在矩陣中分布不均，但是當(dāng)2l-1=rcp時(shí)，非零元素分布將是均勻的。為了便于表示，PI簡(jiǎn)化記為 Hi，j，由擴(kuò)展的性質(zhì)知Hi，j是廣義循環(huán)矩陣，因此其可分解為一個(gè)非奇異的對(duì)角矩陣Y和一個(gè)循環(huán)矩陣之積。將 Hi，j表示為兩個(gè) p×p矩陣Y和的 乘 積 ，即，其中是一個(gè) GF(2l)域上不具有乘 β性質(zhì)的移位循環(huán)矩陣，如果單獨(dú)來看，它是一個(gè)二進(jìn)制矩陣，非零元素取值選自GF(q)域中的某個(gè)非零值，Y是一個(gè)以部分周期循環(huán)元素β0，β，…，β2l-2，β0，β，… 為主對(duì)角線，其余為 0 的p×p大小的方陣，記為Y=diag(β0，β，…)。設(shè) c為碼字向量，則，可知，與是等價(jià)的。所以說，矩陣和的零空間給出的碼字是一樣的。因此，通過可以找到具有系統(tǒng)或部分系統(tǒng)形式的生成矩陣，以實(shí)現(xiàn)有效的線性復(fù)雜度編碼［10］。可以說通過廣義位置向量擴(kuò)展生成的多進(jìn)制LDPC碼充分考慮了編碼和譯碼的實(shí)現(xiàn)復(fù)雜度，在編碼上，由于校驗(yàn)矩陣是廣義QC形式的矩陣，繼承了QC矩陣的特性，可采用QCLDPC碼的有效編碼方法；在譯碼上，通過廣義二維擴(kuò)展，數(shù)值域建立在2的冪次上，使得譯碼可以采用高性能低復(fù)雜度的軟判決譯碼算法，利于工程應(yīng)用。

3 仿真結(jié)果及性能分析

本節(jié)將對(duì)構(gòu)造的大girth多進(jìn)制陣列LDPC碼進(jìn)行仿真比較，仿真中的信號(hào)均采用BPSK調(diào)制，且在雙邊功率譜密度為N02的AWGN信道中傳輸。譯碼采用FFT-QSPA算法且最大迭代次數(shù)設(shè)置為50，仿真中的誤碼率是在檢測(cè)50幀錯(cuò)誤的條件下得出的。為了便于比較，對(duì)于等差陣列碼和非等差陣列碼，取 p=127，其子陣列的大小為127×127，選擇的列重都為3，行重都為6，因此，r=3，n=6。根據(jù)碼的性質(zhì)、girth和等差陣列碼的數(shù)值域選擇的不同構(gòu)造出8種不同的多進(jìn)制LDPC碼。在構(gòu)造出的LDPC碼中，從構(gòu)造性質(zhì)的角度，有等差陣列碼和非等差陣列碼；從girth的角度，有g(shù)irth為8和10的碼；從數(shù)值構(gòu)造域的角度，有128進(jìn)制、64進(jìn)制和32進(jìn)制LDPC碼。

仿真中等差陣列碼陣列行序號(hào)選{0，1，2}，非等差陣列碼陣列行序號(hào)選{0，1，3}。girth大小的選擇按照表1和表4中給出的序列來抽取指數(shù)矩陣中相應(yīng)的列。對(duì)于數(shù)值域GF(2l)選擇如下：當(dāng)l=7時(shí)，rt=1，rc=1，此時(shí)矩陣中元素分布是均勻的；當(dāng) l=6時(shí)，rt=3，；當(dāng) l=5時(shí)，rt=5，。根據(jù)三種GF(2l)域選擇構(gòu)造出不同的多進(jìn)制LDPC碼，但是選擇的指數(shù)矩陣都是相同的。等差數(shù)列情況，R3G8碼（3表示列重，8表示girth值）的指數(shù)矩陣為

R3G10碼的指數(shù)矩陣為

非等差數(shù)列情況，R3G8碼的指數(shù)矩陣為

圖1 不同參數(shù)的多進(jìn)制（762，383）陣列LDPC碼的誤碼性能比較

圖2 不同參數(shù)的多進(jìn)制（762，383）陣列LDPC碼的迭代性能比較

R3G10碼的指數(shù)矩陣為

8種多進(jìn)制（762，383）陣列LDPC碼的誤碼性能和迭代性能分別如圖1和圖2所示。其中等差陣列R3G10碼是存在8環(huán)的，但是通過列陣列的選取還是可以消除大部分存在的8環(huán)。為了便于比較，圖1也給出了RS碼BM算法的誤碼性能，在誤比特率（BitErrorRate，BER）為 10-5處，32進(jìn)制（762，383）R3G8LDPC 碼相對(duì)于 GF(210)域（382，192）RS碼來說，取得了大約4.24dB的編碼增益。從圖1和圖2還可以得出：1）非等差陣列碼在girth為8時(shí)取得的性能優(yōu)于等差陣列碼，但是girth為10時(shí)，其優(yōu)勢(shì)就不太明顯了；2）盡管有的碼只是部分消除了8環(huán)，但是girth為10的碼比girth為8的碼取得了更大的編碼增益；3）等差陣列碼中，隨著進(jìn)制數(shù)的減少，其性能越好，收斂越快，但是之間的差距并不大。進(jìn)制數(shù)的減少同時(shí)也能降低譯碼的復(fù)雜度。對(duì)于結(jié)論3）這種現(xiàn)象Mackay也曾指出［1，12］：隨著域階數(shù)的增加，其誤碼性能并不總是單調(diào)提升，這一現(xiàn)象的產(chǎn)生與校驗(yàn)矩陣的構(gòu)造密切相關(guān)。

下面考慮列重為4的大girth多進(jìn)制LDPC碼的性能。參數(shù)選取如下：p=509，l=6，這樣構(gòu)造出的廣義多進(jìn)制準(zhǔn)循環(huán)校驗(yàn)矩陣位置和數(shù)值的選擇分別基于GF(509)和GF(64)域，列重為4，行重為8，子陣列的大小為 509×509，rt=9，。

R4G8碼的指數(shù)矩陣為

R4G10碼的指數(shù)矩陣為

圖3 64-ary（4072，2039）陣列LDPC碼的誤碼性能曲線

圖4 64-ary（4072，2039）陣列LDPC碼的迭代性能曲線

由上述兩個(gè)指數(shù)矩陣構(gòu)造的校驗(yàn)矩陣大小都為2036×4072矩陣的秩同為2033，其零空間給出了碼率為0.5007的64-ary（4072，2039）陣列LDPC碼，其誤碼性能和迭代性能分別如圖3和圖4所示。從仿真結(jié)果來看，girth為10的碼取得性能略優(yōu)于girth為8的碼。

4 結(jié)語

大girth及其分布是保證碼字性能的一個(gè)重要因素之一。為了構(gòu)造大girth多進(jìn)制LDPC碼，從指數(shù)矩陣出發(fā)，選出避開短環(huán)的陣列列，并將廣義二維擴(kuò)展方法應(yīng)用于指數(shù)矩陣，構(gòu)造出不存在短環(huán)的校驗(yàn)矩陣。仿真結(jié)果表明，基于廣義二維擴(kuò)展方法的多進(jìn)制大girth陣列LDPC碼能取得良好的性能，利于有效的編譯碼，可減少存儲(chǔ)空間。構(gòu)造出的校驗(yàn)矩陣在一定程度上增大girth能明顯提高碼字的性能，保證信息的可靠傳輸，滿足無線通信的高頻帶利用率。