一種改進(jìn)的QC-LDPC碼及其編碼器FPGA實(shí)現(xiàn)

衛(wèi)　霞,張文俊

(1．西北工業(yè)大學(xué) 明德學(xué)院 電子信息工程系，西安710124；2．陜西省通信管理局，西安710075)

?

一種改進(jìn)的QC-LDPC碼及其編碼器FPGA實(shí)現(xiàn)

衛(wèi)霞1,張文俊2

(1．西北工業(yè)大學(xué) 明德學(xué)院 電子信息工程系，西安710124；2．陜西省通信管理局，西安710075)

摘要：為了提高低密度準(zhǔn)循環(huán)奇偶校驗(yàn)碼(quasi-cyclic low density parity check codes, QC-LDPC)的編碼碼率靈活性和降低該碼的實(shí)現(xiàn)復(fù)雜度，提出了一種改進(jìn)的QC-LDPC碼構(gòu)造方法，并通過(guò)構(gòu)造校驗(yàn)矩陣設(shè)計(jì)出了幾種高碼率碼型，仿真結(jié)果表明該碼在中、長(zhǎng)幀長(zhǎng)時(shí)性能優(yōu)于相近參數(shù)的傳統(tǒng)QC-LDPC碼；針對(duì)該碼型設(shè)計(jì)了一種基于隨機(jī)存取存儲(chǔ)器(random-access memory, RAM)的編碼器硬件架構(gòu)，通過(guò)存儲(chǔ)地址指針實(shí)現(xiàn)對(duì)校驗(yàn)矩陣的存儲(chǔ)，使得編碼器能靈活地實(shí)現(xiàn)變碼率和變幀長(zhǎng)編碼。采用verilog硬件描述語(yǔ)言在Spartan-3 XC3S1500芯片上實(shí)現(xiàn)了編碼器。綜合結(jié)果顯示：新的硬件編碼架構(gòu)較基于移位寄存器的傳統(tǒng)QC-LDPC碼的編碼器硬件架構(gòu)，在編碼延時(shí)保持相同而硬件資源大幅降低的情況下，編碼器系統(tǒng)的最高頻率達(dá)到了225.174 MHz，能滿足高速編碼需求。

關(guān)鍵詞：低密度準(zhǔn)循環(huán)奇偶校驗(yàn)碼；基于RAM的編碼器；變碼率編碼

0引言

低密度奇偶校驗(yàn)(low density parity check，LDPC)碼[1]是一種性能逼近香農(nóng)限的前向糾錯(cuò)編碼技術(shù)。由于性能優(yōu)異[2]、設(shè)計(jì)靈活、較低的譯碼復(fù)雜度[3]，LDPC碼已被應(yīng)用于多種通信標(biāo)準(zhǔn)之中[4]。但是，采用普通的編碼方式，編碼復(fù)雜度與碼長(zhǎng)平方成正比，使得碼長(zhǎng)較長(zhǎng)時(shí)編碼復(fù)雜度過(guò)高。

為了適應(yīng)不同的信道環(huán)境，前向糾錯(cuò)編碼的幀長(zhǎng)及碼率需要自適應(yīng)調(diào)整以保證通信質(zhì)量。因此，如何設(shè)計(jì)碼率及幀長(zhǎng)可以自適應(yīng)調(diào)節(jié)的低復(fù)雜度的編譯碼器成為了當(dāng)前編碼領(lǐng)域研究的又一熱點(diǎn)問(wèn)題[5]。

YU Kou通過(guò)有限幾何構(gòu)造出的準(zhǔn)循環(huán)LDPC碼(quasi-cyclic LDPC, QC-LDPC)[6]，其編碼器可以采用移位寄存器簡(jiǎn)單地實(shí)現(xiàn)，降低了編碼復(fù)雜度，且性能在中短幀長(zhǎng)時(shí)與對(duì)應(yīng)參數(shù)的隨機(jī)LDPC碼相當(dāng)。LIN Shu等人提出了由循環(huán)校驗(yàn)矩陣得出系統(tǒng)循環(huán)生成矩陣的方法，并基于此設(shè)計(jì)了幾種基于移位寄存器的QC-LDPC高效編碼器架構(gòu)[7]。近兩年，雖然KANG Jingyu 及DIAO Qiuju等學(xué)者對(duì)QC-LDPC碼的構(gòu)造方法進(jìn)行了不同的改進(jìn)[8-9]，但是其編碼器架構(gòu)依然需要基于移位寄存器實(shí)現(xiàn)。

