基于中國剩余定理和貪婪算法擴展的QC－LDPC 碼*

黃 勝，龐曉磊，田方方，賈雪婷

(重慶郵電大學 光纖通信技術(shù)重點實驗室，重慶400065)

1 引 言

LDPC 碼具有逼近Shannon 限的優(yōu)秀性能［1］，而且譯碼復雜度較低，已經(jīng)成為近幾年編碼學者的研究熱點。目前LDPC 碼的研究主要分為3 個方向，一是性能優(yōu)化設(shè)計方法，二是降低編碼復雜度［2］，三是在通信系統(tǒng)中的應(yīng)用［3］，本文重點在性能優(yōu)化設(shè)計方法方面。而LDPC 碼的構(gòu)造方法主要分為隨機構(gòu)造方法［4］和結(jié)構(gòu)化構(gòu)造方法［5］兩類。由于隨機碼具有很大的編碼復雜度，因此在實際應(yīng)用中受到很大的限制。準循環(huán)(QC)LDPC 碼是一個很好折衷方案，不僅具有非常優(yōu)秀的性能，而且其代數(shù)結(jié)構(gòu)大大降低了運算和存儲復雜度，一些QCLDPC 碼甚至具有和隨機碼比肩的優(yōu)異性能［6］。

陣列碼是一類具有特殊結(jié)構(gòu)的QC－LDPC 碼，不僅具有QC－LDPC 的代數(shù)結(jié)構(gòu)，可以用簡單的移位寄存器進行編碼，同時也具有低錯誤平層、圍長至少為6、糾突發(fā)錯誤的優(yōu)點［7－8］。中國剩余定理(CRT)已被應(yīng)用于計算機、編碼、數(shù)字信號處理等領(lǐng)域，而結(jié)合CRT 的QC－LDPC 碼已經(jīng)被陸續(xù)研究［9－11］。利用CRT 構(gòu)造LDPC 碼的優(yōu)勢是，用若干個QC－LDPC 短碼作為分量碼可以構(gòu)造出QC－LDPC 長碼，并且QC－LDPC 長碼的圍長不小于所有分量碼的最大圍長。將陣列碼作為分量碼，文獻［9］利用CRT 構(gòu)造出了不含4 環(huán)的QC－LDPC 碼，文獻［10］利用CRT 方法構(gòu)造出了一類不含4 環(huán)并且6環(huán)數(shù)量大大減少(但不能完全消除)的QC－LDPC碼。由于陣列碼的循環(huán)置換矩陣(CPM)尺寸為素數(shù)，因此這兩種方法得到的QC－LDPC 碼的碼長取值非常受限。文獻［11］構(gòu)造的CRT 碼雖然最短環(huán)數(shù)列較文獻［12］構(gòu)造的縮短陣列碼(SAC)有一定的減少，但是還有進一步改進的空間。從目前CRT在LDPC 碼的應(yīng)用［9－11］可知，除了第一個是陣列碼外，其他的分量碼都是隨機選擇，導致新構(gòu)造的碼性能有不同程度的削弱。

基于以上問題，本文提出了一種結(jié)合CRT 和貪婪算法擴展QC－LDPC 碼的構(gòu)造方法，其循環(huán)置換子矩陣由0 矩陣、樓梯矩陣及其右移矩陣構(gòu)成。該方法所構(gòu)造的碼與文獻［9－11］不同，不僅碼長更加靈活，而且圍長更大，最重要的是只需已知一個分量碼——縮短陣列碼，通過CRT 和貪婪算法得出剩下分量碼和最終所構(gòu)造碼。仿真結(jié)果表明本文提出的構(gòu)造方法在AWGN 和瑞利衰落信道中與文獻［11－12］的碼字相比，當誤碼率為10－6時，凈編碼增益(NCG)有一定程度的改善，與Gallager 隨機碼性能相似但編碼復雜度大大降低。

2 縮短陣列碼的校驗矩陣

QC－LDPC 碼對應(yīng)的校驗矩陣由許多相同維數(shù)的子循環(huán)方陣組成，循環(huán)方陣由0 矩陣或者CPM組成。

QC－LDPC 碼的校驗矩陣可以表示為

