基于循環中國剩余定理和改進PEG算法的IRA碼

黃　勝，敖　翔，龐曉磊，張　睿

(重慶郵電大學　光通信與網絡重點實驗室，重慶 400065)

?

基于循環中國剩余定理和改進PEG算法的IRA碼

黃勝，敖翔，龐曉磊，張睿

(重慶郵電大學光通信與網絡重點實驗室，重慶 400065)

摘要:為了避免交織器產生的時延，通過改進的漸進邊增長(PEG)算法和循環中國剩余定理構造了一種不規則重復累積(IRA)碼。與常規的IRA碼相比，提出的碼字具有半隨機半結構化形式，不需要設計交織器，且碼長選擇更加靈活。仿真結果顯示，在碼率為1/2的條件下，當誤碼率為10-6時，構造的IRA(1 000，500)碼與PEG-IRA(1 000，500)碼和基于剩余類數對的IRA(1 000，500)碼相比，在對應的相同條件下分別取得了0.2 dB和0.1 dB左右的凈編碼增益提升；且在碼率為3/4時，所構造的IRA(16 200，11 880)碼比相同碼長和碼率的DVB-S2標準LDPC碼凈編碼增益提高了約0.1 dB左右。

關鍵詞:PEG算法；中國剩余定理；不規則重復累積碼；凈編碼增益

低密度奇偶校驗(Low Density Parity Check，LDPC)碼[1]于1962年提出。近十幾年來，LDPC碼在糾錯編碼領域得到了重大發展，被認為是最有希望在廣泛的信道范圍接近香農極限的誤差糾正技術[2]，和Turbo碼一起，被廣泛應用于編碼領域。相比于Turbo碼，LDPC碼有很多優點，比如LDPC碼具有線性譯碼復雜度[3]，而且當碼長較大時，對于非規則LDPC在AWGN信道下幾乎達到香農限的優異性能[4]。但是LDPC碼的編碼復雜度較高，與碼長的二次方成正比，而Turbo碼的編碼復雜度僅碼長呈正線性增加。

隨著對Turbo碼和LDPC碼這兩種碼字的深入研究，學者們找到了一種既具有較低線性編碼復雜度又有較低線性譯碼復雜度的好碼字——重復累積(RA)碼。RA碼最初作為Turbo碼中的一種獨特的串行結構而被提出，因此也可以把RA碼稱作“Turbo相似碼”[5]。后來又有學者在不規則LDPC碼的基礎上，設計出不規則RA(IRA)碼[6]。

IRA碼既可以看作Turbo碼，也可以看作LDPC碼。近年來，設計構造性能優異的IRA碼已經成為了研究的熱點[6-10]。由于初期RA碼是在Turbo碼的基礎上提出的，因此傳統的IRA碼的編碼方法需要設計交織器，從而將導致可能帶來的時延問題。自從Yang等在文獻[7]中提出了能夠實現線性編碼的LDPC碼后，避免重復器、交織器、組合器的設計過程，通過直接設計H1子矩陣研究IRA碼的思路受到了LDPC編碼學者的親睞，使得從LDPC碼的角度來構造IRA碼也受到了極大的關注[8-10]。其中文獻[8]是通過PEG算法設計IRA碼H1子矩陣，間接對交織器進行構造；文獻[9]設計的QC-LDPC碼基于等差數列，但是這種線性編碼計算量的碼型不一定能完全避免短環， 且H2只能構造規則的子矩陣，同時a值固定不可變，靈活性大大受限；文獻[10]提出的H2子矩陣是半隨機結構，性能優異但其構造受到有限乘群構造的限制而不靈活。同時，由于IRA碼通過置信傳播譯碼算法譯碼，不單要求H1不能含有短環，且H=[H1H2]矩陣中同樣要避免短環的存在，否則將會降低譯碼器的收斂速度，破壞IRA碼的誤碼率性能。

本文綜合以上問題，利用循環中國剩余定理和改進的PEG算法構造出了一種新的IRA碼。這類構造方法構造的碼字在保留IRA碼線性編碼復雜度優點的基礎上，有效地避免了短環的存在。此外，該碼不僅有較低的錯誤平層，而且具有較低的構造復雜度和存儲復雜度，從而降低了硬件實現的復雜度及成本。