2011年以來(lái)，Yau和Falcao等[10-11]分別采用圖形處理器(graphics processing unit, GPU) 來(lái)測(cè)試LDPC 碼性能，基于GPU的平臺(tái)雖然不受移位寄存器架構(gòu)限制，但是從工程應(yīng)用方面考慮，基于GPU 的測(cè)試方案無(wú)助于工程應(yīng)用。

工程實(shí)現(xiàn)時(shí)，移位寄存器對(duì)編碼器碼率及幀長(zhǎng)自適應(yīng)變化的靈活性造成了限制，同時(shí)文獻(xiàn)[7]中的編碼架構(gòu)在硬件資源消耗上也存在優(yōu)化空間。

為了克服現(xiàn)有QC-LDPC碼編碼器實(shí)現(xiàn)時(shí)的問(wèn)題，本文作者提供了一種Mended QC-LDPC(MQC-LDPC)碼。該結(jié)構(gòu)可利用校驗(yàn)矩陣直接進(jìn)行編碼，并提供一種與該碼結(jié)構(gòu)對(duì)應(yīng)的基于RAM實(shí)現(xiàn)的編碼器，不僅有效降低硬件資源，還能實(shí)現(xiàn)靈活變碼率編碼。

1QC-LDPC碼介紹

準(zhǔn)循環(huán)LDPC碼的校驗(yàn)矩陣Hqc具有(1)式形式。

(1)

(1)式中：c,t為正整數(shù)，且c

①Ai,j的“重量”ω和b相比是個(gè)很小的整數(shù)，該條件保證了Hqc是稀疏矩陣；

②Ai,j組成的Hqc的任意兩列(行)“1”的重疊度λ≤1，該條件保證了Hqc對(duì)應(yīng)的二分圖上長(zhǎng)度是4的環(huán)不存在，進(jìn)而保證了QC-LDPC碼的譯碼性能[8]。

滿足上述條件Hqc的“零空間”就構(gòu)成了碼長(zhǎng)是b×t的QC-LDPC碼。同時(shí)若Ai,j的“重量”都相同，那么其構(gòu)成的Hqc對(duì)應(yīng)的列重(行重)也相同，都等于ω×c(ω×t)，此時(shí)的QC-LDPC碼即為“規(guī)則QC-LDPC”碼，否則即為“非規(guī)則QC-LDPC”碼。文獻(xiàn)[9]提出了“系統(tǒng)-準(zhǔn)循環(huán)生成矩陣”，即Hqc的秩與其行數(shù)相等且具有一個(gè)秩為r的c×c的子矩陣，此時(shí)Hqc對(duì)應(yīng)的生成矩陣Gqc的結(jié)構(gòu)為

(2)

(2)式中：0是b維的全零陣；I代表b維的單位矩陣；Gi,j代表b×b的循環(huán)方陣。

此時(shí)Gi,j可以被其第一行g(shù)i,j所確定，其中1≤i≤t-c,1≤j≤c，此時(shí)gi,j被稱為Gi,j的“行生成矢量”。由此，相關(guān)文獻(xiàn)在編碼實(shí)現(xiàn)時(shí)把gi,j存儲(chǔ)起來(lái)，通過(guò)移位寄存器來(lái)實(shí)現(xiàn)Gi,j，有效降低了存儲(chǔ)資源，提升了編碼效率[7]。但是在硬件實(shí)現(xiàn)時(shí)移位寄存器的長(zhǎng)度不能靈活變動(dòng)，進(jìn)而限制了自適應(yīng)編碼的靈活性。而且由于Gi,j并非稀疏矩陣，在中長(zhǎng)碼型時(shí)，即使僅僅對(duì)其生成元存儲(chǔ)也需要較多的存儲(chǔ)器資源，所以QC-LDPC碼依然存在優(yōu)化空間。

2MQC-LDPC碼構(gòu)造及其性能分析

通過(guò)在QC-LDPC碼的校驗(yàn)矩陣后面添加具有雙對(duì)角形式的校驗(yàn)矩陣[12]，構(gòu)造出MQC-LDPC碼的校驗(yàn)矩陣，即H=[H1H2]，其中，H2如(3)式。

(3)

