WIMAX LDPC碼譯碼器的FPGA實現(xiàn)*

王秀敏，張洋，陳豪威，付娟

(中國計量學院信息工程學院，浙江杭州310018)

全球微波互聯(lián)接入WIMAX是一種基于IEEE802.16e標準的無線城域網(wǎng)WMAN技術。該技術采用LDPC碼作為其信道編碼方案。WIMAX標準的LDPC碼由于其優(yōu)異的性能而引起了人們的廣泛關注。Torben Brack等人根據(jù)該標準中各個碼率LDPC碼校驗矩陣的不同特點，對碼率為1/2和2/3B的LDPC碼采用TDMP譯碼算法，對其他4種碼率的LDPC碼采用BP算法。設計實現(xiàn)了一個可支持WIMAX標準中所有碼率和碼長的LDPC碼譯碼器[1]。SHIH Xin Yu等人對LDPC碼的校驗基矩陣進行行列置換，使得變量節(jié)點和校驗節(jié)點的處理在時間上可以部分重疊，基于BP算法實現(xiàn)了支持該標準中碼率為1/2的19種碼長的LDPC碼的譯碼器[2]。

重組網(wǎng)絡是部分并行LDPC碼譯碼器中的一個重要組成單元。對數(shù)移位寄存器結構和雙向網(wǎng)絡僅適用于單個碼長。為了實現(xiàn)對多種碼長的支持[3]，采用了Benes網(wǎng)絡，基于該網(wǎng)絡的部分并行譯碼器可支持擴展因子小于該網(wǎng)絡輸入輸出端口數(shù)的各種碼長LDPC碼的譯碼。由于該網(wǎng)絡中各個開關控制信號的產(chǎn)生是基于一種遞推的算法，因此其復雜度較高。

本文將TDMP算法運用于WIMAX標準中所有6種碼率的LDPC碼的譯碼，通過分析得出了各個碼率LDPC碼的變量節(jié)點后驗LLR在前后兩次更新之間的最小時間間隔，采用插入額外時鐘周期的方法使得更新后的節(jié)點信息得到了及時利用。設計了一種基于填充算法的桶形移位寄存器結構的重組網(wǎng)絡單元，實現(xiàn)了對該標準中576、768、1152和2304 4種碼長的支持。采用了基于增量的循環(huán)移位模式，降低了硬件實現(xiàn)復雜度和單次迭代處理的周期數(shù)，提高了吞吐率。

1 LDPC碼的譯碼算法

LDPC碼的標準譯碼算法為BP算法。TDMP及時利用了更新后的節(jié)點信息，加快了譯碼收斂速率。中高信噪比條件下，該算法成功譯碼所需的平均迭代次數(shù)僅是BP算法的一半。TDMP-NMS算法采用歸一化最小和算法更新TDMP算法中的校驗節(jié)點信息，簡化了運算復雜度。該算法的譯碼處理步驟如下[3]:

第二步:對每個校驗節(jié)點i和與其相鄰的所有變量節(jié)點j，j∈R(i)，按如下步驟處理:

(1)根據(jù)式(1)和式(2)計算本次迭代j傳遞給i的消息qij:

其中ri，0，ri，1分別為本次迭代處理時校驗節(jié)點i傳遞給所有與其相鄰的變量節(jié)點信息絕對值的兩種可能取值，imd_min為上次迭代處理時傳遞給i的信息絕對值的最小值對應的變量節(jié)點的序號，sign_j為本次迭代傳遞給變量節(jié)點j的信息的符號。

(2)根據(jù)式(3)和(4)更新ri，0和ri，1:

同時更新ind_min為min(abs(qij))對應的變量節(jié)點的序號，根據(jù)式(5)更新sign_j

(3)根據(jù)式(6)和(7)更新Pj:第三步:對所有變量節(jié)點j硬判決。若Pj≥0，則判決cj=0；否則判決cj=1，計算伴隨式S=Hc。若S=0或者達到最大迭代次數(shù)，則停止迭代，輸出譯碼結果；否則從(2)開始繼續(xù)下一次迭代處理。

2 WIMAX標準的LDPC碼譯碼器設計

2.1 譯碼器總體結構

根據(jù)前述TDMP-NMS譯碼算法，本文設計的部分并行LDPC碼譯碼器結構如圖1所示。整個譯碼器由后驗LLR存儲單元、數(shù)據(jù)重組網(wǎng)絡、處理器陣列、硬判決輸出單元及控制單元構成。為支持連續(xù)譯碼，信道信息的存儲由2組相同的工作于乒乓讀寫模式的RAM完成。數(shù)據(jù)重組網(wǎng)絡根據(jù)校驗基矩陣中對應的數(shù)值對從后驗LLR存儲單元輸出的z個數(shù)據(jù)進行循環(huán)移位后送入處理器陣列中相應單元進行處理。處理器陣列由96個相同的處理器單元構成，當擴展因子為z時，僅使能其中的z個處理單元，并行處理更新對應于1個超碼的z個SPC碼?？刂茊卧a(chǎn)生各個模塊的工作使能信號和控制信號。采用最大迭代次數(shù)停止準則，當譯碼迭代次數(shù)達到設定的最大值時，硬判決輸出單元對從后驗LLR存儲單元中讀出的信息進行硬判決并輸出譯碼結果。

