基于FPGA的不可分層LDPC碼譯碼器

江 濤，仰楓帆

(南京航空航天大學電子信息工程學院，江蘇南京210016)

0 引言

LDPC碼［1］是近年來發展較快也日趨成熟的信道編碼方案。具有準循環特性的QC-LDPC碼已經成 為 IEEE 802.11n(Wi-Fi)、IEEE 802.16e(WiMAX)［2］、(DVB-S2)［3］等眾多標準的信道編碼方案。QC-LDPC譯碼器設計初期多采用部分并行譯碼結構［4］，此后分層譯碼［5］策略又被提出。分層譯碼策略因其更好的譯碼速度和性能以及更簡單的硬件結構，逐漸成為QC-LDPC譯碼器的主流結構。但是分層譯碼要求LDPC碼的伴隨校檢矩陣每一個分層中列權重不能大于1。而在DVB-S2，CMMB以及IEEE 802.15.3c等標準中采用的LDPC碼不滿足這一條件，稱為不可分層碼。文獻［6］提出了一種并行分層置信度傳播(Parallel Layered Belief Propagation，PLBP)譯碼算法，應用PLBP算法設計了一種適用于不可分層QC-LDPC碼的高速譯碼器，并進一步優化了硬件結構，降低了算法實現復雜度。

1 QC-LDPC碼的譯碼策略

置信傳播(Belief Propagation，BP)算法是LDPC的標準譯碼算法，在它的基礎上又可以改進得到最小和(Min-Sum)算法、歸一化最小和(Normalization Min-Sum，NMS)算法等。此類算法皆通過校檢節點更新和變量節點更新2個步驟完成一次譯碼迭代，因此又被稱為2項迭代置信傳播(Two phase Message Passing，TPMP)算法。TPMP算法因為在一次迭代過程中，全部校檢節點更新完后，才對所有變量節點進行更新，所以一次迭代過程中，所有信息只能進行一次更新，收斂速度較慢，譯碼延時較大。雖然此后又提出了復用處理的方法［7］，但未能從根本上提升算法的收斂性和譯碼性能。

分層譯碼策略則改變了TPMP算法的譯碼方式，它將校檢矩陣按行或列劃分成若干分層。在一次迭代過程中，先并行更新第1分層中的所有校檢節點和相關的變量節點，然后逐層進行更新。因此在一次更新過程中，后更新的分層會利用到前面已更新分層的輸出信息，變量節點在此過程中得到多次更新，大大加快了譯碼的收斂速度，提高了譯碼性能。但為保證變量節點信息在各個分層之間能夠進行傳遞，校檢矩陣一個分層中的列權重必須不大于1。

2 并行分層置信傳播譯碼算法

2.1 不可分層QC-LDPC碼

通常QC-LDPC碼采用分層譯碼時，將它校檢矩陣中的一個子塊行作為一個分層，但并非所有的QC-LDPC碼這樣分層都能滿足上一節中所提到的分層譯碼策略對校檢矩陣結構的要求。以圖1中的碼長8 192，碼率為3/4的(3，12)正規QC-LDPC碼為例。伴隨矩陣由大小為128×128的子矩陣組成，其中含有很多和圈出的子矩陣類似的列權重為3的子矩陣，這些子矩陣都是由3個經過循環右移的單位矩陣組成。顯然該矩陣不適于應用分層譯碼算法，稱這樣的 LDPC碼稱為不可分層 LDPC碼。DVB-S2，CMMB以及IEEE 802.15.3c等系統中的LDPC都有類似的不可分層特點。對于這樣的QCLDPC碼，可以采用對分層譯碼算法進行改進后的PLBP算法，使其也能采用分層譯碼結構。

圖1 碼長8 192的不可分層(3，12)規則QC-LDPC的校檢矩陣

2.2 PLBP 算法

PLBP算法解決不可分層QC-LDPC碼譯碼的基本思路是改變傳統QC-LDPC分層譯碼的分層方式。傳統的分層譯碼是將QC-LDPC每一個子塊行作為一個分層，分層內實行并行運算，分層與分層之間實行串行運算。PLBP算法則是從所有子塊行中各取出一行，這些行兩兩之間不超過2個位置皆為1，將這些行組成一個分層，在該分層內可以實行并行運算，然后在這樣組成的分層與分層之間實行串行運算。因為這些行兩兩之間不超過2個位置皆為1，所以它們所組成的分層的列權重必不大于1。

設高斯白噪聲信道的噪聲方差為σ2，接收到的信號序列為y，伴隨矩陣H大小為M×N。迭代過程中信道固有信息Ln，校檢節點信息Rmn，變量節點信息Lmn，其中0≤m≤M －1，0≤n≤N－1。以BPSK調制為例，以NMSA為基礎，將PLBP算法的譯碼過程列述如下:

