在通信系統(tǒng)中糾錯(cuò)碼被用來(lái)提高信道傳輸?shù)目煽啃院凸β世寐?，低密度奇偶校?yàn)碼LDPC(Low Density Parity Check code)是目前性能最好的糾錯(cuò)碼，最初由GaUager提出，但當(dāng)時(shí)并沒(méi)有引起足夠的重視。直到Turbo碼提出后，人們?cè)谘芯縏urbo碼的迭代解碼時(shí)，發(fā)現(xiàn)二者具有相同的特性，即約束隨機(jī)碼集合和迭代解碼算法，這導(dǎo)致了隨后LD-PC碼的復(fù)出。1996年，Mackay和Neal隨機(jī)構(gòu)造出的LDPC碼，當(dāng)碼長(zhǎng)很長(zhǎng)時(shí)其性能超過(guò)Turbo碼，并在實(shí)現(xiàn)上更有優(yōu)勢(shì)，從而激起編碼界對(duì)LDPC碼的研究熱情，成為當(dāng)今信道編碼領(lǐng)域最令人矚目的研究熱點(diǎn)之一。LDPC碼出色的糾錯(cuò)性能以及可以并行解碼的特點(diǎn)特別是其簡(jiǎn)單實(shí)用性使其成為下一代通信糾錯(cuò)編碼的首選。因此，這里介紹一種基于FPGA的LDPC編碼設(shè)計(jì)。

1 LDPC碼
    LDPC碼是一種線性分組碼，其校驗(yàn)矩陣是稀疏矩陣，因?yàn)橄鄳?yīng)的校驗(yàn)矩陣中包含絕大多數(shù)的0而僅有極少數(shù)的1而得名。一個(gè)(n，k)二進(jìn)制LDPC碼可以用一個(gè)非常稀疏的奇偶校驗(yàn)矩陣H來(lái)表示。其中，H是一個(gè)mxn的矩陣，n表示編碼比特長(zhǎng)度，m表示校驗(yàn)比特長(zhǎng)度，k=n-m是信息比特長(zhǎng)度。與校驗(yàn)矩陣H相對(duì)應(yīng)的是一個(gè)生成矩陣G，生成矩陣將要發(fā)送的信息s={sl，s2，…，sm}轉(zhuǎn)換成被傳輸?shù)拇a子c={c1，c2，…，cn}，n>m。對(duì)于任何一個(gè)合法的碼字c，都有校驗(yàn)方程HcT=0。

2 RU編碼算法
    LDPC碼屬于線性分組碼。信號(hào)通過(guò)LDPC編碼后的碼字符合公式：
   
式中，c為碼字，H為校驗(yàn)矩陣。
    直接的編碼方案：1)高斯消元，將校驗(yàn)矩陣H化為下三角形式：2)將c分為信息比特和校驗(yàn)比特2部分，如x=(s，p)，其中s為已知信息比特向量，p為待求校驗(yàn)信息比特向量；3)利用前向迭代方法解方程HcT=O，得到p。由于高斯消元后的矩陣不再具有稀疏性，因此這種編碼方法的硬件實(shí)現(xiàn)方案，其復(fù)雜度是與碼長(zhǎng)的平方成正比。為了降低復(fù)雜度，Richardson和Urbanke充分利用校驗(yàn)矩陣的稀疏性，將LDPC碼的編碼復(fù)雜度降到與碼長(zhǎng)n成線性關(guān)系，即RU算法。
    RU算法包括兩個(gè)階段：預(yù)處理階段和信號(hào)編碼階段。通過(guò)預(yù)處理將校驗(yàn)矩陣日變?yōu)橐粋€(gè)近似下三角的矩陣，由于這種變換僅僅通過(guò)行置換來(lái)實(shí)現(xiàn)，所以矩陣的稀疏特性被保留。如圖1所示，在校驗(yàn)矩陣H的近似下三角形式中，分塊矩陣A、B、C和c都保持了稀疏性，D為密集矩陣，T為稀疏的下三角矩陣。當(dāng)g很小時(shí)，即矩陣D很小時(shí)，可以大大降低編碼運(yùn)算復(fù)雜度。為減少運(yùn)算量應(yīng)在設(shè)計(jì)H矩陣時(shí)使g越小越好。
    實(shí)際編碼由矩陣相乘、前向迭代和向量相加操作組成。對(duì)于給定的一個(gè)校驗(yàn)矩陣，預(yù)處理編碼預(yù)處理過(guò)程和矩陣的計(jì)算只需要做一次，所以可先用軟件完成，實(shí)際編碼在硬件上完成。RU編碼算法中可以進(jìn)行部分并行運(yùn)算，使得吞吐率最大化。通過(guò)有效的矩陣存儲(chǔ)，降低存儲(chǔ)單元的消耗量。
2．1 編碼器設(shè)計(jì)

    預(yù)處理包括2步：三角化和秩校驗(yàn)。三角化通過(guò)行列置換處理將校驗(yàn)矩陣轉(zhuǎn)化成圖1所示的形式，則：
   
