無短環(huán)不規(guī)則QC_LDPC碼的快速編碼及聯(lián)合譯碼

劉蕾等

摘 要： 基于不規(guī)則部分并行結(jié)構(gòu)設(shè)計(jì)了一種高吞吐量，低復(fù)雜度，碼長(zhǎng)碼率可變且去除四環(huán)的低密度奇偶校驗(yàn)LDPC碼及其譯碼結(jié)構(gòu)實(shí)現(xiàn)方案，該編碼結(jié)構(gòu)可針對(duì)不同碼長(zhǎng)的不規(guī)則部分并行結(jié)構(gòu)LDPC碼進(jìn)行擴(kuò)展，譯碼器采用縮放最小和定點(diǎn)（Sum?Min）算法實(shí)現(xiàn)譯碼，中間信息節(jié)點(diǎn)存儲(chǔ)器地址采用格雷碼編碼，降低動(dòng)態(tài)功耗；采用Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片設(shè)計(jì)了一款碼長(zhǎng)1 270，碼率[12]的不規(guī)則部分并行LDPC碼的編碼器和譯碼器。綜合結(jié)果表明：該編碼器信息吞吐量為2.52 Gb/s，譯碼器在10次迭代的情況下信息吞吐率達(dá)到44 Mb/s。

關(guān)鍵詞： 低密度奇偶校驗(yàn)碼； 不規(guī)則碼； 部分并行結(jié)構(gòu)； FPGA

中圖分類號(hào)： TN911.22?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）17?0034?04

Fast coding and joint decoding of irregular QC_LDPC codes without short?cycle

LIU Lei1， SUN Shulong1， CHANG Liang2， LI Huawang2

（1. Shanghai Institute of Microsystem and Information Technology， Chinese Academy of Sciences， Shanghai 200050， China；

2. Shanghai Engineering Center for Microsatellites， Shanghai 200120， China）

Abstract： The low density parity check （LDPC） codes and the implementation scheme of the decoding structure were designed based on irregular semi?parallel structure. LDPC codes without four cycles have high throughput and low complexity， whose length and rate are variable. This coding structure can extend irregular semi?parallel LDPC codes with different code length. The decoder adopts Sum?Min algorithm to realize decoding. The memory address of middle information nodes applies Gray coding to reduce dynamic power consumption. Based on this structure， encoder and decoder of irregular semi?parallel LDPC codes were designed by using Xilinx Virtex?5 XC5VtX150T?ff1156 FPGA， whose code length is 1 270 bit and code rate is [12.] The comprehensive results show that the information throughput of this encoder can achieve 2.52 Gb/s and the information throughput rate of the decoder can reach 44 Mb/s in the case of 10 iterations.

Keywords： LDPC code； irregular code； semi?parallel structure； FPGA

0 引 言

低密度奇偶校驗(yàn)碼（Low Desity Parity Check，LDPC）又被稱為Gallager碼，是Gallager在1960年提出的，LDPC碼在AWGN信道下具有非常好的性能，目前最好的仿真結(jié)果表明，隨機(jī)LDPC碼在AWGN白噪聲下距離Shannon限僅0.004 5 dB。LDPC碼是一類逼近Shannon限的隨機(jī)碼，其譯碼復(fù)雜度低，信息吞吐量大，靈活性高，可以避免Turbo碼類似的錯(cuò)誤平層，且完全可并行實(shí)現(xiàn)，更適合高速的無線數(shù)據(jù)業(yè)務(wù)。LDPC面臨的最主要問題是它的編碼復(fù)雜度高，是碼長(zhǎng)的O（[N2]），而Turbo碼的編碼復(fù)雜度與碼長(zhǎng)線性相關(guān)。現(xiàn)在結(jié)構(gòu)化準(zhǔn)循環(huán)LDPC碼是編碼結(jié)構(gòu)的研究熱點(diǎn)，可以在譯碼性能保持的前提下，用來簡(jiǎn)化編碼器的復(fù)雜度， 已經(jīng)被業(yè)內(nèi)廣泛采用，目前，由于結(jié)構(gòu)化LDPC碼性能優(yōu)越，已經(jīng)被IEEE 802.16e，IEEE 802.11n，IEEE 802.3an和DVB?S.2等標(biāo)準(zhǔn)采用，并被廣泛應(yīng)用于衛(wèi)星通信，深空通信，光通信和下一代移動(dòng)通信系統(tǒng)中。