①初始化

②迭代過程(第t次迭代的第k層)Step1:分層更新

式中，當t=1時，設R(0)mn=0，m為屬于第k層的校檢節點;

Step2:譯碼判決

若L(t，k)n＜0，則c^n=1，否則c^n=0，更新譯碼結果 c^。

③譯碼結構校檢

完成一次迭代后，對更新的譯碼結果進行校檢。若滿足c^×HT=0，或者迭代次數達到系統設置的最大迭代次數，則停止譯碼，輸出譯碼結果;否則，跳回步驟②進行新一次迭代。

3 不可分層QC-LDPC譯碼器

3.1 譯碼器結構

對圖1所示的QC-LDPC碼進行譯碼器設計。該碼的行權重為12，列權重為3，碼長為8 192，碼率3/4，子矩陣大小為128，共有16個子塊行，64個子塊列，192個非零子矩陣。采用PLBP算法實現該譯碼器，譯碼過程中只保存Ln和Rmn2種中間數據，變量節點信息則通過式(2)計算得出，以減小數據存儲量。為便于硬件實現，可以選擇α=0.75作為修正因子，這樣只需要簡單的帶符號位右移和加法運算就可以完成數據修正。由于從16個子塊行中各取一行組成一個分層，因此譯碼器的并行度為16，即共需要16個基本運算單元。對譯碼器中的數據進行6 bits量化，對計算過程中產生溢出的數據采用截位處理，這樣的量化處理使譯碼性能大約有0.1 dB的損失，但大大節約了硬件資源。

圖2為分層譯碼器硬件結構，下面將詳細介紹譯碼器各模塊的功能與結構。

圖2 分層譯碼器硬件結構

(1)數據輸入模塊

接受解調模塊輸出的量化后的LLR數據，完成Ln的初始化。模塊采用乒乓操作，即當其中一個存儲器接收數據的同時，譯碼器讀取另一個存儲器中的數據進行譯碼，以此來提高譯碼器的吞吐量。

(2)數據存儲模塊

根據譯碼過程中存儲數據的不同，存儲模塊劃分為3塊:① 后驗概率存儲模塊Lmem，用于存儲Ln。單個Ln的長度為6位，每一子塊列對應的存儲空間為6×128=768位，對應子塊列數，共需要64個此類模塊。②校檢信息更新存儲模塊Rmem，用于存儲Rmn，單個Rmn的長度為6位，每一行有12個非零元素，所以每行對應的存儲空間為6×12=72位，而每一子塊行所對應的存儲空間為6×12×128=9 216位。對應子塊行數，共需16個此類存儲模塊。③譯碼結果存儲模塊，用于存儲譯碼結果。每一子塊列對應的譯碼數據長度為128位，對應子塊列數，共需64個此類存儲空間。同樣，為了提高吞吐量，譯碼數據輸出模塊也采用乒乓操作，當一個存儲器進行譯碼結果更新的時候，另一個存儲器中的譯碼結果向外設輸出。

(3)校檢節點更新模塊(Parity-Check Update Block，PCUB)

校檢節點模塊是譯碼器的核心處理單元，完成迭代更新過程。共有16個PCUB模塊進行并行處理，一次更新16組數據。每一組相關的12個變量節點信息串行輸入PCUB中的FIFO寄存器，并逐次進行比較，尋找該組數據中的最小值與次最小值。當一組數據輸入完成后，最小值與次最小值得以確定，再從FIFO寄存器中依次讀出數據同最小值與次最小值比較，更新數據，PCUB的結構如圖3所示。由PCUB的結構圖可以看出，迭代譯碼過程主要被劃分為2個階段:變量節點信息輸入FIFO階段，變量節點信息輸出FIFO階段。這樣的結構很適合采用二級流水線，當一組已輸入的變量節點信息從FIFO中讀取的時候，將下一組變量節點信息輸入FIFO。通過二級流水線處理，提高了近一倍的數據吞吐率。

圖3 譯碼器PCUB結構示意圖

(4)地址生成模塊

地址生成模塊中包含一個保存伴隨矩陣中所有子塊位置和子塊偏移量信息的只讀寄存器(ROM)。通過從ROM中調取信息，分別產生Lmem和Rmem的讀寫地址。

(5)校檢模塊

校檢模塊在每一次迭代結束后，對所有校檢方程進行驗證，若全部滿足則停止迭代，否則進行下一次迭代過程，直到達到設定的最高迭代次數為止。

(6)控制模塊

控制模塊中設置整個譯碼器的狀態機，控制譯碼器各子模塊有序運行。

3.2 譯碼器內存讀取中的問題與改進

