新型LDPC碼譯碼器

孟慶剛，劉騰宇

（1.黑龍江工程學(xué)院 電氣與信息工程學(xué)院，黑龍江 哈爾濱150050；2.黑龍江省高級(jí)人民法院，黑龍江 哈爾濱150001）

LDPC（Low－Density Parity－Check）碼具有逼近Shannon限的性能［1］，于1962年由Gallager首先提出，是信道編碼領(lǐng)域的研究熱點(diǎn)之一。隨著研究的不斷深入，CHUNG設(shè)計(jì)出糾錯(cuò)性能超過Turbo碼的LDPC碼［2］，這一研究成果引起學(xué)術(shù)界和通信業(yè)界的高度重視，也使LDPC碼成為許多通信協(xié)議的信道編碼備選方案［3］。由于LDPC碼采用基于消息傳遞機(jī)制（message－passing）的迭代譯碼算法［4］，譯碼流程復(fù)雜，且譯碼過程中會(huì)產(chǎn)生大量的譯碼中間變量，實(shí)現(xiàn)碼長為1 000的LDPC碼譯碼器就要耗費(fèi)170萬邏輯門［5］，譯碼器實(shí)現(xiàn)難度較高，阻礙了LDPC碼在工業(yè)界的廣范應(yīng)用。本文對LDPC碼奇偶校驗(yàn)矩陣的結(jié)構(gòu)特點(diǎn)和譯碼算法的數(shù)據(jù)流程進(jìn)行研究，設(shè)計(jì)出一種新型的LDPC碼譯碼器，降低了譯碼器的硬件實(shí)現(xiàn)復(fù)雜度，為LDPC碼譯碼器通用芯片的研發(fā)提供參考。

1 校驗(yàn)矩陣結(jié)構(gòu)和LDPC碼譯碼算法

1.1 LDPC 碼的校驗(yàn)矩陣結(jié)構(gòu)

LDPC碼的校驗(yàn)矩陣，又稱H矩陣。H矩陣的結(jié)構(gòu)是影響LDPC碼糾錯(cuò)性能和LDPC碼譯碼復(fù)雜度的關(guān)鍵因素。本文基于準(zhǔn)循環(huán)結(jié)構(gòu)的校驗(yàn)矩陣設(shè)計(jì)LDPC碼譯碼器［6］，H＝［HS｜HP］表示譯碼器所采用的校驗(yàn)矩陣，HS和 HP如式（1）、式（2）所示。

式中：0是p×p的零陣，I是p×p的單位陣，子矩陣Hj，l或是零陣，或是矩陣I按行循環(huán)左移sj，l次后得到的矩陣。利用密度進(jìn)化理論能夠計(jì)算出每個(gè)Hj，l矩陣的最優(yōu)循環(huán)移位次數(shù)，使H矩陣的圍長（girth）最大，從而生成一組糾錯(cuò)性能最好的LDPC碼字。

1.2 歸一化最小和譯碼算法

BP算法是糾錯(cuò)性能最佳的LDPC碼譯碼算法，其譯碼復(fù)雜度最高。最小和算法（BP－Based）是復(fù)雜度最低的LDPC碼譯碼算法，但譯碼的誤差較大，嚴(yán)重降低了LDPC碼的糾錯(cuò)性能［7］。歸一化最小和（normalized BP－Based）譯碼算法對最小和算法進(jìn)行了改進(jìn)，不僅譯碼復(fù)雜度較低，而且提高了譯碼性能［7］。下面在AWGN信道環(huán)境下（噪聲均值為0，方差為σ2，接收變量為yj），采用BPSK調(diào)制，給出歸一化最小和譯碼算法。N（i）＼｛j｝表示H 矩陣第i行中1的位置集合除去位置j，M（j）＼｛i｝表示H矩陣第j列中1的位置集合除去位置i，L（x）為x的對數(shù)似然比，gij為變量節(jié)點(diǎn)信息，hij為校驗(yàn)節(jié)點(diǎn)信息。

1）初始化。

2）迭代過程。

步驟1（更新校驗(yàn)節(jié)點(diǎn)）：將L（gij）分解成αij＝sign（L（gij）），βij＝｜L（gij）｜。

步驟2（更新變量節(jié)點(diǎn)）：

步驟4（對譯碼信息進(jìn)行硬判決）：設(shè)＾c＝［＾c1…＾cn］，當(dāng)L（Qj）＜0，使＾cj＝1，當(dāng)L（Qj）≥0，使＾cj＝0。如果H·＾c＝0，則迭代譯碼過程停止，＾c為譯碼結(jié)果，否則返回步驟1重復(fù)執(zhí)行。當(dāng)?shù)螖?shù)到達(dá)設(shè)定的最大值，將最末次硬判決值作為譯碼結(jié)果。

2 LDPC碼譯碼器設(shè)計(jì)