其中，aij∈﹛ 0，1，2，…，L－1，∞﹜。如果aij=∞，Paij(0≤i≤m－1，0≤j≤n－1)代表一個0 矩陣，否則表示一個循環(huán)右移單位矩陣aij次的L×L 循環(huán)置換矩陣。H 矩陣的m 塊行記為從0 到m－1 塊行，n 塊列記為從0 到n－1 列。

校驗矩陣H 的指數(shù)矩陣E(H)可以如式(2)表示:

并且H 可以由E(H)中每個元素aij用Paij替代獲得。

陣列碼是一類基于L×L 循環(huán)置換矩陣的QCLDPC 碼。陣列碼的指數(shù)矩陣被定義為E(H)=(aij)，aij=i×j mod L，這里0≤i≤M－1 并且0≤j≤L－1，M 是正整數(shù)，L 是素數(shù)且保證M≤L。陣列碼的校驗矩陣［7］為

縮短陣列碼為在陣列碼的基礎(chǔ)上刪除特定的列的矩陣，以便獲得更大圍長［12］。

定理［7］:當在陣列碼的校驗矩陣H 中存在一個塊行列指數(shù)對序列(i1，j1)，(i1，j2)，(i2，j2)，(i2，j3)，...，(ik，jk)，(ik，j1)使得i1(j1－j2)+i2(j2－j3)+...+ik(jk－j1)≡0 mod L，則此陣列碼存在一個2k 環(huán)，其中il≠il+1，jl≠jl+1，l=1，2，…，k－1，且ik≠i1，jk≠j1。

圖1是指數(shù)矩陣存在6 環(huán)的結(jié)構(gòu)以及約束方程［12］。表1為對應(yīng)列重為4 的指數(shù)矩陣存在環(huán)6的約束方程以及消除環(huán)的序列［12］。

圖1 存在6 環(huán)的指數(shù)矩陣和對應(yīng)的約束方程Fig.1 Exponent matrix with six cycles and its governing equation

表1 列重為4 的指數(shù)矩陣在模L 下對應(yīng)的環(huán)6 約束方程和消去6 環(huán)的序列Table 1 Six cycle－governing equation for shortened array codes with modulus L and column－weight r=4，and greedy sequences avoiding solutions to six cycle－governing equation

3 基于CRT 和貪婪算法構(gòu)造圍長至少為8的QC－LDPC 碼

由表1中消除所有環(huán)6 的序列可以得到縮短陣列碼，但縮短陣列碼獲得的大圍長是以犧牲特定的列獲得的，因此縮短陣列碼相對一般的陣列碼具有較大圍長且較短碼長的特點。為進一步改善性能，把CRT 和貪婪算法結(jié)合起來擴展縮短陣列碼以便獲得更大圍長、更加靈活的碼長，如果圍長一樣，則使得最短環(huán)的數(shù)量盡可能地少。

設(shè)L1，L2，…，Ls是CRT 中s 個不同的的除數(shù)使得L=L1×L2…Ll…Lf…×Ls。其中f= 1，2，…，s，GCD(Ll，Lf)= 1(GCD 表示最大公約數(shù))。設(shè)Cf是一個QC－LDPC 碼，它的校驗矩陣Hf是一個基于Lf×Lf的CPM 或者0 矩陣的m×n 陣列。而且E(Hf)=是Hl的一個指數(shù)矩陣。

在縮短陣列碼的基礎(chǔ)上結(jié)合CRT 和貪婪算法構(gòu)造一個QC－LDPC 長碼，它是一個mL×nL 的校驗矩陣H。aij表示s 個分量碼經(jīng)過CRT 和貪婪算法之后形成新的碼字H 的指數(shù)矩陣中的元素，步驟如下所示(符號說明:E(Hf)表示第f(f=1，2，…，s)個分量碼指數(shù)矩陣，afij表示為E(Hf)的第i 行第j 列元素。E(Bf)表示第f 個臨時新構(gòu)造的指數(shù)矩陣，bfij為E(Bf)的第i 行第j 列元素):

(1)E(H1)置為上文所述縮短陣列碼的指數(shù)矩陣，其余f－1 個分量碼指數(shù)矩陣E(Hf)的第一行第一列的元素置為0;

