張佳巖，張士偉，吳 瑋，張 弛，王 碩

(哈爾濱工業(yè)大學(xué) 通信技術(shù)研究所，黑龍江 哈爾濱 150001)

快速收斂的EG-LDPC譯碼算法設(shè)計(jì)實(shí)現(xiàn)

張佳巖，張士偉，吳 瑋，張 弛，王 碩

(哈爾濱工業(yè)大學(xué) 通信技術(shù)研究所，黑龍江 哈爾濱 150001)

歐氏幾何構(gòu)造的LDPC碼屬于不可分層的LDPC碼，無(wú)法采用TDMP算法譯碼結(jié)構(gòu)，針對(duì)該問(wèn)題設(shè)計(jì)實(shí)現(xiàn)了一種新型分層譯碼器。在Xilinx V5FPGA上實(shí)現(xiàn)了碼長(zhǎng)為1 023、碼率為0.781 EG-LDPC碼的譯碼器設(shè)計(jì)。仿真驗(yàn)證表明：理論上該方法與優(yōu)化的規(guī)范化最小和譯碼算法相比，迭代次數(shù)減少一倍，存儲(chǔ)資源消耗得到降低，而誤碼性能幾乎相同。FPGA實(shí)現(xiàn)上，譯碼輸出與MATLAB定點(diǎn)仿真給出的結(jié)果相同，誤碼性能由于量化和限幅處理與理論值相比約有0.3 dB的損失。在時(shí)鐘頻率為50 MHz串行處理各分層時(shí)，吞吐量為49.7 Mbit/s。

EG-LDPC；分層最小和譯碼；FPGA

低密度奇偶校驗(yàn)碼(LDPC)是由Gallager在19世紀(jì)60年代提出的逼近香農(nóng)限的信道編碼[1]，但其并沒(méi)有給出高性能LDPC碼校驗(yàn)矩陣系統(tǒng)的構(gòu)造方法。Shu Lin和Forssorier基于有限域歐氏幾何理論首次提出了一種系統(tǒng)的構(gòu)造高碼率LDPC碼的方法[2]，這類碼具有不可分層、準(zhǔn)循環(huán)形式的校驗(yàn)矩陣，編碼簡(jiǎn)單且適用不同的傳統(tǒng)譯碼算法。LDPC碼在無(wú)線通信中應(yīng)用廣泛，在LTE中使用可保證系統(tǒng)性能[3]。

LDPC碼譯碼算法的研究主要集中在提升誤碼性能，減少譯碼復(fù)雜度及加快收斂速度3個(gè)方面。文獻(xiàn)[4]提出了一種低復(fù)雜度的BP譯碼算法，在迭代過(guò)程中只更新可靠度低的節(jié)點(diǎn)消息，省去高可靠度的節(jié)點(diǎn)消息的計(jì)算，從而來(lái)提高譯碼算法的收斂速度，但仍避免不了概率域BP算法中乘法運(yùn)算及對(duì)數(shù)域BP中的雙曲正切、反正切計(jì)算，收斂雖然較快但資源消耗大，不適合硬件實(shí)現(xiàn)。文獻(xiàn)[5]提出了整數(shù)量化最小和譯碼算法，易于硬件實(shí)現(xiàn)，通過(guò)新增額外校驗(yàn)因子使誤碼性能提高，但在高信噪比下與連續(xù)譯碼存在差距。文獻(xiàn)[6]首次提出把Turbo譯碼消息傳遞機(jī)制應(yīng)用到LDPC譯碼中的TDMP算法，誤碼性能良好，收斂速度快，但不適用不可分層LDPC碼。針對(duì)該問(wèn)題，結(jié)合TDMP的消息傳遞機(jī)制與NMSA算法[7]提出了一種分層NMSA算法并對(duì)其進(jìn)行FPGA實(shí)現(xiàn)。該算法誤碼性能較好，最大迭代5次即可，較文獻(xiàn)[8]中迭代30次相比，能夠有效減少譯碼延遲和資源消耗。

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

本設(shè)計(jì)基于m=2，s=5的歐氏幾何構(gòu)造的校驗(yàn)矩陣。構(gòu)造EG-LDPC碼校驗(yàn)矩陣具體步驟如下：

