基于循環(huán)差集的LDPC碼的快速編碼實(shí)現(xiàn)

楊衛(wèi)國，于志軍

(海軍航空大學(xué)，煙臺 264001)

0 引 言

低密度奇偶校驗(yàn)碼(Low-Density Parity-Check，LDPC碼)因其接近香農(nóng)極限的譯碼性能，成為近年來信道編碼研究的熱點(diǎn)。LDPC碼是Gallager博士在1962年提出的，但由于當(dāng)時(shí)的條件所限，并沒有引起人們足夠的關(guān)注，在沉寂了幾十年后，由Mackay和Neal證明了其在BP譯碼算法下，可以達(dá)到接近香農(nóng)極限的性能，這之后，LDPC碼爆發(fā)出了巨大的生命力[1-3]。以Gallager隨機(jī)構(gòu)造法和Mackay隨機(jī)構(gòu)造法為代表的隨機(jī)構(gòu)造法引領(lǐng)了LDPC碼最初幾年的發(fā)展，在Yu Kou和Shu Lin等人提出了利用有限域里的歐式幾何和投影幾何來構(gòu)造LDPC碼之后，循環(huán)和準(zhǔn)循環(huán)LDPC碼進(jìn)入了人們的視線，這一類碼字的校驗(yàn)矩陣具有循環(huán)或準(zhǔn)循環(huán)特性，在編碼過程中，編碼器只需要使用簡單的線性反饋移位寄存器來實(shí)現(xiàn)，大大降低了編譯碼復(fù)雜度，且有效縮減了需要的存儲空間，是近幾年來發(fā)展的重點(diǎn)。本文根據(jù)循環(huán)差集構(gòu)造的檢驗(yàn)矩陣自身的特點(diǎn)，采用快速編碼的方法完成循環(huán)差集QC-LDPC碼的構(gòu)造，進(jìn)一步降低了編碼復(fù)雜度[4-8]。

1 循環(huán)差集的基本定義

1.1 循環(huán)差集的定義

定義一個(gè)循環(huán)差集由3個(gè)整數(shù)(v,k,λ)組成的整數(shù)對確定，記作D(v,k,λ)，表示以正整數(shù)v為模的k個(gè)互不同余的整數(shù)所組成的集，具體如(1)式所示

D=(a1,a2, …,ak)(modv)

(1)

如果對于d≠0(modv)，在D中恰好存在λ個(gè)有序?qū)?ai,aj)能使等式(2)成立，

d=ai-aj(modv)

(2)

其中v稱為循環(huán)差集的模，k稱為循環(huán)差集的大小，3個(gè)參數(shù)之間滿足k(k-1)=λ(v-1)的關(guān)系式。

當(dāng)λ=1時(shí)，一個(gè)大小為k的循環(huán)差集的模v滿足等式(3)，我們稱這樣的循環(huán)差集為完備循環(huán)差集。

v=k2-k+1

(3)

在完備循環(huán)差集的差集表中，非零元素只出現(xiàn)一次。例如一個(gè)大小為k=4，模v=13的完備循環(huán)差集{0,1,8,10}的差集表如表1所示。

表1 k=4，v=13完備循環(huán)差集差集表

表1中左側(cè)表的第一行和第一列順序排列k=4，v=13完備循環(huán)差集的元素，表中其余行的元素均由其上一行元素對應(yīng)減去第一列的該行元素所得；對表1中左側(cè)的表的有效部分取模13就可以得到右側(cè)的差值表，表中除了0元素外，其余元素均不相同，且每個(gè)元素都只出現(xiàn)一次，且13滿足等式v=k2-k+1，因此循環(huán)差集{0,1,8,10}是一個(gè)完備循環(huán)差集。又例如模v=21，大小為k=5的完備循環(huán)差集為{0,5,6,9,19}。

1.2 完備循環(huán)差集的構(gòu)造

差集以0，0，1開頭，序列中其他元素滿足如下等式：

an=A·an-1+B·an-2+C·an-3

(4)

當(dāng)A=B=C=1時(shí)，得到如下序列：

0，0，1，1，2，4，7，13，24，