為了在工程實(shí)踐中降低編譯碼器的復(fù)雜度，研究人員系統(tǒng)地研究了結(jié)構(gòu)化LDPC碼的硬件實(shí)現(xiàn)技術(shù)，發(fā)現(xiàn)了一些制約LDPC碼的編碼器和譯碼器高速實(shí)現(xiàn)的因素，具體包括：編碼器如果直接由生成截止實(shí)現(xiàn)，工程復(fù)雜度過高；全并行譯碼器結(jié)構(gòu)實(shí)現(xiàn)時(shí)內(nèi)部聯(lián)系過多，運(yùn)算單元過于復(fù)雜；對(duì)于串行結(jié)構(gòu)，LDPC碼的高速并行特點(diǎn)很難發(fā)揮。

針對(duì)以上問題，本文提出了一種高吞吐量，低復(fù)雜度并且碼速、碼率可擴(kuò)展的非奇異子矩陣的不規(guī)則部分并行編碼、譯碼結(jié)構(gòu)，構(gòu)造了性能優(yōu)良、結(jié)構(gòu)合理的部分并行譯碼實(shí)現(xiàn)的結(jié)構(gòu)化LDPC碼校驗(yàn)矩陣，并采用Xilinx公司的Virtex?5 XC5VtX150T?ff1156 FPGA芯片設(shè)計(jì)了一款碼長(zhǎng)1 270，碼率[12]的不規(guī)則部分并行LDPC碼的編碼器和譯碼器，實(shí)驗(yàn)結(jié)果表明，該編碼器可以實(shí)現(xiàn)數(shù)據(jù)吞吐率2.51 Gb/s，譯碼器在采用10次迭代的情況下，信息吞吐量達(dá)到44 Mb/s。

1 不規(guī)則QC碼快速編碼

文獻(xiàn)[1]指出，規(guī)則QC碼的校驗(yàn)矩陣是奇異的，如果將校驗(yàn)矩陣分成兩個(gè)子矩陣即[H=[Ha Hb]，]則無法得到奇異的子矩陣[Ha或Hb，]參考802.16e中的LDPC碼的設(shè)計(jì)，可以獲得快速編碼的不規(guī)則QC編碼的LDPC校驗(yàn)矩陣的子矩陣。

結(jié)構(gòu)化LDPC碼的奇偶校驗(yàn)矩陣[H]是[M×N]維的矩陣，由[mb×nb]的標(biāo)準(zhǔn)循環(huán)移位矩陣構(gòu)成，其中[M=mb×z，][N=nb×z，][H]矩陣的形式如式（1）：

[H=[HaHb]=I1Ia…Iak-1Ix1I0…0IbIab…Iak-1b0II…0Ib2Iab2…Iak-1b2Ix20II…?????????Ibk-1Iabk-1…Iak-1bk-1Ix300…I] （1）

