云飛龍，朱宏鵬，呂 晶，杜 鋒

(中國人民解放軍理工大學(xué)，江蘇 南京 210001)

一種基于QC-LDPC碼的低復(fù)雜度分層迭代譯碼器*

云飛龍，朱宏鵬，呂 晶，杜 鋒

(中國人民解放軍理工大學(xué)，江蘇 南京 210001)

針對具有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼，設(shè)計(jì)了一種低復(fù)雜度譯碼器。利用校驗(yàn)矩陣的循環(huán)特性以及分層迭代的譯碼算法，對一般的分層迭代架構(gòu)進(jìn)行改進(jìn)，實(shí)現(xiàn)了譯碼器流水線處理，有效的減少迭代時間，提高吞吐量，最后針對碼長為1200的LDPC碼，基于FPGA平臺Kintex7 xc7k325的芯片實(shí)現(xiàn)了該架構(gòu)設(shè)計(jì)，結(jié)果表明，該譯碼器只消耗了100多個Slices和幾塊RAM，有效節(jié)省了硬件資源，同時譯碼時間比一般的分層架構(gòu)減少了2/3左右，吞吐量提高了約2倍，研究成果具有重要的實(shí)用價值，可應(yīng)用于資源有限的低速通信領(lǐng)域。

QC-LDPC;分層迭代;低復(fù)雜度;流水線

0 引 言

LDPC碼(Low-Density Parity-Check Code)[1]是一類具有稀疏校驗(yàn)矩陣的線性分組碼，不僅有逼近Shannon極限的良好性能，而且譯碼復(fù)雜度低、結(jié)構(gòu)靈活、易于在FPGA上實(shí)現(xiàn)等特點(diǎn)，成為近年信道編碼領(lǐng)域的研究熱點(diǎn)，已廣泛用于深空通信、光纖通信、衛(wèi)星數(shù)字視頻廣播和音頻廣播等領(lǐng)域。QC-LDPC碼[2-3]更是由于其校驗(yàn)矩陣擁有準(zhǔn)循環(huán)結(jié)構(gòu)特點(diǎn)，目前已被多個通信標(biāo)準(zhǔn)采用，如IEEE 802.16e、DVB-S2和802.11等。

目前在導(dǎo)航定位領(lǐng)域，往往傳輸?shù)闹皇俏恢眯畔?，速率比較低，而手持化的終端設(shè)備又要求硬件資源消耗少。針對這種領(lǐng)域低資源消耗、低速的特點(diǎn)，文獻(xiàn)[4]提出了一種低存儲量和簡化譯碼器控制邏輯的低復(fù)雜度譯碼器架構(gòu)，該架構(gòu)采用分層思想，將每個校驗(yàn)節(jié)點(diǎn)輸出的變量節(jié)點(diǎn)軟信息進(jìn)行累加，最后將累加值更新變量節(jié)點(diǎn)存儲器，該方法省去了變量節(jié)點(diǎn)處理單元，降低了復(fù)雜度，雖然文獻(xiàn)中針對的是PEG[5]算法構(gòu)造的非QC-LDPC碼，但對于QC-LDPC碼,采用該架構(gòu)同樣適用，然而該架構(gòu)在譯碼過程中需要一個n維的累加器，n為碼長，隨著碼長增加，資源會增加。文獻(xiàn)[6]介紹了一種經(jīng)典的分層迭代架構(gòu)，該架構(gòu)復(fù)雜度低，但時延相對來說比較長，導(dǎo)致吞吐量比 較低。針對上述問題，本文設(shè)計(jì)了一種改進(jìn)的分層迭代譯碼架構(gòu)，可省去n維的累加器，有效降低復(fù)雜度，同時將該架構(gòu)應(yīng)用到QC-LDPC碼中，實(shí)現(xiàn)流水線譯碼，有效的減少了譯碼時間，提高吞吐量，最后完成了FPGA設(shè)計(jì)實(shí)現(xiàn)。

1 準(zhǔn)循環(huán)LDPC碼譯碼算法

1.1 準(zhǔn)循環(huán)LDPC碼

