1、    利用FPGA實現(xiàn)基于RU算法編碼器(LDPC編碼器)的設計引言低密度奇偶校驗（LowDensityParityCheckCode，LDPC）碼是一類具有稀疏校驗矩陣的線性分組碼，不僅有逼近Shannon限的良好性能，而且譯碼復雜度較低,結構靈活，是近年信道編碼領域的研究熱點，目前已廣泛應用于深空通信、光纖通信、衛(wèi)星數(shù)字視頻和音頻廣播等領域。LDPC碼已成為第四代通信系統(tǒng)(4G)強有力的競爭者，而基于LDPC碼的編碼方案已經(jīng)被下一代衛(wèi)星數(shù)字視頻廣播標準DVB-S2采納。編碼器實現(xiàn)指標分析作為前向糾錯系統(tǒng)的重要引言低密度奇偶校驗（Low Densit

2、y Parity Check Code，LDPC）碼是一類具有稀疏校驗矩陣的線性分組碼，不僅有逼近Shannon限的良好性能，而且譯碼復雜度較低, 結構靈活，是近年信道編碼領域的研究熱點，目前已廣泛應用于深空通信、光纖通信、衛(wèi)星數(shù)字視頻和音頻廣播等領域。LDPC碼已成為第四代通信系統(tǒng)(4G)強有力的競爭者，而基于LDPC碼的編碼方案已經(jīng)被下一代衛(wèi)星數(shù)字視頻廣播標準DVB-S2采納。編碼器實現(xiàn)指標分析作為前向糾錯系統(tǒng)的重要部分，設計高速率低復雜度LDPC碼編譯碼器成為提高系統(tǒng)性能的關鍵。對LDPC碼來說，其編碼復雜度相對較大，編碼器的設計與實現(xiàn)是首要任務，也是譯碼器設計與實現(xiàn)的前提，有著十分重要

3、的作用。編碼速率與復雜度是評價LDPC編碼器好壞的重要指標?？紤]高清晰度電視（HDTV）標準在分辨率為1920×1080，幀率為60幀/s，每個像素以24比特量化時，總數(shù)據(jù)率在2Gb/s的數(shù)量級。采用MPEG-2壓縮，要求數(shù)據(jù)率大約在2040Mb/s。編碼器設計思路設LDPC碼檢驗矩陣為H、生成矩陣為G 。傳統(tǒng)的編碼方法是利用生成矩陣G直接進行編碼。由于G并不具有稀疏性，直接編碼的復雜度與碼長N的平方成正比。本文的編碼器采用RU編碼算法。該算法通過對交換校驗矩陣行列的位置，保持矩陣的稀疏性，利用交換行列后的校驗矩陣進行編碼，有效降低了編碼的復雜度。經(jīng)過行列交換的校驗矩陣具有近似下三角

4、形式，如圖1所示。圖1 交換校驗矩陣設信息序列為s，碼字為C利用圖1的矩陣可對信息序列s進行編碼。碼字分為三部分：C=（s，p1，p2），其中s是信息比特序列，長度為k；p1和p2是校驗比特序列，長度分別為g和N-k-g。校驗比特序列p1、p2計算公式如下：編碼流程如圖2所示。圖2 編碼流程圖設計LDPC編碼器的時候注意：在RU算法中，對校驗矩陣進行行列交換，轉化為近似下三角形式稱為編碼預處理過程。給定一個校驗矩陣，編碼預處理過程和矩陣的計算只需要做一次，所以可先用軟件完成。實際的編碼計算通過硬件實現(xiàn)。這樣做有利于提高編碼硬件實現(xiàn)的效率。LDPC碼編碼器實現(xiàn)LDPC碼編碼器硬件結構基于RU算法

