引言

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

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

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

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

編碼器設(shè)計思路

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

圖1  交換校驗矩陣

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

編碼流程如圖2所示。

圖2  編碼流程圖

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

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

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

基于RU算法的LDPC編碼實現(xiàn)過程主要是計算p₁、p₂的過程。設(shè)計編碼器時，為了提高編碼速度，將可以同時計算的步驟作并行處理，得到編碼器的硬件結(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）、前向迭代運算器（FS）、向量合成器（CWG）等運算單元以及存儲各個矩陣相關(guān)信息的存儲器組成。因為前向迭代運算基本上是矩陣與向量的乘法計算，所以矩陣向量乘法是LDPC編碼過程最核心的單元。

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

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

表1和表2描述了編碼器計算校驗序列p₁、p₂的流程及相應(yīng)的復(fù)雜度。

表1  p1的計算

表2 p2的計算

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

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

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

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

假設(shè)，

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

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

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

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

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

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

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

圖5  output=X_s仿真時序圖

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

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

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