1IRA碼的LDPC結構

由于IRA碼是一類特殊的LDPC碼，因此它能用Tanner圖和校驗矩陣H這兩種方式分別表達，其Tanner圖具體見圖1，校驗矩陣H=[H1H2]具體用式 (1)表示。

圖1　IRA碼的LDPC碼結構

(1)

式中：IRA碼對應的校驗矩陣H為m×(m+k)維矩陣，其中，H1是一個列重為[q1，q2，…，qk]，行重為a的隨機子矩陣；H2是一個m×m的雙對角線結構子矩陣。H1列重由重復器變量q確定，H1行重由組合器的參數a確定，H1里面的每個1元素的位置通過交織器來確定。因此，一旦得到H1子矩陣的同時，也間接地知道了重復器、組合器及其交織器的具體參數。本文從LDPC碼的角度直接針對H1的設計，沒有涉及交織器的設計，避免可能帶來的時延。

2基于改進的PEG和循環中國剩余定理的IRA碼構造

1)H1和Hb中的所有項置0。

2)通過PEG算法設計基矩陣Hb時，如果PEG算法中的候選最小度校驗節點超過一個且候選校驗節點的度d(cu)滿足約束條件d(cu) ≤a(0≤u

(1)不管變量節點還是校驗節點接收到前面的一層傳遞過來的ACE值，均從當前節點里面選取值最小的數。

(2)把(1)中傳遞過來的值和本身的ACE值加在一起，記為值z。且把加在一起的z值傳遞到與當前節點相互連接的下面所有節點。

3)從1)和2)中得到Hb基矩陣，對Hb的每項為1的元素進行下面步驟：

vtp=t+xmodLp

(2)

(3)

(4)

qtp=tmodLp

(5)

(6)

(7)

如果上述運算過程中得到有相鄰行且同一列位置都為1的情況，則停止目前的計算且刪除當前的H1矩陣，同時進行x+1操作，接著從3)重新開始。否則直接進行4)。

4)將H1和H2結合起來形成所構造的IRA碼的校驗矩陣H=[H1H2]。

引理1[13]:設gb為一個基矩陣Hb的圍長，gc為由CRT擴展的校驗矩陣H的圍長，則gc≥gb。

基于引理1，再根據H2的雙對角線結構及四環在校驗矩陣H中的特點可知，只要H1任意相鄰兩行同列位置都不同時為1，那么所構造的IRA碼不存在短環。

2.1IPEG-CRT算法得到H1矩陣的行列重分析

為了說明一般性，假設Hb第i行經過CRT擴展后有一行的行重為w(w不等于a)。

首先考慮w

w>a的情況同理可得。因此行重為a的基矩陣Hb與經過CRT擴展的H1行重都為a。

列重和行重的分析相似，同理可知當前列列重通過CRT擴展之后的列重不變，因此Hb與H1具有相同的信息節點度分布。

故Hb與H1具有相同的度分布。

2.2IPEG-CRT IRA碼的存儲復雜度分析

IPEG-CRTIRA碼H=[H1H2]的存儲復雜度分為兩部分：1)H2為雙對角線，只需已知第一行一個1和第二行兩個1的位置，后面每行在第二行的基礎上利用移位寄存器依次可得；2)H1僅考慮利用改進的PEG算法構造的基矩陣Hb，在Hb中的每個1元素行列標的基礎上利用CRT結構可以唯一地確定H1矩陣中每個1元素的行列標，很大程度上降低了H1隨機矩陣所需要的存儲空間。相應地，這也一定程度上降低了硬件實現的復雜度。

通過上述分析可知，無論哪種方法設計的IRA碼均具有線性編碼復雜度，但是IPEG-CRT IRA碼直接利用改進的PEG算法和中國剩余定理構造H1子矩陣，它具有半隨機半結構化形式，而非隨機構造。因此，所構造的IEPG-CRT IRA碼具有較低的存儲復雜度，一定程度上降低了硬件實現的復雜度以及所需要的實現成本。同時，所提出的算法在高信噪比區域能保持較低的錯誤平層以及消除短環。