步驟1：根據(jù)碼長(zhǎng)和碼率等參數(shù)確定歐氏幾何的參數(shù)m和s，計(jì)算GF(2ms)的本原元α及其子域GF(2s)本原元β。

步驟2：創(chuàng)建一個(gè)向量v，向量的元素為子域GF(2s)中的所有元素，v向量記錄了EG(m,2s)中一條過(guò)原點(diǎn)的直線上的點(diǎn)。

步驟3：構(gòu)造出EG(m,2s)歐氏空間中所有過(guò)原點(diǎn)的直線所對(duì)應(yīng)的向量。

α·v,α2·v,…,αn·v(n=2ms/2s)

(1)

步驟4：取出任意一條過(guò)原點(diǎn)直線對(duì)應(yīng)的向量αi·v，進(jìn)行以下計(jì)算

x+αi·vx∈GF(2ms)

(2)

即可得到與直線αi·v平行的所有直線對(duì)應(yīng)的向量。取不同的值計(jì)算結(jié)果可能出現(xiàn)重復(fù)，如果重復(fù)則去掉，不重復(fù)則保留。遍歷步驟3中的所有向量，即可求出EG(m,2s)歐氏幾何上所有直線對(duì)應(yīng)的保存著直線上點(diǎn)的向量。

步驟5：計(jì)算EG(m,2s)歐氏幾何上所有直線的關(guān)聯(lián)向量L。創(chuàng)建一個(gè)向量，向量的大小與歐氏幾何中點(diǎn)的數(shù)目相同，L的每個(gè)元素與GF(2ms)域上的元素一一對(duì)應(yīng)，取出步驟4中的一個(gè)向量Γ，把L中與Γ中元素相對(duì)應(yīng)的位置置1，其他位置置0，遍歷步驟4中的所有向量，就構(gòu)造出了EG(m,2s)歐氏幾何中所有直線的關(guān)聯(lián)向量。

步驟6：去掉所有過(guò)原點(diǎn)的直線的關(guān)聯(lián)向量并去掉原點(diǎn)，就得到了EG-LDPC碼的奇偶校驗(yàn)矩陣H。

對(duì)于m=2，校驗(yàn)矩陣H只有一個(gè)循體。當(dāng)m大于2時(shí)，校驗(yàn)矩陣存在(2(m-1)s-1)/(2s-1)個(gè)循環(huán)體。取出校驗(yàn)矩陣H的一個(gè)行向量γ，對(duì)其進(jìn)行2ms-2次循環(huán)移位，對(duì)所得向量縱向排列就得到了一個(gè)循環(huán)體。從校驗(yàn)矩陣H中去掉該循環(huán)體中的所有向量，在校驗(yàn)矩陣H余下的向量中再取出一個(gè)向量，進(jìn)行同樣的處理，直到處理完矩陣H的所有向量。然后對(duì)每個(gè)循環(huán)體進(jìn)行橫向排列就得到了基于有限域歐氏幾何的QC-LDPC碼的校驗(yàn)矩陣Hqc。通過(guò)以上步驟得到了EG-1 023 LDPC碼的校驗(yàn)矩陣H。

2 改進(jìn)的分層最小和譯碼算法

記R,q,r分別為變量節(jié)點(diǎn)后驗(yàn)概率對(duì)數(shù)似然比，校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)消息，變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)消息。yi,σ2分別為信道輸入的采樣值，信道中高斯白噪聲的方差。采用BPSK的調(diào)制方式。l為迭代次數(shù)，k為第幾層。校驗(yàn)矩陣的一行即為一個(gè)分層。對(duì)于高行重的EG-LDPC碼，規(guī)范化系數(shù)一般取值較小[9-10]，大約為0.25。為了節(jié)省硬件資源減少開銷，本設(shè)計(jì)中規(guī)范化系數(shù)α取0.5。

1)初始化

(3)

2)迭代過(guò)程

(4)

(5)

(6)

3)判決譯碼

在每次迭代結(jié)束時(shí)，根據(jù)對(duì)接收碼字做出硬判決

(7)