44，81，149，274，504，927，…

對該序列取模q=3，并從0開始計(jì)數(shù)得：

表2 模13的完備循環(huán)差集

從表2中可以看出，對上述序列取模q=3后，若以“雙0”為起始點(diǎn)，序列構(gòu)成了一個(gè)周期為13的循環(huán)，而0的位置{0,1,8,10}剛好是模13的完備循環(huán)差集。完備循環(huán)差集序列的構(gòu)造由三元數(shù)組(A,B,C)來確定，當(dāng)取A=C=1,B=0時(shí)，對生成的序列取模q=2得：

表3 模7的完備循環(huán)差集

這樣就構(gòu)成了一個(gè)模為7的完備循環(huán)差集{0,1,5}，需要特別注意的是，循環(huán)差集的模和序列取模是不一樣的(循環(huán)差集的模v=7，序列取模q=2)。

通過以上兩個(gè)例子可以看出，當(dāng)完備循環(huán)差集的模v不同時(shí)，用來生成循環(huán)差集的序列不同，對序列取模的模q也不相同，這里模q只可以是任意素?cái)?shù)，通過改變(A,B,C)的值，我們總能找到可以生成模v=q2+q+1，大小k=q+1的完備循環(huán)差集的序列，具體不同模q所對應(yīng)的(A,B,C)的生成規(guī)則如下：

(1)A,B∈[0,1,2,…,q-1]，C∈[1,2,…,q-1]且A和B不能同時(shí)為零，改變A,B,C的值，使到的序列的周期為v=q2+q+1，q=k-1是個(gè)素?cái)?shù)；

(2)若存在任意一個(gè)正的整數(shù)z，滿足式子z3=Az2+Bz+C(modq)，則此時(shí)的(A,B,C)所對應(yīng)的序列不是我們需要的。

2 基于完備循環(huán)差集LDPC碼的構(gòu)造

使用和積譯碼算法時(shí)，校驗(yàn)矩陣中的環(huán)長對譯碼性能影響很大，一旦出現(xiàn)長度為4的環(huán)，將使碼字的性能急劇惡化，而利用完備循環(huán)差集構(gòu)造的LDPC碼可以保證校驗(yàn)矩陣中不含有長度為4的短環(huán)，因此，在校驗(yàn)矩陣擴(kuò)展后產(chǎn)生的新的校驗(yàn)矩陣中也不會含有4環(huán)[4-5]。具體的構(gòu)造步驟如下：

(1)根據(jù)完備循環(huán)差集的大小k，模v以及三元數(shù)組(A,B,C)來生成一個(gè)完備循環(huán)差集；

(2)根據(jù)生成的完備循環(huán)差集得到相應(yīng)的關(guān)聯(lián)矢量，關(guān)聯(lián)矢量可以通過對完備循環(huán)差集取模q=k-1得到，當(dāng)模值為零則對應(yīng)位取“1”，否則取“0”，關(guān)聯(lián)矢量的長度為v，例如，表-3中的模7完備循環(huán)差集的關(guān)聯(lián)矢量為[1 1 0 0 0 1 0];

(3)將關(guān)聯(lián)矢量按照每次一位的位移量同方向循環(huán)移位v-1次，依次得到初始矩陣的2～v行，組合得到一個(gè)v×v的矩陣，例如首行為[1 1 0 0 0 1 0]，次行為[0 1 1 0 0 0 1]，依此類推；

(4)根據(jù)不同的權(quán)重和碼率要求，將初始矩陣進(jìn)行列分割得到校驗(yàn)矩陣的基矩陣；

(5)直接用步驟(4)生成的基矩陣作為校驗(yàn)矩陣或者擴(kuò)展基矩陣，將基矩陣中的0元素和1元素分別替換為全零矩陣和循環(huán)移位矩陣，即得碼字的校驗(yàn)矩陣。

