李劍凌，陳斌杰

1. 哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001 2. 北京遙感設(shè)備研究所，北京 100854

低密度奇偶校驗(low density parity check, LDPC)碼是一種校驗矩陣具有稀疏奇偶特性的線性分組碼，由Gallager[1]首次提出，經(jīng)常用于通信系統(tǒng)和儲存系統(tǒng)的糾錯，在滿足一定的假設(shè)條件下，LDPC碼的性能非常接近香農(nóng)容量極限[2]。

隨機(jī)構(gòu)造的LDPC 碼雖然具有優(yōu)良的性能，但由于其沒有確定性結(jié)構(gòu)，編譯碼復(fù)雜度較大，不利于硬件實現(xiàn)。Fossorier[3]提出的準(zhǔn)循環(huán)低密度奇偶校驗(QC-LDPC)碼在譯碼性能與譯碼復(fù)雜度方面有良好的折中。譯碼方面，最小和算法由于NR 和LTE 譯碼模塊之間具有可重用性、硬件實現(xiàn)復(fù)雜度低等優(yōu)點成為了現(xiàn)代SoC 設(shè)計用于LDPC 譯碼中使用最多的譯碼算法。傳統(tǒng)的譯碼結(jié)構(gòu)橫向更新與縱向更新是完全分開完成的，縱向更新需等待橫向更新完成后才可以開始，這很大程度上限制了吞吐率的提高。本文設(shè)計了一種層間流水線結(jié)構(gòu)的譯碼器，并以FPGA 作為實現(xiàn)平臺，以WIMAX 標(biāo)準(zhǔn)[4](2304，1152)QC-LDPC碼為例，設(shè)計仿真了基于最小和算法[4]的QC-LDPC碼譯碼器，并提高了吞吐率。

1 QC-LDPC 碼的校驗矩陣

QC-LDPC 碼的校驗矩陣[5]是由一組循環(huán)子矩陣構(gòu)成，子矩陣具有如下特點:

1)每一個子矩陣都是一個n×n大小的方陣；

2)循環(huán)子矩陣的任意一行(列)都是由上一行(列)向右(下)移動一位得到的，特別的，循環(huán)子矩陣的第一行(列)由循環(huán)子矩陣的最后一行(列)向右(下)移動一位得到。

QC-LDPC 碼的校驗矩陣可定義為

式中:M，N為正整數(shù)，Aij是n×n大小的子矩陣，由全零矩陣或單位循環(huán)移位矩陣組成。根據(jù)式(1)可知，QC-LDPC 碼的校驗矩陣由M×N個n×n大小單位循環(huán)方陣組成。WIMAX 標(biāo)準(zhǔn)(2304，1152)QC-LDPC 碼的基矩陣如圖1 所示。

圖1 WIMAX 標(biāo)準(zhǔn)(2304，1152)QC-LDPC 碼的基矩陣

2 QC-LDPC 碼的分層最小和譯碼算法

分層最小和譯碼算法[6]是分層算法與最小和算法的結(jié)合。最小和算法是BP 譯碼算法的簡化版本，對校驗節(jié)點傳遞給變量節(jié)點的對數(shù)似然比概率信息進(jìn)行近似運(yùn)算，該算法不需要信道估計，將復(fù)雜的雙曲正切運(yùn)算轉(zhuǎn)化為比較(取最小)運(yùn)算和加法運(yùn)算，與BP 譯碼算法相比大大減少了計算量，降低了硬件實現(xiàn)難度。分層算法則是將校驗矩陣H以行為基準(zhǔn)分為若干層，每層列重最大為1。首先基于第一層進(jìn)行校驗信息的更新；其次將更新后的校驗信息代入到變量節(jié)點中進(jìn)行變量信息的更新，當(dāng)?shù)谝粚有畔⒏峦瓿珊螅磳⒏潞蟮男畔鬟f給下一層，繼續(xù)進(jìn)行下一層的校驗信息和變量信息的更新，直至所有分層都完成信息的更新；最后對得到的后驗概率信息進(jìn)行硬判決并進(jìn)行校驗，如符合判決條件則停止譯碼，不符合則重新開始直至符合判決條件。在非分層算法中，信息是雙向傳遞的，變量節(jié)點需要等待校驗節(jié)點完全更新后才能開始更新，反之亦然。而在分層算法中的變量信息是用后驗概率信息與校驗信息來表示的，因此無需儲存變量信息；橫向更新使用的信息都是上一行或上一次迭代縱向更新的信息。分層譯碼算法與非分層算法相比，減少了單次迭代所需時間，信息迭代過程中分層譯碼算法簡化了儲存器與數(shù)據(jù)交換網(wǎng)絡(luò)，降低譯碼復(fù)雜度和鏈路延時。