構(gòu)造出參數(shù)為(6 131，5 110)的MQC-LDPC碼，H的行重為22(第一行為21)，對(duì)應(yīng)碼率為0.83，校驗(yàn)矩陣H為

(4)

(4)式中，H1是一個(gè)1 021×4 088的矩陣，列重為4。則H的列重包括4，2和1 3種情況。同理，構(gòu)造參數(shù)分別為(7 153，6 132)和(8 175，7 154)的MQC-LDPC碼，對(duì)應(yīng)碼率分別為0.86和0.88，校驗(yàn)矩陣的行重分別為26(第1行為25)和30(第1行為29)?？梢?jiàn)，3種碼型的碼率略有不同但均大于0.8，都屬于高碼率碼型。

圖1是上述3種參數(shù)的MQC-LDPC碼和與其相近參數(shù)的QC-LDPC碼的性能比較。由圖1可見(jiàn)，MQC-LDPC碼在幀長(zhǎng)分別為6131，7153和8175比特時(shí)，其性能均比相近參數(shù)的QC-LDPC碼略好。

3MQC-LDPC碼編碼器硬件實(shí)現(xiàn)

假定a為編碼前輸入的信息序列，C為編碼后得到的碼字，根據(jù)線性分組碼的定義C=a·G，由MQC-LDPC的校驗(yàn)矩陣對(duì)應(yīng)的生成矩陣具有系統(tǒng)形式：G=[I|P]，那么碼字C就可以劃分成信息序列a和校驗(yàn)序列p兩部分，即C=[a|p]，獲得校驗(yàn)序列p即可實(shí)現(xiàn)編碼過(guò)程。已知校驗(yàn)矩陣H=[H1H2],且C·HT=0，因此

(5)

由此可推出校驗(yàn)序列為

(6)

(7)

圖2　MQC-LDPC碼編碼器框架圖Fig.2　Encoding structure of MQC-LDPC codes

圖2中，中間校驗(yàn)序列pjk計(jì)算電路是在結(jié)合MQC-LDPC碼的Hqc矩陣的整體特性以及H1矩陣的循環(huán)特性設(shè)計(jì)出的基于RAM的編碼器架構(gòu)，其中，引入雙口RAM陣列存儲(chǔ)中間校驗(yàn)比特，通過(guò)地址指針表征校驗(yàn)矩陣并指示雙口RAM的操作地址，由對(duì)雙口RAM的讀寫(xiě)操作實(shí)現(xiàn)中間校驗(yàn)位的更新過(guò)程，最終將雙口RAM陣列的中間校驗(yàn)比特進(jìn)行模二加得到校驗(yàn)序列。中間校驗(yàn)序列pjk計(jì)算電路由異或門(mén)、地址指針存儲(chǔ)器、地址處理器、雙口RAM陣列、數(shù)據(jù)分配器以及模二加法器共6個(gè)部分組成，計(jì)算電路如圖3所示。

圖3　中間校驗(yàn)序列pj計(jì)算電路Fig.3　Intermediate check sequence pjcalculating circuit

(8)

(9)

表1　移位累加器電路操作真值表

實(shí)現(xiàn)時(shí)采用雙口RAM，每個(gè)RAM每個(gè)時(shí)鐘只能處理一個(gè)地址，所以為了提高編碼速度，需要多個(gè)RAM同時(shí)操作，具體RAM的數(shù)目則與一列校驗(yàn)子矩陣中生成元中的1的個(gè)數(shù)相對(duì)應(yīng)，每個(gè)RAM對(duì)應(yīng)一組地址指針，當(dāng)一幀信息位完成編碼后，將所有RAM的相同位置的存儲(chǔ)內(nèi)容取出做模二和運(yùn)算后送入重復(fù)累加器即得到了最終所求的中間校驗(yàn)序列。

3.2地址指針實(shí)現(xiàn)

地址指針處理器由2個(gè)雙輸入選擇器以及模b加法器組成。雙輸入選擇器中，第1個(gè)選擇器的1個(gè)輸入端固定接零，另1個(gè)輸入端固定接1；第2個(gè)選擇器的1個(gè)輸入端接地址指針存儲(chǔ)器的輸出端，另1個(gè)輸入端接加法器的輸出端。地址指針處理器每b個(gè)時(shí)鐘讀取一次地址指針存儲(chǔ)器的值，且僅在當(dāng)前時(shí)鐘時(shí)第1個(gè)選擇器選擇0作為輸入，其余b-1個(gè)時(shí)鐘選擇器選擇1作為輸出，這樣就實(shí)現(xiàn)了對(duì)RAM操作的地址指示。