準(zhǔn)循環(huán)LDPC碼(QC-LDPC)的校驗(yàn)矩陣具有雙對角結(jié)構(gòu)[7]。該類LDPC碼的校驗(yàn)矩陣便于存儲，且具有線性復(fù)雜度的快速編碼算法。給定兩個常數(shù)c和t，且c≤t，準(zhǔn)循環(huán)LDPC碼的奇偶校驗(yàn)矩陣由c×t的大小均為z×z的循環(huán)矩陣陣列組成，校驗(yàn)矩陣一般形式為：

(1)

式中，P是z×z的單位循環(huán)移位矩陣或者0矩陣。

定義mb×nb的基礎(chǔ)矩陣Hb，c=mb×z，t=nb×z,矩陣形式如下式所示，其中，sij為-1～(z-1)之間的整數(shù)，稱為循環(huán)移位因子。

(2)

校驗(yàn)矩陣H可由mb×nb的基礎(chǔ)矩陣Hb擴(kuò)展得到?；A(chǔ)矩陣中對應(yīng)的元素值為-1時，將其擴(kuò)展為z×z的0矩陣，若為其它值s，則將其擴(kuò)展為z×z的單位陣循環(huán)右移s次。

1.2 譯碼算法

采用的算法是修正的最小和譯碼算法[8]，它是由BP算法[9]演化而來，由于最小和算法易于硬件實(shí)現(xiàn)，因此被廣泛采用，算法如下：

(2)校驗(yàn)節(jié)點(diǎn)更新：更新校驗(yàn)節(jié)點(diǎn)Cm向變量節(jié)點(diǎn)Vn，n∈B(m)傳輸?shù)男畔?，B(m)表示與校驗(yàn)節(jié)點(diǎn)Cm相連接的變量節(jié)點(diǎn)集合；

(3)

(4)

(5)

式(5)中，m′∈A(n)m表示集合不包括m本身；

(4)一般在硬件實(shí)現(xiàn)中，設(shè)置最大迭代次數(shù)，當(dāng)一次迭代完成后，若k小于最大迭代次數(shù)，則k=k+1，返回第2歩，否則，終止迭代，譯碼輸出。

1.3 分層迭代

假設(shè)一個矩陣如下：

(6)

矩陣中，一個行塊對應(yīng)一個校驗(yàn)節(jié)點(diǎn)處理模塊(CNU)，一個列塊對應(yīng)一個變量節(jié)點(diǎn)處理模塊(VNU)。通常譯碼過程是行列結(jié)合的過程，只有校驗(yàn)節(jié)點(diǎn)全部更新完后，才進(jìn)行變量節(jié)點(diǎn)更新。而在分層迭代架構(gòu)中，并沒有涉及到VNU模塊計(jì)算，同時CNU模塊只有一個，每一行通過這個CNU模塊進(jìn)行更新迭代，該過程如下：先取出矩陣(6)第0行對應(yīng)的6個變量節(jié)點(diǎn)的值a1,a2,a3,a4 ,a5,a6,并串行送入CNU模塊進(jìn)行處理，處理完后得到6個新的變量節(jié)點(diǎn)的值a′1,a′2,a′3,a′4,a′5,a′6,并將原來的值覆蓋更新，處理下一行時，從已經(jīng)被更新過的數(shù)據(jù)中，讀取下一行對應(yīng)變量節(jié)點(diǎn)的值，重復(fù)上面過程，直到迭代終止。該過程對應(yīng)的算法如下，同時總結(jié)了文獻(xiàn)[4]中的算法，并進(jìn)行了比較。

分層譯碼算法如下：

4、一個校驗(yàn)節(jié)點(diǎn)運(yùn)算完后(即一行處理完)，更新對應(yīng)的似然值，然后返回第2歩，處理下一個校驗(yàn)節(jié)點(diǎn)：

5、一次迭代完成后(即所有行處理完)，若k小于最大迭代次數(shù)，則k=k+1，返回第2歩，開始下一次迭代，否則，終止迭代，譯碼輸出。

文獻(xiàn)[4]中的譯碼算法如下：

若k小于最大迭代次數(shù)，則k=k+1，返回第2歩，開始下一次迭代，否則，終止迭代，譯碼輸出。

圖1 2種譯碼架構(gòu)的不同

