基于改進的分層譯碼算法的QC-LDPC譯碼器設計

馬匯淼，馬林華，田 雨

（空軍工程大學 工程學院航空電子工程系，陜西 西安710038）

LDPC 碼[1]（Low-Density Parity-Check Code）已 經 被證明是實用的好碼，因其優異的糾錯性能和高效的迭代譯碼算法而具有廣闊的應用前景。QC-LDPC碼(Quasi-Cyclic LDPC Code)是根據系統化構造方法構造的一類非常重要的LDPC碼，目前已經成為LDPC碼硬件實現研究的熱點。空間數據系統委員會（CCSDS）推薦了多種碼長和碼率的QC-LDPC碼作為衛星通信和深空通信的信道編碼標準[2]。

為滿足不同碼率的需要，同時考慮譯碼器應當具有低復雜度和低功耗，本文設計了一種基于改進分層譯碼算法的譯碼器結構，以滿足實際需要。

1 QC-LDPC碼及其譯碼算法

QC-LDPC碼具有分塊矩陣的形式，由多個子矩陣構成，形式如下：

其中每個子矩陣 Ai，j都是一個 z×z的循環方陣，此方陣只可能是零矩陣、單位陣或者單位循環移位后的矩陣。

置信傳播算法[3-4]BP(Belief-propagation decoding algorithm)是很重要的一類基于LDPC碼的譯碼算法，因其具有嚴格的數學結構和良好的性能，可以對譯碼算法的性能做定量分析。修正最小和（MMSP）譯碼算法[5]實際采用的是BP算法機制，雖然具有較低復雜度并保持良好的性能，但在實際應用中會占用大量硬件資源，且譯碼延時較長。基于OMS(Offset Min-Sum)的分層譯碼算法[6]能保證信息馬上得到傳遞，從而改進信息的收斂性。

結合MMSP譯碼算法和基于OMS的分層譯碼算法的優點并采用整數量化后的改進算法如下：

(1)校驗節點更新

(3)校驗檢測

②ξ=ξ+1，如果ξ＜K，則進行下一層的校驗節點更新。

③如果v?·H=，則停止迭代，輸出為譯完碼字,否則轉④。

④l=l+1，ξ=1；若 l＞Nmax，Nmax為最大迭代次數，譯碼結束，輸出譯碼結果；否則，轉⑤。

⑤重復①～④。

2 譯碼器的FPGA實現

2.1 譯碼器結構總體設計

譯碼器有三種不同的譯碼結構：全并行結構、串行結構和部分并行結構。部分并行結構避免了全并行結構資源消耗過大、硬件實現難度大的缺點，同時譯碼速率比串行結構快得多，十分適于實際應用。然而，部分并行結構對校驗矩陣中非零元素的分布有特定的要求，而現有的大多數LDPC碼其校驗矩陣中“l”的分布具有隨機性，因此譯碼器采用部分并行結構十分困難。

QC-LDPC校驗矩陣H的每行校驗子矩陣中所有行對應的校驗節點自然地被劃分為一個校驗節點集合，而且任意兩個集合 Li和 Lj，滿足 Li∩Lj=φ。 集合 Li中的任意兩個校驗節點Ci、Cj不與相同的變量節點相連，因此可以并行地對每一集合中的校驗節點Ci進行更新。

為此，借鑒全并行結構的思想，對串形結構進行修改，增加譯碼器中的并行節點更新模塊（NUU）個數，得到的部分并行結構共有b個NUU單元。b為循環子矩陣的行數。

QC-LDPC并行譯碼器模塊主要由以下幾個模塊構成：輸入緩沖模塊、控制模塊、節點更新模塊(NUU)、數據存儲模塊、數據重構模塊、校驗模塊和譯碼輸出緩沖模塊，如圖1所示。其中，控制模塊分別產生各子模塊的使能，它是譯碼器的核心控制模塊，控制著迭代的正確進行；NUU為譯碼器的核心運算模塊；數據緩沖模塊用來判斷譯碼器速率是否大于進入譯碼器的數據速率；數據存儲模塊完成中間數據的存儲；數據重構模塊將變量節點更新的輸出數據按照校驗節點運算的取數順序重新排列；校驗模塊用來校驗判決出的碼字是否滿足校驗矩陣。

2.2 節點更新模塊（NUU）

本文實現的譯碼器采用基于修正因子的分層譯碼算法，每一層的校驗節點處理完成以后，信息立即被用來更新變量節點。它的結果被用來提供給下一層的校驗節點處理。因而校驗節點處理模塊和變量節點處理模塊可以合并成同一個模塊，簡稱節點更新模塊NUU（Node Update Unit）。

本文只研究信息位k=1 024的QC-LDPC碼，其結構如表1所示。

表1 QC-LDPC碼結構

圖2所示的模塊是每層b路并行處理單元中的一個，b為校驗矩陣H的循環子矩陣的行數。為了降低部分并行LDPC碼譯碼器中連接的復雜度，節點更新模塊(NUU)中節點更新的信息都采用數據串行方法。變量節點的度決定了校驗節點單元一次處理的節點數，將校驗節點單元處理的節點數設為節點變量的最大值，可以通過邏輯選通來適應不同的碼率。