這種編碼方法雖然利用完備循環(huán)差集的特性，構(gòu)造了不含四環(huán)的校驗(yàn)矩陣，但是在編碼過程中仍然需要用到生成矩陣，對于碼長較長的碼字仍有大量的計(jì)算，沒有能充分利用完備循環(huán)差集的特性。在生成關(guān)聯(lián)矩陣的過程中不難發(fā)現(xiàn)，由于構(gòu)造碼字設(shè)定的完備循環(huán)差集均以“雙0”開頭，因此，產(chǎn)生的關(guān)聯(lián)矢量的前兩位永遠(yuǎn)是“1”，即[1 1 …]，以此生成的關(guān)聯(lián)矩陣就必然具有雙對角線的結(jié)構(gòu)，繼續(xù)前面的例子，以模7完備循環(huán)差集為例，關(guān)聯(lián)矢量循環(huán)移位后的矩陣如下式所示：

(5)

式(5)中的矩陣H具有標(biāo)準(zhǔn)的雙對角線結(jié)構(gòu)，在快速編碼算法中，通過將校驗(yàn)矩陣合理的進(jìn)行排列，使得校驗(yàn)位的元素可以構(gòu)成準(zhǔn)雙對校驗(yàn)結(jié)構(gòu)，就可以在編碼過程中不通過生成矩陣直接進(jìn)行編碼生成系統(tǒng)碼。以此為依據(jù)，重新定義步驟(4)，在對初始矩陣進(jìn)行列分割的過程中，特意保留雙對角線上的1元素，即：

(4’)對初始矩陣進(jìn)行列分割，對于第j列(j>1)，保留H(j-1,j),H(j,j)兩元素，并將其余位置置0生成新的列，將新生成的列放置于基矩陣的第v+j列，第一列只保留第一行的元素。

步驟(5)不變。

繼續(xù)上面的例子，初始矩陣H按照快速編碼方法進(jìn)行列分割后生成的基矩陣如式(6)所示。

?

(6)

生成矩陣Hb由于具有雙對角線結(jié)構(gòu)，在編碼過程中可以采用快速編碼方法，在不需要生成矩陣的情況下完成對信息的編碼，相對于以往利用循環(huán)差集構(gòu)造LDPC碼的方法，具有更高的編譯碼速率。

在對基矩陣進(jìn)行擴(kuò)展時(shí)，最簡單的方法就是將矩陣中的1元素和0元素分別替換為單位矩陣和全零矩陣，但這樣生成的校驗(yàn)矩陣與基矩陣的環(huán)結(jié)構(gòu)基本一致，并無太多改善，為了確保獲得性能更加優(yōu)良的碼字，在擴(kuò)展基矩陣的過程中，可以通過計(jì)算機(jī)搜索的方式確定循環(huán)移位矩陣的移位次數(shù)，減少校驗(yàn)矩陣中的6環(huán)，改善碼性能。

3 仿真分析

按照前文所示的步驟，由于進(jìn)行步驟(4’)時(shí)，除了第1列分割出一個(gè)“1”，其余v-1列分割出兩個(gè)“1”，當(dāng)k>3時(shí)，在不需要進(jìn)行快速編碼的情況下，可以根據(jù)碼率繼續(xù)對前v列進(jìn)行列分割得到相應(yīng)的校驗(yàn)矩陣。根據(jù)不同的素?cái)?shù)可以構(gòu)造不同的循環(huán)差集，繼而可以構(gòu)造不同碼率的各種碼長的LDPC碼，表4列出了不同素?cái)?shù)對應(yīng)的不同碼長的LDPC碼。

表4 部分循環(huán)差集對應(yīng)的LDPC碼

根據(jù)香農(nóng)信道編碼定理的三個(gè)必要條件之一碼長趨于無限長時(shí)碼性能接近香農(nóng)極限，且q較大時(shí)循環(huán)差集的構(gòu)造比較復(fù)雜，因此本文只研究碼長較短的情況。表-5列出了部分素?cái)?shù)對應(yīng)的完備循環(huán)差集，首先考慮快速編碼算法，即碼率均為1/2。

表5 部分素?cái)?shù)對應(yīng)的完備循環(huán)差集

根據(jù)表5所示，取z=0，對應(yīng)不同的q可以得到不同碼長的LDPC碼，按照前文所述的步驟，根據(jù)完備循環(huán)差集生成的碼，對編碼輸出采用BPSK調(diào)制，傳輸信道選用AWGN信道，譯碼算法采用和積譯碼算法，對不同碼長的碼性能仿真結(jié)果如圖1所示。

