江 濤，仰楓帆

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

0 引言

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

1 QC-LDPC碼的譯碼策略

置信傳播(Belief Propagation，BP)算法是LDPC的標(biāo)準(zhǔn)譯碼算法，在它的基礎(chǔ)上又可以改進(jìn)得到最小和(Min-Sum)算法、歸一化最小和(Normalization Min-Sum，NMS)算法等。此類算法皆通過校檢節(jié)點(diǎn)更新和變量節(jié)點(diǎn)更新2個(gè)步驟完成一次譯碼迭代，因此又被稱為2項(xiàng)迭代置信傳播(Two phase Message Passing，TPMP)算法。TPMP算法因?yàn)樵谝淮蔚^程中，全部校檢節(jié)點(diǎn)更新完后，才對(duì)所有變量節(jié)點(diǎn)進(jìn)行更新，所以一次迭代過程中，所有信息只能進(jìn)行一次更新，收斂速度較慢，譯碼延時(shí)較大。雖然此后又提出了復(fù)用處理的方法［7］，但未能從根本上提升算法的收斂性和譯碼性能。

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

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

2.1 不可分層QC-LDPC碼

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

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

2.2 PLBP 算法

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

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

①初始化

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

式中，當(dāng)t=1時(shí)，設(shè)R(0)mn=0，m為屬于第k層的校檢節(jié)點(diǎn);

Step2:譯碼判決

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

③譯碼結(jié)構(gòu)校檢

完成一次迭代后，對(duì)更新的譯碼結(jié)果進(jìn)行校檢。若滿足c^×HT=0，或者迭代次數(shù)達(dá)到系統(tǒng)設(shè)置的最大迭代次數(shù)，則停止譯碼，輸出譯碼結(jié)果;否則，跳回步驟②進(jìn)行新一次迭代。

3 不可分層QC-LDPC譯碼器

3.1 譯碼器結(jié)構(gòu)

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

圖2為分層譯碼器硬件結(jié)構(gòu)，下面將詳細(xì)介紹譯碼器各模塊的功能與結(jié)構(gòu)。

圖2 分層譯碼器硬件結(jié)構(gòu)

(1)數(shù)據(jù)輸入模塊

接受解調(diào)模塊輸出的量化后的LLR數(shù)據(jù)，完成Ln的初始化。模塊采用乒乓操作，即當(dāng)其中一個(gè)存儲(chǔ)器接收數(shù)據(jù)的同時(shí)，譯碼器讀取另一個(gè)存儲(chǔ)器中的數(shù)據(jù)進(jìn)行譯碼，以此來提高譯碼器的吞吐量。

(2)數(shù)據(jù)存儲(chǔ)模塊

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

(3)校檢節(jié)點(diǎn)更新模塊(Parity-Check Update Block，PCUB)

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

圖3 譯碼器PCUB結(jié)構(gòu)示意圖

(4)地址生成模塊

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

(5)校檢模塊

校檢模塊在每一次迭代結(jié)束后，對(duì)所有校檢方程進(jìn)行驗(yàn)證，若全部滿足則停止迭代，否則進(jìn)行下一次迭代過程，直到達(dá)到設(shè)定的最高迭代次數(shù)為止。

(6)控制模塊

控制模塊中設(shè)置整個(gè)譯碼器的狀態(tài)機(jī)，控制譯碼器各子模塊有序運(yùn)行。

3.2 譯碼器內(nèi)存讀取中的問題與改進(jìn)

在介紹PCUB模塊時(shí)已經(jīng)了解，每一個(gè)校檢節(jié)點(diǎn)對(duì)應(yīng)的12個(gè)變量節(jié)點(diǎn)信息串行加入迭代過程，而這些節(jié)點(diǎn)信息存儲(chǔ)在與子塊列相對(duì)應(yīng)的64個(gè)Lmem中。由于伴隨矩陣的列權(quán)重為3，因此當(dāng)16個(gè)PCUB并行從Lmem中讀取數(shù)據(jù)時(shí)，如果按照伴隨矩陣原本的結(jié)構(gòu)，順序讀取變量節(jié)點(diǎn)信息時(shí)可能從某一子塊列對(duì)應(yīng)的Lmem中讀取1～3個(gè)數(shù)據(jù)。圖4為校驗(yàn)節(jié)點(diǎn)更新時(shí)PCUB讀取Lmem順序。

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

圖4 校檢節(jié)點(diǎn)更新時(shí)PCUB讀取Lmem順序

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

4 FPGA實(shí)現(xiàn)

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

表1 譯碼器硬件資源消耗統(tǒng)計(jì)

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

由于僅有16個(gè)PCUB模塊，譯碼器的并行度相對(duì)于普通的部分并行譯碼結(jié)構(gòu)還比較低，因此數(shù)據(jù)的吞吐量還有限?？梢酝ㄟ^將子層進(jìn)一步劃分，增加PCUB模塊來提升并行度，以達(dá)到更好的譯碼吞吐速度。

通過圖5中的性能曲線可以看到，將圖1的不可分層QC-LDPC碼用改進(jìn)后的分層譯碼器處理后，在最大迭代次數(shù)同為5次的情況下，較采用傳統(tǒng)部分并行結(jié)構(gòu)譯碼具有更好的譯碼性能表現(xiàn)。

圖5 部分并行結(jié)構(gòu)與分層譯碼結(jié)構(gòu)的譯碼性能曲線比較

5 結(jié)束語

基于PLBP算法，針對(duì)碼長8 192，碼率3/4的(3，12)規(guī)則不可分層QC-LDPC碼設(shè)計(jì)了一種分層譯碼器。突破了不可分層LDPC碼不能應(yīng)用分層譯碼算法的局限，較傳統(tǒng)的部分并行結(jié)構(gòu)具有了更好的收斂性，降低了迭代次數(shù)要求。設(shè)計(jì)在Altera公司的CycloneⅢ系列FPGA上得以實(shí)現(xiàn)，達(dá)到了較高的譯碼吞吐量，且具有很強(qiáng)的通用性，僅需要修改部分參數(shù)就可以適用不同的不可分層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］郭琨，黑勇，周玉梅，等.一種應(yīng)用于不可分層LDPC碼的并行分層譯碼算法［J］.電子與信息學(xué)報(bào)，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.