流水線式LDPC譯碼器的FPGA設(shè)計(jì)與仿真

單元旭+崔聞

摘 要： LDPC碼在深空通信中有很好的實(shí)用價(jià)值，同時(shí)LDPC碼也被廣泛應(yīng)用于光纖通信、衛(wèi)星數(shù)字視頻和音頻廣播等領(lǐng)域。針對(duì)LDPC譯碼器提出一種新的設(shè)計(jì)思路，將流水線思想從譯碼算法本身擴(kuò)展到譯碼器的整體設(shè)計(jì)中，設(shè)計(jì)出可以多幀并行且結(jié)構(gòu)簡(jiǎn)單的譯碼器，最后從吞吐量和資源消耗兩方面進(jìn)行仿真驗(yàn)證。

關(guān)鍵詞： LDPC； 譯碼器； 流水線； FPGA

中圖分類號(hào)： TN91?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2014）21?0015?04

Design and simulation of pipeline style LDPC decoder based on FPGA

SHAN Yuan?xu， CUI Wen

（School of Electronics and Information Engineering， Harbin Institute of Technology， Harbin 150001， China）

Abstract： LDPC code in deep space communication has very good practical value， and has been widely used in optical fiber communication， satellite digital video and audio broadcasting. A new method to design LDPC decoder is proposed. The idea of pipeline is abstracted from decoding algorithm and applied to the overall design of decoder. Based on this method， a decoder with simple structure， which can process multiple parallel frames， was designed. Its throughput and resource consumption were verified by simulation.

Keywords： LDPC； decoder； pipeline； FPGA

0 引 言

LDPC碼已被廣泛應(yīng)用于深空通信、光纖通信、衛(wèi)星數(shù)字視頻和音頻廣播等領(lǐng)域[1]。在加性高斯白噪聲信道環(huán)境下，BPSK調(diào)制時(shí)，歸一化最小和譯碼算法能很好地平衡譯碼性能和算法復(fù)雜度，易于硬件實(shí)現(xiàn)[2]，且常以流水線的形式出現(xiàn)在譯碼器的設(shè)計(jì)中。本文針對(duì)LDPC譯碼器提出一種新的設(shè)計(jì)思路，將流水線思想應(yīng)用到譯碼器的整體設(shè)計(jì)中，設(shè)計(jì)出可以多幀并行且結(jié)構(gòu)簡(jiǎn)單的譯碼器，最后通過仿真對(duì)其性能進(jìn)行驗(yàn)證。

1 歸一化最小和譯碼算法的流水線化

歸一化最小和譯碼算法分為兩步迭代，即變量節(jié)點(diǎn)運(yùn)算（VNP）與校驗(yàn)節(jié)點(diǎn)運(yùn)算（CNP）。

VNP：

[qnm=Pn+m∈M（n）＼mrmn] （1）

CNP：

[rmn=n∈N（m）＼nsign（qnm）×minn∈N（m）＼nqnm×α] （2）

式中：[M（n）]表示[H]矩陣中第n列中1的所有位置；[N（m）]表示[H]矩陣中第m行中1的所有位置；[M（n）＼m]表示從[M（n）]中去掉第m行那個(gè)1之后的子集；[N（m）＼n]表示從[N（m）]中去掉第n列那個(gè)1之后的子集；Pn表示第n列對(duì)應(yīng)的接收到的初始電平值；[qnm]表示本次迭代中第n列第m行那個(gè)1對(duì)應(yīng)的變量節(jié)點(diǎn)運(yùn)算結(jié)果；[rmn]表示本次迭代中第m列第n行那個(gè)1對(duì)應(yīng)的校驗(yàn)節(jié)點(diǎn)運(yùn)算結(jié)果；[α]為歸一化因子。初始化時(shí)先進(jìn)行VNP運(yùn)算，此時(shí)的rmn均為0。每次進(jìn)行VNP運(yùn)算時(shí)可同時(shí)計(jì)算本次迭代的判決結(jié)果：

[Qn=Pn+m∈M（n）rmn] （3）

如果Qn≥0，則令第n列判決碼字xn=0，否則xn=1。若[x]=[x1，x2，…，xn]滿足[HxT=0，]則停止迭代，將[x]作為譯碼輸出，否則繼續(xù)迭代，直到滿足[HxT=0]或達(dá)到最大迭代次數(shù)為止。