如果HCT=0成立，終止迭代，否則進(jìn)行下一次迭代，直到達(dá)到最大迭代次數(shù)。該算法以規(guī)范化最小和譯碼算法為基礎(chǔ)，采用Turbo譯碼消息傳遞機(jī)制，使上層更新的信息及時(shí)得到利用，從而加快收斂速度。只需通過(guò)實(shí)時(shí)的加法運(yùn)算即可更新變量節(jié)點(diǎn)，節(jié)省了存儲(chǔ)資源，更利于硬件實(shí)現(xiàn)。

3 譯碼器結(jié)構(gòu)設(shè)計(jì)、仿真及分析

3.1 校驗(yàn)節(jié)點(diǎn)處單元

圖1 校驗(yàn)節(jié)點(diǎn)處理單元結(jié)構(gòu)圖

3.2 最小值計(jì)算模塊

該模塊輸出32個(gè)CTV絕對(duì)值中的最小值、次小值和最小值編號(hào)[11]。該結(jié)構(gòu)由比較器和連接單元構(gòu)成，詳見(jiàn)參考文獻(xiàn)[11]。仿真結(jié)果如圖2所示，輸入data0～data31，data1為0是最小值，可以看到index為1，求出最小值min_1st為0，次小值min_2st也是0。計(jì)算結(jié)果存儲(chǔ)到RAM中，絕對(duì)值量化為4 bit，共有1 023層，最小值和次小值消耗8 kbit的存儲(chǔ)資源，Index用5 bit來(lái)表示，供需消耗5 kbit的存儲(chǔ)資源。還需存儲(chǔ)的符號(hào)，每層32個(gè)，需要消耗32 kbit。需要的存儲(chǔ)單元共為45 kbit，存儲(chǔ)資源的消耗相當(dāng)小，而碼長(zhǎng)更長(zhǎng)如(4 599， 4 227)的EG-LDPC碼存儲(chǔ)資源的消耗與本文中的(1 023， 781)的EG-LDPC碼存儲(chǔ)資源消耗是相同的。

圖2 最小值計(jì)算模塊結(jié)果(截圖)

3.3 譯碼器工作過(guò)程

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

圖4 譯碼輸出結(jié)果(截圖)

理論誤碼性能(α=0.5)與硬件實(shí)現(xiàn)的誤碼性能對(duì)比如圖5所示。由于初始化信息與變量、校驗(yàn)節(jié)點(diǎn)信息量化的影響，硬件實(shí)現(xiàn)與理論大概有0.3 dB的誤碼性能損失。

圖5 理論與硬件誤碼性能

對(duì)于(1 023，781)的EG-LDPC碼，規(guī)范化系數(shù)取0.25時(shí)，此算法誤碼性能最優(yōu)，在迭代5次時(shí)比概率域BP譯碼算法迭代50次時(shí)有0.2 dB的編碼增益，比對(duì)數(shù)域BP算法約有0.3 dB的增益，比最小和譯碼算法(min-sum)約有2 dB的編碼增益，如圖6所示。所以該算法誤碼性能良好且具有較快的收斂速度，從而減小了硬件實(shí)現(xiàn)時(shí)的譯碼延遲。

圖6 與其他譯碼算法誤碼性能對(duì)比圖

4 小結(jié)

該譯碼器在平均迭代2～3次即可收斂，硬件實(shí)現(xiàn)時(shí)誤碼性能由于量化和計(jì)算過(guò)程中的限幅處理，與理論相比僅有0.3 dB的損失，資源消耗僅為45 kbit，譯碼延遲小，在串行情況50 MHz時(shí)鐘下吞吐量達(dá)到49.7 Mbit/s，進(jìn)行一定的并行處理吞吐量將更高。如果初始化信息和中間計(jì)算結(jié)果量化位數(shù)增多，可以選擇修正因子為0.25，誤碼性能會(huì)得到進(jìn)一步提高。

[1] 晏堅(jiān)，何元智，潘亞漢，等.差錯(cuò)控制編碼[M].北京：機(jī)械工業(yè)出版社，2007.

[2] KOU Yu， LIN Shu，F(xiàn)OSSORIER M P C. Low-density parity-check codes based on finite geometries： a rediscovery and new results[J]. IEEE Trans. Information Theory， 2001，47(7)：2711-2736.

