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

2015-03-25 05:55:39云飛龍朱宏鵬

通信技術(shù) 2015年11期

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

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

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

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

針對(duì)具有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼，設(shè)計(jì)了一種低復(fù)雜度譯碼器。利用校驗(yàn)矩陣的循環(huán)特性以及分層迭代的譯碼算法，對(duì)一般的分層迭代架構(gòu)進(jìn)行改進(jìn)，實(shí)現(xiàn)了譯碼器流水線處理，有效的減少迭代時(shí)間，提高吞吐量，最后針對(duì)碼長(zhǎng)為1200的LDPC碼，基于FPGA平臺(tái)Kintex7 xc7k325的芯片實(shí)現(xiàn)了該架構(gòu)設(shè)計(jì)，結(jié)果表明，該譯碼器只消耗了100多個(gè)Slices和幾塊RAM，有效節(jié)省了硬件資源，同時(shí)譯碼時(shí)間比一般的分層架構(gòu)減少了2/3左右，吞吐量提高了約2倍，研究成果具有重要的實(shí)用價(jià)值，可應(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)，目前已被多個(gè)通信標(biāo)準(zhǔn)采用，如IEEE 802.16e、DVB-S2和802.11等。

目前在導(dǎo)航定位領(lǐng)域，往往傳輸?shù)闹皇俏恢眯畔ⅲ俾时容^低，而手持化的終端設(shè)備又要求硬件資源消耗少。針對(duì)這種領(lǐng)域低資源消耗、低速的特點(diǎn)，文獻(xiàn)[4]提出了一種低存儲(chǔ)量和簡(jiǎn)化譯碼器控制邏輯的低復(fù)雜度譯碼器架構(gòu)，該架構(gòu)采用分層思想，將每個(gè)校驗(yàn)節(jié)點(diǎn)輸出的變量節(jié)點(diǎn)軟信息進(jìn)行累加，最后將累加值更新變量節(jié)點(diǎn)存儲(chǔ)器，該方法省去了變量節(jié)點(diǎn)處理單元，降低了復(fù)雜度，雖然文獻(xiàn)中針對(duì)的是PEG[5]算法構(gòu)造的非QC-LDPC碼，但對(duì)于QC-LDPC碼,采用該架構(gòu)同樣適用，然而該架構(gòu)在譯碼過程中需要一個(gè)n維的累加器，n為碼長(zhǎng)，隨著碼長(zhǎng)增加，資源會(huì)增加。文獻(xiàn)[6]介紹了一種經(jīng)典的分層迭代架構(gòu)，該架構(gòu)復(fù)雜度低，但時(shí)延相對(duì)來(lái)說(shuō)比較長(zhǎng)，導(dǎo)致吞吐量比較低。針對(duì)上述問題，本文設(shè)計(jì)了一種改進(jìn)的分層迭代譯碼架構(gòu)，可省去n維的累加器，有效降低復(fù)雜度，同時(shí)將該架構(gòu)應(yīng)用到QC-LDPC碼中，實(shí)現(xiàn)流水線譯碼，有效的減少了譯碼時(shí)間，提高吞吐量，最后完成了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)矩陣具有雙對(duì)角結(jié)構(gòu)[7]。該類LDPC碼的校驗(yàn)矩陣便于存儲(chǔ)，且具有線性復(fù)雜度的快速編碼算法。給定兩個(gè)常數(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ò)展得到。基礎(chǔ)矩陣中對(duì)應(yīng)的元素值為-1時(shí)，將其擴(kuò)展為z×z的0矩陣，若為其它值s，則將其擴(kuò)展為z×z的單位陣循環(huán)右移s次。

1.2 譯碼算法

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

(2)校驗(yàn)節(jié)點(diǎn)更新：更新校驗(yàn)節(jié)點(diǎn)Cm向變量節(jié)點(diǎn)Vn，n∈B(m)傳輸?shù)男畔ⅲ珺(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è)一個(gè)矩陣如下：

(6)

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

分層譯碼算法如下：

4、一個(gè)校驗(yàn)節(jié)點(diǎn)運(yùn)算完后(即一行處理完)，更新對(duì)應(yīng)的似然值，然后返回第2歩，處理下一個(gè)校驗(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)的不同

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

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

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

圖2 2個(gè)子矩陣切換示意

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

?n=z-p

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

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

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

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

對(duì)L值存儲(chǔ)器的地址addr_L讀取公式如下：

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

(7)

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

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

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

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

圖4 CNU模塊

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

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

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

3.1 性能分析

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

圖5 性能仿真

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

3.2 資源消耗

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

表1 資源消耗情況

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

(8)

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

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

4 結(jié) 語(yǔ)

本文針對(duì)QC-LDPC碼設(shè)計(jì)了一種改進(jìn)的低復(fù)雜度分層迭代譯碼器，該架構(gòu)可實(shí)現(xiàn)流水線操作，有效的降低了譯碼周期，提高了吞吐量，且適用范圍廣，具有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼幾乎都適用。同時(shí)針對(duì)碼長(zhǎng)為1 200的LDPC碼進(jìn)行了FPGA實(shí)現(xiàn)，最后表明只消耗了100多個(gè)Slices和幾塊RAM，同時(shí)也看到，雖然對(duì)傳統(tǒng)的分層迭代架構(gòu)進(jìn)行了改進(jìn)，但由于其本身譯碼時(shí)間長(zhǎng)的特性，導(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 信號(hào)LDPC譯碼器設(shè)計(jì)[J] .國(guó)防科技大學(xué)學(xué)報(bào),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

1002-0802(2015)11-1228-06