2.2 重組網(wǎng)絡的設計

本設計所提出的重組網(wǎng)絡單元結構支持對輸入數(shù)據(jù)個數(shù)為該網(wǎng)絡輸入輸出端口數(shù)的因子的數(shù)據(jù)序列的循環(huán)移位。該結構由數(shù)據(jù)填充單元和桶形移位寄存器單元構成。為支持最大擴展因子zmax=96碼長的LDPC碼，本設計中桶形移位寄存器單元的輸入輸出數(shù)據(jù)端口數(shù)均為96。填充單元在預處理階段用并行輸入的z個有效數(shù)據(jù)填充桶形移位寄存器的所有96個輸入端口，第nz+i個端口用第i個有效輸入數(shù)據(jù)填充。其中n=0，1，…，(96/z)-1，i=1，…，z。桶形移位寄存器單元對這96個數(shù)據(jù)根據(jù)輸入的循環(huán)移位值控制信號進行循序移位。移位結束之后，輸出端口的前z個數(shù)據(jù)即為所需的數(shù)據(jù)序列。一個輸人輸出數(shù)據(jù)端口數(shù)均為12的重組網(wǎng)絡，當有效輸入數(shù)據(jù)個數(shù)為6，循環(huán)移位值為3時，數(shù)據(jù)流圖如圖2所示。

每次迭代處理過程中，傳遞給處理器陣列的每個單元處理的變量節(jié)點后驗LLR值是經(jīng)過數(shù)據(jù)重組網(wǎng)絡循環(huán)移位后的數(shù)據(jù)序列。為使下一次迭代處理時輸入至該單元的數(shù)據(jù)是按原始順序排列的序列[4]，采用了兩個重組網(wǎng)絡，一個用于將從變量節(jié)點LLR存儲器中的讀出數(shù)據(jù)進行重組，另一個用于將處理更新后的LLR后驗數(shù)據(jù)進行反重組。為了降低硬件實現(xiàn)的復雜度，同時減少單次迭代處理所需的時鐘周期，提高譯碼器吞吐率，本設計將采用一種增量循環(huán)移位的方案[5]。采用該方案，每次對從存儲器中讀出的z個變量節(jié)點后驗LLR信息循環(huán)移位的值是本次該組數(shù)據(jù)所需移位的值與上一次所需移位值的模z的差值。經(jīng)處理器陣列處理更新后的后驗LLR值不經(jīng)過重組網(wǎng)絡直接存儲至原單元。

2.3 運算單元設計

為使譯碼器能夠支持WIAMX標準中的所有6種碼率，本文設計了如圖3所示的基于串行處理的運算單元結構。其中alpha運算單元接收以壓縮形式輸入的本超碼的內(nèi)信息ri，0，ri，1，ind_min，sign_j和變量節(jié)點j的后驗LLR信息Pj，根據(jù)式(1)和式(2)計算出qij。qij一路傳遞給alpha緩存單元用于后續(xù)的后驗LLR更新，一路傳遞給TC2SM轉換模塊，將以二進制補碼表示的qij轉換為符號-絕對值的表示形式，并傳遞給超碼內(nèi)信息處理更新單元。該單元每個周期接收一個幅度值和符號值，根據(jù)該幅度值與當前最小值min0和次小值min1的比較結果更新min0，min1，ind_min，將接收到的符號值存儲于寄存器并執(zhí)行模2累加運算。當對應于一個校驗節(jié)點的所有變量節(jié)點信息接收完畢，開始執(zhí)行min0，min1的歸一化操作計算ri，0和ri，1，以及sign_j的更新。該運算完成之后開始從alpha緩存單元中順序讀出之前存儲的qij，根據(jù)(6)(7)完成變量節(jié)點后驗LLR值Pj的更新?？刂颇K的作用主要是根據(jù)當前超碼校驗節(jié)點的度數(shù)產(chǎn)生計算qij和更新ind_min、Pj時所需的當前變量節(jié)點的序號和各個模塊的工作使能信號。為減少控制單元的扇出，本設計中采用8個運算單元共享一個控制單元的模式，整個處理器陣列96個運算單元共使用了12個控制單元。

2.4 變量節(jié)點后驗LLR信息的讀取