圖1是對(duì)三輸入VNP進(jìn)行流水線化的一個(gè)實(shí)例，其中“擴(kuò)位補(bǔ)零”是為了防止加法結(jié)果溢出，通過補(bǔ)零的方式增加輸入數(shù)據(jù)的整數(shù)位；“截位”將絕對(duì)值超出原有位數(shù)范圍的數(shù)據(jù)轉(zhuǎn)化為原有位數(shù)下的極值；“添位”將判決碼字[xn]附加在數(shù)據(jù)的末尾，便于在CNP運(yùn)算時(shí)計(jì)算[HxT]對(duì)應(yīng)各行的結(jié)果。

圖2是對(duì)四輸入CNP進(jìn)行流水線化的一個(gè)實(shí)例，其中“相乘比較”結(jié)果的符號(hào)位為2個(gè)輸入數(shù)據(jù)符號(hào)位的異或值，數(shù)據(jù)位為2個(gè)輸入數(shù)據(jù)數(shù)據(jù)位中的較小者。為了便于硬件實(shí)現(xiàn)將[α]定[3]為0.75，即0.5+0.25，因此“乘以[α]”可以用移位相加來實(shí)現(xiàn)。同時(shí)CNP還應(yīng)將四個(gè)輸入的末位取出并進(jìn)行異或運(yùn)算，得出[HxT]對(duì)應(yīng)本行的結(jié)果。

圖1 三輸入流水線化VNP

圖2 四輸入流水線化CNP

2 基于FPGA的流水線式譯碼器的結(jié)構(gòu)設(shè)計(jì)

VNP與CNP的運(yùn)算結(jié)果同時(shí)也是彼此的輸入數(shù)據(jù)，將二者首尾相連就構(gòu)成了一個(gè)流水線環(huán)路，如圖3所示。如果以圖1和圖2的方法為例，VNP是6級(jí)流水線，那么在VNP中可容納6幀數(shù)據(jù)，在CNP中可容納3幀數(shù)據(jù)，兩個(gè)RAM各1幀，那么在環(huán)路中總共可以實(shí)現(xiàn)11幀數(shù)據(jù)的循環(huán)并行處理。

圖4是根據(jù)一個(gè)簡(jiǎn)單的LDPC碼的校驗(yàn)矩陣畫出的結(jié)構(gòu)圖，其中寄存器組“M”的位置與[H]矩陣中1的位置對(duì)應(yīng)，“M”陣列將多個(gè)流水線環(huán)路交織在一起就構(gòu)成了整個(gè)譯碼器?！癕”由兩個(gè)容量為2的RAM組成，容量為2是為了避免讀寫地址沖突，讀寫方式如圖5中左圖所示。

圖3 流水線環(huán)路示意圖

圖4 流水線式譯碼器結(jié)構(gòu)圖

圖5 VNP與CNP對(duì)“M”的讀寫方式

不過這種全并行結(jié)構(gòu)卻不適用于較長(zhǎng)的LDPC碼，如果給一個(gè)1 008×504的[H]矩陣中的每行與每列都配備一個(gè)CNP或VNP，硬件資源的消耗量是很大的[4]。QC?LDPC碼可以解決這個(gè)問題。

圖6所示是一個(gè)24×12的校驗(yàn)基矩陣，其中每個(gè)數(shù)字代表一個(gè)42×42的子矩陣，這些子矩陣都是由單位陣循環(huán)右移得到的，數(shù)字的大小表示單位陣循環(huán)右移的位數(shù)。此時(shí)譯碼器的結(jié)構(gòu)就要與基矩陣相對(duì)應(yīng)，即部分并行結(jié)構(gòu)，譯碼器的并行處理能力將體現(xiàn)在單幀內(nèi)部，VNP或CNP可以同時(shí)對(duì)多列或多行進(jìn)行循環(huán)處理。但VNP與CNP不能同時(shí)對(duì)同一幀數(shù)據(jù)進(jìn)行處理，因?yàn)槟菢訒?huì)帶來諸多問題[5]，解決的方法是讓譯碼器對(duì)兩幀數(shù)據(jù)并行譯碼，VNP對(duì)第一幀處理的同時(shí)CNP對(duì)第二幀進(jìn)行處理，然后依次交替。每?jī)蓭瑸橐惠?，?dāng)兩幀都譯碼成功或達(dá)到最大迭代次數(shù)時(shí)，才進(jìn)行下一輪譯碼。