針對上述情況，本文進(jìn)行了改進(jìn)。由于QC-LDPC碼，一個循環(huán)子矩陣內(nèi)的變量節(jié)點(diǎn)度為1，而分層迭代算法的核心是：下一行需要利用最近更新的變量節(jié)點(diǎn)來進(jìn)行譯碼。也就是說當(dāng)譯碼的兩行沒有重疊的變量節(jié)點(diǎn)時，兩行校驗(yàn)節(jié)點(diǎn)關(guān)系是互不相干的，可獨(dú)立進(jìn)行，因此一個循環(huán)子矩陣內(nèi)的變量節(jié)點(diǎn)可流水線處理，而不用等上一行完全更新完后才進(jìn)行下一行處理，可有效節(jié)省譯碼時間，只有當(dāng)校驗(yàn)矩陣相鄰2行對應(yīng)列都有循環(huán)移位因子時，由于變量節(jié)點(diǎn)的不確定性，可能當(dāng)前需要更新的變量節(jié)點(diǎn)，由于之前還未更新完，需進(jìn)入等待狀態(tài)。

為此，可對校驗(yàn)矩陣做變換，通常譯碼時，CNU模塊從矩陣的第一行開始，依次往下譯碼，事實(shí)上，CNU模塊可從任意行開始迭代，也就是說矩陣的行可任意交換，而不會影響譯碼性能。于是可將對應(yīng)列都有循環(huán)移位因子的相鄰2行隔開，打亂校驗(yàn)矩陣行的次序，當(dāng)某些行無法隔開時，則同一列的循環(huán)移位因子需滿足一定的條件。

圖2表示的是校驗(yàn)矩陣相鄰2行同一列都有循環(huán)移位因子的條件下，不同子矩陣間的切換示意圖。其中N(N≠0的情況)為矩陣上一行的循環(huán)移位因子,M為下一行循環(huán)移位因子，假設(shè)數(shù)據(jù)n從讀取到更新消耗了k個時鐘，期間總共讀取了p個數(shù)據(jù)，z為子矩陣的階數(shù)，由于p比較小，一般p

圖2 2個子矩陣切換示意

圖2中，M、N、z可直接從校驗(yàn)矩陣中看出，p和FPGA時鐘設(shè)計(jì)有關(guān)，一般是固定值，在下文FPGA實(shí)現(xiàn)中，p設(shè)為3，而n不容易看出，比較復(fù)雜，于是下面推導(dǎo)出了的和n無關(guān)的結(jié)論。

①當(dāng)N≠0，mod(n+p-1,z)=N-1

若0≤n≤N-1

?n+p-1=N-1，n=N-p

?0≤N-p≤N-1

若N≤n≤z-1

?n+p-1-z=N-1，n=N+z-p

?N≤N+z-p≤z-1

②當(dāng)N=0時，n+p-1=z-1

?n=z-p

2 譯碼器的FPGA實(shí)現(xiàn)

譯碼器的結(jié)構(gòu)框圖如圖3所示，主要由3個模塊組成：地址產(chǎn)生模塊、數(shù)據(jù)存儲模塊、CNU數(shù)據(jù)處理模塊。其中數(shù)據(jù)存儲模塊主要是存儲信道似然比信息L值以及產(chǎn)生的中間結(jié)果r值，每一行數(shù)據(jù)處理后，似然比信息被更新，而中間結(jié)果需要保存下來，只有當(dāng)下一次迭代的時候，中間結(jié)果才可以被更新。

圖3 譯碼器結(jié)構(gòu)

圖3中地址產(chǎn)生模塊，用來讀取和更新存儲器中的數(shù)據(jù)，為了實(shí)現(xiàn)流水線操作，地址產(chǎn)生模塊將連續(xù)的產(chǎn)生新地址進(jìn)行讀取。其中對L值的讀取，采用段首地址與偏移量結(jié)合的方法來實(shí)現(xiàn)。假設(shè)碼長為576，按上述矩陣(6)計(jì)算，將576的碼字分成24段，段首地址就是每段的第一個數(shù)據(jù)地址，如第一段數(shù)據(jù)地址是0～23，則段首地址為0，第2段為24～47，則段首地址為24。矩陣(6)中有76個循環(huán)移位因子，將它們存入到ROM中，同時每個循環(huán)移位因子對應(yīng)的段首地址也存入到ROM中。

