低密度奇偶校驗(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)有力的競爭者，而基于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)鍵。對LDPC碼來說，其編碼復(fù)雜度相對較大，編碼器的設(shè)計(jì)與實(shí)現(xiàn)是首要任務(wù)，也是譯碼器設(shè)計(jì)與實(shí)現(xiàn)的前提，有著十分重要的作用。

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

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

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

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

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

編碼流程如圖2所示。

　　圖2 編碼流程圖

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

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

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

基于RU算法的LDPC編碼實(shí)現(xiàn)過程主要是計(jì)算p1、p2的過程。設(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)算單元以及存儲各個(gè)矩陣相關(guān)信息的存儲器組成。因?yàn)榍跋虻\(yùn)算基本上是矩陣與向量的乘法計(jì)算，所以矩陣向量乘法是LDPC編碼過程最核心的單元。

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

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

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

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

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

矩陣X每行中“1”的位置可看作選擇向量s相應(yīng)元素的地址索引，將選擇的所有元素相加作和，即完成X中某行與向量的運(yùn)算。由于涉及的運(yùn)算都是二進(jìn)制加法，相加作和操作可以作如下簡化：根據(jù)矩陣每行“1”的位置選擇向量s的元素。統(tǒng)計(jì)被選擇的元素中“1”的個(gè)數(shù)，若結(jié)果為奇數(shù)則說明相加的結(jié)果為“1”，否則說明相加的結(jié)果為“0”。判斷結(jié)果為奇數(shù)或者偶數(shù)可由其二進(jìn)制形式的末位是“1”或者“0”得到。通過設(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)生各模塊單元的使能信號；緩存單元（Info_buffer），對輸入信息序列進(jìn)行緩存處理；存儲器控制單元（Rom_ctrl），產(chǎn)生存儲器的地址信號；“1”位置存儲器（Rom_num），存儲矩陣各行“1”的位置；行重存儲器，存儲矩陣相應(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”是使能信號，“clock”是時(shí)鐘信號，addr_num、addr_wei分別為兩個(gè)存儲器的地址信號，info_seq是輸入信息信號，rece是信息信號經(jīng)過緩存后的輸出信號，num_t是“1”在各行的位置信息，row_wei_t是相應(yīng)各行的行重，output是矩陣與向量相乘的結(jié)果。由圖5可知，output=[1 1 1]，信號輸出有一個(gè)時(shí)鐘周期的延時(shí)，仿真結(jié)果正確。

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

本文利用FPGA實(shí)現(xiàn)了基于RU算法的編碼器設(shè)計(jì)實(shí)現(xiàn)。在Quartus II軟件環(huán)境下對LDPC編碼器進(jìn)行仿真，使用Stratix系列EP1s25F672I7芯片，對碼長為504的碼字進(jìn)行編碼。編碼器占用約9%的邏輯單元，約5%的存儲單元，綜合后時(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碼。另外通過優(yōu)化時(shí)序和編碼結(jié)構(gòu)，可以進(jìn)一步提高本文的編碼器的編碼速度。