圖1 不同q值構(gòu)造的LDPC碼

從圖1中可以看出，在信噪比較低時(shí)，較小的q值和較短碼長的碼字性能反而高于碼長較長的碼字，這是因?yàn)椋诶醚h(huán)差集構(gòu)造LDPC碼時(shí)，行重就等于循環(huán)差集的大小k，由LDPC碼校驗(yàn)矩陣的性質(zhì)可知，變量節(jié)點(diǎn)的度越大，該變量節(jié)點(diǎn)從校驗(yàn)節(jié)點(diǎn)上獲得的校驗(yàn)信息就越多，在譯碼時(shí)就可以迅速收斂到其真值，而校驗(yàn)節(jié)點(diǎn)的度數(shù)越大，在校驗(yàn)方程中引入的誤差就越大，校驗(yàn)節(jié)點(diǎn)的度數(shù)就是常用的行重，因此，行重小的碼在一定碼長范圍內(nèi)有更優(yōu)異的性 能，但當(dāng)信噪比較大時(shí)，碼長對碼性能的影響更加明顯。

圖1顯示的是直接采用循環(huán)差集構(gòu)造的LDPC碼的性能，當(dāng)z≠0時(shí)，理論上可以通過改變z的值獲得各種碼長的碼字，繼續(xù)對各種循環(huán)差集構(gòu)造的碼字進(jìn)行仿真，同樣對編碼輸出采用BPSK調(diào)制，傳輸信道選用AWGN信道，譯碼算法采用和積譯碼算法。對上述不同q的取值，分別取z=5,z=10，仿真結(jié)果如圖2～圖5所示。

圖2 q=5時(shí)循環(huán)差集LDPC碼性能仿真

圖3 q=7時(shí)循環(huán)差集LDPC碼性能仿真

圖4 q=11時(shí)循環(huán)差集LDPC碼性能仿真

圖5 q=17時(shí)循環(huán)差集LDPC碼性能仿真

通過對圖2～5的比較不難看出，當(dāng)z≠0時(shí)，碼長變長了，以不同q值構(gòu)造的碼性能均有了一定程度的提高，但各種碼字性能提高的程度大相徑庭，對于q=17的情況，根據(jù)上述分析性能仍然較差；q=11時(shí)，在低信噪比情況下碼字性能幾乎沒有改善，只有信噪比較高時(shí)碼字性能改善明顯；q=5和q=7兩種情況下碼字性能改善最為明顯。

當(dāng)不采用快速編碼算法，對q=5，q=7，q=11和q=17分別取碼率為1/3，1/3，1/4，1/4進(jìn)行仿真，仿真條件不變，仿真結(jié)果如圖6所示。

圖6 不同q值不同碼率LDPC性能比較

從圖6中可以看出，仍然是q=5和q=7時(shí)構(gòu)造的碼字具有最優(yōu)的性能，q=11和q=17的碼字性能幾乎相同。由于對不同q值的仿真結(jié)果中碼字長度均不一致，q=5和q=7時(shí)在碼字長度較短的情況下仍然獲得了比碼字長度較長的碼更優(yōu)異的性能，因此，單獨(dú)對q=5和q=7時(shí)構(gòu)造的碼字進(jìn)行仿真。

圖7 q=5和q=7時(shí)構(gòu)造的碼字性能比較

從圖7中可以看出，當(dāng)碼率為1/2時(shí)，q=5和q=7構(gòu)造的碼長相近的碼字性能幾乎相同，而當(dāng)碼率為1/3時(shí)，q=7構(gòu)造的碼字性能更為優(yōu)異，但無論q值的改變，本文方法構(gòu)造的碼字在1/2碼率時(shí)擁有最佳的性能。

基于此，分別采用q=5和q=7構(gòu)造的碼字為基準(zhǔn)碼，碼率為1/2，通過改變z的值使其與IEEE802.16e標(biāo)準(zhǔn)的碼字性能進(jìn)行比較，仿真結(jié)果如圖8。