1.1 中H矩陣的子矩陣分為3類，即單位矩陣、單位矩陣的循環(huán)移位矩陣和全0矩陣。在譯碼過程中，可以串行處理每個(gè)子矩陣中的數(shù)據(jù)，并行處理相互之間沒有數(shù)據(jù)傳遞聯(lián)系的子矩陣塊，從而依據(jù)部分并行機(jī)制設(shè)計(jì)LDPC碼譯碼器的數(shù)據(jù)流程，硬件整體結(jié)構(gòu)如圖1所示。譯碼步驟如下：

第1步：串并轉(zhuǎn)換模塊將接收到的譯碼初始化信息按照校驗(yàn)矩陣的結(jié)構(gòu)特點(diǎn)進(jìn)行分塊。

第2步：數(shù)據(jù)分塊完成后被存入存儲(chǔ)器陣列，以供數(shù)據(jù)處理單元調(diào)用。

圖1 譯碼器硬件結(jié)構(gòu)

第3步：變量信息處理陣列從存儲(chǔ)器陣列中取出數(shù)據(jù)進(jìn)行更新處理，將更新的數(shù)據(jù)再存入存儲(chǔ)器陣列。

第4步：校驗(yàn)信息處理陣列從存儲(chǔ)器陣列中取出數(shù)據(jù)進(jìn)行更新處理，完成一次迭代譯碼，并將譯出的碼字暫存，將更新的數(shù)據(jù)再存入存儲(chǔ)器陣列。

一種基于纜索的堆石混凝土堆石入倉方式及應(yīng)用……………………………… 陳長久，安雪暉，閉忠明等（20.36）

以上步驟由時(shí)序控制部分有序控制，譯碼器根據(jù)譯碼迭代數(shù)值重復(fù)執(zhí)行第3步和第4步，將最后一次迭代中第4步得到的碼字作為譯碼的最終結(jié)果，輸出給并串轉(zhuǎn)換單元，至此，一幀數(shù)據(jù)譯碼結(jié)束。存儲(chǔ)器陣列是影響譯碼器占用硬件資源量的關(guān)鍵部件之一，其結(jié)構(gòu)如圖2所示。

圖2 存儲(chǔ)器陣列結(jié)構(gòu)

設(shè)校驗(yàn)矩陣的子矩陣維數(shù)為w，則圖2中每個(gè)存儲(chǔ)器的存儲(chǔ)深度為w。存儲(chǔ)器陣列分為兩個(gè)子陣列：子陣列1，即R＿I1……R＿In，存儲(chǔ)譯碼初始化信息，若碼長為N，則將初始化信息等分為n＝N／w段，依次存入R＿I1至R＿In；子陣列2，即R＿11……R＿mn，與校驗(yàn)矩陣中單位矩陣及單位矩陣的循環(huán)移位矩陣一一對應(yīng)。利用雙口RAM組成存儲(chǔ)器陣列，每個(gè)RAM交替存儲(chǔ)變量節(jié)點(diǎn)信息和校驗(yàn)節(jié)點(diǎn)信息，在地址發(fā)生器陣列的控制下，兩個(gè)輸出口分別輸出更新后的校驗(yàn)節(jié)點(diǎn)信息和變量節(jié)點(diǎn)信息，實(shí)現(xiàn)了數(shù)據(jù)存儲(chǔ)空間的復(fù)用，可以有效提高資源利用率。

H矩陣元素?cái)?shù)量與碼長的平方成正比，在硬件中記錄這些地址值將占用大量的存儲(chǔ)空間，為了降低硬件譯碼器實(shí)現(xiàn)難度，地址發(fā)生器陣列如圖3所示。

圖3 地址發(fā)生器陣列結(jié)構(gòu)

初始化地址控制陣列由n個(gè)w進(jìn)制的計(jì)數(shù)器構(gòu)成每個(gè)計(jì)數(shù)器的初值為0，為譯碼初始化和校驗(yàn)節(jié)點(diǎn)信息更新提供地址。變量信息處理地址控制陣列中w進(jìn)制計(jì)數(shù)器的個(gè)數(shù)與校驗(yàn)矩陣中單位矩陣和單位矩陣的循環(huán)移位矩陣的個(gè)數(shù)相同，計(jì)數(shù)器的初值為單位矩陣的循環(huán)移位次數(shù)，為變量節(jié)點(diǎn)信息更新提供地址。地址發(fā)生器陣列充分利用了非規(guī)則準(zhǔn)循環(huán)矩陣中非零子矩陣內(nèi)部地址具有連續(xù)性和各個(gè)非零子矩陣地址具有獨(dú)立性的特點(diǎn)，將硬件記錄地址的最大值縮小到組成校驗(yàn)矩陣的單位矩陣的維數(shù)。

LDPC碼譯碼算法的迭代次數(shù)較多，且每次譯碼迭代需要處理的譯碼信息量龐大，時(shí)序控制復(fù)雜。本設(shè)計(jì)采用主從結(jié)構(gòu)狀態(tài)機(jī)實(shí)現(xiàn)譯碼器的時(shí)序控制，狀態(tài)轉(zhuǎn)換如圖4～7所示。

