基于FPGA的大圍數QC_LDPC碼的譯碼器

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

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

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

1 校驗矩陣的構造

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

1.1 子矩陣D的構造

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

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

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

1.2 子矩陣E的構造

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

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

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

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

1.3 子矩陣F的構造

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

(2)將F0向右循環(huán)移位，每移動(dòng)1位生成v-1個(gè)新矩陣，共生成個(gè)新矩陣時(shí)停止移位，將新矩陣記為F1，F2，F3，…，Fv-1。

(3)將F0，F1，F2，F3，…，Fv-1按照列的方向排列，生成的矩陣記為Fv=[F0，F1，F2，F3，…，Fv-1]T。

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

1.4 矩陣H2的擴展算法

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

1.5 擴展H2得到校驗矩陣H

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

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

(3)將矩陣H2中的“1”用產(chǎn)生的隨機數來(lái)替代。

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

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

2 QC_LDPC碼的譯碼算法

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

2.1 QC_LDPC碼的分層譯碼策略

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

2.2 分層迭代譯碼算法

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

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

(1)初始化

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

Step1分層更新。

Step2譯碼判決。若Zj0，則

=1，否則

=0，更新譯碼結果

。 (3)譯碼結構校驗。完成一次迭代后，對更新的譯碼結果進(jìn)行校驗。若滿(mǎn)足

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

3 正規QC_LDPC碼的譯碼器

3.1 譯碼器的結構

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

圖1為分層譯碼器的整體硬件結構。

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

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

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

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

(5)校驗模塊。校驗模塊在每一次迭代結束之后，對所有校驗方程進(jìn)行驗證，若全部滿(mǎn)足則停止迭代，否則進(jìn)行下一次迭代過(guò)程，直至達到預先設定的最高迭代次數為止。

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

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

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

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

4 FPGA實(shí)現

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

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

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

5 結束語(yǔ)

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