(2)CRT:如果ri≠∞，其中i = 1，2，則t =這里且Ai為滿足Ai≡1mod Ki約束條件的最小正整數(shù);否則若ri=∞，則t=∞。其中，ri表示參與CRT 操作的指數(shù)矩陣中的元素，Ki表示參與CRT 運算對應(yīng)指數(shù)矩陣循環(huán)置換矩陣的維數(shù);

(3)利用CRT 和貪婪算法求E(Hf)和E(H)中的各個元素，如圖2所示。

圖2 獲得aij與(2＜f≤s)的流程圖Fig.2 Flow chart of acquring both aij and (2＜f≤s)

具體的步驟如下:

1)i=2，j=2;

2)根據(jù)E(H1)，利用CRT，計算E(B1)中的元素和E(H2)中的元素，確定的策略就是利用貪婪算法在0 至L2－1 中通過和E(H1)中對應(yīng)位置的已知元素利用CRT 選擇使當前構(gòu)造的校驗矩陣圍長H1B最大的元素。如果有多個元素同時滿足該條件，即選擇同時使得當前分量碼圍長盡可能大的最小元素。在確定H1B中b1ij的同時也確定a2ij，維數(shù)變?yōu)?/p>

3)f 從2 到s 遞增變化循環(huán)執(zhí)行下面的操作:根據(jù)E(Bf)，利用CRT 計算E(Bf)中的元素bfij和E(Hf+1)中的元素確定的策略就是利用貪婪算法在0 至Lf+1－1 中通過和E(Bf)中對應(yīng)位置的已知元素利用CRT 選擇使當前構(gòu)造的校驗矩陣圍長最大的元素。如果有多個元素同時滿足該條件，即選擇同時使得當前分量碼圍長盡可能大的最小元素，維數(shù)變?yōu)檠h(huán)結(jié)束后，計算獲得的E(Bs－1)中的元素bs－1ij，即為E(H)中的元素aij;

4)先遞增i，再遞增j，循環(huán)執(zhí)行第2 步和第3步，計算出E(H)中的所有元素aij;

(4)將得到指數(shù)矩陣E(H)記為E(H)=(aij);

(5)把E(H)中的每個元素aij用Daij代替獲得碼字C 的校驗矩陣H。其中循環(huán)置換D 矩陣不同于第2 節(jié)中的循環(huán)置換矩陣P，采用樓梯矩陣D，L階樓梯矩陣D 的構(gòu)造方法如下所示:

1)把第一個1 放在第一行第[L/2] 列;

2)接下來每一個數(shù)1 放在前一個數(shù)1 的右上一格;

3)如果這個數(shù)1 所要放的格已經(jīng)超出了頂行那么就把它放在底行，仍然要放在右一列;

4)如果這個數(shù)1 所要放的格已經(jīng)超出了最右列那么就把它放在最左列，仍然要放在上一行;

5)按照上面的方法放置L 次后保證所得L 階矩陣每行每列只有一個數(shù)1。

引理［9］:假設(shè)l=1，2，…，s，讓gl記為分量碼Cl的圍長，g 為s 個分量碼經(jīng)過CRT 構(gòu)造的碼C 的圍長，則g≥max{g1，g2，…，gs}。

推論:如果存在任意s 個兩兩互素的數(shù)L1，L2，…，Ls，則其中任意l 個數(shù)的乘積與剩下的s－l 個數(shù)兩兩互素，其中1＜l≤s。

證明:由s 個兩兩互素的數(shù)可知GCD(Lα，Lβ)=1，其中1≤α，β≤s 且α≠β。A= L1×L2…Ll，B=Lf，l＜f≤s，GCD(A，B)≠1，則存在GCD(Lγ，Lf)≠1，1≤γ≤l。這顯然與題目條件矛盾，所以假設(shè)不成立，原命題成立。

由上述定理和推論可知，經(jīng)過CRT 和貪婪算法，由上述方法構(gòu)造的新碼圍長依次為gB1≥max{g1，g2}→gB2≥max{gB1，g3}→…→gBs－2≥max{gBs－3，gs－1}→g≥max{gBs－2，gs}gBi(1≤i≤s－2)。