5、的LDPC編碼實現(xiàn)過程主要是計算p1、p2的過程。設計編碼器時，為了提高編碼速度，將可以同時計算的步驟作并行處理，得到編碼器的硬件結構如圖3所示。圖3 LDPC碼編碼器結構圖3中A、B、C、E分別代表圖1中相應的矩陣，F(xiàn)代表矩陣。從圖3可知，LDPC編碼器主要由緩沖器（buffer）、矩陣向量乘法器（MVM）、矩陣加法器（VA）、前向迭代運算器（FS）、向量合成器（CWG）等運算單元以及存儲各個矩陣相關信息的存儲器組成。因為前向迭代運算基本上是矩陣與向量的乘法計算，所以矩陣向量乘法是LDPC編碼過程最核心的單元。分析圖3可知，編碼過程中，Cs與As的計算是同時進行的，其他的操作都是串行進行的。

6、由于行列交換保持了矩陣的稀疏性，所以與A、B、C、E矩陣的相關運算是稀疏矩陣的運算，存儲矩陣所需的空間少同時實現(xiàn)的復雜度低和運算速度快。是g×g的矩陣，由于在編碼預處理過程中保證了g盡量小，所以與矩陣相關的運算也是比較快的。LDPC碼編碼器復雜度表1和表2描述了編碼器計算校驗序列p1、p2的流程及相應的復雜度。表1 p1的計算表2 p2的計算從表1和表2可知RU算法的復雜度與N+g2成正比，g越小，編碼復雜度越低。所以對校驗矩陣進行行列交換時，使g盡量小是進一步降低編碼復雜度的關鍵。表1中序號2與表2中序號4的操作涉及到下三角矩陣T。由于T-1也是下三角矩陣，為了降低復雜度，可采用前

7、向迭代進行計算。例如：假設Qx=y，Q為下三角矩陣，求x。計算過程如下：編碼器核心模塊矩陣向量乘法器（MVM）的實現(xiàn)矩陣與矩陣的乘法運算以及前向迭代運算實質上都是矩陣與向量的乘法。下面舉例說明矩陣向量乘法器硬件實現(xiàn)的過程：假設，對于LDPC編碼器，如何有效率地存儲各個矩陣的信息是降低復雜度的關鍵。下面給出一種矩陣存儲的方案：矩陣存儲器中記錄“1”在行中的位置以及對應行行重，如表3所示。例如矩陣X第3行的“1”元素，在行中的位置為“0”，該行的行重為1。由于LDPC編碼過程中使用的矩陣大多是稀疏矩陣，所以采用該矩陣存儲方案能比較有效地利用存儲的空間并有利于矩陣與向量乘法的快速實現(xiàn)。矩陣X每行中“

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

9、er），產(chǎn)生各模塊單元的使能信號；緩存單元（Info_buffer），對輸入信息序列進行緩存處理；存儲器控制單元（Rom_ctrl），產(chǎn)生存儲器的地址信號；“1”位置存儲器（Rom_num），存儲矩陣各行“1”的位置；行重存儲器，存儲矩陣相應各行行重；乘法單元（Multipler），進行向量乘法運算，最后輸出碼字。矩陣向量乘法器仿真結果驗證在Quartus II環(huán)境下，實現(xiàn)output=Xs，得到如圖5所示時序圖。圖5 output="Xs仿真時序圖"圖5中“en”是使能信號，“clock”是時鐘信號，addr_num、addr_wei分別為兩個存儲器的地址信號，info_seq是輸入信息信號，rece是信息信號經(jīng)過緩存后的輸出信號，num_t是“1”在各行的位置信息，row_wei_t是相應各行的行重，output是矩陣與向量相乘的結果。由圖5可知，output=1 1 1，信號輸出有一個時鐘周期的延時，仿真結果正確。編碼器方案驗證與優(yōu)缺點分析本文利用FPGA實現(xiàn)了基于RU算法的編碼器設計實現(xiàn)。在Quartus II軟件環(huán)境下對LDPC編碼器進行仿真，使用Stratix系列EP1s25F672I7芯片，對碼長為504的碼字進行編碼。編碼器占用約9%的邏輯單元，約5%的存儲單元，綜合后時