3.3變碼率實(shí)現(xiàn)

同理，對(duì)于(8 175，7 154)碼，其校驗(yàn)矩陣形式為

(10)

4編碼器性能分析

傳統(tǒng)的QC-LDPC碼在編碼時(shí)，充分利用碼字特點(diǎn)，首先將校驗(yàn)矩陣通過(guò)計(jì)算變換成生成矩陣，然后利用生成矩陣的循環(huán)特性，通過(guò)移位寄存器進(jìn)行編碼。而本文基于RAM的MQC-LDPC碼編碼架構(gòu)，直接利用校驗(yàn)矩陣的特點(diǎn)，不需要求出生成矩陣而直接利用校驗(yàn)矩陣進(jìn)行編碼，由于校驗(yàn)矩陣的稀疏循環(huán)特性，從而使得編碼器占用的硬件資源與傳統(tǒng)的編碼器相比大幅度降低；由于引入了地址指針表示校驗(yàn)矩陣的存儲(chǔ)，不僅大大降低了存儲(chǔ)校驗(yàn)矩陣的資源，而且可以靈活實(shí)現(xiàn)變碼率編碼。

在ISE 6下使用Verilog HDL語(yǔ)言采用Xilinx公司的Spartan-3 XC3S1500芯片，設(shè)計(jì)了參數(shù)為(6 131，5 110)和(8 175，7 154)MQC-LDPC碼的編碼器，資源占用情況如表2所示，最終綜合結(jié)果表明整個(gè)編碼器系統(tǒng)的最高頻率為225.174 MHz。由于編碼器主要模塊有效地實(shí)現(xiàn)了復(fù)用，所以實(shí)現(xiàn)更多碼率時(shí)，除了Block RAM資源，其他資源類型不會(huì)額外增加。

表2　(6131，5110)和(8175，7154)MQC-LDPC碼編碼器

(11)

(11)式中，Ai,j的維數(shù)b=511。轉(zhuǎn)換成對(duì)應(yīng)的生成矩陣，需要存儲(chǔ)6×2×511=6 132個(gè)二進(jìn)制數(shù)值。表3給出了實(shí)現(xiàn)相同參數(shù)的2種碼型所需要資源對(duì)比情況。如上所述，同QC-LDPC碼編碼器實(shí)現(xiàn)時(shí)所用的移位寄存器以及存儲(chǔ)器相比，資源占用率大為降低。

表3　QC-LDPC碼編碼實(shí)現(xiàn)和MQC-LDPC

綜上所述，基于RAM實(shí)現(xiàn)的MQC-LDPC碼的編碼器較之與基于移位寄存器實(shí)現(xiàn)的QC-LDPC碼編碼器在編碼保持相同的情況下，在硬件資源占用上有了大幅的降低。

5結(jié)論

本文提出了一種對(duì)QC-LDPC的改進(jìn)構(gòu)造，該結(jié)構(gòu)在中、長(zhǎng)幀長(zhǎng)時(shí)編碼性能較之于QC-LDPC碼有所提升，該改進(jìn)碼型具有線性的編碼復(fù)雜度。本文還針對(duì)該改進(jìn)碼型提出了基于RAM的硬件實(shí)現(xiàn)架構(gòu)。與傳統(tǒng)的利用移位寄存器實(shí)現(xiàn)QC-LDPC碼的編碼器相比，該架構(gòu)不僅在硬件資源占用上大為降低，而且由于對(duì)校驗(yàn)矩陣的存儲(chǔ)簡(jiǎn)化為對(duì)地址指針的存儲(chǔ)，更加有利于靈活變碼率實(shí)現(xiàn)。這就為L(zhǎng)DPC碼在不同通信質(zhì)量和傳輸環(huán)境下的應(yīng)用提供了可能性。

參考文獻(xiàn)：

[1]GALLAGER R G. Low-Density Parity-Check Codes[D]. IRE Transactions Information Theory. 1962 (8):21-28.

[2]MACKAY D J C, NEAL R M. Near Shannon Limit Performance of Low-Density Parity-Check Codes[J]. Electronics letters. 1997 (33):457-458.

[3]DARABIHA A, CARUSONE A C, KSCHISCHANG F R. Multi-Gbit/sec Low Density Parity Check Decoders with Reduced Interconnect Complexity[EB/OL]. [2015-01-12]. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1465805, 2005-08-25/2008-07-10.

