摘要：基于軟判決譯碼規(guī)則，采用完全并行的解碼結(jié)構(gòu)，使用Verilog硬件描述語(yǔ)言，在Xilinx公司的FPGA（Virtex-2 xcv1000）上實(shí)現(xiàn)了碼率為1/2、幀長(zhǎng)為20bit的規(guī)則（3，6）LDPC碼的譯碼器，最大傳輸速率可達(dá)20Mbps。對(duì)LDPC碼的實(shí)際應(yīng)用具有重要的推動(dòng)作用。

    關(guān)鍵詞：LDPC碼 變量節(jié)點(diǎn) 校驗(yàn)檢點(diǎn) 因子圖 譯碼

在通信系統(tǒng)中糾錯(cuò)碼被用來(lái)提高信道傳輸?shù)目煽啃院凸β世�用率，低密度奇偶校�?yàn)碼（LDPC碼）是目前最逼近香農(nóng)限的一類(lèi)糾錯(cuò)碼。1962年，Gallager首次提出了LDPC碼的古典模型，即規(guī)則（regular）的LDPC碼：（n,j,k），校驗(yàn)矩陣H具有恒定的列重量和行重量。LDPC碼由于比Turbo碼列接近香農(nóng)限的誤碼率性能和完全并行的迭代譯碼算法使其比Turbo碼在部分場(chǎng)合具有更廣泛的應(yīng)用前景，從而使LDPC碼成為當(dāng)前糾錯(cuò)編碼的一個(gè)研究熱點(diǎn)�；�于良好的譯碼性能，LDPC碼被認(rèn)為是通信系統(tǒng)的下一代糾錯(cuò)碼。

1 規(guī)則LDPC碼

1．1 因子圖描述

因子圖有兩類(lèi)頂點(diǎn)，分別為變量節(jié)點(diǎn)（variable nodes,用空的圓點(diǎn)表示）和校驗(yàn)節(jié)點(diǎn)（check nodes,用方框表示）。Tanner圖就是這兩類(lèi)頂點(diǎn)之間的二部圖，即每條邊的一端與變量節(jié)點(diǎn)相連，另一端與校驗(yàn)節(jié)點(diǎn)相連。變量節(jié)點(diǎn)代表實(shí)際的變量，校驗(yàn)節(jié)點(diǎn)代表這些變量節(jié)點(diǎn)之間的約束。對(duì)于（j,k）-LDPC碼的每個(gè)變量（bit）都受j個(gè)校驗(yàn)（check）的結(jié)束，因此每個(gè)變量節(jié)點(diǎn)應(yīng)該連接j個(gè)校驗(yàn)節(jié)點(diǎn)。每個(gè)校驗(yàn)方程有k個(gè)變量，因此每個(gè)校驗(yàn)節(jié)點(diǎn)應(yīng)與k個(gè)變量節(jié)點(diǎn)相連。由于LDPC是一種線(xiàn)性碼，使得它的因子圖一邊為變量節(jié)點(diǎn)，一邊為校驗(yàn)節(jié)點(diǎn)，故LDPC碼的因子圖表示有專(zhuān)用的定義：二部圖（bipartite graphs）。

圖1表示了校驗(yàn)矩陣為H的規(guī)則（3，6）LDPC的因子圖，它是由10個(gè)變量定點(diǎn)和5個(gè)校驗(yàn)定點(diǎn)組成的二部圖，邊剛好對(duì)應(yīng)于矩陣中1的位置，這種因子圖是LDPC迭代譯碼算法的基礎(chǔ)。

1．2 LDPC碼的譯碼算法

LDPC碼的譯碼采用信度傳播（belief-propagation或BP）算法，它與因子圖相對(duì)應(yīng)，如圖1所示，利用BP算法獲得好的譯碼性能，LDPC碼的因子圖中環(huán)的長(zhǎng)度必須盡可能地長(zhǎng)，長(zhǎng)度為4的環(huán)會(huì)降低BP算法的性能，H矩陣設(shè)計(jì)時(shí)應(yīng)避免出現(xiàn)。如果直接使用BP算法，由于在迭代過(guò)程中存在大量的乘運(yùn)算，將使硬件的復(fù)雜度大幅度上升，本論文采用改進(jìn)的Log-BP算法，把大量的乘運(yùn)算轉(zhuǎn)換成加運(yùn)算，從而降低硬件復(fù)雜主生產(chǎn)成本。