全局控制狀態(tài)機(jī)為主狀態(tài)機(jī)，遵循譯碼流程驅(qū)動(dòng)EN－INITIAL從狀態(tài)機(jī)、EN－VNU 從狀態(tài)機(jī)和EN－CNU從狀態(tài)機(jī)交替運(yùn)行。主從結(jié)構(gòu)的時(shí)序控制機(jī)層次分明，每個(gè)狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換比較簡單，各個(gè)狀態(tài)機(jī)組合起來具有強(qiáng)大的時(shí)序控制功能。

3 LDPC碼譯碼器實(shí)現(xiàn)及驗(yàn)證

基于Xilinx公司生產(chǎn)的V2PRO系列FPGA中的XC2VP30芯片實(shí)現(xiàn)了碼長為384bit，碼率為1／2的LDPC碼譯碼器，譯碼算法為歸一化最小和算法，譯碼迭代15次。對整個(gè)譯碼器進(jìn)行綜合、轉(zhuǎn)換、映射、布局布線。綜合報(bào)告如下：

Device utilization summary：

Selected Device：2vp30ff896－6

Number of Slices：2849out of 13696 20%

Number of Slice Flip Flops：3082out of 27392 11%

Number of 4input LUTs：5448out of 27392 19%

Timing Summary：

Speed Grade：－6Minimum period：2.920ns（Maximum Frequency：342.466MHz）

最大時(shí)鐘頻率342.466MHz，譯碼內(nèi)核完成一幀譯碼的最小時(shí)延（迭代15次）為

譯碼吞吐量為11.24Mbit／s。利用 Modelsim SE 6.0進(jìn)行布局布線后仿真，仿真波形如圖8所示。

圖8 譯碼結(jié)果縮略圖

模擬通信系統(tǒng)，用 Matlab函數(shù)產(chǎn)生信源［9－10］，在計(jì)算機(jī)上對LDPC碼字進(jìn)行BPSK調(diào)制，加高斯白噪聲噪、解調(diào)、量化譯碼初始化信息，通過串口傳給硬件譯碼器，譯碼器進(jìn)行譯碼，最后把譯碼結(jié)果反饋給計(jì)算機(jī)。對整個(gè)系統(tǒng)進(jìn)行了測試，將測試結(jié)果與理論仿真結(jié)果作對比，如圖9所示。

圖9 譯碼性能驗(yàn)證

理論仿真性能與實(shí)際測試結(jié)果基本吻合，證明設(shè)計(jì)是合理的。

4 結(jié)束語

本文設(shè)計(jì)了一種新型的LDPC碼譯碼器，具有如下優(yōu)點(diǎn)：①良好的可擴(kuò)展性，如果需要增加LDPC碼譯碼器的譯碼碼長，只需要在存儲(chǔ)陣列中增加RAM模塊的數(shù)量，時(shí)序控制模塊基本不用改動(dòng)。②硬件實(shí)現(xiàn)復(fù)雜度低，用簡單的計(jì)數(shù)器實(shí)現(xiàn)了復(fù)雜的地址控制。主從結(jié)構(gòu)的時(shí)序控制狀態(tài)機(jī)易于實(shí)現(xiàn)、功能強(qiáng)大。這些特點(diǎn)使本文設(shè)計(jì)的譯碼器非常適合硬件實(shí)現(xiàn)。③硬件資源利用率高，復(fù)用存儲(chǔ)器陣列，利用計(jì)數(shù)器記錄校驗(yàn)矩陣中非零元素的地址，這些措施節(jié)省了大量的存儲(chǔ)空間，提高了硬件資源利用率。

［1］Mackay D J C.Good error correcting codes based on very sparse matrices［J］.IEEE Trans on Inform Theroy，1999，45：399－431.

［2］CHUNG S Y.On the design of low－density parity－check within 0.0045dB of the Shannon limit［J］.IEEE Commun，Lett，2001，5（2）：437－439.

［3］單明.LDPC碼解碼技術(shù)研究及實(shí)現(xiàn)［D］.南京：東南大學(xué)，2004.

［4］葉芳，劉鈞雷，朱琦.LDPC碼的譯碼算法［J］.南京郵電學(xué)院學(xué)報(bào)，2003，23（3）：65－69.

［5］Howland C，Blanksby A.A 690mW 1Gbps 1024－b，Rate－1／2Low－density Parity－check Code Decoder［J］.IEEE Journal of Solid－state Circuits，2002，37（3）：404－412.

［6］Zhiyong He.A class of irregular LDPC codes with low error floor and low encoding complexity［J］.IEEE Commun，Lett，2006，5（10）：372－374.

［7］尹曉琪.LDPC碼編碼及譯碼算法的研究［D］.南京：南京師范大學(xué)，2006.

［8］馬丕明.低密度校驗(yàn)碼的理論及應(yīng)用研究［D］.濟(jì)南：山東大學(xué)，2005.

［9］梅志紅 楊萬銓.MATLAB程序設(shè)計(jì)基礎(chǔ)及其應(yīng)用［M］.北京：清華大學(xué)出版社，2005.

［10］劉敏，魏玲.MATLAB通信仿真與應(yīng)用［M］.北京：國防工業(yè)出版社，2007.