基于FPGA的大圍數(shù)QC_LDPC碼的譯碼器

摘要 針對QC_LDPC碼的短環(huán)對碼性能的重要影響，采用了1種圍數(shù)為8的QC_LDPC碼設(shè)計(jì)。算法首先分別對3個不同的子矩陣進(jìn)行移位運(yùn)算，每個子矩陣分別與它們移位后生成的子矩陣共同組合形成1個新的子矩陣，然后再將新生成的3個子矩陣組合成1個矩陣構(gòu)成基陣，最后將該矩陣轉(zhuǎn)置后用單位矩陣及其移位矩陣隨機(jī)擴(kuò)展即可得到所需校驗(yàn)矩陣。根據(jù)該校驗(yàn)矩陣的特殊結(jié)構(gòu)，采用分層迭代譯碼算法，選用Altera公司的Stratix III系列FPGA，實(shí)現(xiàn)碼率為1/2、碼長為3456的正規(guī)(3，6)QC_LDPC碼譯碼器的布局布線。

LDPC碼是近年來發(fā)展較快且日趨成熟的一種信道編碼方案，因其具有的優(yōu)越性能和實(shí)用價(jià)值而被人們認(rèn)知，但由于隨機(jī)結(jié)構(gòu)的LDPC碼編譯碼器硬件實(shí)現(xiàn)較為復(fù)雜，具有的準(zhǔn)循環(huán)特性QC_LDPC碼已成為IEEE 802.11n(WiFi)、IEEE 802.16e(WiMAX)、(DVB—S2)等眾多標(biāo)準(zhǔn)的信道編碼方案。LDPC碼是一種基于稀疏校驗(yàn)矩陣的線性分組碼，具有類似于Turbo碼的良好糾錯性能。1981年Tanner提出的用二部圖表示一個低密度線性分組碼的方法，成為LDPC碼的主要分析工具。若LDPC碼的Tanner圖是無環(huán)的，那么與積SP(Sum—Product)譯碼算法可實(shí)現(xiàn)最佳譯碼，若存在環(huán)尤其是短環(huán)的話，則由和積算法計(jì)算所得的概率并非真正的后驗(yàn)概率(這是因?yàn)榈^程中的獨(dú)立性假設(shè)不能成立)，因而譯碼并不是最優(yōu)的逐符號最大后驗(yàn)概率譯碼，因此，環(huán)的存在大幅影響了譯碼的性能。MacKay和Neal經(jīng)過大量的仿真結(jié)果證明信息傳遞算法(Message —Passing Algorithm，MPA)在Tanner圖中有環(huán)的情況下仍具有較好的譯碼性能，但短環(huán)的存在還是會降低譯碼性能。因此通過增大碼的最小圍數(shù)(環(huán)長)，可提高碼字的性能，圍數(shù)達(dá)到一定的值就可接近無環(huán)時的性能。

文獻(xiàn)提出一種圍數(shù)為8的低密度校驗(yàn)矩陣的設(shè)計(jì)算法，獲得的QC_LDPC碼在AWGN信道下的仿真結(jié)果表明，其具有逼近隨機(jī)QC_LDPC碼的誤碼率性能。本文采用該算法構(gòu)造的校驗(yàn)矩陣屬于正規(guī)的QC_LDPC碼，具有更好的分塊循環(huán)移位特性，大幅降低了編譯碼復(fù)雜度，而Mansour和Sha nbhag則提出了一種LDPC譯碼策略——分層譯碼(Lnyered decoding)，本文采用分層譯碼方案，為降低硬件復(fù)雜度，在Mansour和Shanbhag的基礎(chǔ)上進(jìn)一步優(yōu)化，采用更為簡單的歸一化最小和算法(NMS)代替了傳統(tǒng)的和積算法(SPA)。整個譯碼過程只包含比較、移位和加減運(yùn)算，運(yùn)算量比SPA算法大幅降低，同時譯碼性能損失可不超過0.1 dB。