通過上述分析，本文通過CRT 和貪婪算法構(gòu)造的新碼與傳統(tǒng)的CRT 方法擴展的LDPC 碼［9－11］不同，不僅具有靈活的碼長和更大的圍長，如果圍長一樣，則最短環(huán)的數(shù)量盡可能地少，而且只需要一個分量碼即可。

4 仿真與性能分析

4.1 LDPC 碼在加性高斯白噪聲信道下的性能仿真

本文仿真中調(diào)制方法采用的是BPSK 調(diào)制，傳輸信道選用的是加性高斯白噪聲(AWGN)信道，采用BP 譯碼算法。首先仿真了所構(gòu)造的碼字在BP譯碼算法中不同迭代次數(shù)時的糾錯性能，如圖3所示。由圖3可知QC－LDPC(7592，3796)碼隨著迭代次數(shù)的增大，其NCG 有一定的提高，但是迭代次數(shù)到達一定次數(shù)時，其NCG 的差別就越來越小，甚至不再提高，但是迭代次數(shù)的增加會增加譯碼的復雜度，譯碼耗時就越長。綜合以上分析本文折衷選擇迭代次數(shù)16。

圖3 不同迭代次數(shù)時QC－LDPC(7592，3796)碼糾錯性能Fig.3 Error correction performance of QC－LDPC code(7592，3796)with different number of iterations

利用表1構(gòu)造一個圍長為8、列重為4 的縮短陣列碼，其校驗矩陣H1是一個基于73×73 的循環(huán)置換子矩陣的4×8 陣列。為把H1擴展為一個949×949 的循環(huán)置換子矩陣的4×8 陣列。首先，選擇s=2，L2=13，則L=949。利用貪婪算法構(gòu)造一個維數(shù)是4×8 陣列碼指數(shù)矩陣E(H2)，其次通過CRT 和貪婪算法構(gòu)造E(H)。最后把E(H)中的每個元素aij用Daij代替，獲得了一個圍長為8 的QC－LDPC 碼字C，但是新構(gòu)造的碼最短環(huán)的數(shù)量相對于文獻［11－12］大大降低，具體如表2所示。圖4為構(gòu)造碼字的誤比特率性能曲線。為了充分說明本文提出碼字的糾錯性能，文獻［12］中的縮短陣列碼(SAC)和文獻［11］中的CRT 碼以及Gallager 隨機碼也在圖中顯示。從圖3中可以看出在相同碼長、碼率、列重的條件下，本文提出的QC－LDPC 碼字在10－6誤碼率條件下比文獻［12］中的碼字有1.2 dB 左右的NCG，比文獻［11］的碼字有0.3 dB左右的改善，和Gallagher 隨機碼具有相似性能但編碼復雜度大大降低。

表2 不同算法構(gòu)造的QC－LDPC 碼對應(yīng)的最短環(huán)的數(shù)量Table 2 The number of the shortest cycles through constructing QC－LDPC codes via different algorithms

圖4 不同算法構(gòu)造的碼率為1/2 且相同碼長、列重為4條件下的QC－LDPC 碼在AWGN 信道下誤碼率性能對比Fig.4 BER performance of constructing QC－LDPC codes by different algorithms with the same code rate，code length and column－weight r=4 in AWGN channel

4.2 LDPC 碼在瑞利衰落信道下的性能仿真

LDPC 碼在瑞利衰落信道的性能仿真對比如圖5所示，采用BPSK 調(diào)制，BP 譯碼算法，瑞利衰落信道Ts=0.5×10－6，fd=100，未知初始信道狀態(tài)信息，迭代30 次。

圖5 不同算法構(gòu)造的碼率為1/2 且相同碼長、列重為4條件下的QC－LDPC 碼在瑞利衰落信道下誤碼率性能對比Fig.4 BER performance of constructing QC－LDPC codes by different algorithms with the same code rate，code length and column－weight r=4 in Rayleigh fading channel

從圖5中可以看出在相同碼長、碼率、列重的條件下，本文提出的QC－LDPC 碼字在10－6誤碼率條件下比文獻［12］中的碼字有2 dB左右的NCG，比文獻［11］的碼字有0.7 dB左右的改善，和Gallagher 隨機碼具有相似性能但編碼復雜度大大降低。

通過上述仿真可知，無論瑞利衰落信道還是AWGN 信道，本文提出算法相比其他算法均具有更好的性能，通過不同信道下的NCG 對比，本文提出的算法更具抗干擾性。