[4]XU Dazheng, LIU Aijun. Research on Combined LDPC Decoding Iterative Soft—Decision Demodulation Algorithm of 16·APSK in DVB-S2[J]. Journal of Astronautics, March, 2011, 94 (1):634-639.

[5]SUN Y, KARKOOTI M, CAVALLARO J R. VLSI decoder architecture for high throughput, variable block-size and multi-rate LDPC codes[C]// IEEE International Symposium on Circuits and Systems, 2007. New Orleans, LA : IEEE, 2007: 2104-2107.

[6]YU Kou, LIN Shu, FOSSORIER M P C. Low-density parity-check codes based on finite geometries: a rediscovery and new results[J]. IEEE Trans Info Theory, 2001, 47 (7)：2711-2736.

[7]LI Zongwang, CHEN Lei, ZENG Lingqi, et al. Efficient Encoding of Quasi-cyclic Low-Density Parity-Check Codes[J]. IEEE Transactions on Communications, 2006, 54(1):71-81.

[8]KANG Jingyu, HUANG Qin, ZHANG Li, et al. Quasi-Cyclic LDPC Codes: An Algebraic Construction[J]. IEEE Transactions on Communications, 2010, 58(5): 1383-1396.

[9]DIAO Qiuju, HUANG Qin, LIN Shu. Life Fellow, IEEE, and Khaled Abdel-Ghaffar. A Matrix-Theoretic Approach for Analyzing Quasi-Cyclic Low-Density Parity-Check Codes[J]. IEEE Transactions on Information Theory, 2012, 58(6): 4030-4048.

[10] YAU S F, WONG T L, LAU F C M. Extremely fast simulator for decoding LDPC codes[C]//Proceeding of 13th International Conference on Advanced Communication Technology(ICACT). Gangwon-Do, Korea:IEEE, 2011: 635-639.

[11] FALCAO G, ANDRADE J, SILVA V, SOUSA L. GPU-based DVB-S2 LDPC decoder with high throughput and fast error floor detection[J]. Electronics Letters, 2011, 47(9):542-546.

[12] CAI Z, HAO J, TAN P H, et al. Efficient encoding of IEEE 802.11n LDPC codes[J]. Electronics Letters, 2006, 42(25): 1471-1472.

[13] YANG M, RYAN W E,YAN L. Design of Efficiently Encodable Moderate-Length High-Rate Irregular LDPC Codes[J]. IEEE Transactions on Communications, 2004, 52 (4): 564-571.

An improved structure of QC-LDPC codes and its FPGA encoder implementation

WEI Xia1，ZHANG Wenjun2

(1. Department of Electronic Information Engineering, Mingde College of Northwestern Polytechnical University, Xian 710124, P. R. China;2. Shanxi Communications Administration, Xian 710075, P. R. China)

Abstract:In order to increase encoding rate flexibility and reduce its operation complexity, an improved structure of QC-LDPC codes is proposed, and several high rate codes were designed. Simulation result shows that the performance of the improved LDPC codes is better than that of conventional QC-LDPC codes in moderate and long frame length. An encoding architecture based on RAM is designed. The encoder stores the check matrix by storing address-pointers, thus multi-rate encoding is flexible. The encoder is implemented with Verilog HDL language on the chip of Spartan 3 XC3S1500. Synthesis reports show that the systems maximum frequency is 225.174 MHz with less resource and the same encoding time-delay of normal QC-LDPC encoder based on shift-register.

Keywords：quasi-cyclic low density parity check codes; encoder based on RAM; multi-rate encoding

DOI：10.3979/j.issn.1673-825X.2016.01.009

收稿日期：2015-03-18

修訂日期：2016-01-05通訊作者： 張文俊185691479@qq.com

中圖分類號(hào)：TN911.22

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

文章編號(hào)：1673-825X(2016)01-0060-06

作者簡(jiǎn)介：

衛(wèi)霞(1984-)，女，山西運(yùn)城人，講師，碩士，主要從事信道編碼方面的研究。

E-mail：wxia66@163.com。

張文俊(1984-)，男，河南商丘人，工程師，碩士，工作研究方向?yàn)樾诺谰幋a、網(wǎng)絡(luò)與信息安全。E-mail：185691479@qq.com。

(編輯：魏琴芳)