1 校驗(yàn)矩陣的構(gòu)造

該方法構(gòu)造的是一個列重為3，行重>3的校驗(yàn)矩陣。首先構(gòu)造3個子矩陣D、E和F，然后將子矩陣D、D和F按照行的方向排列生成H1，H1=[D E F]，再將H1轉(zhuǎn)置生成矩陣H2，最終用pxp的單位矩陣及其移位矩陣作為隨機(jī)因子，對矩陣H2中的“1”進(jìn)行隨機(jī)擴(kuò)展，即可生成所需的校驗(yàn)矩陣H。

1.1 子矩陣D的構(gòu)造

構(gòu)造一個v行、v2列的矩陣D0，其中D0的元素D0(1，1)=D0(2，1)=D0(3，1)=…=D0(v，1)=1，其余元素均為0，

(1)將矩陣D0中的元素向右循環(huán)移位，每移動1位生成一個新矩陣。當(dāng)D0中所有元素為1的列移動到第v2列時移位完畢，共生成v2-1個新矩陣D1，D2，D3，…，Dv2-1。

(2)將D0，D1，D2，D3，…，Dv2-1按照列的方向排列便生成子矩陣D=[D0，D1，D2，…，Dv2-1]T，其維數(shù)為v3×v2。

1.2 子矩陣E的構(gòu)造

(1)構(gòu)造一個v行、v2列的矩陣E0，其中E0中的元素E0(1，1)=E0(2，2)=E0(3，3)=…=E0(v，v)=1，其余元素均為0，即E0的前v列所構(gòu)成的塊為單位矩陣。如，當(dāng)v=4時

(2)將v個E0矩陣按照列的方向排列生成矩陣E1=[E0，E0，…，E0]T。

(3)將矩陣E1向右循環(huán)移位，每移動v位生成一個新矩陣，由此共生成v-1個新矩陣，分別記為E2，E3，…，Ev。

(4)將E1，E2，E3，…，Ev按照列的方向排列生成子矩陣E=[E1，E2，E3，…，Ev]T，其維數(shù)為v3×v2。

1.3 子矩陣F的構(gòu)造

(1)構(gòu)造一個v行v2、列的矩陣F0。其中F0中的元素F0(1，1)=F0(2，v+1)=F0(3，2v+1)=…=F0(v，v2-v+1)=1，其余元素均為0。即在F0中，從第2行開始，每行中的元素“1”的列位置較上一行中的“1”向右移動v位。假設(shè)，當(dāng)v=4時

(2)將F0向右循環(huán)移位，每移動1位生成v-1個新矩陣，共生成個新矩陣時停止移位，將新矩陣記為F1，F(xiàn)2，F(xiàn)3，…，F(xiàn)v-1。

(3)將F0，F(xiàn)1，F(xiàn)2，F(xiàn)3，…，F(xiàn)v-1按照列的方向排列，生成的矩陣記為Fv=[F0，F(xiàn)1，F(xiàn)2，F(xiàn)3，…，F(xiàn)v-1]T。

(4)將v個Fv按照列的方向排列生成矩陣F=[Fv，F(xiàn)v，…，F(xiàn)v]T，其維數(shù)為v3×v2。

1.4 矩陣H2的擴(kuò)展算法

將生成的子矩陣按行排列得到H1

1.5 擴(kuò)展H2得到校驗(yàn)矩陣H

(1)設(shè)一個單位矩陣I的維數(shù)為p×p，則

(2)隨機(jī)產(chǎn)生1-p之間的隨機(jī)數(shù)，該隨機(jī)數(shù)即為單位矩陣的循環(huán)移位數(shù)。

(3)將矩陣H2中的“1”用產(chǎn)生的隨機(jī)數(shù)來替代。