3性能分析

本文仿真過程：首先編碼后利用BPSK 調制，接著經過加性高斯白噪聲(AWGN)信道，最后把信道中輸出的數據解調后通過置信傳播(BP)譯碼算法恢復原始數據，迭代次數選為50次。

通過改良的度分布[7]構造IRA碼，首先令IPEG-CRT IRA碼H1子矩陣信息節點的度分布φ(x)=0.238 02x+0.209 97x2+0.034 92x3+0.120 15x4+0.015 87x6+0.004 80x13+0.376 27x14以及a=8(校驗節點度分布dc=8)。再根據改進的PEG算法構造125×125階基矩陣Hb，令s=1，L=4，然后利用公式CRT擴展后得到校驗矩陣子矩陣H1，其維數是500×500，最后得到碼率為1/2及碼長為1 000的校驗矩陣H=[H1H2]。為了可以更好地分析本文構造的IRA碼的優越性，本文把所構造的IPEG-CRT IRA碼在相同條件下與基于PEG算法構造的IRA碼、基于剩余類數對構造的IRA碼及隨機交織器進行比較，仿真結果如圖2所示。由圖2可知當誤碼率為10-6時，在1/2碼率的情況下，所構造的IPEG-CRT IRA碼同基于PEG算法構造的IRA碼、基于剩余類數對構造的IRA碼相比，均有不同程度的性能提升。當誤碼率是10-6時，在1/2碼率的條件下，所構造的(1 000，500)IPEG-CRT IRA碼與文獻[8]的(1 000，500)PEG-IRA碼相比具有0.2 dB左右NCG的改善，比文獻[10]的基于剩余類數對構造的(960，480)IRA碼NCG提高了0.1 dB左右，且碼長選擇更加靈活。同時誤碼率性能遠比隨機交織構造的IRA碼優秀，且不會存在交織器時延問題。

圖2　IPEG-CRT IRA碼與其他IRA碼性能比較

為了充分說明本文所構造的IRA碼的性能和應用潛力，同樣根據改進后的PEG算法構造維數為810×2 430的基矩陣Hb，令s=1，L=5，然后利用公式CRT擴展后得到維數4 050×12 150的校驗矩陣子矩陣H1，最后得到碼率為3/4及碼長為16 200的H=[H1H2]。將其與DVB-S2標準LDPC碼對比，圖3為仿真結果。通過圖3表明，在誤碼率等于10-6情況下，本文構造的IRA碼性能優于DVB-S2標準LDPC碼，凈編碼增益提升了約0.1dB。

圖3　IPEG-CRT IRA碼與DVB-S2標準LDPC碼性能比較

4小結

首先通過改進的PEG算法構造出IRA碼H1子矩陣的基矩陣，然后利用循環中國剩余定理來構造IRA碼。IPEG-CRT方法除了具備常規IRA碼較低線性編碼復雜度的優勢，還在避免短環的同時降低了錯誤平層，且降低了傳統構造IRA碼的存儲復雜度，這樣在很大程度上節省了系統所需要的存儲空間，從而減少了硬件實現的成本和復雜度。仿真結果表明，在對應的同等條件下，本文所構造的IRA碼優于剩余類數對IRA碼和PEG-IRA碼。除此之外，優于DVB-S2標準LDPC碼，并且不需要設計交織器，可以作為代替衛星通信領域的DVB-S2標準LDPC碼的一種選擇方案。

參考文獻：

[1]GALLAGER R. Low-density parity-check codes[J].IRE transactions on information theory，1962，8(1)：21-28.DOI:10.1109/TIT.1962.1057683.

[2]范文同，馬林華，林志國，等. 一類環長至少為10的準循環LDPC碼 [J]. 電視技術，2015，39(19)：59-62.DOI：10.16280/j.videoe.2015.19.015.

[3]FOSSORIER M P C，MIHALJEVIC M，INAI H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation[J]. IEEE transactions on communications，1999，47(5)：673-680.DOI：10.1109/26.768759.

[4]CHUANG S Y，FORNEY Jr G D，RICHARDSON T J，et al. On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit[J]. IEEE communications letters，2001，5(2)：58-60.DOI：10.1109/4234.905935.

