利用FPGA實(shí)現(xiàn)基于RU算法編碼器(LDPC編碼器)的設(shè)計(jì)

低密度奇偶校驗(yàn)（Low Density Parity Check Code，LDPC）碼是一類具有稀疏校驗(yàn)矩陣的線性分組碼，不僅有逼近Shannon限的良好性能，而且譯碼復(fù)雜度較低, 結(jié)構(gòu)靈活，是近年信道編碼領(lǐng)域的研究熱點(diǎn)，目前已廣泛應(yīng)用于深空通信、光纖通信、衛(wèi)星數(shù)字視頻和音頻廣播等領(lǐng)域。LDPC碼已成為第四代通信系統(tǒng)(4G)強(qiáng)有力的競(jìng)爭(zhēng)者，而基于LDPC碼的編碼方案已經(jīng)被下一代衛(wèi)星數(shù)字視頻廣播標(biāo)準(zhǔn)DVB-S2采納。

編碼器實(shí)現(xiàn)指標(biāo)分析

作為前向糾錯(cuò)系統(tǒng)的重要部分，設(shè)計(jì)高速率低復(fù)雜度LDPC碼編譯碼器成為提高系統(tǒng)性能的關(guān)鍵。對(duì)LDPC碼來(lái)說(shuō)，其編碼復(fù)雜度相對(duì)較大，編碼器的設(shè)計(jì)與實(shí)現(xiàn)是首要任務(wù)，也是譯碼器設(shè)計(jì)與實(shí)現(xiàn)的前提，有著十分重要的作用。

編碼速率與復(fù)雜度是評(píng)價(jià)LDPC編碼器好壞的重要指標(biāo)?？紤]高清晰度電視（HDTV）標(biāo)準(zhǔn)在分辨率為1920×1080，幀率為60幀/s，每個(gè)像素以24比特量化時(shí)，總數(shù)據(jù)率在2Gb/s的數(shù)量級(jí)。采用MPEG-2壓縮，要求數(shù)據(jù)率大約在20～40Mb/s。

編碼器設(shè)計(jì)思路

設(shè)LDPC碼檢驗(yàn)矩陣為H、生成矩陣為G 。傳統(tǒng)的編碼方法是利用生成矩陣G直接進(jìn)行編碼。由于G并不具有稀疏性，直接編碼的復(fù)雜度與碼長(zhǎng)N的平方成正比。本文的編碼器采用RU編碼算法。該算法通過(guò)對(duì)交換校驗(yàn)矩陣行列的位置，保持矩陣的稀疏性，利用交換行列后的校驗(yàn)矩陣進(jìn)行編碼，有效降低了編碼的復(fù)雜度。經(jīng)過(guò)行列交換的校驗(yàn)矩陣具有近似下三角形式，如圖1所示。

　　圖1 交換校驗(yàn)矩陣

設(shè)信息序列為s，碼字為C利用圖1的矩陣可對(duì)信息序列s進(jìn)行編碼。碼字分為三部分：C=（s，p1，p2），其中s是信息比特序列，長(zhǎng)度為k；p1和p2是校驗(yàn)比特序列，長(zhǎng)度分別為g和N-k-g。校驗(yàn)比特序列p1、p2計(jì)算公式如下：

編碼流程如圖2所示。

　　圖2 編碼流程圖

設(shè)計(jì)LDPC編碼器的時(shí)候注意：在RU算法中，對(duì)校驗(yàn)矩陣進(jìn)行行列交換，轉(zhuǎn)化為近似下三角形式稱為編碼預(yù)處理過(guò)程。給定一個(gè)校驗(yàn)矩陣，編碼預(yù)處理過(guò)程和矩陣的計(jì)算只需要做一次，所以可先用軟件完成。實(shí)際的編碼計(jì)算通過(guò)硬件實(shí)現(xiàn)。這樣做有利于提高編碼硬件實(shí)現(xiàn)的效率。