在介紹PCUB模塊時已經了解，每一個校檢節點對應的12個變量節點信息串行加入迭代過程，而這些節點信息存儲在與子塊列相對應的64個Lmem中。由于伴隨矩陣的列權重為3，因此當16個PCUB并行從Lmem中讀取數據時，如果按照伴隨矩陣原本的結構，順序讀取變量節點信息時可能從某一子塊列對應的Lmem中讀取1～3個數據。圖4為校驗節點更新時PCUB讀取Lmem順序。

在圖4(a)中列出了16個PCUB讀取不同子塊對應的Lmem的順序。從中可以看到，在每組變量節點信息輸入迭代譯碼的第1時刻。第2、9、11子塊行對應的PCUB模塊同時從第1子塊列對應的Lmem中共讀取3個數據，第8、15子塊行對應的PCUB模塊則同時從第2子塊列對應的Lmem中共讀取2個數據。這樣不同的讀取情況，會對Lmem的硬件設計引入更多的復雜度。

圖4 校檢節點更新時PCUB讀取Lmem順序

由于變量節點信息加入迭代過程的先后順序并不影響譯碼結構，因此對變量節點信息的讀取順序稍作改進，如圖4(b)所示，將原有的讀取順序重新排列，使得在同一時刻不同的PCUB從不同的子塊列對應的Lmem中讀取數據，即每一時刻Lmem最多提供一個數據，這就大大降低了Lmem的設計復雜度，提高了硬件的通用性。

4 FPGA實現

選用Altera公司的CycloneⅢ系列中的EP3C120器件，設置最大迭代次數為 5次，在QuartusⅡ10.0下完成綜合和布局布線，硬件資源的消耗如表1所示。

表1 譯碼器硬件資源消耗統計

在譯碼過程中，首先花費128個時鐘進行Lmem的初始化過程，完成后開始迭代譯碼。在每一次迭代過程中，核心的PCUB模塊進行128次更新，由于是采用流水線結構，每次更新實際僅花費12個時鐘，再加上第1組數據進入流水線花費的額外12個時鐘，5次迭代共花費12×(128×5)+12=7 692個時鐘。因此整個譯碼過程最多花費7 692+128=7 820個時鐘。完成布局布線后，譯碼器的最高時鐘頻率可以達到45.44 MHz。此時譯碼器的吞吐量達到:(45.44 ×8 129)/7 820=47.60 Mbps。

由于僅有16個PCUB模塊，譯碼器的并行度相對于普通的部分并行譯碼結構還比較低，因此數據的吞吐量還有限。可以通過將子層進一步劃分，增加PCUB模塊來提升并行度，以達到更好的譯碼吞吐速度。

通過圖5中的性能曲線可以看到，將圖1的不可分層QC-LDPC碼用改進后的分層譯碼器處理后，在最大迭代次數同為5次的情況下，較采用傳統部分并行結構譯碼具有更好的譯碼性能表現。

圖5 部分并行結構與分層譯碼結構的譯碼性能曲線比較

5 結束語

基于PLBP算法，針對碼長8 192，碼率3/4的(3，12)規則不可分層QC-LDPC碼設計了一種分層譯碼器。突破了不可分層LDPC碼不能應用分層譯碼算法的局限，較傳統的部分并行結構具有了更好的收斂性，降低了迭代次數要求。設計在Altera公司的CycloneⅢ系列FPGA上得以實現，達到了較高的譯碼吞吐量，且具有很強的通用性，僅需要修改部分參數就可以適用不同的不可分層LDPC碼。

［1］GALLAGER R G.Low-density parity-check codes［J］.IRE Trans.on Inf.Theory，1962，IT －8(1)：21 －28.

［2］LDPC coding for OFDMA PHY.802.16REVe sponsor ballot recirculation comment［S］.IEEE C802.16e － 04 2004，7：639.

［3］Digital video broadcasting(DVB)，second generation［S］.ET-SI EN 302 307 v.1.1，2005.

［4］MARJAN K，JOSEPH R C.Semi-parallel reconfigurable architectures for real-time LDPC decoding ［C］∥Proceedings of the International Conference on Information Technology：Coding and Computing(ITCC04)Orleans，USA，2004，1(4)：579 －585.

［5］MANSOUR M M，SHANBHAG N R.High-Throughput LDPC Decoders［J］.IEEE Transaction on Very Large Scale Integration Systems，2003(11)：976 －978.

［6］郭琨，黑勇，周玉梅，等.一種應用于不可分層LDPC碼的并行分層譯碼算法［J］.電子與信息學報，2010，32(8)：1956 －1960.

［7］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［J］.IEEE Journal of Solid-state Circuits，2008，43(3)：672－683.