快速編碼算法，令信息比特[S=[s1s2s3…sk]，]結(jié)構(gòu)化LDPC碼根據(jù)結(jié)果可以分為信息序列和校驗(yàn)序列，由信息序列[S]可以得到校驗(yàn)序列[Vm×1，]其中[si，][i≤k]是一個(gè)[Z]維的列向量，編碼后的輸出[C=[SV]；]根據(jù)校驗(yàn)方程，[HaSΤ+HbVΤ=0]。[Ix1+Ix2+Ix3?VT1=i=1kj=1kHi，jSTj，]設(shè)中間變量[T（i）=i=1kHi，j?STj，]根據(jù)[Vi]計(jì)算[Vi+1，][Vi+1=Vi+T（i），i

2 LDPC譯碼算法選擇

LDPC碼譯碼算法分為基于置信傳播的BP算法以及在此基礎(chǔ)上衍生出的LLR BP算法，另一類譯碼算法基于比特翻轉(zhuǎn)（BF）算法，由于比特翻轉(zhuǎn)過程損失了信道軟信息，譯碼性能較差，BP算法涉及大量非線性運(yùn)算，復(fù)雜度較高。本文采用一種改進(jìn)的基于BP原理的歸一化最小和積算法實(shí)現(xiàn)LDPC的譯碼，即Normalized MSA。算法描述如下：

（1） 初始化。將變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的信息初始化概率為：

[L0Qij=2yiσ2] （2）

式中：[yi]為接收到的信號(hào)；[σ2]為噪聲方差。

（2） 校驗(yàn)節(jié)點(diǎn)更新。在第[i]次迭代時(shí)，更新與校驗(yàn)節(jié)點(diǎn)[j]相鄰的變量節(jié)點(diǎn)[i∈Rj]傳給校驗(yàn)節(jié)點(diǎn)的信息。

[LlRji=i∈Rjisgn（Ll-1（Qij））?minQijα] （3）

式中：[Rji]為除了變量節(jié)點(diǎn)[i]外所有與校驗(yàn)節(jié)點(diǎn)[j]相鄰的變量節(jié)點(diǎn)的集合。

（3） 變量節(jié)點(diǎn)更新。在第[i]次迭代時(shí)，更新與變量節(jié)點(diǎn)[i]相鄰的校驗(yàn)節(jié)點(diǎn)傳給變量節(jié)點(diǎn)的信息：

[Ll（Qij）=L0Qij+j∈CijLlRji] （4）

式中：[Cij]為除了校驗(yàn)節(jié)點(diǎn)[j]外所有與變量節(jié)點(diǎn)[i]相鄰的校驗(yàn)節(jié)點(diǎn)的集合。

（4） 譯碼判決。

[Ll（Qij）=L0Qij+j∈CijLlRji] （5）

則：

[Ci=0，if LlQij>01，else] （6）

（5） 結(jié)束。增加迭代次數(shù)，把譯碼結(jié)果代入[HΤ?C=0]進(jìn)行校驗(yàn)，如果等式成立或已經(jīng)超過最大迭代次數(shù)，輸出譯碼結(jié)果，否則返回步驟（2）。

3 LDPC碼編碼器實(shí)現(xiàn)

針對(duì)上文提出的編譯碼算法，選擇[H]矩陣中對(duì)應(yīng)的系數(shù)[a=2，][b=5，][z=127，][x1=x2=x3=0，]得到快速編碼的不規(guī)則QC碼，采用文獻(xiàn)[2]提出的四環(huán)檢測(cè)定理，首先從圖1觀察[O=HΤH]矩陣，除主對(duì)角線元素以外的其他元素都不大于1，所以校驗(yàn)矩陣不存在四環(huán)。

結(jié)構(gòu)化矩陣采用[m]路準(zhǔn)并行編碼結(jié)構(gòu)，硬件編碼器按照快速編碼算法計(jì)算序列的[V=Vim×1，]信息序列分成[k]組，每組[z=127 ]b，輸入到編碼信息存儲(chǔ)器EM中，根據(jù)[Ha]移位矩陣將信息循環(huán)移位中間變量存儲(chǔ)在EM中，首先對(duì)每組移位塊完全異或，[m]組中間序列再經(jīng)過異或陣列得到校驗(yàn)序列[V1，]采用流水線同時(shí)進(jìn)行，編碼器通過循環(huán)移位寄存器完成，如圖2所示。流水線設(shè)計(jì)極大地提高了編碼器的信息吞吐率。

對(duì)于不同編碼長(zhǎng)度和編碼速率，通過改變[z]值和移位規(guī)則，利用以上LDPC編碼器架構(gòu)就可以得到不同碼長(zhǎng)，碼率以及不同并行度的LDPC碼的編碼，而且可以通過打孔自適應(yīng)地實(shí)現(xiàn)不同碼率，因此，以上結(jié)構(gòu)LDPC碼具有很好的靈活性。

4 譯碼器結(jié)構(gòu)設(shè)計(jì)

本文設(shè)計(jì)的LDPC譯碼器總體結(jié)構(gòu)如圖3所示。

變量節(jié)點(diǎn)處理模塊完成變量節(jié)點(diǎn)信息更新和譯碼輸出判決，接收的數(shù)據(jù)一方面來自初始信道似然信息，另一方面是校驗(yàn)節(jié)點(diǎn)傳遞給變量節(jié)點(diǎn)的迭代信息，本文變量節(jié)點(diǎn)采用10組并行處理，每組127 b，這樣在127個(gè)時(shí)鐘周期完成所有變量的軟信息更新，每個(gè)變量節(jié)點(diǎn)的更新輸出是所有與之相連的校驗(yàn)節(jié)點(diǎn)傳遞過來的迭代信息和初始信道似然信息的和，再減去其自身的內(nèi)信息，去所有信息之后最高位作為判決輸出。

檢驗(yàn)節(jié)點(diǎn)處理模塊主要是更新校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)的信息，也是在127個(gè)時(shí)鐘周期內(nèi)完成所有校驗(yàn)節(jié)點(diǎn)一輪更新，更新后的輸出作為下次變量節(jié)點(diǎn)更新的外信息。