對L值存儲器的地址addr_L讀取公式如下：

addr_L=mod(addr_first+s+k,24)

(7)

式(7)中，addr_first為段首地址，s為對應(yīng)的循環(huán)移位因子，k為每段讀取個數(shù)的序號，如讀取第1個數(shù)，則k為0；讀取第2個數(shù)，則k為1。

由于對段首地址與循環(huán)移位因子的讀取操作是完全一樣的，因此為了降低資源，將2個值存儲到同一塊ROM中。假設(shè)段首地址位寬為10，循環(huán)移位因子位寬為5，則ROM的數(shù)據(jù)位寬應(yīng)為15位，高10位存段首地址，低5位存循環(huán)移位因子。

同時由于對L值存儲器以及r值存儲器讀和寫的地址是一樣的，因此在設(shè)計(jì)時，對讀地址進(jìn)行簡單的延遲操作即得到寫地址，有效降低了復(fù)雜度。

CNU模塊主要包括對數(shù)據(jù)的相減、比較以及相加，如圖4所示。

圖4 CNU模塊

從圖4中可看出，CNU模塊對數(shù)據(jù)的處理是流水線操作，串行輸入6個L值和r值，處理完成后，同樣串行輸出6個新的L值與r值。其中比較關(guān)鍵的部分是比較器，要比較出最小值和次小值以及它們所在的位置，圖4中比較器采用單一端口輸入，串行比較，輸出最小和次小值，再與符號位結(jié)合，串行輸出對應(yīng)的最小真值。

同時本譯碼器可接收不連續(xù)的數(shù)據(jù)。如果一幀數(shù)據(jù)傳輸?shù)臅r候，遇到中斷事件，要先去處理其他優(yōu)先級事件，譯碼器則進(jìn)入等待狀態(tài)，只有等一幀數(shù)據(jù)接收完成后才開始譯碼。

3 仿真結(jié)果及資源消耗情況

3.1 性能分析

在實(shí)際設(shè)計(jì)中，采用了12x24的校驗(yàn)矩陣(并非上述矩陣(6))，碼長為1 200的LDPC碼，圖5給出了經(jīng)過BPSK調(diào)制后的誤碼率性能，采用分層譯碼算法，利用軟件仿真，迭代次數(shù)為20次，6 bit量化．

圖5 性能仿真

從圖5中可看出，在2.3 dB條件下，誤碼率就達(dá)到了10-6級別，完全可以滿足實(shí)際中的應(yīng)用。

3.2 資源消耗

針對碼長為1 200的LDPC碼，分別對改進(jìn)前后的架構(gòu)進(jìn)行了FPGA的實(shí)現(xiàn)，F(xiàn)PGA采用Kintex7系列xc7k325t芯片，設(shè)計(jì)實(shí)現(xiàn)后分別測試了100幀數(shù)據(jù)(信噪比為2.3 dB)，均無錯，最后經(jīng)過ISE軟件環(huán)境下的布局布線后，資源消耗情況如表1所示。

表1 資源消耗情況

吞吐量的計(jì)算公式如下：

(8)

式(8)中，fmax是處理模塊能達(dá)到的最高工作主頻，nLDPC是LDPC編碼幀包含的信息比特數(shù)，C是譯碼器迭代一次的主時鐘周期數(shù)，Iter是迭代次數(shù)。

從表1中可看出，改進(jìn)后時鐘周期為改進(jìn)前的1/3左右,有效降低了譯碼周期，同時吞吐量也提高了2倍左右，而資源相差不大。

4 結(jié) 語

本文針對QC-LDPC碼設(shè)計(jì)了一種改進(jìn)的低復(fù)雜度分層迭代譯碼器，該架構(gòu)可實(shí)現(xiàn)流水線操作，有效的降低了譯碼周期，提高了吞吐量，且適用范圍廣，具有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼幾乎都適用。同時針對碼長為1 200的LDPC碼進(jìn)行了FPGA實(shí)現(xiàn)，最后表明只消耗了100多個Slices和幾塊RAM，同時也看到，雖然對傳統(tǒng)的分層迭代架構(gòu)進(jìn)行了改進(jìn)，但由于其本身譯碼時間長的特性，導(dǎo)致吞吐量比較低，因此需應(yīng)用于低速、低資源消耗的領(lǐng)域。