寄存器組“M”的位置與基矩陣中的數(shù)字對(duì)應(yīng)，“M”由兩個(gè)容量為42的RAM構(gòu)成，讀寫方式如圖5中右圖所示，圖中實(shí)線與虛線交替存在，在每輪譯碼中每個(gè)RAM始終與同一幀數(shù)據(jù)對(duì)應(yīng)。以基矩陣中數(shù)字“17”對(duì)應(yīng)的“M”為例，該列的VNP與該行的CNP對(duì)此“M”的讀地址時(shí)序如圖7所示。若VNP為6級(jí)流水線，那么VNP對(duì)“M”的寫地址永遠(yuǎn)比讀地址滯后6，CNP亦如此。

圖6 （1 008，504）雙對(duì)角QC?LDPC碼校驗(yàn)基矩陣

圖7 長(zhǎng)碼譯碼器VNP與CNP的讀地址時(shí)序

在譯碼器啟動(dòng)時(shí)各模塊的讀寫地址的相對(duì)關(guān)系就已確定并被永久保持，使得各條流水線環(huán)路按著正確的規(guī)則不停地運(yùn)轉(zhuǎn)下去。為實(shí)現(xiàn)“乒乓操作”，本文將Pn寄存器的容量擴(kuò)大一倍，在譯碼器工作的同時(shí)把下一輪的初始值寫入Pn寄存器的閑置區(qū)間。當(dāng)本輪譯碼結(jié)束并且下一輪的初始值已被寫入閑置區(qū)間時(shí)，只需控制模塊發(fā)出區(qū)間切換信號(hào)，指示VNP將此刻Pn寄存器的讀地址加或減84，譯碼器就很自然地進(jìn)入到下一輪的譯碼工作中，而且這種切換可以隨時(shí)進(jìn)行，不必顧及當(dāng)時(shí)各模塊讀寫地址的位置?？刂颇K在發(fā)出區(qū)間切換信號(hào)后立即將內(nèi)部的周期性計(jì)數(shù)器歸零并開始重新計(jì)數(shù)，根據(jù)計(jì)數(shù)值在相應(yīng)的時(shí)段上連續(xù)收集各個(gè)VNP與CNP得出的[xn]與[HxT]信息，當(dāng)所有的[HxT]信息均為0或達(dá)到最大迭代次數(shù)時(shí)將[xn]輸出，否則進(jìn)入下一個(gè)計(jì)數(shù)周期。流水線式譯碼器的核心思想就是將整個(gè)譯碼過程流水線化，并盡量避免對(duì)流水線的干預(yù)，這樣不僅可以實(shí)現(xiàn)多幀并行，還省去了每輪譯碼之間的準(zhǔn)備時(shí)間，同時(shí)也讓輔助模塊的功能得到簡(jiǎn)化。

3 基于QuartusⅡ的仿真分析

本文采用CycloneⅢ系列EP3C120F780I7型號(hào)的FPGA芯片作為仿真平臺(tái)，使用QuartusⅡ9.0作為開發(fā)工具，根據(jù)LDPC碼長(zhǎng)度的不同設(shè)計(jì)了兩款譯碼器：碼長(zhǎng)為20 b的8幀并行短碼譯碼器和碼長(zhǎng)為1 008 b的2幀并行長(zhǎng)碼譯碼器，二者碼率均為[12。]譯碼器最高工作頻率為117.65 MHz，穩(wěn)定工作頻率取110 MHz。

利用Matlab將編碼后的碼字進(jìn)行BPSK調(diào)制，再通過AWGN信道，接收端信噪比為4 dB，最后進(jìn)行取樣量化得到初始值。初始值的量化位數(shù)[6]為8 b，包括1 b符號(hào)位，3 b整數(shù)位和4 b小數(shù)位。仿真前將初始值預(yù)先存入ROM中，并在仿真開始時(shí)向INPUT_FIFO中順序?qū)懭搿?/p>

圖8為短碼譯碼器的仿真時(shí)序圖，圖中judge1～ judge10為10個(gè)CNP得出的[HxT]對(duì)應(yīng)各行的結(jié)果，在每個(gè)times區(qū)間里順序輸出本次迭代中各幀的[HxT]信息；times為迭代次數(shù)；signal為區(qū)間切換信號(hào)；checkout為譯碼完成信號(hào)，由于在第6次迭代時(shí)8幀數(shù)據(jù)對(duì)應(yīng)的各行judge均為零，故checkout發(fā)出了一個(gè)高脈沖；answer為OUT_FIFO的輸出，即譯碼碼字，一輪譯碼后譯碼器串行輸出8個(gè)20位數(shù)據(jù)。每次迭代需11個(gè)時(shí)鐘周期，假設(shè)每輪需20次迭代[7]，那么短碼譯碼器的吞吐量為[20×][8×110 MHz（11×20）]=80 Mb/s。