具體分層最小和譯碼算法如下:

1)初始化

利用初始信道信息解調(diào)后得到的對數(shù)似然比序列對后驗概率信息進(jìn)行初始化:

2)分層更新

①根據(jù)上一層得到的后驗概率信息和校驗節(jié)點信息更新變量節(jié)點信息:式中:n為當(dāng)前迭代次數(shù)；m為當(dāng)前層數(shù)。

②根據(jù)更新后的變量節(jié)點信息更新當(dāng)前層的校驗節(jié)點信息:

式中α為歸一化因子，是一個小于1 的常數(shù)。

③根據(jù)更新后的變量節(jié)點信息與校驗節(jié)點信息更新后驗概率信息，作為下一層的后驗概率信息:

式中m=m+1，重復(fù)步驟①～③，直至最后一層。3)譯碼判決

則Zi=1；若則Zi=0。

將矩陣H與序列Zi相乘得到校驗結(jié)果，若校驗結(jié)果為0 或者達(dá)到最大迭代次數(shù)，停止迭代；若校驗結(jié)果不為0 且未達(dá)到最大迭代次數(shù)，重復(fù)步驟2)、3)。

3 QC-LDPC 碼譯碼器的FPGA 設(shè)計

本文選擇WIMAX 標(biāo)準(zhǔn)(2304，1152)QC-LDPC碼來設(shè)計層間流水線結(jié)構(gòu)譯碼器。根據(jù)QCLDPC 碼的校驗矩陣特性可知，該結(jié)構(gòu)十分適合使用水平分層譯碼算法進(jìn)行譯碼，將WIMAX 標(biāo)準(zhǔn)(2304，1152)QC-LDPC 碼的校驗矩陣分為12 層，每次迭代信息從頂層到底層垂直傳遞。本文所設(shè)計的譯碼器采用分層最小和算法，既擁有分層算法的高速收斂特性，又具有最小和算法的低復(fù)雜度特性。該譯碼器結(jié)構(gòu)框圖如圖2 所示。

圖2 層間流水線結(jié)構(gòu)譯碼器結(jié)構(gòu)框圖

本文設(shè)計的譯碼器主要包括初始信道信息接收模塊、后驗概率信息儲存模塊、節(jié)點信息更新模塊、校驗信息儲存模塊、控制模塊以及判決模塊。其主要特點有:

1)優(yōu)化譯碼策略，設(shè)計流水線結(jié)構(gòu)，通過修正校驗矩陣克服了數(shù)據(jù)沖突的問題，使層間可以并行，有效提高譯碼器工作效率與吞吐率。

2)優(yōu)化校驗節(jié)點更新過程中取最小值與次小值的結(jié)構(gòu)，使其在更短的時間內(nèi)完成比較功能。

3.1 譯碼策略

常用的分層譯碼策略有2 種:1)以層數(shù)為并行度的策略，每次迭代所需時間與子矩陣大小n有關(guān)；2)以子矩陣大小n為并行度的策略，每次迭代所需時間與層數(shù)S有關(guān)。對于WIMAX 標(biāo)準(zhǔn)(2304,1152)QC-LDPC 碼來說，分層數(shù)最小為12 層，子矩陣大小n為96，因此采用以子矩陣大小n為并行度的策略實現(xiàn)的譯碼器會獲得更高的吞吐率。傳統(tǒng)的分層譯碼算法的時序如圖3 所示。

圖3 傳統(tǒng)分層最小和算法時序示意