LDPC碼編碼器實(shí)現(xiàn)

LDPC碼編碼器硬件結(jié)構(gòu)

基于RU算法的LDPC編碼實(shí)現(xiàn)過(guò)程主要是計(jì)算p1、p2的過(guò)程。設(shè)計(jì)編碼器時(shí)，為了提高編碼速度，將可以同時(shí)計(jì)算的步驟作并行處理，得到編碼器的硬件結(jié)構(gòu)如圖3所示。

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

圖3中A、B、C、E分別代表圖1中相應(yīng)的矩陣，F(xiàn)代表Φ矩陣。從圖3可知，LDPC編碼器主要由緩沖器（buffer）、矩陣向量乘法器（MVM）、矩陣加法器（VA）、前向迭代運(yùn)算器（FS）、向量合成器（CWG）等運(yùn)算單元以及存儲(chǔ)各個(gè)矩陣相關(guān)信息的存儲(chǔ)器組成。因?yàn)榍跋虻\(yùn)算基本上是矩陣與向量的乘法計(jì)算，所以矩陣向量乘法是LDPC編碼過(guò)程最核心的單元。

分析圖3可知，編碼過(guò)程中，Cs與As的計(jì)算是同時(shí)進(jìn)行的，其他的操作都是串行進(jìn)行的。由于行列交換保持了矩陣的稀疏性，所以與A、B、C、E矩陣的相關(guān)運(yùn)算是稀疏矩陣的運(yùn)算，存儲(chǔ)矩陣所需的空間少同時(shí)實(shí)現(xiàn)的復(fù)雜度低和運(yùn)算速度快。Φ是g×g的矩陣，由于在編碼預(yù)處理過(guò)程中保證了g盡量小，所以與Φ矩陣相關(guān)的運(yùn)算也是比較快的。

LDPC碼編碼器復(fù)雜度

表1和表2描述了編碼器計(jì)算校驗(yàn)序列p1、p2的流程及相應(yīng)的復(fù)雜度。

　　表1 p1的計(jì)算

　　表2 p2的計(jì)算

從表1和表2可知RU算法的復(fù)雜度與N+g2成正比，g越小，編碼復(fù)雜度越低。所以對(duì)校驗(yàn)矩陣進(jìn)行行列交換時(shí)，使g盡量小是進(jìn)一步降低編碼復(fù)雜度的關(guān)鍵。

表1中序號(hào)2與表2中序號(hào)4的操作涉及到下三角矩陣T。由于T-1也是下三角矩陣，為了降低復(fù)雜度，可采用前向迭代進(jìn)行計(jì)算。例如：假設(shè)Qx=y，Q為下三角矩陣，求x。計(jì)算過(guò)程如下：

編碼器核心模塊——矩陣向量乘法器（MVM）的實(shí)現(xiàn)

矩陣與矩陣的乘法運(yùn)算以及前向迭代運(yùn)算實(shí)質(zhì)上都是矩陣與向量的乘法。下面舉例說(shuō)明矩陣向量乘法器硬件實(shí)現(xiàn)的過(guò)程：

假設(shè)，對(duì)于LDPC編碼器，如何有效率地存儲(chǔ)各個(gè)矩陣的信息是降低復(fù)雜度的關(guān)鍵。下面給出一種矩陣存儲(chǔ)的方案：矩陣存儲(chǔ)器中記錄“1”在行中的位置以及對(duì)應(yīng)行行重，如表3所示。例如矩陣X第3行的“1”元素，在行中的位置為“0”，該行的行重為1。由于LDPC編碼過(guò)程中使用的矩陣大多是稀疏矩陣，所以采用該矩陣存儲(chǔ)方案能比較有效地利用存儲(chǔ)的空間并有利于矩陣與向量乘法的快速實(shí)現(xiàn)。