[1] Gallager R G. Low-Density Parity-Check Codes[J]. Information Theory, IRE Transactions on,1962,8(1):21-28.

[2] CHEN L, XU J, Djurdjevic I, et al. Near-Shannon-Limit Quasi-Cyclic Low-Density Parity-Check Codes[J]. Communications, IEEE Transactions on, 2004, 52(7): 1038-1042.

[3] Fossorier M P C. Quasi-Cyclic Low-Density Parity-Check Codes from Circulant Permutation Matrices[J]. Information Theory, IEEE Transactions on. 2004, 50(8):1788-1793.

[4] 王建輝,李井源,倪少杰等.GPS L1C 信號LDPC譯碼器設(shè)計(jì)[J] .國防科技大學(xué)學(xué)報,2013(01):014. WANG Jian-hui ,LI Jing-yuan, Ni Shao-jie, et al. Design of LDPC Decoder on GPS L1C Signal[J].Journal of National University of Defense Technology.2013.1:014.

[5] 胡應(yīng)鵬,王健,程雯.LDPC短碼的編譯碼研究[J].通信技術(shù),2013,45(09):25-28. HU Ying-peng, WANG Jian, CHEN Wen. Modified Coding/Decoding Algorithm for Short LDPC Code[J].Communications Technology,2013, 45(09):25-28.

[6] Kim S, Sobelman G E, Lee H. A Reduced -Complexity Architecture for LDPC Layered Decoding Schemes[J],Very Large Scale Integration (VLSI) Systems. IEEE Transactions on, 2011 19(6): 1099-1103.

[7] Tanner R M, Sridhara D, et al. LDPC Block and Convolutional Codes based on Circulant Matrices[J] . Information Theory, IEEE Transactions on, 2004, 50(12):2966-2984.

[8] 姜明.低密度奇偶校驗(yàn)碼譯碼算法及其應(yīng)用研究[D]. 南京: 東南大學(xué), 2006. JIANG Ming. Decoding Algorithm and Applied Research of Low-Density Parity-Check Code[D] . Nanjing: Southeast University, 2006.(in China)

[9] CHEN J, Dholakia A, Eleftheriou E, et al .Reduced-cComplexity Decoding of LDPC Codes[J].Communications, IEEE Transactions on,2005,53(8):1288-1299.

A Low-Complexity Layer-Iterative Decoder based QC-LDPC

YUN Fei-long1，ZHU Hong-peng2，LV Jing3， DU Feng4

(PLA University of Science and Technology, Nanjing Jiangsu 210001, China)

In light of LDPC with quasi-cyclic structure, a low-complexity decoder is designed. Circulation of check matrix and layer-iterative decoding algorithm are applied to improving the common layer-iterative architecture,and thus achieving pipeline processing of decoder, and this could effectively reduce the iteration time and increases the throughput. Finally, based on FPGA platform of Kintex7 xc7k325 for LDPC with code length of 1200,the architecture design is realized. Results show that this decoder merely consumes over 100 Slice and several RAMs, thus effectively saving the hardware resource. In addition, the decoding time is only one third of that of the common architecture, while the throughput increases almost two times. The research is of important practical value, and the result could be applied to the low-speed communication field with limited resources.

QC-LDPC; layer-iterative; low-complexity; pipeline

10.3969/j.issn.1002-0802.2015.11.005

2015-06-10；

2015-09-23 Received date:2015-06-10；Revised date：2015-09-23

TN911.22

A

1002-0802(2015)11-1228-06

云飛龍(1990—)，男，碩士，主要研究方向?yàn)樾诺谰幋a；

朱宏鵬(1982—)，男，博士，主要研究方向?yàn)樾诺谰幋a；

呂 晶(1965—)，男，教授，主要研究方向?yàn)樾l(wèi)星通信；

杜 鋒(1990—)，男，碩士，主要研究方向?yàn)樾l(wèi)星通信。