??? 摘?要： 基于軟判決譯碼規(guī)則，采用完全并行的解碼結構，使用Verilog硬件描述語言，在Xilinx公司的FPGA（Virtex-2 xcv1000）上實現(xiàn)了碼率為1/2、幀長為20bit的規(guī)則（3,6）LDPC碼的譯碼器" title="譯碼器">譯碼器，最大" title="最大">最大傳輸速率" title="傳輸速率">傳輸速率可達20Mbps。對LDPC碼的實際應用具有重要的推動作用。
??? 關鍵詞： LDPC碼? 變量節(jié)點? 校驗檢點? 因子圖? 譯碼
?
??? 在通信系統(tǒng)中糾錯碼" title="糾錯碼">糾錯碼被用來提高信道傳輸?shù)目煽啃院凸β世寐剩兔芏绕媾夹ｒ灤a(LDPC碼)是目前最逼近香農限的一類糾錯碼。1962年，Gallager[1]首次提出了LDPC碼的古典模型,即規(guī)則（regular）的LDPC碼：(n,j,k)，校驗矩陣H具有恒定的列重量和行重量。LDPC碼由于比Turbo碼更接近香農限的誤碼率性能[2]和完全并行的迭代譯碼算法使其比Turbo碼在部分場合具有更廣泛的應用前景，從而使LDPC碼成為當前糾錯編碼的一個研究熱點?；诹己玫淖g碼性能，LDPC碼被認為是通信系統(tǒng)的下一代糾錯碼。
1 規(guī)則LDPC碼
1.1 因子圖描述
??? 因子圖[2]有兩類頂點，分別為變量節(jié)點(variable nodes,用空的圓點表示)和校驗節(jié)點(check nodes,用方框表示)。Tanner圖就是這兩類頂點之間的二部圖，即每條邊的一端與變量節(jié)點相連，另一端與校驗節(jié)點相連。變量節(jié)點代表實際的變量，校驗節(jié)點代表這些變量節(jié)點之間的約束。對于（j，k）-LDPC碼的每個變量（bit）都受j個校驗(check)的約束，因此每個變量節(jié)點應該連接j個校驗節(jié)點。每個校驗方程有k個變量，因此每個校驗節(jié)點應與k個變量節(jié)點相連。由于LDPC是一種線性碼，使得它的因子圖一邊為變量節(jié)點，一邊為校驗節(jié)點，故LDPC碼的因子圖表示有專用的定義：二部圖（bipartite graphs）。
??? 圖1表示了校驗矩陣為H的規(guī)則（3，6）LDPC碼的因子圖，它是由10個變量定點和5個校驗定點組成的二部圖，邊剛好對應于矩陣中1的位置，這種因子圖是LDPC迭代譯碼算法的基礎。
?
1.2 LDPC碼的譯碼算法
??? LDPC碼的譯碼采用信度傳播（belief-propagation或BP）算法[1]，它與因子圖相對應，如圖1所示，利用BP算法獲得好的譯碼性能，LDPC碼的因子圖中環(huán)的長度必須盡可能地長，長度為4的環(huán)會降低BP算法的性能，H矩陣設計時應避免出現(xiàn)。如果直接使用BP算法，由于在迭代過程中存在大量的乘運算，將使硬件的復雜度大幅度上升，本論文采用改進的Log-BP算法[1][4]，把大量的乘運算轉換成加運算，從而降低硬件復雜度及生產成本。
??? 首先定義可能用到的幾個變量及符號的意義：H表示一個M×N的LDPC校驗矩陣，Hi,j表示矩陣H中第i行第j列的元素。定義校驗節(jié)點m上的第n個變量節(jié)點為N（m）＝{n:Hm,n=1}，關聯(lián)在變量節(jié)點n上的第m個校驗節(jié)點為M(n)={m:Hmn=1}。定義校驗節(jié)點m上關聯(lián)的除了第n個變量節(jié)點以外的所有變量節(jié)點為N(M)n，變量節(jié)點n上關聯(lián)的除了第m個校驗節(jié)點外的所有校驗節(jié)點為M(n)m。
??? Log－BP算法的譯碼過程：
??? 輸入數(shù)據(jù)：初始概率
n=1, …, N;
??? 輸出數(shù)據(jù)" title="輸出數(shù)據(jù)">輸出數(shù)據(jù)：硬判決結果
??? 譯碼過程：
??? 初始化：對于接收到的每個變量節(jié)點n計算初始信道信息
并對每個點計算初始信息，其中（m,n）∈{(i,j)|Hi j=1}。
??? 
??? 迭代譯碼：
??? (1)校驗節(jié)點計算
??? 
??? 
???? 對于每個變量節(jié)點n，在完成變量節(jié)點計算后，對
??? (3)判決條件
??? 
??? 
否則跳到第2步迭代譯碼部分，直至校驗成功或者達到最大迭代次數(shù)。
??? 上面算法中的αm,n和βm,n都被稱為外部信息，其中αm,n是從變量節(jié)點向校驗節(jié)點傳遞的信息，βm,n是從變量節(jié)點向校驗節(jié)點傳遞的信息。通過log－BP算法和BP算法的比較可以發(fā)現(xiàn)，log－BP算法中除了f(x)=log
剩下的都是加法運算，從而避免了BP算法中乘運算過多的弊病。在本文中函數(shù)f(x)利用FPGA中的查找表（Look-up Table, LUT）實現(xiàn)。
2 H矩陣的生成
??? Gallager提出的LDPC碼的H矩陣[1]必須滿足以下兩點：
??? (1)H矩陣的每一列有j個1，j>=3;
??? (2)H矩陣的每一行有k個1，k>j;
??? 本文中選擇j=3,k=6,通過編程用matalab軟件生成若干滿足條件的H矩陣，選擇其中一個性能最好的H矩陣進行LDPC碼的fpga譯碼實現(xiàn)。當n=20時，最終選擇H矩陣如圖2所示。
?
?
3 LDPC碼完全平行譯碼結構
??? 由二部圖可以直觀地看出，變量節(jié)點計算需要的信息只需由校驗節(jié)點來提供，校驗節(jié)點計算需要的信息只需要由變量節(jié)點來提供，譯碼器在設計時可以給每個變量節(jié)點分配一個變量節(jié)點處理單元（Variable Node processing Unit，VNU），給每個校驗節(jié)點分配一個校驗節(jié)點處理單元（Check Node processing Unit，CNU），從而實現(xiàn)譯碼器的完全并行結構。
??? 譯碼器的核心模塊是迭代譯碼部分，迭代譯碼的結構與算法是緊密相連的，譯碼結構的確定必須在仔細分析算法的基礎上，迭代譯碼的過程是CNU和VNU模塊計算結果的相互傳遞和更新。如果直接將CNU和VNU連接，不但不容易控制迭代的過程并且可能出現(xiàn)不穩(wěn)定狀態(tài)，所以需要在CNU和VNU之間安插RAM以起到數(shù)據(jù)的緩沖和控制作用。輸入、輸出模塊分別控制數(shù)據(jù)的輸入和輸出，當條件滿足或者是迭代完成時，讀入數(shù)據(jù)并把迭代結果輸出。
3.1 迭代譯碼結構
??? 圖3表示平行迭代譯碼結構[5][6]。其中只畫出兩個節(jié)點之間一條數(shù)據(jù)通路的連接方式，因為是完全平行迭代譯碼結構，其他節(jié)點之間數(shù)據(jù)通路的連接方式與此相同。信道初始化數(shù)據(jù)送入VNU模塊進行數(shù)據(jù)處理后，送入RAM模塊，數(shù)據(jù)經過CNU模塊，最后再送入VNU模塊，這樣就完成一次迭代。數(shù)據(jù)信息從VNU到CNU與數(shù)據(jù)信息從CNU到VNU分別在不同的數(shù)據(jù)線上傳輸（圖1）。
?
3.2 變量節(jié)點結構（VNU）
??? 變量節(jié)點的結構如圖4所示。從中可以看出每個變量節(jié)點的度為3（j=3），四個5 bit輸入信息包含一個信道信息和三個與之相連的校驗節(jié)點的信息。由log-BP算法可以看到α進行的是量化值的計算，沒有牽扯到符號位，而γm,n和λn的計算都有包含符號位的相加，實際上其中還包含了減法運算，而本文采用的符號信息位的格式不能用于減法運算，需要將其轉換為其他格式。在本文進行和運算時，首先將其轉換為二進制補碼形式，運算結束后再轉換回符號量化位格式，查表(FX_LUT)進行f(x)運算。
可由FPGA中的邏輯單元LUT來實現(xiàn)。Comb模塊把1bit的判決結果x、4bit的查找表運算結果與符號位合在一起作為外部信息送入校驗節(jié)點(CNU)。圖4上半部分為輸出譯碼的結果，下半部分為三個數(shù)據(jù)輸出通道中的一個，其余兩個的結構與此完全相同，唯一不同的是加法器的輸入， 根據(jù)log-BP算法，其中初始化數(shù)據(jù)經過S-to-T轉換后的數(shù)據(jù)輸入固定，另外兩個輸入數(shù)據(jù)為其他兩個數(shù)據(jù)通道的輸入經過S-to-T轉換后的數(shù)據(jù)。
?
?
3.3 校驗節(jié)點結構（CNU）
??? 校驗節(jié)點(CNU)結構如圖5所示，每個檢驗節(jié)點的度數(shù)為6(k=6)，圖5只畫出數(shù)據(jù)的一個輸出通道，其余5個輸出通道的結構與此完全相同，加法器為檢驗節(jié)點首先對外部信息中的判決結果進行驗證，看是否滿足H·xT=0，滿足則結束迭代。CNU模塊中f(x)的x計算是只計算量化值而不管正負的，而本譯碼器采用的符號量化位格式只需將符號位屏蔽即可得到相當于絕對值效果的量化位運算，也就是CNU模塊中不需要將符號量化位轉化為二進制補碼形式。
?
3.4? 數(shù)據(jù)輸入與輸出
??? 完全平行譯碼結構可以分為三部分：迭代譯碼模塊、數(shù)據(jù)輸入模塊和數(shù)據(jù)輸出模塊。因為是完全平行譯碼方式，輸入數(shù)據(jù)經過串并轉換后，同時讀入VNU進行迭代計算。在數(shù)據(jù)輸出模塊，每一次迭代完成要進行條件判別，如果CNU所有的校驗結果都為零，則輸出數(shù)據(jù)?；蛘咭呀浲瓿?7次迭代，此時強制輸出數(shù)據(jù)。數(shù)據(jù)的輸入與輸出分別用不同的時鐘進行控制。圖6為譯碼器其中一幀數(shù)據(jù)的測試結果，編碼之前的信息為01010101，圖6中OutData為編碼后數(shù)據(jù)的輸出。
?
4? FPGA實現(xiàn)
??? 根據(jù)規(guī)則（3，6）LDPC碼的完全平行譯碼結構，選擇在Xilinx Virtex2 XC2V1000-fg256上對其進行物理實現(xiàn)，譯碼器采用Verilog硬件描述語言編寫，用Xilinx的開發(fā)工具ISE6.1在XC2V1000上對譯碼器進行布局布線。硬件資源的占有率如表1所示。通過時序分析可以看出，譯碼器的最大時鐘頻率為20MHz,以輸入時鐘為基準，完成17次迭代最多需要20個時鐘，完成一幀數(shù)據(jù)的輸入需要20個時鐘，可以得出譯碼器的最大譯碼速率為：V=20×20/20=20Mbps。圖7為幀長為20bit的LDPC碼的譯碼性能，因為碼長較短，性能沒有達到最好。這為更高速 LDPC碼譯碼器的設計打下堅實的基礎，碼長為1024bit，傳輸速率可進一步提高，甚至達到1Gbps,譯碼性能會更好[6][7]。
?
?
??? 本文基于軟判決譯碼規(guī)則，采用完全平行譯碼結構，設計出幀長為20bit，碼率為1/2的規(guī)則（3，6）LDPC碼的譯碼器，在Xilinx virtex2 XC2V1000-fg256上對其進行物理實現(xiàn)，最大迭代次數(shù)為17次，傳輸速率達到20Mbps。LDPC碼具有良好譯碼性能，與Turbo碼相比更易于硬件實現(xiàn)，并能得到更高的譯碼速度。下一步將設計出碼長為1024bit或碼長更長的LDPC譯碼器，進一步提高傳輸速率，降低誤碼率，為加速該技術在中國的商用奠定基礎。
參考文獻
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