從譯碼算法中可以看出，存儲(chǔ)器地址時(shí)刻在變換，由于數(shù)字電路的動(dòng)態(tài)功耗正比于芯片信號(hào)變換頻率，因此本譯碼器存儲(chǔ)器地址采用格雷碼編碼，這樣信號(hào)每個(gè)周期只會(huì)翻轉(zhuǎn)一位，大大降低了系統(tǒng)的動(dòng)態(tài)功耗。

5 仿真與實(shí)現(xiàn)

本文通過大量的仿真，在信噪比低的環(huán)境下，置信傳播譯碼算法譯碼性能優(yōu)于位比特翻轉(zhuǎn)算法。在對(duì)信息吞吐率，譯碼性能綜合要求高的場(chǎng)合，采用BP算法具有明顯的優(yōu)勢(shì)，同時(shí)對(duì)比定點(diǎn)化BP方案和浮點(diǎn)BP算法，定點(diǎn)化BP算法以最小的性能損失換取芯片復(fù)雜度的大幅度降低，然后分析仿真定點(diǎn)化不同位格式，確定采用最小和積置信傳播算法作為L(zhǎng)DPC的譯碼方案，縮放最小和算法的定點(diǎn)化格式為（8[∶]3），即量化位寬為8 b，其中最高的1 b表示符號(hào)，2 b表示整數(shù)位，5 b表示小數(shù)位，并得到[α=1.25，]圖4給出了在AWGN 信道下，采用BPSK調(diào)制，碼長(zhǎng)1 270，固定10次迭代，[12]碼率條件下，置信傳播算法、最小和算法定點(diǎn)、縮放最小和算法定點(diǎn)及其不同定點(diǎn)格式，以及位翻轉(zhuǎn)算法的誤碼率性能曲線。由仿真結(jié)果可知，縮放最小和算法定點(diǎn)的性能已經(jīng)非常接近置信傳播算法浮點(diǎn)的性能。

圖4 不同譯碼算法的誤碼率性能曲線

基于上述編碼器和譯碼器的結(jié)構(gòu)，通過硬件描述語言實(shí)現(xiàn)了碼長(zhǎng)1 270，碼率[12]的不規(guī)則結(jié)構(gòu)化LDPC編碼譯碼電路。通過ISE 14.7進(jìn)行綜合，布局布線，在Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片上實(shí)現(xiàn)，編碼器最大時(shí)鐘頻率為332 MHz，編碼器信息吞吐率達(dá)到2.52 Gb/s，譯碼器的時(shí)鐘最大頻率為78 MHz，譯碼器在10次迭代后的信息吞吐率達(dá)到44 Mb/s，這對(duì)于碼長(zhǎng)為1 270 b的LDPC譯碼器是很快的。

編碼器采用127 b準(zhǔn)并行結(jié)構(gòu)，輸入比特根據(jù)校驗(yàn)矩陣均等切割，每組劃分127 b，切割5組，編碼器中組合邏輯完全由移位和異或構(gòu)成，BLOCK RAM用于對(duì)輸入、輸出緩存進(jìn)行時(shí)序調(diào)節(jié)，在跨時(shí)鐘域場(chǎng)合用來解決讀/寫時(shí)序的邏輯膠合，本文不僅從系統(tǒng)層面用戶角度采用輸入、輸出FIFO解決時(shí)序問題，用戶甚至可以直接改變編碼器移位矩陣設(shè)置不同的碼長(zhǎng)、碼率，具有很強(qiáng)的可擴(kuò)展性。編碼器綜合報(bào)表如表1所示。

譯碼器同樣采用輸入、輸出FIFO與外部用戶進(jìn)行交互，數(shù)據(jù)流同樣以1 270 b為一幀，譯碼開始前首先按編碼順序?qū)⑿蛄羞M(jìn)行均等切割，每127 b為一組，譯碼開始時(shí)，信道根據(jù)輸入比特初始化，初始化完成后譯碼狀態(tài)機(jī)進(jìn)入校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)軟信息更新狀態(tài)，直到變量節(jié)點(diǎn)判別后得出的譯碼序列滿足校驗(yàn)方程或者迭代次數(shù)超過最大值，輸出譯碼序列，完成本幀數(shù)據(jù)的譯碼，譯碼結(jié)果存入緩沖器，等待用戶讀取。譯碼器資源消耗如表2所示。