圖3 中，Tc表示一層校驗節(jié)點信息讀寫計算所占用的時間，Tv表示一層變量節(jié)點信息讀寫計算所占用的時間，S表示所分層數(shù)。于是一次迭代所需時間Titer=(Tc+Tv)×S。從圖3 可以看出，傳統(tǒng)的分層譯碼算法層與層之間是串行進(jìn)行的，校驗節(jié)點處理過程和變量節(jié)點處理過程是分開的。傳統(tǒng)的分層譯碼算法采用層間串行策略是因為WIMAX 標(biāo)準(zhǔn)(2304,1152)QC-LDPC 碼的校驗矩陣上下層間都有共用的校驗節(jié)點，而迭代過程中每次傳遞的后驗概率信息必須是已完成的更新值，否則校驗節(jié)點會同時處理來自同一變量節(jié)點的多個數(shù)據(jù)，數(shù)據(jù)沖突導(dǎo)致譯碼性能急劇下降。為了實現(xiàn)層間并行，需要對校驗矩陣進(jìn)行修正，使上下2 層不共用校驗節(jié)點。根據(jù)這一修正條件，本文將WIMAX 標(biāo)準(zhǔn)(2304,1152)QC-LDPC碼的校驗矩陣修正為如圖4 所示。

圖4 修正后(2304,1152)QC-LDPC 碼的基矩陣

從圖4 中可以看出，修正后矩陣上下兩層不再有共用的校驗節(jié)點。為了得知修正對WIMAX標(biāo)準(zhǔn)(2304，11452)QC-LDPC 碼的影響，對原始的QC-LDPC 碼和修正后的QC-LDPC 碼進(jìn)行仿真，并將結(jié)果進(jìn)行比較。仿真條件譯碼算法采用分層最小和譯碼算法，最大迭代次數(shù)設(shè)定為10 次，量化方案采用浮點數(shù)量化，得到原始的QC-LDPC 碼和修正后的QC-LDPC 碼性能如圖5 所示。圖5中比較結(jié)果顯示，修正后的QC-LDPC 碼譯碼性能比原始QC-LDPC 碼譯碼性能略有下降，但幾乎可以忽略，采用修正后的QC-LDPC 碼校驗矩陣進(jìn)行譯碼可以使層與層間進(jìn)行交替計算，提高了吞吐量。

圖5 原始譯碼性能與修正后譯碼性能比較

本文采用層間流水線策略進(jìn)行譯碼，時序圖如圖6 所示。

圖6 中，Tc表示一層校驗節(jié)點信息讀寫計算占用的時間，Tv表示一層變量節(jié)點信息讀寫計算占用的時間，S表示所分層數(shù)。由于修正后的QCLDPC 碼的校驗矩陣上下兩層不共用校驗節(jié)點，使得校驗節(jié)點和變量節(jié)點可以并行更新信息，于是一次迭代所需時間Titer=(Tc+Tv)×(S/2+1)。與傳統(tǒng)分層譯碼相比節(jié)約了每次迭代的時間，提升了吞吐率。

圖6 層間流水線策略分層最小和算法時序示意

3.2 比較模塊結(jié)構(gòu)

校驗節(jié)點信息處理模塊是節(jié)點信息處理模塊中的核心處理單元，它主要完成對從校驗節(jié)點傳輸過來的信息的處理。在校驗節(jié)點更新的過程中，校驗節(jié)點反饋給變量節(jié)點的信息的最小值是不包括該變量節(jié)點傳遞給校驗節(jié)點的信息的，因此需要比較與校驗節(jié)點相連的變量節(jié)點所含信息的最小值與次小值。比較模塊是校驗節(jié)點信息處理模塊中最核心的部分，對于WIMAX 標(biāo)準(zhǔn)(2304，1152)QC-LDPC 碼來說，與校驗節(jié)點相連的變量節(jié)點為6 或7 個。文獻(xiàn)[7]中使用的是最通用的串行比較器，將輸入信息的前2 個值進(jìn)行比較并將比較結(jié)果按最小值(min)和次小值(smin)的順序儲存到寄存器中，并將剩下的信息按順序與儲存的最小值與次小值進(jìn)行比較，并更新最小值與次小值直至最后一個信息。對于七輸入的比較器來說，該方法共需要進(jìn)行11 次比較，并需要6 個時鐘完成比較計算。文獻(xiàn)[8]對串行比較器進(jìn)行改進(jìn)，使用如圖7 所示的結(jié)構(gòu)。

圖7 文獻(xiàn)[8]中比較模塊結(jié)構(gòu)