圖8 完備循環(huán)差集構(gòu)造的LDPC碼與IEEE802.16e標(biāo)準(zhǔn)的碼在長碼時(shí)性能比較

圖8中，q=5，z=28構(gòu)造的碼長為1736的碼字，q=7，z=15構(gòu)造的碼長為1710的碼字與IEEE802.16e標(biāo)準(zhǔn)中碼長為1728的碼字性能進(jìn)行對比，通過觀察不難發(fā)現(xiàn)，三種碼的性能極為接近，在信噪比小于1.5時(shí)，q=5構(gòu)造的碼字與IEEE802.16e標(biāo)準(zhǔn)碼性能幾乎一致，但當(dāng)信噪比增大時(shí)，完備循環(huán)差集q=7構(gòu)造的LDPC碼的性能更加優(yōu)異。

4 結(jié) 語

本文基于完備循環(huán)差集構(gòu)造了QC-LDPC碼的校驗(yàn)矩陣，并根據(jù)構(gòu)造特點(diǎn)對檢驗(yàn)矩陣進(jìn)行了列分割重排，使得校驗(yàn)矩陣具有了雙對角線結(jié)構(gòu)，在編碼過程中可以采用快速編碼算法，不必計(jì)算生成矩陣，進(jìn)一步簡化了編碼過程，且由完備循環(huán)差集構(gòu)造的校驗(yàn)矩陣中不含四環(huán)，保證了碼性能，同時(shí)由于在校驗(yàn)矩陣的構(gòu)造過程中只是對關(guān)聯(lián)矢量的移位組合，因此大大節(jié)省了存儲空間，此外，根據(jù)完備循環(huán)差集的生成方式，幾乎可以覆蓋所有碼字長度，且可以通過改變z的值，對校驗(yàn)矩陣進(jìn)行擴(kuò)展，構(gòu)造方式多樣，碼字性能優(yōu)異。另外通過仿真分析發(fā)現(xiàn)，并不是所有的完備循環(huán)差集都適合構(gòu)造LDPC碼，特別是當(dāng)差集大小較大，對應(yīng)構(gòu)造的校驗(yàn)矩陣的行重過大會嚴(yán)重影響碼字性能，在本文選取的幾種循環(huán)差集構(gòu)造的LDPC碼中，q=5和q=7時(shí)構(gòu)造的碼字無論是短碼還是長碼都有較優(yōu)異的誤碼性能，低信噪比時(shí)q=5構(gòu)造的碼字性能占優(yōu)，而高信噪比時(shí)q=7構(gòu)造的碼字性能占優(yōu)[9-10]。

[1] GALLAGER R G.Low-density parity-check codes[J].Information Theory,IRE Transactions on,1962,8(1):21-28.

[2] MacKay D J C.Good error-correcting codes based on very sparse matrices[J].Information Theory,IEEE Transactions on,1999,45(2):399-431.

[3] 何善寶，趙春明，姜明.LDPC碼的一種循環(huán)差集構(gòu)造方法[J].通信學(xué)報(bào)，2004,25(11)：112-118.

[4] 靳蕃，陳志.組合編碼原理及應(yīng)用[M].上?？茖W(xué)技術(shù)出版社，1994.

[5] 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.

[6] Tanner R M,Sridhara D,et al.LDPC block and convolutional codes Based on circulant matrices[J].IEEE Transactions on Information Theory,2004,50(12):2966-2984.

[7] Gallager R G.Low-Density Parity-Check Codes[D],Cambridge,M A:MIT Press,1963.

[8] MA Ke-xiang,ZHANG Peng.Low-Delay Loop Detection Algorithm for LDPC Codes[J].Journal of CAEIT,2015(4):341-343.

[9] Ivan B.Djordjevic.Quanturn LDPC Codes from Balanced Incomplete Block Designs[J].IEEE Commun.Letters,Vol.12,No.15,May 2008.

[10] Baraza J,Gracia J,Blanc S,et al.Enhancement of Fault Injection Techniques Based on the Modification of VHDL Codes[J].IEEE Trans.on Very Large Scale Integration Systems,2008,16(6):693-706.