[5]JIN H. Analysis and design of turbo-like codes[D]. California ：California Institute of Technology，2001.

[6]鹿增輝，方勇，霍迎秋. 基于滑窗置信傳播算法的聯合信源信道編碼[J]. 電視技術，2015，39 (11)：99-103.DOI：10.16280/j.videoe.2015.11.023.

[7]YANG M，RYAN W E，LI Y. Design of efficiently encodable moderate-length high-rate irregular LDPC codes[J]. IEEE transactions on communications，2004，52(3)：564-571.DOI：10.1109/TCOMM.2004.826367.

[8]CHEN P J，ZHU L X，HU Q，et al. PEG algorithm based interleavers design for systematic IRA codes[C]//Proc. 8th International Symposium on Antennas，Propagation and EM Theory (ISAPE). Kunming：IEEE，2008：1458-1461.DOI：10.1109/ISAPE.2008.4735505.

[9]彭立，朱光喜，吳曉曉. 基于等差數列的LDPC碼編碼器設計[J]. 電子學報，2007，35(5)：950-954.

[10]彭立，張琦，王渤，等. 針對 IRA-LDPC 碼類的半隨機半代數結構設計[J]. 通信學報，2014，35 (3)：77-84.DOI：10.3969/j.issn.1000-436x.2014.03.009.

[11]HU X Y，ELEFTHEIOU E，ARNOLD D M. Progressive edge-growth Tanner graphs[C]//Proc. 2001 Global Telecommunications Conference (GLOBECOM′01). San Antonio：IEEE，2001：995-1001.DOI：10.1109/GLOCOM.2001.96556.

[12]TIAN T，JONES C R，VILLASENOR J D，et al. Selective avoidance of cycles in irregular LDPC code construction[J]. IEEE transactions on communications，2004，52(8)：1242-1247.DOI：10.1109/TCOMM.2004.833048.

[13]JIANG X Q，XIA X G，LEE M. Efficient progressive edge-growth algorithm based on chinese remainder theorem[J]. IEEE transactions on communications，2014，62(2)：442-451.DOI：10.1109/TCOMM.2014.011114.130285.

責任編輯：許盈

IRA codes based on cyclic Chinese remainder theorem and improved PEG algorithm

HUANG Sheng, AO Xiang, PANG Xiaolei, ZHANG Rui

(KeyLaboratoryofOpticalCommunicationsandNetwork,ChongqingUniv.ofPostsandTelecommunications,Chongqing400065,China)

Abstract:In order to avoid the delay generated by the interleaver, a kind of irregular repeat accumulation (IRA) code is built by the improved progressive edge growth (PEG) algorithm and the cyclic Chinese remainder theorem. Compared with regular IRA codes, the proposed code has the quasi-randomized and semi-structured forms, and does not need to design the interleaver, and the code length selection is more flexible. The simulation results show that when the bit error rate is 10-6, the net coding gain(NCG) of the proposed IRA(1 000,500) code with the code rate of 1/2 is about 0.2 dB and 0.1 dB higher than those of the PEG-IRA(1 000,500) code and the IRA(1 000,500) code based on residue class respectively. In addition, the NCG of the proposed IRA(16 200, 11 880) code is about 0.1 dB more than that of the DVB-S2 standard LDPC code with the same conditions correspondingly with the code rate of 3/4 and the bit error rate(BER) of 10-6.

Key words:PEG algorithm; CRT; IRA code; NCG

中圖分類號：TN911.22

文獻標志碼：A

DOI：10.16280/j.videoe.2016.05.009

基金項目：國家自然科學基金項目(61571072)；重慶市基礎與前沿研究計劃項目(cstc2015jcyjA40015)

收稿日期：2015-12-15

文獻引用格式：黃勝，敖翔，龐曉磊，等. 基于循環中國剩余定理和改進PEG算法的IRA碼[J].電視技術，2016，40(5)：36-39.

HUANG S，AO X，PANG X L，et al. IRA codes based on cyclic Chinese remainder theorem and improved PEG algorithm [J].Video engineering，2016，40(5)：36-39.