[3] LAO L， LI L， ZHU M， et al. The improved Turbo-decoding Message-passing algorithm and corresponding decoder for LDPC based on LTE[C]//Proc. IEEE International Conference on Signal Processing， Communications and Computing (ICSPCC). [S.l.]：IEEE Press，2014： 890-894.

[4] 郭銳，劉濟(jì)林.LDPC碼的一種低復(fù)雜度BP譯碼算法[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2008，42(3)：450-455.

[5] 馬匯淼，馬林華，張嵩，等.基于整數(shù)運(yùn)算的LDPC碼改進(jìn)最小和譯碼算法[J].電視技術(shù)，2013，37(17)：197-199.

[6] MANSOUR M M，SHANBHANG N R. High throughput LDPC decoders[J]. IEEE Trans. Very Large Scale Integration Systems， 2003(11)：976-978.

[7] 楊知行，林之初，王軍，等.準(zhǔn)循環(huán)LDPC碼的半并行譯碼器設(shè)計(jì)[J].電視技術(shù)，2006，30(2)：24-26.

[8] YAN Ying，DAN Bo，HUANG Shuangqu. A cost efficient LDPC decoder for DVB-S2[C]//Proc. IEEE 8th International Conference on ASIC. [S.l.]：IEEE Press，2009：1007-1010.

[9] CHEN Jinhu，MARC P C. Fossorier near optimum universal belief propagation based decoding of low-density parity check codes[J]. IEEE Trans. Communications， 2002，50(3)：406-414.

[10] 馬匯淼，馬林華，田雨. 基于改進(jìn)的分層譯碼算法的QC-LDPC譯碼器設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2012，38(7)：51-53.

[11] WEY C-L， SHIEH Ming-Der，LIN Shin-Yo. Algorithms of finding the first two minimum values and their hardware implementation[J]. IEEE Trans. Circuits and Systems I： Regular Papers，2008，55(11)：3430 -3437.

張佳巖(1974— )，副教授，碩士生導(dǎo)師，主要研究方向?yàn)樾诺谰幗獯a、擴(kuò)頻、深空通信技術(shù)；

張士偉(1990— )，碩士生，主研信道編碼技術(shù)；

吳 瑋(1981— )，博士，講師，主研無(wú)線自組網(wǎng)、LTE/LTE-A移動(dòng)通信系統(tǒng)；

張 弛(1990— )，碩士生，主研擴(kuò)頻信號(hào)快速捕獲、跟蹤技術(shù)。

王 碩(1992— )，女，碩士生，主研跳頻系統(tǒng)FPGA實(shí)現(xiàn)技術(shù)。

責(zé)任編輯：閆雯雯

Implementation of Efficient Convergence EG-LDPC Decoding Algorithm

ZHANG Jiayan, ZHANG Shiwei,WU Wei,ZHANG Chi,WANG Shuo

(CommunicationResearchCenter,HarbinInstituteofTechnology,Harbin150001,China)

For TDMP decoding structure is not applicable to LDPC code which is constructed based on finite field Euclidean geometry, a new layered decoder structure is proposed. The design can be able to decode the EG-1023 LDPC which code rate is 0.781 on Xilinx V5 FPGA. The simulation results show that on theory the speed of convergence is twice as quick as the optimal normalized min-sum algorithm and memory resources cost decreases, but the error performance does not change. When implemented on the FPGA, the error performance has a loss about 0.3 dB because of quantization and amplitude limiting. The throughput is 49.7 Mbit/s working on the 50 MHz clock.

EG-LPDC; layered min-sum algorithm; FPGA

國(guó)家自然科學(xué)基金項(xiàng)目(61201147)；國(guó)家科技重大專項(xiàng)項(xiàng)目(2012ZX03003011-004)

TN911

A

10.16280/j.videoe.2015.17.023

2015-04-06

【本文獻(xiàn)信息】張佳巖，張士偉，吳瑋，等.快速收斂的EG-LDPC譯碼算法設(shè)計(jì)實(shí)現(xiàn)[J].電視技術(shù),2015，39(17).