衛(wèi)　霞,張文俊

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

1QC-LDPC碼介紹

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

(1)

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

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

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

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

(2)

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

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

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

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

(3)

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

(4)

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

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

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

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

(5)

由此可推出校驗序列為

(6)

(7)

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

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

圖3　中間校驗序列pj計算電路Fig.3　Intermediate check sequence pjcalculating circuit

(8)

(9)

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

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

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

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

3.3變碼率實現(xiàn)

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

(10)

4編碼器性能分析

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

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

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

(11)

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

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

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

5結(jié)論

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

參考文獻：

[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

中圖分類號：TN911.22

文獻標志碼：A

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

作者簡介：

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

E-mail：wxia66@163.com。

張文俊(1984-)，男，河南商丘人，工程師，碩士，工作研究方向為信道編碼、網(wǎng)絡(luò)與信息安全。E-mail：185691479@qq.com。

(編輯：魏琴芳)