對WIMAX標準中碼率為1/2和2/3B的LDPC碼，通過改變各個超碼的迭代處理順序，可以使得任何兩個相鄰的超碼沒有公共的變量節(jié)點，因此當前超碼的處理不用等到前一個超碼迭代處理結束。在本設計中，當前一個超碼的變量節(jié)點后驗LLR從相應的存儲單元讀出完畢一個周期之后即開始讀取當前超碼的變量節(jié)點后驗LLR信息。對于其他碼率，通過分析其對應的校驗矩陣的特點，發(fā)現(xiàn)同一個變量節(jié)點在前后兩個相鄰超碼中的迭代處理順序最大相差3個周期，如圖4中碼率為2/3的A碼第一個超碼和第二個超碼方框內(nèi)所示的數(shù)字對應的一組z個變量節(jié)點，在第一個超碼中的處理順序是第8，在第二個超碼中的處理順序是第5。又由于從當前超碼所有校驗節(jié)點相鄰的變量節(jié)點后驗LLR讀出完畢至第一組z個更新后的后驗LLR輸出之間相差7個時鐘周期，為了在當前超碼處理時用到更新后的變量節(jié)點后驗LLR信息，本設計在對其他碼率的LDPC碼迭代處理時，當前一個超碼對應的所有變量節(jié)點讀出完畢10個周期之后開始讀取下一個超碼的變量節(jié)點后驗LLR信息。

3 實現(xiàn)結果及分析

選擇CycloneII系列的FPGA芯片EP2C70F896C6作為目標器件，編譯綜合后的結果顯示，該譯碼器共消耗27 077個邏輯單元，最高工作頻率可達69 MHz，在該工作頻率下，譯碼器對該標準中碼長為2 304的各碼率的LDPC碼譯碼迭代10次時，所需的譯碼周期數(shù)分別為:1 011、1 686、985、1 520、1 550、1 257，對應的譯碼吞吐率分別為:79 Mb/s、63 Mb/s、109 Mb/s、79 Mb/s、78 Mb/s、106 Mb/s，完全能夠滿足WIMAX標準數(shù)據(jù)吞吐率的要求。

在DE2-70開發(fā)板上對所設計的譯碼器進行了硬件測試，測試系統(tǒng)結構如圖5所示。

譯碼數(shù)據(jù)及控制信號產(chǎn)生模塊產(chǎn)生譯碼器工作所需的譯碼數(shù)據(jù)和相關的控制信號:碼率、碼長、最大迭代次數(shù)、輸入數(shù)據(jù)有效指示信號。譯碼器根據(jù)輸入的數(shù)據(jù)及控制信號進行譯碼。譯碼數(shù)據(jù)及控制信號產(chǎn)生模塊中有一個存儲一幀譯碼數(shù)據(jù)的ROM。為了在Quartus2的SignalTap II Logic Analyzer中觀察到譯碼器的輸出信號，該模塊周期性地從ROM中讀取譯碼數(shù)據(jù)和產(chǎn)生相應的控制信號。本文對碼率為1/2，碼長為2 304的LDPC碼進行了測試。測試中系統(tǒng)工作頻率為50 MHz，邏輯分析儀的采樣時鐘為100 MHz，由輸入的50 MHz信號經(jīng)PLL倍頻得到。得到譯碼器的譯碼輸出波形如圖6所示。圖中hdd_en為輸出有效數(shù)據(jù)指示信號，dout0～dout11為譯碼器并行輸出的96 bit數(shù)據(jù)，將該數(shù)據(jù)與原信息序列相比較，結果完全相同，譯碼器工作正常。

本文設計實現(xiàn)了一種支持WIMAX標準的碼長、碼率可配置LDPC碼譯碼器，通過設計一種基于串行工作模式的運算單元，實現(xiàn)了對該標準中所有碼率的支持。通過設計一種基于填充算法的重組網(wǎng)絡單元實現(xiàn)了對該標準中擴展因子為24、32、48、96的4種碼長的支持。采用TDMP-NMS算法，在提高譯碼收斂收率的同時，降低了硬件復雜度。實驗結果表明，所設計的譯碼器在50 Hz的時鐘頻率下工作正常，完全能夠滿足WIMAX標準數(shù)據(jù)吞吐率的要求。

[1]BRACK T，ALLES M，KIENLE F，et al.A synthesizable IP core for WIMAX 802.16E LDPC code decoding.IEEE 17th International Symposium on Personal，Indoor and Mobile Radio Communications，2006:1-5.

[2]SHIH Xin Yu，ZHAN Cheng zhou，LIN Cheng Hung，et al.An 8.29 mm252 mW Multi-Mode LDPC Decoder Design for Mobile WiMAX System in 0.13 μm CMOS Process.IEEE Journal of Solid-state Circuits，2008，43(3):672-683.

[3]XIAO Peng，GOTO S.Implementation of LDPC decoder for 802.16e.IEEE 8th International Conference on ASIC(ASICON′09)，2009:501-504.

[4]OH D，KESHAB K.Parhi.Low-complexity switch network for reconfigurable LDPC decoders.IEEE Transactions on Very Large Scale Integration(VLSI)Systems，2010，18(1):85-93.

[5]YANG Sun，KARKOOTI M，JOSEPH R C.VLSI decoder architecture for high throughput，Variable Block-size and Multi-rate LDPC Codes.IEEE International Symposium on Circuits and Systems(ISCAS 2007)，2007:2104-2107.