李劍凌，陳斌杰

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

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

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

1 QC-LDPC 碼的校驗(yàn)矩陣

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

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

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

QC-LDPC 碼的校驗(yàn)矩陣可定義為

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

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

1)初始化

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

2)分層更新

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

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

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

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

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

則Zi=1；若則Zi=0。

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

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

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

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

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

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

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

3.1 譯碼策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

圖11 LDPC 譯碼器實(shí)際性能與理論性能比較

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

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

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

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

5 結(jié)論

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

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

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

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