(4)將矩陣中的隨機(jī)數(shù)用對應(yīng)的置換矩陣替代填充，而矩陣H2中的元素“0”用p×P的零矩陣代替，由此即可生成所需的校驗(yàn)矩陣H，其維數(shù)為3pv2×pv3。

文獻(xiàn)中也給出了4環(huán)和6環(huán)的檢驗(yàn)算法，同時可驗(yàn)證按照此方法得到的校驗(yàn)矩陣最小圍長為8。

2 QC_LDPC碼的譯碼算法

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

2.1 QC_LDPC碼的分層譯碼策略

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

2.2 分層迭代譯碼算法

由上述子矩陣移位法構(gòu)造的是規(guī)則的QC_LDPC碼，因而采用分層譯碼時通常就是將校驗(yàn)矩陣行重的一個子塊行作為一個分層，以碼長3 456，碼率為1/2的(3，6)正規(guī)QC_LDPC碼為例，基陣大小為108×216，填充矩陣塊為16×16，以每個子塊行作為一個分層即每個分層16行，共有108個子層。

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

(1)初始化

(2)迭代過程(第t次迭代的第k層)。

Step1分層更新。

Step2譯碼判決。若Zj0，則

=1，否則

=0，更新譯碼結(jié)果

。 (3)譯碼結(jié)構(gòu)校驗(yàn)。完成一次迭代后，對更新的譯碼結(jié)果進(jìn)行校驗(yàn)。若滿足

xHT=0，或迭代次數(shù)達(dá)到系統(tǒng)設(shè)置的最大迭代次數(shù)，則停止譯碼，并輸出譯碼結(jié)果。否則，跳回步驟(2)進(jìn)行新一次迭代。

3 正規(guī)QC_LDPC碼的譯碼器

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

對碼長為3 456，碼率為1/2的(3，6)正規(guī)QC_LDPC碼，子矩陣大小為16×16，共有108個子塊行，216個子塊列，648個非零子矩陣。采用分層迭代譯碼算法實(shí)現(xiàn)譯碼器，譯碼過程中只保存Zn和Lm,n兩種中間數(shù)據(jù)，變量節(jié)點(diǎn)信息則通過式(2)計(jì)算得出，以減小數(shù)據(jù)存儲量。為便于硬件實(shí)現(xiàn)，選擇α=0.75作為修正因子，這樣只需簡單的帶符號位右移和加法運(yùn)算便可完成數(shù)據(jù)修正。由于將每一個子塊行作為一個分層，因此譯碼器的并行度為108，即共需108個基本運(yùn)算單元。對譯碼器中的數(shù)據(jù)進(jìn)行6 bit量化，并對計(jì)算過程中產(chǎn)生的溢出數(shù)據(jù)采用截?cái)嗵幚?，這樣的量化處理使譯碼性能約有0.1 dB的損失，但節(jié)約了硬件資源。

圖1為分層譯碼器的整體硬件結(jié)構(gòu)。

(1)數(shù)據(jù)輸入模塊。接收解調(diào)模塊輸出量化后的對數(shù)似然比數(shù)據(jù)，完成Zn的初始化。該模塊采用乒乓操作，即當(dāng)其中一個存儲器接收數(shù)據(jù)的同時，譯碼器從另外一個存儲器中讀取數(shù)據(jù)進(jìn)行譯碼，以此來提高譯碼器的吞吐量。

