單元旭+崔聞

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

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

中圖分類號： TN91?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 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)制時，歸一化最小和譯碼算法能很好地平衡譯碼性能和算法復(fù)雜度，易于硬件實現(xiàn)[2]，且常以流水線的形式出現(xiàn)在譯碼器的設(shè)計中。本文針對LDPC譯碼器提出一種新的設(shè)計思路，將流水線思想應(yīng)用到譯碼器的整體設(shè)計中，設(shè)計出可以多幀并行且結(jié)構(gòu)簡單的譯碼器，最后通過仿真對其性能進(jìn)行驗證。

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

歸一化最小和譯碼算法分為兩步迭代，即變量節(jié)點運算（VNP）與校驗節(jié)點運算（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行那個1之后的子集；[N（m）＼n]表示從[N（m）]中去掉第n列那個1之后的子集；Pn表示第n列對應(yīng)的接收到的初始電平值；[qnm]表示本次迭代中第n列第m行那個1對應(yīng)的變量節(jié)點運算結(jié)果；[rmn]表示本次迭代中第m列第n行那個1對應(yīng)的校驗節(jié)點運算結(jié)果；[α]為歸一化因子。初始化時先進(jìn)行VNP運算，此時的rmn均為0。每次進(jìn)行VNP運算時可同時計算本次迭代的判決結(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是對三輸入VNP進(jìn)行流水線化的一個實例，其中“擴位補零”是為了防止加法結(jié)果溢出，通過補零的方式增加輸入數(shù)據(jù)的整數(shù)位；“截位”將絕對值超出原有位數(shù)范圍的數(shù)據(jù)轉(zhuǎn)化為原有位數(shù)下的極值；“添位”將判決碼字[xn]附加在數(shù)據(jù)的末尾，便于在CNP運算時計算[HxT]對應(yīng)各行的結(jié)果。

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

圖1 三輸入流水線化VNP

圖2 四輸入流水線化CNP

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

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

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

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

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

圖5 VNP與CNP對“M”的讀寫方式

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

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

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

圖6 （1 008，504）雙對角QC?LDPC碼校驗基矩陣

圖7 長碼譯碼器VNP與CNP的讀地址時序

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

3 基于QuartusⅡ的仿真分析

本文采用CycloneⅢ系列EP3C120F780I7型號的FPGA芯片作為仿真平臺，使用QuartusⅡ9.0作為開發(fā)工具，根據(jù)LDPC碼長度的不同設(shè)計了兩款譯碼器：碼長為20 b的8幀并行短碼譯碼器和碼長為1 008 b的2幀并行長碼譯碼器，二者碼率均為[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符號位，3 b整數(shù)位和4 b小數(shù)位。仿真前將初始值預(yù)先存入ROM中，并在仿真開始時向INPUT_FIFO中順序?qū)懭搿?/p>

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

圖8 短碼譯碼器的仿真時序圖

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

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

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

圖9 長碼譯碼器的仿真時序圖

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

[資源名稱＼&短碼譯碼器＼&長碼譯碼器＼&芯片總資源＼&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é) 語

本文針對LDPC譯碼器提出一種新的設(shè)計思路，將流水線思想應(yīng)用到譯碼器的整體設(shè)計中，并利用Verilog語言設(shè)計出可以多幀并行且結(jié)構(gòu)簡單的譯碼器，其綜合性能突出，且具有很大的優(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碼譯碼研究與實現(xiàn)[D].南京：南京航空航天大學(xué)，2011.

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

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

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

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

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

[9] 王鵬，陳詠恩.高速LDPC碼分層譯碼器設(shè)計[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.