式中，A為(m-g)×(n-m)，B為(m-g)×g，T為(m-g)×(m-g)，C為gx(n-m)，D為gxg，E為gx(m-g)。除D外，其他全是稀疏矩陣，且T為對(duì)角線上全為l的下三角矩陣。
    設(shè)c：[sp1 p2]，其中s為系統(tǒng)信息部分，p1和p2共同組成校驗(yàn)信息部分，p1長(zhǎng)為g，p2長(zhǎng)為(m-g)。HcT=0左乘得到
    
    定義F=-ET-1 B+D，并且假定F是非奇的，由式(3)可得到p1和p2的求解式分別為
    
    在式(4)求解p1的過(guò)程中，要求矩陣F可逆，因此F必須為非奇異的，即可逆。因此實(shí)際編碼前必須進(jìn)行秩校驗(yàn)。為得到F，對(duì)原始H矩陣進(jìn)行高斯消元得到式(6)的形式：
    
    如果F為奇異的，則將F中的列與其最左邊的列進(jìn)行交換，直到F非奇異為止。
    編碼復(fù)雜度主要由g×g維矩陣F-1與向量(-ET-1 A+C)sT相乘決定。RU算法在g很小時(shí)，即g2<<n時(shí)，編碼復(fù)雜度與碼長(zhǎng)n成線性關(guān)系。因此，為了進(jìn)行有效編碼，預(yù)處理要使得g應(yīng)盡量的小。
2．2 編碼器硬件結(jié)構(gòu)
    基于RU算法的LDPC編碼實(shí)現(xiàn)過(guò)程主要是計(jì)算p1、p2的過(guò)程。設(shè)計(jì)編碼器時(shí)，為了提高編碼速度，將可以同時(shí)計(jì)算的步驟作并行處理，得到編碼器的硬件結(jié)構(gòu)如圖2所示。

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

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

    對(duì)于LDPC編碼器，如何有效存儲(chǔ)各個(gè)矩陣的信息是降低復(fù)雜度的關(guān)鍵。本文采用存儲(chǔ)矩陣中元素‘1’在行中的位置以及對(duì)應(yīng)行行重，如表1所示。例如矩陣X第3行的“1”元素，在行中的位置分別為“0”、“4”，該行的行重為2。由于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é)果為“l(fā)”，否則說(shuō)明相加的結(jié)果為“0”。判斷結(jié)果為奇數(shù)或者偶數(shù)可由其二進(jìn)制形式的末位是“1”或者“0”得到。通過(guò)設(shè)置2個(gè)計(jì)數(shù)器分別計(jì)算各行行重和選擇的向量s相應(yīng)位置的元素中“1”的個(gè)數(shù)，即可實(shí)現(xiàn)乘法單元的運(yùn)算。矩陣向量乘法器的硬件結(jié)構(gòu)如圖3所示。

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

4 結(jié)果驗(yàn)證
    矩陣向量乘法器仿真結(jié)果驗(yàn)證在Qum-tusⅡ環(huán)境下，實(shí)現(xiàn)output=XsT，得到如圖4所示的仿真時(shí)序圖。圖4中“en”是使能信號(hào)，“cloc-k”是時(shí)鐘信號(hào)，addr_nun、adds_t分別為2個(gè)存儲(chǔ)器的地址信號(hào)，info_seq是輸入信息信號(hào)，rece是信息信號(hào)經(jīng)過(guò)緩存后的輸出信號(hào)，num_t是“1”在各行的位置信息，rOW_t是相應(yīng)各行的行重，output是矩陣與向量相乘的結(jié)果。

    由圖4可知，output=[1 1 1]，信號(hào)輸出有一個(gè)時(shí)鐘周期的延時(shí)，仿真結(jié)果正確。

5 結(jié)束語(yǔ)
    用本文描述的方法，在1片Stratix系列的FPGAEPIS25F67217中，實(shí)現(xiàn)了最大碼長(zhǎng)為4 096的靈活編碼方案，編碼器占用約lO％的邏輯單元，約13％的存儲(chǔ)單元，綜合后時(shí)鐘頻率達(dá)到166 MHz，數(shù)據(jù)吞吐率達(dá)到48．33 Mb／s。該編碼器結(jié)構(gòu)是一種通用的設(shè)計(jì)方案，可以靈活地應(yīng)用于各種不同類(lèi)型的LDPC編碼中，并可有效地分配存儲(chǔ)器單元和最大可能地實(shí)現(xiàn)運(yùn)算過(guò)程中的并行處理，但由于其采用通用的編碼算法，實(shí)現(xiàn)的復(fù)雜度高于某些特殊結(jié)構(gòu)的LDPC編碼器，比如準(zhǔn)循環(huán)LDPC碼。另外通過(guò)優(yōu)化時(shí)序和編碼結(jié)構(gòu)，可以進(jìn)一步提高本文編碼器的編碼速度。