首先定義可能用到的幾個(gè)變量及符號(hào)的意義：H表示一個(gè)M×N的LDPC校驗(yàn)矩陣，Hi,j表示矩陣H中第i行第j列的表示。定義校驗(yàn)節(jié)點(diǎn)m上的第n個(gè)變量節(jié)點(diǎn)為N（m）={n:Hm,n=1}，并聯(lián)在變量節(jié)點(diǎn)n上的第m個(gè)數(shù)驗(yàn)節(jié)點(diǎn)為M（n）={m:Hmn=1}。定義校驗(yàn)節(jié)點(diǎn)m上關(guān)聯(lián)的除了第n個(gè)變量節(jié)點(diǎn)以外的所有變量節(jié)點(diǎn)為N（M），變量節(jié)點(diǎn)n上關(guān)聯(lián)的除了第m個(gè)校驗(yàn)節(jié)點(diǎn)外的所有校驗(yàn)節(jié)點(diǎn)為M（n）。

Log-BP算法的譯碼過(guò)程：

譯碼過(guò)程：

初始化：對(duì)于接收到的每個(gè)變量節(jié)點(diǎn)n計(jì)算初始信道信息，并對(duì)每個(gè)點(diǎn)計(jì)算初始信息

    迭代譯碼：

（1）校驗(yàn)點(diǎn)計(jì)算

其中α=∑n" ∈N(m)|αm,n"|

(2)變量節(jié)點(diǎn)計(jì)算

對(duì)于每個(gè)變量節(jié)點(diǎn)n，在完成變量節(jié)點(diǎn)計(jì)算后，對(duì)log似然率λn進(jìn)行更新：

(3)判決條件

(a)如果λn>0,則x"N=0;返之如果λn≤0,則x"N=1;

(b)如果H·x"=0，則迭代結(jié)束，否則跳到第2步迭代譯碼部分，直至校驗(yàn)成功或者達(dá)到最大迭代次數(shù)。

上面算法中的αm,n和βm,n都被換為外部信息，其中αm,n是從變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳遞的信息，βm,n是從變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳遞的信息。通過(guò)log-BP算法和BP算法的比較可以實(shí)現(xiàn)，log-BP算法中除了f(x)=log運(yùn)算，剩下的都是加法運(yùn)算，從在則避免了BP算法中乘運(yùn)算過(guò)多的弊病。在本文中函數(shù)f(x)利用FPGA中的查找表（Look-up Table,LUT）實(shí)現(xiàn)。

2 H矩陣的生成

Gallager提出的LDPC碼的H矩陣必須滿(mǎn)足以下兩點(diǎn)：

（1） H矩陣的第一列有j個(gè)1，j>=3;

（2） H矩陣的第一行有k個(gè)1，k>j；

本文中選擇j=3,k=6，通過(guò)編程用matalab軟件生成若干滿(mǎn)足條件的H矩陣，選擇其中一個(gè)性能最好的H矩陣進(jìn)行LDPC碼的fpga譯碼實(shí)現(xiàn)。當(dāng)n=20時(shí)，最終選擇H矩陣如圖2所示。

3 LDPC碼完全平行譯碼結(jié)構(gòu)

由二部圖可能直接地看出，變量節(jié)點(diǎn)計(jì)算需要的信息只需由校驗(yàn)節(jié)點(diǎn)來(lái)提供，校驗(yàn)節(jié)點(diǎn)計(jì)算需要的信息只需要由變量節(jié)點(diǎn)來(lái)提供，譯碼器在設(shè)計(jì)時(shí)可以給每個(gè)變量節(jié)點(diǎn)分配一個(gè)變量節(jié)點(diǎn)處理單元（Variable Node processing Unit,VNU），給每個(gè)校驗(yàn)節(jié)點(diǎn)分配一個(gè)校驗(yàn)節(jié)點(diǎn)處理單元（Check Node processing Unit,CNU），從而實(shí)現(xiàn)譯碼器的完全并行結(jié)構(gòu)。