5 結(jié) 論

本文利用CRT 和貪婪算法，在縮短陣列碼基礎(chǔ)上通過CRT 和貪婪算法構(gòu)造更大圍長和碼長更加靈活的QC－LDPC 碼字，所構(gòu)造的碼字的校驗矩陣是采用樓梯矩陣D 循環(huán)置換而成。與目前CRT 在LDPC碼的應(yīng)用相比，本文所提出的碼字的構(gòu)造只需已知一個分量碼——縮短陣列碼，通過CRT 和貪婪算法得出剩下分量碼和最終所構(gòu)造碼，同時碼盡可能大地增大圍長，如果圍長一樣，則盡可能地降低最短環(huán)的數(shù)量。仿真結(jié)果表明，在AWGN 信道和瑞利衰落信道條件下，本文提出的構(gòu)造方法性能均優(yōu)于文獻［11－12］中構(gòu)造的碼字，具有更好的抗干擾性能，且與Gallager 隨機碼在相同條件下具有相似的性能但具有較低的編碼復雜度，由此可見，本文提出的構(gòu)造方案在不同的信道環(huán)境下均有較強的競爭力，為未來移動通信系統(tǒng)糾錯碼提供了一種選擇方案。

在今后的研究工作中，可以在本文提出的構(gòu)造方法基礎(chǔ)上，與雙對角線結(jié)構(gòu)相結(jié)合并進行一定的改進，以便在降低編碼復雜度的同時盡可能地減少對性能的削弱。

［1］ MacKay D J C，Neal R M.Near Shannon limit performance of low density parity check codes［J］.Electronics Letters，1996，32(18):1645.

［2］ 劉原華，張美玲.一種可快速編碼的QC—LDPC 碼構(gòu)造新方法［J］.電訊技術(shù)，2013，53(1):55－59.LIU Yuan－h(huán)ua，ZHANG Mei－ling.A New Desin Method for Quasi－cycle LDPC Codes with Fast Encoding Ability［J］.Telecommunication Engineering，2013，53(1):55－59.(in Chinese)

［3］ 程浩，仰楓帆.基于有限域的QC－LDPC 碼編碼協(xié)作通信及其聯(lián)合迭代譯碼技術(shù)［J］.電訊技術(shù)，2013，53(12):1574－1579.CHENG Hao，YANG Feng－fan.Finite Field QC－LDPCbased Encoding Cooperative System and its Joint Iterative Decoding Technology［J］.Telecommunication Engineering，2013，53(12):1574－1579.(in Chinese)

［4］ Khazraie S，Asvadi R，Banihashemi A H.A PEG construction of finite－Length LDPC codes with low error floor［J］.IEEE Communications Letters，2012，16(8):1288－1291.

［5］ Wang L，Zhang X，Yu F，et al.QC－LDPC Codes with Girth Eight Based on Independent Row－Column Mapping Sequence［J］.IEEE Communications Letters，2013，17(11):2140－2143.

［6］ Fossorier M P C.Quasi－cyclic low－density parity－check codes from circulant permutation matrices［J］.IEEE Transactions on Information Theory，2004，50(8):1788－1793.

［7］ Fan J L.Array codes as LDPC codes［M］//Constrained Coding and Soft Iterative Decoding. Berlin:Springer，2001:195－203.

［8］ Blaum M，Roth R M.New array codes for multiple phased burst correction［J］.IEEE Transactions on Information Theory，1993，39(1):66－77.

［9］ Myung S，Yang K.A combining method of quasi－cyclic LDPC codes by the Chinese remainder theorem［J］.IEEE Communications Letters，2005，9(9):823－825.

［10］ Liu Y，Wang X，Chen R，et al.Generalized combining method for design of quasi－cyclic LDPC codes［J］.IEEE Communications Letters，2008，12(5):392－394.

［11］ Jiang X，Lee M H.Large girth quasi－cyclic LDPC codes based on the chinese remainder theorem［J］.IEEE Communications Letters，2009，13(5):342－344.

［12］ Milenkovic O，Kashyap N，Leyba D. Shortened array codes of large girth［J］.IEEE Transactions on Information Theory，2006，52(8):3707－3722.