2.3 數據存儲模塊

本文對接收到的原始數據和計算過程產生的中間數據都采用了8 bit整數量化，其中1 bit為符號位，7 bit為數據位。將譯碼開始時外部輸入的數據存入判決信息存儲器時，將接收的前b個二進制數據的最高位依次級聯為一個b bit的數據，存入判決信息存儲器1，地址為0；將前b個數據的次高位級聯為一個b bit的數據，存入判決信息存儲器2；然后依次將b個數據剩下的相同位置的數據級聯，存入判決信息存儲器2：7，地址為0；將接收的后b個數據按上述同樣的方式存入判決信息存儲器1：7，地址為1；當待譯碼字的所有數據都存入了判決信息存儲器后，就開始譯碼。圖3為數據存儲模塊框圖。

當開始譯碼時，再將存放在存儲器里的b個級聯的數據還原成b個7 bit的數據。而當信息需要傳遞給下一層時，按照校驗節點運算的取數順序重新排列判決信息在子矩陣中的位置，這個功能由數據重構模塊實現。

3 性能測試

3.1 誤碼率性能測試

首先由數字信號發生器對待譯碼字進行BPSK調制，然后由加噪儀對調制后的信號加噪（高斯白噪聲）。在信號的接收端對該信號經行解調、同步后，將待譯碼字的信道軟信息輸入FPGA譯碼芯片。譯碼芯片將譯碼后的結果傳輸給誤碼儀進行誤碼比對，計算誤碼率。

圖4為8 bit整數量化譯碼的仿真結果，在譯碼過程中所有的數據長度都為 8 bit，其中符號位 1 bit，信息位7 bit。其中，1/2和2/3碼率的QC-LDPC碼，迭代的最大次數為25；4/5碼率的QC-LDPC碼，迭代的最大次數為20。

3.2 譯碼器布局布線后結果

按照本節的半并行碼結構，在Xilinx公司的Virtex4 vlx160芯片上分別實現了CCSDS推薦的三種不同碼率的QC-LDPC碼編碼器。經過綜合布線后得到芯片內嵌的存儲單元，如表2所示。

3.3 譯碼速率性能測試

輸入緩沖模塊中的FIFO有溢出指示電平en_full，可用來判斷譯碼速率是否合適。若數據緩沖區沒有數據溢出，則逐步增加數字信號發生器的符號速率，一直增加到緩沖區溢出的臨界值。這時得到的數字信號發生器的信息比特速率就是該譯碼器在該信噪比條件下的最大譯碼速率。

表2 譯碼器布局布線后結果

最后測試結果：當1/2碼率QC-LDPC碼譯碼器在信噪比 Eb/N0=2 dB時，譯碼速率為 183 Mb/s；當 2/3碼率QC-LDPC碼譯碼器在信噪比Eb/N0=2.7 dB時，譯碼速率為143 Mb/s；當4/5碼率QC-LDPC碼譯碼器在信噪比Eb/N0=3.6 dB時，譯碼速率為90 Mb/s。

隨著信噪比的增加，譯碼器譯完一個碼字的迭代次數將隨之減少，因此譯碼的速率會隨著信噪比的增加而增加，但是并不是完全成比例的增加。這是因為待譯碼字的輸入速率是受限的，隨著譯碼速率的增加，譯碼器將擁有超過其待譯碼字輸入速率的能力，此時譯碼的速率將不再增加。本文實現的譯碼器最高可實現200 Mb/s的譯碼速率。

在對CCSDS推薦的QC-LDPC碼研究的基礎上，設計了一種基于改進分層譯碼算法的部分并行結構QCLDPC譯碼器，并給出了節點更新模塊和數據存儲模塊的結構。譯碼器性能測試表明，該結構譯碼速率高，設計模塊化，布線簡單，便于Xilinx綜合布線工具生成性能良好的可下載文件。

[1]GALLAGER R G.Low density parity-check codes[J].IEEE Trans.Inf.Theory，1962，8(1)：21-28.

[2]The consultative committee for space data systems.131.1-O-2 low density parity check codes for use in near-earth and deep space applications[S].Washington D.C，USA，CCSDS，2007.

[3]KSCHISCHANG F R，FREY B J，LOELIGER H A.Factor graphs and the sum-product algorithm[J].IEEE Transaction.Information.Theory，2001(47)：498-519.

[4]FREY B J，KSCHISCHANG F R.Probability propagation and iterative decoding[C].In Proceeding.34th Allerton Conference.On Communication，Control，and Computing，Monticello，Illinois，Oct.1996.

[5]Zhang Luoming，Gui Lin，Xu Youyun，et al.Configurable multi-rate decoder architecture for QC-LDPC codes based broadband broadcasting system[J].IEEE Transactons on broadcasting，2008，54(2)：226-235.

[6]GUNNAM K K，CHOI G S，Wang Weihuang，et al.Decoding of quasic-cyclic LDPC codes using an on-thefly computation[C].Signals，Systems and Computers，2006.ACSSC’06，2006(1)：1192-1199.