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

(重慶郵電大學(xué)　光通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

?

基于循環(huán)中國剩余定理和改進(jìn)PEG算法的IRA碼

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

(重慶郵電大學(xué)光通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

關(guān)鍵詞:PEG算法；中國剩余定理；不規(guī)則重復(fù)累積碼；凈編碼增益

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

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

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

本文綜合以上問題，利用循環(huán)中國剩余定理和改進(jìn)的PEG算法構(gòu)造出了一種新的IRA碼。這類構(gòu)造方法構(gòu)造的碼字在保留IRA碼線性編碼復(fù)雜度優(yōu)點(diǎn)的基礎(chǔ)上，有效地避免了短環(huán)的存在。此外，該碼不僅有較低的錯(cuò)誤平層，而且具有較低的構(gòu)造復(fù)雜度和存儲復(fù)雜度，從而降低了硬件實(shí)現(xiàn)的復(fù)雜度及成本。

1IRA碼的LDPC結(jié)構(gòu)

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

圖1　IRA碼的LDPC碼結(jié)構(gòu)

(1)

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

2基于改進(jìn)的PEG和循環(huán)中國剩余定理的IRA碼構(gòu)造

1)H1和Hb中的所有項(xiàng)置0。

2)通過PEG算法設(shè)計(jì)基矩陣Hb時(shí)，如果PEG算法中的候選最小度校驗(yàn)節(jié)點(diǎn)超過一個(gè)且候選校驗(yàn)節(jié)點(diǎn)的度d(cu)滿足約束條件d(cu) ≤a(0≤u

(1)不管變量節(jié)點(diǎn)還是校驗(yàn)節(jié)點(diǎn)接收到前面的一層傳遞過來的ACE值，均從當(dāng)前節(jié)點(diǎn)里面選取值最小的數(shù)。

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

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

vtp=t+xmodLp

(2)

(3)

(4)

qtp=tmodLp

(5)

(6)

(7)

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

4)將H1和H2結(jié)合起來形成所構(gòu)造的IRA碼的校驗(yàn)矩陣H=[H1H2]。

引理1[13]:設(shè)gb為一個(gè)基矩陣Hb的圍長，gc為由CRT擴(kuò)展的校驗(yàn)矩陣H的圍長，則gc≥gb。

基于引理1，再根據(jù)H2的雙對角線結(jié)構(gòu)及四環(huán)在校驗(yàn)矩陣H中的特點(diǎn)可知，只要H1任意相鄰兩行同列位置都不同時(shí)為1，那么所構(gòu)造的IRA碼不存在短環(huán)。

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

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

首先考慮w

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

列重和行重的分析相似，同理可知當(dāng)前列列重通過CRT擴(kuò)展之后的列重不變，因此Hb與H1具有相同的信息節(jié)點(diǎn)度分布。

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

2.2IPEG-CRT IRA碼的存儲復(fù)雜度分析

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

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

3性能分析

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

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

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

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

圖3　IPEG-CRT IRA碼與DVB-S2標(biāo)準(zhǔn)LDPC碼性能比較

4小結(jié)

首先通過改進(jìn)的PEG算法構(gòu)造出IRA碼H1子矩陣的基矩陣，然后利用循環(huán)中國剩余定理來構(gòu)造IRA碼。IPEG-CRT方法除了具備常規(guī)IRA碼較低線性編碼復(fù)雜度的優(yōu)勢，還在避免短環(huán)的同時(shí)降低了錯(cuò)誤平層，且降低了傳統(tǒng)構(gòu)造IRA碼的存儲復(fù)雜度，這樣在很大程度上節(jié)省了系統(tǒng)所需要的存儲空間，從而減少了硬件實(shí)現(xiàn)的成本和復(fù)雜度。仿真結(jié)果表明，在對應(yīng)的同等條件下，本文所構(gòu)造的IRA碼優(yōu)于剩余類數(shù)對IRA碼和PEG-IRA碼。除此之外，優(yōu)于DVB-S2標(biāo)準(zhǔn)LDPC碼，并且不需要設(shè)計(jì)交織器，可以作為代替衛(wèi)星通信領(lǐng)域的DVB-S2標(biāo)準(zhǔn)LDPC碼的一種選擇方案。

參考文獻(xiàn)：

[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]范文同，馬林華，林志國，等. 一類環(huán)長至少為10的準(zhǔn)循環(huán)LDPC碼 [J]. 電視技術(shù)，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，F(xiàn)ORNEY 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]鹿增輝，方勇，霍迎秋. 基于滑窗置信傳播算法的聯(lián)合信源信道編碼[J]. 電視技術(shù)，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]彭立，朱光喜，吳曉曉. 基于等差數(shù)列的LDPC碼編碼器設(shè)計(jì)[J]. 電子學(xué)報(bào)，2007，35(5)：950-954.

[10]彭立，張琦，王渤，等. 針對 IRA-LDPC 碼類的半隨機(jī)半代數(shù)結(jié)構(gòu)設(shè)計(jì)[J]. 通信學(xué)報(bào)，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.

責(zé)任編輯：許盈

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

文獻(xiàn)標(biāo)志碼：A

DOI：10.16280/j.videoe.2016.05.009

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61571072)；重慶市基礎(chǔ)與前沿研究計(jì)劃項(xiàng)目(cstc2015jcyjA40015)

收稿日期：2015-12-15

文獻(xiàn)引用格式：黃勝，敖翔，龐曉磊，等. 基于循環(huán)中國剩余定理和改進(jìn)PEG算法的IRA碼[J].電視技術(shù)，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.