??? 摘?要： 基于軟判決譯碼規(guī)則，采用完全并行的解碼結(jié)構(gòu)，使用Verilog硬件描述語(yǔ)言，在Xilinx公司的FPGA（Virtex-2 xcv1000）上實(shí)現(xiàn)了碼率為1/2、幀長(zhǎng)為20bit的規(guī)則（3,6）LDPC碼的譯碼器" title="譯碼器">譯碼器，最大" title="最大">最大傳輸速率" title="傳輸速率">傳輸速率可達(dá)20Mbps。對(duì)LDPC碼的實(shí)際應(yīng)用具有重要的推動(dòng)作用。
??? 關(guān)鍵詞： LDPC碼? 變量節(jié)點(diǎn)? 校驗(yàn)檢點(diǎn)? 因子圖? 譯碼
?
??? 在通信系統(tǒng)中糾錯(cuò)碼" title="糾錯(cuò)碼">糾錯(cuò)碼被用來(lái)提高信道傳輸?shù)目煽啃院凸β世寐?，低密度奇偶校?yàn)碼(LDPC碼)是目前最逼近香農(nóng)限的一類糾錯(cuò)碼。1962年，Gallager[1]首次提出了LDPC碼的古典模型,即規(guī)則（regular）的LDPC碼：(n,j,k)，校驗(yàn)矩陣H具有恒定的列重量和行重量。LDPC碼由于比Turbo碼更接近香農(nóng)限的誤碼率性能[2]和完全并行的迭代譯碼算法使其比Turbo碼在部分場(chǎng)合具有更廣泛的應(yīng)用前景，從而使LDPC碼成為當(dāng)前糾錯(cuò)編碼的一個(gè)研究熱點(diǎn)?；诹己玫淖g碼性能，LDPC碼被認(rèn)為是通信系統(tǒng)的下一代糾錯(cuò)碼。
1 規(guī)則LDPC碼
1.1 因子圖描述
??? 因子圖[2]有兩類頂點(diǎn)，分別為變量節(jié)點(diǎn)(variable nodes,用空的圓點(diǎn)表示)和校驗(yàn)節(jié)點(diǎn)(check nodes,用方框表示)。Tanner圖就是這兩類頂點(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)的約束，因此每個(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是一種線性碼，使得它的因子圖一邊為變量節(jié)點(diǎn)，一邊為校驗(yàn)節(jié)點(diǎn)，故LDPC碼的因子圖表示有專用的定義：二部圖（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）算法[1]，它與因子圖相對(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算法[1][4]，把大量的乘運(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}，關(guān)聯(lián)在變量節(jié)點(diǎn)n上的第m個(gè)校驗(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)n，變量節(jié)點(diǎn)n上關(guān)聯(lián)的除了第m個(gè)校驗(yàn)節(jié)點(diǎn)外的所有校驗(yàn)節(jié)點(diǎn)為M(n)m。
??? Log－BP算法的譯碼過(guò)程：
??? 輸入數(shù)據(jù)：初始概率
n=1, …, N;
??? 輸出數(shù)據(jù)" title="輸出數(shù)據(jù)">輸出數(shù)據(jù)：硬判決結(jié)果
??? 譯碼過(guò)程：
??? 初始化：對(duì)于接收到的每個(gè)變量節(jié)點(diǎn)n計(jì)算初始信道信息
并對(duì)每個(gè)點(diǎn)計(jì)算初始信息，其中（m,n）∈{(i,j)|Hi j=1}。
??? 
??? 迭代譯碼：
??? (1)校驗(yàn)節(jié)點(diǎn)計(jì)算
??? 
??? 
???? 對(duì)于每個(gè)變量節(jié)點(diǎn)n，在完成變量節(jié)點(diǎn)計(jì)算后，對(duì)
??? (3)判決條件
??? 
??? 
否則跳到第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算法的比較可以發(fā)現(xiàn)，log－BP算法中除了f(x)=log
剩下的都是加法運(yùn)算，從而避免了BP算法中乘運(yùn)算過(guò)多的弊病。在本文中函數(shù)f(x)利用FPGA中的查找表（Look-up Table, LUT）實(shí)現(xiàn)。
2 H矩陣的生成
??? Gallager提出的LDPC碼的H矩陣[1]必須滿足以下兩點(diǎn)：
??? (1)H矩陣的每一列有j個(gè)1，j>=3;
??? (2)H矩陣的每一行有k個(gè)1，k>j;
??? 本文中選擇j=3,k=6,通過(guò)編程用matalab軟件生成若干滿足條件的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)條件滿足或者是迭代完成時(shí)，讀入數(shù)據(jù)并把迭代結(jié)果輸出。
3.1 迭代譯碼結(jié)構(gòu)
??? 圖3表示平行迭代譯碼結(jié)構(gòu)[5][6]。其中只畫出兩個(gè)節(jié)點(diǎn)之間一條數(shù)據(jù)通路的連接方式，因?yàn)槭峭耆叫械g碼結(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ù)線上傳輸（圖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è)5 bit輸入信息包含一個(gè)信道信息和三個(gè)與之相連的校驗(yàn)節(jié)點(diǎn)的信息。由log-BP算法可以看到α進(jìn)行的是量化值的計(jì)算，沒有牽扯到符號(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)算。
可由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ù)。
?
?
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=6)，圖5只畫出數(shù)據(jù)的一個(gè)輸出通道，其余5個(gè)輸出通道的結(jié)構(gòu)與此完全相同，加法器為檢驗(yàn)節(jié)點(diǎn)首先對(duì)外部信息中的判決結(jié)果進(jìn)行驗(yàn)證，看是否滿足H·xT=0，滿足則結(jié)束迭代。CNU模塊中f(x)的x計(jì)算是只計(jì)算量化值而不管正負(fù)的，而本譯碼器采用的符號(hào)量化位格式只需將符號(hào)位屏蔽即可得到相當(dāng)于絕對(duì)值效果的量化位運(yùn)算，也就是CNU模塊中不需要將符號(hào)量化位轉(zhuǎn)化為二進(jìn)制補(bǔ)碼形式。
?
3.4? 數(shù)據(jù)輸入與輸出
??? 完全平行譯碼結(jié)構(gòu)可以分為三部分：迭代譯碼模塊、數(shù)據(jù)輸入模塊和數(shù)據(jù)輸出模塊。因?yàn)槭峭耆叫凶g碼方式，輸入數(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ǔ)言編寫，用Xilinx的開發(fā)工具ISE6.1在XC2V1000上對(duì)譯碼器進(jìn)行布局布線。硬件資源的占有率如表1所示。通過(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)較短，性能沒有達(dá)到最好。這為更高速 LDPC碼譯碼器的設(shè)計(jì)打下堅(jiān)實(shí)的基礎(chǔ)，碼長(zhǎng)為1024bit，傳輸速率可進(jìn)一步提高，甚至達(dá)到1Gbps,譯碼性能會(huì)更好[6][7]。
?
?
??? 本文基于軟判決譯碼規(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。LDPC碼具有良好譯碼性能，與Turbo碼相比更易于硬件實(shí)現(xiàn)，并能得到更高的譯碼速度。下一步將設(shè)計(jì)出碼長(zhǎng)為1024bit或碼長(zhǎng)更長(zhǎng)的LDPC譯碼器，進(jìn)一步提高傳輸速率，降低誤碼率，為加速該技術(shù)在中國(guó)的商用奠定基礎(chǔ)。
參考文獻(xiàn)
1 R.G. Gallager.Low density parity check codes.IRE Trans. Inform. Theory,1962； IT-8（Jan）：21～28
2 R. M. Tanner. A recursive approach to low complexity?codes.IEEE Trans. Inform. Theory，1981; IT-42:533～547
3 M. Chiani, A. Conti, and A. Ventura.Evaluation of lowdensity parity-check codes over block fading channels. in??2000 IEEE International Conference on Communications.?2000：1183～1187
4 S. Kim, G. E. Sobelman, J. Moon.Parallel VLSI Architectures for a Class of LDPC Codes. Circuits and Systems.IEEE International Symposium on, 2002;Volume:2
5 C. J. Howland and A. J. Blanksby.Parallel decoding architectures for lowdensity parity check codes. in Proc. IEEE?ISCAS,2001;4(5):742～745
6 A. J. Blanksby and C. J. Howland. A 690-mW 1-Gb/s?1024-b, rate-1/2 low-density parity-check code decoder.?IEEE Journal of Solid-State Circuits,2002;37(3)：404～412
7 T. Zhang and K.K. Parhi.VLSI implementation-oriented（3,k）egular low-density parity-check codes. IEEE Workshop on Signal Processing Systems (SiPS), 2001;9