文獻(xiàn)[8]的比較結(jié)構(gòu)將輸入信息兩兩分為一組進(jìn)行比較，再將比較后的最小值與次小值輸入到下一級比較器中進(jìn)行比較，完成7 個初始信息的比較只需要3 個時鐘，該方法也需要進(jìn)行11 次比較。文獻(xiàn)[9]使用了一種交叉比較結(jié)構(gòu)，如圖8所示。

圖8 文獻(xiàn)[9]中比較模塊結(jié)構(gòu)

文獻(xiàn)[9]中的比較器同樣需要進(jìn)行11 次比較，流水線長度為3 個時鐘周期。

本文使用一種樹狀比較結(jié)構(gòu)，其結(jié)構(gòu)如圖9所示。

圖9 本文比較結(jié)構(gòu)

圖9 中，將7 個輸入信息分為4 個信息和3 個信息共2 組，分別求最小值和次小值，再將2 組最小值和次小值進(jìn)行比較得出結(jié)果，該結(jié)構(gòu)同樣需要進(jìn)行11 次比較，流水線長度為2 個時鐘周期，在不增加計算量的情況下縮短了比較計算所消耗的時間。在硬件資源充裕的情況下可改為組合邏輯電路，在一個時鐘周期下完成七輸入求最小值與次小值的計算。

4 實驗結(jié)果及分析

系統(tǒng)在AWGN 信道下測試，調(diào)制方式為QPSK調(diào)制，采用WIMAX 標(biāo)準(zhǔn)(2304，1152)QC-LDPC 碼，譯碼算法為分層最小和譯碼算法，最大迭代次數(shù)設(shè)置為10 次，對基于最小和算法的QC-LDPC 譯碼器的FPGA 平臺進(jìn)行Modelsim 仿真，流程如圖10所示。

圖10 LDPC 譯碼器系統(tǒng)流程

測試流程如下:由Matlab 軟件模擬高斯白噪聲信道環(huán)境產(chǎn)生不同信噪比下的噪聲加入到初始信息中，傳遞給FPGA 的譯碼器進(jìn)行譯碼，譯碼結(jié)束后將結(jié)果輸出到Matlab 軟件中測得譯碼器性能，再與理論性能比較，比較結(jié)果如圖11 所示。

圖11 LDPC 譯碼器實際性能與理論性能比較

通過仿真發(fā)現(xiàn)，實際系統(tǒng)與理論相比由于數(shù)據(jù)量化精度和數(shù)據(jù)截位等原因會有大約0.1 dB 的性能損失，基本不影響譯碼器的整體性能，很好地完成了譯碼的功能。譯碼器吞吐率公式為

式中:f為時鐘頻率；N為碼長；t為單次迭代所消耗的時鐘周期數(shù)；i為最大迭代次數(shù)。當(dāng)時鐘頻率為200 MHz、最大迭代次數(shù)為10 時，吞吐量可達(dá)1 Gb/s。將本文設(shè)計的譯碼器與其他文獻(xiàn)設(shè)計的譯碼器進(jìn)行對比，其性能如表1 所示。

表1 FPGA 實現(xiàn)的譯碼器性能比較

從表1 可以看出，與文獻(xiàn)[10]、[11]、[12]提出的譯碼器相比，本文提出的譯碼器吞吐量最大。

5 結(jié)論

QC-LDPC 碼由于其校驗矩陣的準(zhǔn)循環(huán)特性使得其硬件實現(xiàn)具有比較低的復(fù)雜度，如何提升吞吐率則成為重點。本文針對現(xiàn)有的譯碼器，從以下2 個方面提出如下改進(jìn):

1) 從譯碼策略角度，針對分層最小和譯碼由于層間串行限制吞吐率的問題，本文設(shè)計了一種層間流水線結(jié)構(gòu)譯碼器，很好地解決了層間串行的問題，同時提高了吞吐量。

2) 從比較模塊結(jié)構(gòu)角度，優(yōu)化校驗節(jié)點更新過程中取最小值與次小值的結(jié)構(gòu)，使其在更短的時間內(nèi)完成比較功能，提高吞吐量。

改進(jìn)后的譯碼器大幅提升了吞吐量，但仍有不足，這種改進(jìn)方法僅適用于基于基矩陣擴(kuò)展而來的QC-LDPC 碼。隨著硬件的發(fā)展，基于最小和算法的QC-LDPC 譯碼器在對吞吐率要求高的情況下，會有很好的應(yīng)用前景。