圖8 短碼譯碼器的仿真時(shí)序圖

圖9為長(zhǎng)碼譯碼器的仿真時(shí)序圖，一輪譯碼后譯碼器串行輸出24個(gè)42 b數(shù)據(jù)，即2幀碼字的信息位。每次迭代需84個(gè)時(shí)鐘周期，假設(shè)每輪需20次迭代，那么長(zhǎng)碼譯碼器吞吐量為[1 008×110 MHz（84×20）=132] Mb/s。

表1為全編譯后QuartusⅡ給出的硬件資源消耗情況。

綜上可見，與其他LDPC譯碼器相比[8?10]，在硬件資源消耗量大致相當(dāng)?shù)那闆r下，流水線式譯碼器具有較為突出的吞吐量。當(dāng)然，本文設(shè)計(jì)的譯碼器仍有很大的優(yōu)化空間，比如可以將8幀數(shù)據(jù)分成兩組分別進(jìn)行判決和輸出，并在輸出端對(duì)各組進(jìn)行排序，這樣就能降低平均迭代次數(shù)，進(jìn)一步提高吞吐量。

圖9 長(zhǎng)碼譯碼器的仿真時(shí)序圖

表1 譯碼器硬件資源消耗情況

[資源名稱＼&短碼譯碼器＼&長(zhǎng)碼譯碼器＼&芯片總資源＼&Total logic elements＼&6 599＼&16 516＼&119 088＼&Total combinational functions＼&5 107 ＼&15 617＼&119 088＼&Dedicated logic registers＼&5 517＼&10 008＼&119 088＼&Total memory bits＼&7 304＼&147 476＼&3 981 312＼&]

4 結(jié) 語

本文針對(duì)LDPC譯碼器提出一種新的設(shè)計(jì)思路，將流水線思想應(yīng)用到譯碼器的整體設(shè)計(jì)中，并利用Verilog語言設(shè)計(jì)出可以多幀并行且結(jié)構(gòu)簡(jiǎn)單的譯碼器，其綜合性能突出，且具有很大的優(yōu)化空間，因此流水線式LDPC譯碼器具有很好的開發(fā)前景。

參考文獻(xiàn)

[1] 楊雪飛，高俊.LDPC碼在深空通信中的應(yīng)用技術(shù)研究[J].現(xiàn)代電子技術(shù)，2009，32（23）：33?34.

[2] 孫汝杰.LDPC譯碼方法研究及應(yīng)用[D].南京：南京理工大學(xué)，2012.

[3] 竇戈.基于CMMB標(biāo)準(zhǔn)的LDPC碼譯碼研究與實(shí)現(xiàn)[D].南京：南京航空航天大學(xué)，2011.

[4] 江濤.QC?LDPC碼設(shè)計(jì)和分層譯碼器的FPGA實(shí)現(xiàn)[D].南京：南京航空航天大學(xué)，2011.

[5] 袁瑞佳.LDPC碼的高效編譯碼實(shí)現(xiàn)技術(shù)研究[D].西安：西安電子科技大學(xué)，2012.

[6] 吳斌，楊波，葉明.LDPC硬件實(shí)現(xiàn)中的數(shù)據(jù)量化位數(shù)選擇及其性能仿真[J].信息通信，2012（2）：26?28.

[7] 吉晉龍.LDPC碼的高速編譯碼器設(shè)計(jì)及FPGA實(shí)現(xiàn)[D].西安：西安電子科技大學(xué)，2013.

[8] 楊建平，陳慶春.IEEE802.16標(biāo)準(zhǔn)LDPC譯碼器設(shè)計(jì)和實(shí)現(xiàn)[J].通信技術(shù)，2010，43（5）：18?19.

[9] 王鵬，陳詠恩.高速LDPC碼分層譯碼器設(shè)計(jì)[J].小型微型計(jì)算機(jī)系統(tǒng)，2009，30（11）：2294?2297.

[10] XIAO Peng， GOTO Satoshi. Implementation of LDPC decoder for 802.16e [C]// 2009 IEEE 8th International Conference on ASIC. [S.l.]： IEEE， 2009： 501?504.