譯碼器的核心模塊是迭代譯碼部分，迭代譯碼的結(jié)構(gòu)與算法是緊密相連的，譯碼結(jié)構(gòu)的確定必須在仔細(xì)分析算法的基礎(chǔ)上，迭代譯碼的過(guò)程是CNU和VNU模塊計(jì)算結(jié)果的相互傳遞和更新。如果直接將CNU和VNU連接，不但不容易控制迭代的過(guò)程并且可能出現(xiàn)不穩(wěn)定狀態(tài)，所以需要在CNU和VNU之間安插RAM以起到數(shù)據(jù)的緩沖和控制作用。輸入、輸出模塊分別控制數(shù)據(jù)的輸入和輸出，當(dāng)條件滿(mǎn)足或者迭代完成時(shí)，讀入數(shù)據(jù)并把迭代結(jié)果輸出。

3.1 迭代譯碼結(jié)構(gòu)

圖3表示平行迭代譯碼結(jié)構(gòu)。其中只畫(huà)出兩個(gè)節(jié)點(diǎn)之間一條數(shù)據(jù)通路的連接方式，因?yàn)槭峭耆�平行迭代譯碼結(jié)構(gòu)，其他節(jié)點(diǎn)之間數(shù)據(jù)通路的連接方式與此相同。信道初始化數(shù)據(jù)送入VNU模塊進(jìn)行數(shù)據(jù)處理后，送入RAM模塊，數(shù)據(jù)經(jīng)過(guò)CNU模塊，最后再送入VNU模塊，這樣就完成一次迭代。數(shù)據(jù)信息從VNU到CNU與數(shù)據(jù)信息從CNU到VNU分別在不同的數(shù)據(jù)線(xiàn)上傳輸（圖1）。

    3.2 變量節(jié)點(diǎn)結(jié)構(gòu)（VNU）

變量節(jié)點(diǎn)的結(jié)構(gòu)如圖4所示。從中可以看出每個(gè)變量節(jié)點(diǎn)的度為3(j=3)，四個(gè)5bit輸入信息包含一個(gè)信道信息和三個(gè)與之相連的校驗(yàn)節(jié)點(diǎn)的信息。由log-BP算法可以看到α進(jìn)行的是量化值的計(jì)算，沒(méi)有牽扯到符號(hào)位，而ψm,n和λn的計(jì)算都有包含符號(hào)位的相加，實(shí)際上其中還包含了減法運(yùn)算，而本文采用的符號(hào)信息位的格式不能用于減法運(yùn)算，需要將其轉(zhuǎn)換的其他格式。在本文進(jìn)行和運(yùn)算時(shí)，首先將轉(zhuǎn)換為二進(jìn)制補(bǔ)碼形式，運(yùn)算結(jié)束后再轉(zhuǎn)換回符號(hào)量化位格式，查表（FX_LUT）進(jìn)行f(x)運(yùn)算。函數(shù)可由FPGA中的邏輯單元LUT來(lái)實(shí)現(xiàn)。Comb模塊把1bit的判決結(jié)果x、4bit的查找表運(yùn)算結(jié)果與符號(hào)位合在一起作為外部信息送入校驗(yàn)節(jié)點(diǎn)（CNU）。圖4上半部分為輸入譯碼的結(jié)果，下半部分為三個(gè)數(shù)據(jù)輸出通道中的一個(gè)，其余兩個(gè)的結(jié)構(gòu)與此完全相同，唯一不同的是加法器的輸入，根據(jù)log-BP算法，其中初始化數(shù)據(jù)經(jīng)過(guò)S-to-T轉(zhuǎn)換后的數(shù)據(jù)輸入固定，另外兩個(gè)輸入數(shù)據(jù)為其他兩個(gè)數(shù)據(jù)通道的輸入經(jīng)過(guò)S-to-T轉(zhuǎn)換后的數(shù)據(jù)。

圖4

    3.3 校驗(yàn)節(jié)點(diǎn)結(jié)構(gòu)（CNU）