(2)數(shù)據(jù)存儲模塊。根據(jù)譯碼過程中所存儲數(shù)據(jù)的不同，存儲模塊可劃分為3塊：1)后驗(yàn)概率存儲模塊Zmem，用于存儲Zn。單個Zn的長度為6位，每個子塊列對應(yīng)的存儲空間為6×16=96位，對應(yīng)子塊列數(shù)，共需216個此類模塊。2)校驗(yàn)信息更新存儲模塊Lmem，用于存儲，單個的長度為6位，每一行有6個非零元素，所以每行對應(yīng)的存儲空間為6×6=36位，而每一子塊行所對應(yīng)的存儲空間為6×6×16=576位。對應(yīng)子塊行數(shù)，共需108個此類存儲模塊。3)譯碼結(jié)果存儲模塊，用于存儲譯碼的結(jié)果。每一子塊列對應(yīng)的譯碼數(shù)據(jù)長度為16位，對應(yīng)子塊列數(shù)，共需216個此類存儲空間。同樣為了提高吞吐量，譯碼數(shù)據(jù)輸出模塊也采用乒乓操作，當(dāng)一個存儲器進(jìn)行譯碼結(jié)果更新時，另一個存儲器向外設(shè)輸出存儲器中的譯碼結(jié)果。

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

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

(5)校驗(yàn)?zāi)K。校驗(yàn)?zāi)K在每一次迭代結(jié)束之后，對所有校驗(yàn)方程進(jìn)行驗(yàn)證，若全部滿足則停止迭代，否則進(jìn)行下一次迭代過程，直至達(dá)到預(yù)先設(shè)定的最高迭代次數(shù)為止。

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

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

在PCUB模塊中，每個校驗(yàn)節(jié)點(diǎn)對應(yīng)的6個變量節(jié)點(diǎn)信息串行加入迭代過程，而這些節(jié)點(diǎn)信息存儲在與之對應(yīng)的216個Zmem中。由于校驗(yàn)矩陣列重為3，因此，若按照校驗(yàn)矩陣原來的結(jié)構(gòu)，當(dāng)108個PCUB并行從Zmem中讀取數(shù)據(jù)時，順序讀取變量節(jié)點(diǎn)信息時可能從某一子塊列對應(yīng)的Zmem中讀取1～3個數(shù)據(jù)，這樣不同的讀取情況，會增加Zmem的硬件設(shè)計(jì)復(fù)雜度。

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

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

選用Altera公司StratixIII系列的EP3SL340器件，設(shè)置最大迭代次數(shù)為5次，在QuartusII 9.0下完成綜合與布局布線，硬件資源消耗如表1所示。

在譯碼過程中，首先花費(fèi)108個時鐘進(jìn)行Zmem的初始化過程，完成后開始迭代譯碼。在每一次迭代過程中，PCUB模塊進(jìn)行108次更新，由于采用流水線結(jié)構(gòu)，每次更新實(shí)際僅需花費(fèi)6個時鐘，再加上第一組數(shù)據(jù)進(jìn)入流水線花費(fèi)的額外6個時鐘，5次迭代共花費(fèi)6×(108×5)+6=3 246個時鐘。

圖2為傳統(tǒng)迭代與分層迭代譯碼算法的性能曲線比較，為AWGN信道模式下采用BPSK調(diào)制，進(jìn)行6 bit量化。通過圖中的性能曲線可看出，在最大迭代次數(shù)同為5次的情況下，對正規(guī)QC_LDPC碼采用分層譯碼器處理后相比采用傳統(tǒng)部分并行結(jié)構(gòu)譯碼器具有較好的譯碼性能表現(xiàn)，在信噪比為2.5 dB的情況一，誤碼率可以達(dá)到10-5量級。

5 結(jié)束語

文中首先利用3個不同的子矩陣分別按照指定的方法進(jìn)行移位運(yùn)算，組合得到無4環(huán)和6環(huán)的基陣，進(jìn)而利用單位矩陣及其移位矩陣作為替換因子隨機(jī)替換基陣中的“1”而擴(kuò)展得到所需的校驗(yàn)矩陣。隨后采用分層譯碼算法，該算法較傳統(tǒng)的部分并行結(jié)構(gòu)有較好的收斂性，并降低了迭代次數(shù)的要求。同時在Altera公司的StratixIII系列FPGA上得以實(shí)現(xiàn)，驗(yàn)證其達(dá)到了較高的譯碼吞吐量。