基于最小和算法的QC-LDPC 譯碼器的FPGA 實現

李劍凌，陳斌杰

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

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

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

1 QC-LDPC 碼的校驗矩陣

QC-LDPC 碼的校驗矩陣[5]是由一組循環子矩陣構成，子矩陣具有如下特點:

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

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

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

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

圖1 WIMAX 標準(2304，1152)QC-LDPC 碼的基矩陣

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

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

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

1)初始化

利用初始信道信息解調后得到的對數似然比序列對后驗概率信息進行初始化:

2)分層更新

①根據上一層得到的后驗概率信息和校驗節點信息更新變量節點信息:式中:n為當前迭代次數；m為當前層數。

②根據更新后的變量節點信息更新當前層的校驗節點信息:

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

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

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

則Zi=1；若則Zi=0。

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

3 QC-LDPC 碼譯碼器的FPGA 設計

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

圖2 層間流水線結構譯碼器結構框圖

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

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

2)優化校驗節點更新過程中取最小值與次小值的結構，使其在更短的時間內完成比較功能。

3.1 譯碼策略

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

圖3 傳統分層最小和算法時序示意

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

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

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

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

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

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

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

3.2 比較模塊結構

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

圖7 文獻[8]中比較模塊結構

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

圖8 文獻[9]中比較模塊結構

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

本文使用一種樹狀比較結構，其結構如圖9所示。

圖9 本文比較結構

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

4 實驗結果及分析

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

圖10 LDPC 譯碼器系統流程

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

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

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

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

表1 FPGA 實現的譯碼器性能比較

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

5 結論

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

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

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

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