校驗(yàn)節(jié)點(diǎn)（CNU）結(jié)構(gòu)如圖5所示，每個(gè)檢驗(yàn)節(jié)點(diǎn)的度數(shù)為6（k=5），圖5只畫(huà)出數(shù)據(jù)的一個(gè)輸出通道，其余5個(gè)輸出通道的結(jié)構(gòu)與此完全相同，加法器為檢驗(yàn)節(jié)點(diǎn)首先對(duì)外部信息中的判決結(jié)果進(jìn)行驗(yàn)證，看是否滿(mǎn)足H·x T=0，滿(mǎn)足則結(jié)束迭代。CNU模塊中f(x)的x計(jì)算是只計(jì)算量化值而不管正負(fù)的，而本譯碼器采用的符號(hào)量化位轉(zhuǎn)化為二進(jìn)制初碼形式。

圖5

    3．4 數(shù)據(jù)輸入與輸出

完全平行譯碼結(jié)構(gòu)可以分為三部分：迭代譯碼模塊、數(shù)據(jù)輸入模塊和數(shù)據(jù)輸出模塊。因?yàn)槭峭耆�平行譯碼方式，輸入數(shù)據(jù)經(jīng)過(guò)串并轉(zhuǎn)換后，同時(shí)讀入VNU進(jìn)行迭代計(jì)算。在數(shù)據(jù)輸出模塊，每一次迭代完成要進(jìn)行條件判別，如果CNU所有的校驗(yàn)結(jié)果都為零，則輸出數(shù)據(jù)�；蛘咭呀�(jīng)完成17次迭代，此時(shí)強(qiáng)制輸出數(shù)據(jù)。數(shù)據(jù)的輸入與輸出分別用不同的時(shí)鐘進(jìn)行控制。圖6為譯碼器其中一幀數(shù)據(jù)的測(cè)試結(jié)果，編碼之前的信息為01010101，圖6中OutData為編碼后數(shù)據(jù)的輸出。

4 FPGA實(shí)現(xiàn)

根據(jù)規(guī)則（3，6）LDPC的完全平行譯碼結(jié)構(gòu)，選擇在Xilinx Virtex2 XC2V1000-fg256上對(duì)其進(jìn)行物理實(shí)現(xiàn)，譯碼器采用Verilog硬件描述語(yǔ)言編寫(xiě)，用Xilinx的開(kāi)發(fā)工具ISE6.1在XC2V1000上對(duì)譯碼器進(jìn)行布局布線(xiàn)。通過(guò)時(shí)序分析可以看出，譯碼器的最大時(shí)鐘頻率為20MHz，以輸入時(shí)鐘為基準(zhǔn)，完成17次迭代最多需要20個(gè)時(shí)鐘，完成一幀數(shù)據(jù)的輸入需要20個(gè)時(shí)鐘，可以得出譯碼器的最大譯碼速率為：V=20×20/20=20Mbps。圖7為幀長(zhǎng)為20bit的LDPC碼的譯碼性能，因?yàn)榇a長(zhǎng)較短，性能沒(méi)有達(dá)到最好。這為更高速LDPC碼譯碼器的設(shè)計(jì)打下堅(jiān)實(shí)的基礎(chǔ)，碼長(zhǎng)為1024bit，傳輸速率可進(jìn)一步提高，甚至達(dá)到1Gbps，譯碼性能會(huì)更好。

    本文基于軟判譯碼規(guī)則，采用完全平行譯碼結(jié)構(gòu)，設(shè)計(jì)出幀長(zhǎng)為20bit，碼率為1/2的規(guī)則（3，6）LDPC碼的譯碼器，在Xilinx virtex2 XC2V1000-fg256上對(duì)其進(jìn)行物理實(shí)現(xiàn)，最大迭代次數(shù)為17次，傳輸速率達(dá)到20Mbps。DPC碼具有良好譯碼性能，與Turbo碼相比更易于硬件實(shí)現(xiàn)，并能得到更高的譯碼速度。下一步將設(shè)計(jì)出碼長(zhǎng)為1024bit或碼長(zhǎng)更長(zhǎng)的LDPC譯碼器，進(jìn)一步提高傳輸速率，降低誤碼率，為加速該技術(shù)在中國(guó)的商用奠定基礎(chǔ)。