矩陣X每行中“1”的位置可看作選擇向量s相應(yīng)元素的地址索引，將選擇的所有元素相加作和，即完成X中某行與向量的運(yùn)算。由于涉及的運(yùn)算都是二進(jìn)制加法，相加作和操作可以作如下簡(jiǎn)化：根據(jù)矩陣每行“1”的位置選擇向量s的元素。統(tǒng)計(jì)被選擇的元素中“1”的個(gè)數(shù)，若結(jié)果為奇數(shù)則說(shuō)明相加的結(jié)果為“1”，否則說(shuō)明相加的結(jié)果為“0”。判斷結(jié)果為奇數(shù)或者偶數(shù)可由其二進(jìn)制形式的末位是“1”或者“0”得到。通過(guò)設(shè)置兩個(gè)計(jì)數(shù)器分別計(jì)算各行行重和選擇的向量s相應(yīng)位置的元素中“1”的個(gè)數(shù)，即可實(shí)現(xiàn)乘法單元的運(yùn)算。

矩陣向量乘法器的硬件結(jié)構(gòu)如圖4所示。

　　圖4 矩陣向量乘法器的硬件結(jié)構(gòu)

從圖4可知矩陣向量乘法器包括以下六個(gè)部分：調(diào)度單元（Scheduler），產(chǎn)生各模塊單元的使能信號(hào)；緩存單元（Info_buffer），對(duì)輸入信息序列進(jìn)行緩存處理；存儲(chǔ)器控制單元（Rom_ctrl），產(chǎn)生存儲(chǔ)器的地址信號(hào)；“1”位置存儲(chǔ)器（Rom_num），存儲(chǔ)矩陣各行“1”的位置；行重存儲(chǔ)器，存儲(chǔ)矩陣相應(yīng)各行行重；乘法單元（Multipler），進(jìn)行向量乘法運(yùn)算，最后輸出碼字。

矩陣向量乘法器仿真結(jié)果驗(yàn)證

在Quartus II環(huán)境下，實(shí)現(xiàn)output=Xs，得到如圖5所示時(shí)序圖。

　　圖5 output="Xs仿真時(shí)序圖"

圖5中“en”是使能信號(hào)，“clock”是時(shí)鐘信號(hào)，addr_num、addr_wei分別為兩個(gè)存儲(chǔ)器的地址信號(hào)，info_seq是輸入信息信號(hào)，rece是信息信號(hào)經(jīng)過(guò)緩存后的輸出信號(hào)，num_t是“1”在各行的位置信息，row_wei_t是相應(yīng)各行的行重，output是矩陣與向量相乘的結(jié)果。由圖5可知，output=[1 1 1]，信號(hào)輸出有一個(gè)時(shí)鐘周期的延時(shí)，仿真結(jié)果正確。

編碼器方案驗(yàn)證與優(yōu)缺點(diǎn)分析

本文利用FPGA實(shí)現(xiàn)了基于RU算法的編碼器設(shè)計(jì)實(shí)現(xiàn)。在Quartus II軟件環(huán)境下對(duì)LDPC編碼器進(jìn)行仿真，使用Stratix系列EP1s25F672I7芯片，對(duì)碼長(zhǎng)為504的碼字進(jìn)行編碼。編碼器占用約9%的邏輯單元，約5%的存儲(chǔ)單元，綜合后時(shí)鐘頻率達(dá)到120MHz，數(shù)據(jù)吞吐率達(dá)到33Mb/s，基本符合編碼器設(shè)計(jì)的要求。該編碼器結(jié)構(gòu)是一種通用的設(shè)計(jì)方案，可以應(yīng)用于各種不同的LDPC編碼中，但由于其采用通用的編碼算法，實(shí)現(xiàn)的復(fù)雜度高于某些特殊結(jié)構(gòu)的LDPC碼編碼器，比如準(zhǔn)循環(huán)LDPC碼。另外通過(guò)優(yōu)化時(shí)序和編碼結(jié)構(gòu)，可以進(jìn)一步提高本文的編碼器的編碼速度。