6 結(jié) 語

本文根據(jù)IEEE 802.16e中LDPC碼的設(shè)計(jì)規(guī)則，提出了一種無短環(huán)、高速、部分并行、準(zhǔn)循環(huán)，不規(guī)則LDPC編碼器和譯碼器結(jié)構(gòu)，碼長(zhǎng)1 270 b，碼率[12，]該LDPC編碼器采用移位和異或操作完成編碼，同時(shí)采用流水線結(jié)構(gòu)提高時(shí)鐘頻率，可以通過打孔和參數(shù)設(shè)置進(jìn)行擴(kuò)展，采用對(duì)數(shù)域縮放最小和定點(diǎn)算法對(duì)LDPC碼進(jìn)行譯碼，采用8 b量化，1 b符號(hào)位，2 b整數(shù)位，5 b小數(shù)位，縮放系數(shù)[α=1.25，]中間信息節(jié)點(diǎn)存儲(chǔ)器地址采用格雷碼編碼，降低動(dòng)態(tài)功耗，通過硬件描述語言設(shè)計(jì)相應(yīng)的編碼、譯碼電路，用ISE 14.7進(jìn)行綜合，布局布線，在Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片上實(shí)現(xiàn)，編碼器最大時(shí)鐘頻率為332 MHz，編碼器信息吞吐率達(dá)到2.52 Gb/s，譯碼器的時(shí)鐘最大頻率為78 MHz，譯碼器在10次迭代后的信息吞吐率達(dá)到44 Mb/s，這對(duì)于碼長(zhǎng)1 270 b的LDPC譯碼器來說是很快的，針對(duì)信息吞吐率，譯碼性能要求高，可擴(kuò)展性強(qiáng)，從與外部通信使用便利的角度出發(fā)，該編譯碼結(jié)構(gòu)體現(xiàn)出明顯的優(yōu)勢(shì)。

參考文獻(xiàn)

[1] ZHANG L， HUANG Q， LIN S， et al. Quasi?cyclic LDPC codes： An algebraic construction， rank analysis， and codes on Latin squares [J]. IEEE Transactions on Communications， 2010， 58（11）： 3126?3139.

[2] 肖揚(yáng)，徐丹.準(zhǔn)循環(huán)LDPC好碼設(shè)計(jì)[J].系統(tǒng)工程與電子技術(shù)，2009，31（5）：1011?1016.

[3] GALLAGER R G. Low?density parity?check codes [M]. Cambridge： MIT Press， 1963.

[4] 徐娟，姚如貴，李路，等.優(yōu)化稀疏LU分解LDPC編碼算法研究[J].西安電子科技大學(xué)學(xué)報(bào)，2015（2）：127?132.

[5] MA Kexiang， LIU Yi， HU Jianhua， et al. Low complexity decoding algorithm for LDPC codes and design of key circuits [J]. Journal of Xidian University， 2013， 40（6）： 6?12.

[6] FALSAFAIN H， ESMAEILI M. A new construction of structured binary regular LDPC codes based on steiner systems with parameter [J]. IEEE Transactions on Communications， 2012， 60（1）： 74?80.

[7] COSTELLO D J， FORNEY G D. Channel coding： the road to channel capacity [J]. Proceedings of the IEEE， 2007， 95（6）： 1150?1177.

[8] IEEE LAN/MAN Standards Committee. IEEE Standard 802.11n. Wireless LAN medium access control （MAC） and physical layer （PHY） specifications： Amendment 4： Enhancements for higher throughputs improvement [S]. New York： IEEE LAN/MAN Standards Committee， 2007.

[9] 袁瑞佳，白寶明，童勝.10 Gbps LDPC編碼器的FPGA設(shè)計(jì)[J].電子與信息學(xué)報(bào)，2011，33（12）：2492?2497.

[10] 張洋，王秀敏，陳豪威.基于FPGA的低密度奇偶校驗(yàn)碼編碼器設(shè)計(jì)[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2011，45（9）：1582?1586.

[11] CCSDS. CCSDS 131.1.1?0?2. Low density parity check codes for use in near?earth and deep space application [S]. Washington， DC： CCSDS， 2007.

[12] XIAO Y， KIM K. Good encodable irregular quasi?cycle LDPC codes [C]// 2008 11th IEEE Singapore International Conference on Communication Systems. Guangzhou： IEEE， 2008： 1291?1296.