譚敬龍，劉 穎

（北京交通大學 電子信息工程學院，北京 100044）

無線Mesh網(wǎng)絡是近年新興的、采用無中心節(jié)點技術的新型寬帶無線網(wǎng)絡，具有容量大、速率高、覆蓋廣等特點。

IEEE802.16d協(xié)議是國際標準組織IEEE802（Institute of Electrical and Electronics Engineers 802）為無線Mesh網(wǎng)絡制定的最新標準。IEEE802.16d協(xié)議中所規(guī)定的信道編譯碼包括：隨機化模塊、RS編碼模塊、卷積編碼模塊、交織模塊、解交織模塊、Viterbi譯碼模塊、RS譯碼模塊以及解隨機化模塊。其中，RS譯碼模塊和Viterbi譯碼模塊是整個信道編譯碼的重點，其性能將直接影響到信道編譯碼整體的檢錯與糾錯能力；隨機化模塊和交織模塊的性能將直接影響系統(tǒng)接收端的同步性能。因此，信道編譯碼是整個無線Mesh網(wǎng)絡的基礎。

FPGA（Field Programmable Gate Array）即現(xiàn)場可編程門陣列，屬于可編程邏輯器件的一種。經(jīng)過近20年的發(fā)展，目前已成為實現(xiàn)數(shù)字通信系統(tǒng)的主流平臺之一。

1 基于IEEE802.16d標準的信道編譯碼原理

IEEE802.16d協(xié)議規(guī)定的信道編譯碼的8個模塊中，前4個模塊構(gòu)成編碼部分，后4個模塊構(gòu)成譯碼部分。本文對各個模塊的原理分別進行說明。

1.1 隨機化與解隨機化原理

隨機化也稱為擾碼，作用是避免發(fā)送端出現(xiàn)長時間的連0或連1而影響接收端的時鐘同步?；舅枷胧抢冒l(fā)送端和接收端已存儲的特定序列進行隨機化操作，使得經(jīng)過隨機化操作之后的數(shù)據(jù)出現(xiàn)連0以及連1的概率更小。解隨機化操作即在接收端進行與隨機化操作相反的過程以提取原始數(shù)據(jù)。

1.2 RS編碼原理

RS編碼是一種典型的線性塊編碼，表示形式為RS(N,K)，碼元通常是多進制，非常適合于突發(fā)錯誤的糾錯，最大可糾錯1/2(N－K)個錯誤。

通用的RS編碼的運算步驟：

（1）計算相應Galois域內(nèi)的RS編碼生成多項式；

（2）將長度為K個碼元的信息塊以輸入多項式M(x)的形式表示，輸入多項式權(quán)重的高低對應碼元輸入順序的先后；

（3）將輸入多項式寫成xn-kM(x) 形式；

（4）在Galois域內(nèi)計算xn-kM(x) mod(g(x))，結(jié)果，即為RS編碼的校驗多項式；

（5）將校驗多項式轉(zhuǎn)換為碼元形式，與輸入碼元組成長度為N個碼元的編碼塊。

1.3 卷積編碼算法原理

圖1是一個常見的（2, 1, 3）二進制卷積編碼器。每一單位時間內(nèi)，輸入碼元ui進入累加器和延遲器中；同時，在上方的累加器中ui與前2個單位時間內(nèi)輸入的碼元ui-1和ui-2做模二加運算生成校驗元c1i，在下方的累加器中ui與ui-2做模二加運算生定校驗元c2i，c1i和c2i即為輸出碼字。由此可知此卷積編碼器的編碼規(guī)則為：c1i=111,c1i=ui+ui-1+ui-2，c2i=ui+ui-2。

圖1 （2,1,3）卷積編碼器

1.4 交織與解交織算法原理

交織的基本原理為：將待交織的碼元數(shù)據(jù)接收后進行存儲并對其進行重新排列。具體實現(xiàn)方式為：將接收的碼元序列逐列填充到一個M行N列的矩陣中，當矩陣完全填滿后將碼元數(shù)據(jù)逐行輸出。

在接收端，解交織的操作與交織操作相反，即利用接收到的碼元數(shù)據(jù)逐行填滿相同矩陣后將碼元數(shù)據(jù)逐列輸出。

1.5 Viterbi譯碼原理

Viterbi譯碼是基于網(wǎng)格圖的回溯譯碼。其基本思想為：將網(wǎng)格圖的所有可能路徑與接收序列進行對比，選取與接收序列距離最小的序列作為其譯碼序列。

1.6 RS譯碼原理

將RS編碼端輸出碼元、端接收的碼元分別記為S(x)、R(x)，錯誤碼元E(x)表示為：

將αj(j=1, 2, ……, 2t；t=1/2(N－K))代入多項式E(x)再進行計算，若Ej=0說明數(shù)據(jù)在信道傳輸過程中未發(fā)生錯誤；若Ej≠0說明接收數(shù)據(jù)存在錯誤。

當有錯誤時，設錯誤位置多項式σ(x)為：

設其中第i位為錯誤位置，根據(jù)公式（2），有：σ(Xi-1)=0。

將x=Xi-1代入公式（2），有：

因此求解錯誤位置就是求解錯誤位置多項式σ(x)的根。

做乘積S(x)σ(x)，用w(x)=1+w1(x)+w2(x)+……表示，得到方程：

公式（4）中的w(x)為錯誤位置多項式。由w(x)得到錯誤位置，進而得出錯誤碼字E(x)，最終根據(jù)R(x)－E(x)=C(x)求出正確碼字，完成譯碼糾錯過程。

2 各模塊在FPGA的實現(xiàn)

2.1 隨機化和解隨機化的FPGA實現(xiàn)

隨機化和解隨機化操作，就是利用一個偽隨機二進制數(shù)據(jù)生成器，對所有的輸入數(shù)據(jù)進行異或操作并在接收端進行反向操作。

FPGA實現(xiàn)的生成器如圖2所示，由15個移位寄存器和2個異或門組成。當數(shù)據(jù)輸入時，移位寄存器中的第15位和第14位中的數(shù)據(jù)先進行異或后和輸入數(shù)據(jù)再進行異或；同時寄存器中的所有數(shù)據(jù)右移一位，并將剛才第15位和第14位的異或結(jié)果存入第1位。

圖2 FPGA實現(xiàn)的生成器

2.2 RS編碼的FPGA實現(xiàn)

按照IEEE802.16d協(xié)議規(guī)定，本文選用RS(32,24)碼。其生成多項式為：

RS(32,24)碼的硬件實現(xiàn)如圖3所示。

為節(jié)省硬件資源，利用伽羅華域內(nèi)加法運算來代替乘法運算。以圖3中最右側(cè)乘法器為例，已知其乘數(shù)之一為g7，假設另外一個乘數(shù)為：

c=c7x7+c6x6+c5x5+c4x4+c3x3+c2x2+c1x1+c0（6）

則有：

假設該乘法器的輸出分別為：b7,b6,L,b0，則有：

以上8個式子可代替g7與任意輸入多項式做乘法運算。分別計算出gi(i=0, 1,……,7)的替代式，可減少圖3中乘法器的運算量，進而減少FPGA資源的占用。

2.3 卷積編碼的FPGA實現(xiàn)

本文在FPGA實現(xiàn)的卷積編碼器如圖4所示，由6個移位寄存器及2個模二加法器組成，卷積編碼碼率為1/2，約束長度為7，生成多項式為：G1=171OCT，G2=133OCT。

圖4 FPGA實現(xiàn)的卷積編碼器

IEEE802.16d協(xié)議還要求對編碼后序列進行碼率變換操作，即將編碼后的序列每隔一個編碼周期丟棄一位X路的輸出使輸出呈現(xiàn)X1Y1Y2的形式，以達到提高信道利用率的目的。

2.4 交織與解交織的FPGA實現(xiàn)

一次交織或解交織操作處理的均為384個數(shù)據(jù)，交織器與解交織器使用的矩陣均為32行12列。在交織器中，當數(shù)據(jù)輸入時將數(shù)據(jù)逐列進行存儲，存滿384后再逐行輸出；在解交織器中數(shù)據(jù)是逐行進行存儲、逐列輸出的。

在FPGA實現(xiàn)中，為節(jié)省處理時間，在交織器和解交織器中各用2塊RAM，采用“乒乓”操作來提高效率，并做到連續(xù)處理接收數(shù)據(jù)。

2.5 Viterbi譯碼的FPGA實現(xiàn)

常用的Viterbi譯碼器結(jié)構(gòu)框圖如圖5所示。

圖5 Viterbi譯碼模塊結(jié)構(gòu)框圖

本文在FPGA實現(xiàn)分支度量計算模塊時，為節(jié)省FPGA資源使用曼哈頓距離來表示分支度量，為降低系統(tǒng)的復雜性采用3 bit軟判決，分別計算出各輸入數(shù)據(jù)的期望碼字與實際接收到的碼字之間的分支度量值存在寄存器中，待需要相應的度量值時直接調(diào)用。

在FPGA實現(xiàn)Viterbi譯碼過程中，為防止加比選模塊因迭代累加操作出現(xiàn)數(shù)據(jù)溢出錯誤，必須在溢出之前對其進行取模歸一化操作。歸一化的加比選模塊的電路圖如圖6所示。

圖6 歸一化的加比選模塊的電路圖

假設B=(k－1)δmax，其中k為卷積編碼約束長度，δmax為路徑積累的最大值。則任意2個路徑積累值PMa與PMb的運算關系如公式（8）。

由公式（8）的計算結(jié)果可對路徑距離的大小進行判別。

Viterbi譯碼算法的幸存路徑管理分為3步：寫入數(shù)據(jù)操作、回溯讀操作以及譯碼讀操作。在FPGA實現(xiàn)時，為提高譯碼器的工作速度，使用4塊RAM構(gòu)成一個流水線結(jié)構(gòu)以實現(xiàn)回溯算法的幸存路徑管理的3個操作。每一時刻，4塊RAM將輪流執(zhí)行新數(shù)據(jù)寫入、回溯讀、譯碼等3個過程。

對于本文使用的(2,1,7)卷積碼，其分支度量的最大值δmax為14、累積值上界為168。所以，在FPGA實現(xiàn)時需要用8 bit來表示每個狀態(tài)的路徑累積值，共使用64個8 bit寄存器進行存儲。另外，在FPGA實現(xiàn)過程中由于每個狀態(tài)輸入的不同可能性，RAM的存儲空間應為狀態(tài)總數(shù)的2倍，但由于2個相鄰狀態(tài)的期望碼字具有相關性，可以相互推出，所以只要存儲一半數(shù)據(jù)即可。因此，本文在FPGA實現(xiàn)中使用總長度為64 bit的RAM來存儲其中偶狀態(tài)的各期望碼字，每一狀態(tài)使用2 bit，分別對應輸入為0及輸入為1。

2.6 RS譯碼的FPGA實現(xiàn)

通用的RS譯碼模塊結(jié)構(gòu)如圖7所示。其中，SC模塊為伴隨式計算模塊，KES模塊為關鍵方程求解模塊，ESEE模塊為錯誤值以及錯誤位置計算模塊。

圖7 RS譯碼模塊結(jié)構(gòu)圖

在FPGA硬件電路的實現(xiàn)時，SC模塊可以由帶控制的反饋寄存器來實現(xiàn)，如圖8所示。

圖8 SC模塊

關鍵方程求解模塊的FPGA實現(xiàn)可由以下3個圖示的硬件電路進行實現(xiàn)。

圖9所示為RS譯碼模塊中的控制單元。主要用以計算輔助參數(shù)并產(chǎn)生迭代運算中需要用到的控制信號，計數(shù)器對關鍵方程求解的2t步迭代進行計數(shù)，利用L的MSB可以判斷參數(shù)是否大于或等于0，SEL信號連接到參數(shù)γ的使能端，使得只有SEL=1時寄存器中的數(shù)據(jù)才會被置換。圖10、圖11分別為偏差計算模塊、錯誤位置多項式更新模塊。錯誤位置及錯誤值計算模塊如圖12所示，在本文中將搜索模塊與錯誤值計算模塊合并為一個模塊以達到節(jié)約FPGA資源的目的。

圖9 控制單元

圖10 偏差計算模塊

圖11 錯誤位置更新模塊實現(xiàn)電路圖

圖12 錯誤位置及錯誤值計算模塊電路圖

3 仿真及測試驗證

本文以QuartusⅡ軟件為平臺，依據(jù)FPGA算法，利用Verilog語言編寫了各模塊，在各模塊經(jīng)過驗證的基礎上，合成信道編譯碼的整體工程，實現(xiàn)了IEEE802.16d協(xié)議要求的信道編譯碼功能并通過Modelsim進行布線后仿真。信道編譯碼的仿真波形圖如圖13、圖14所示。

圖13 發(fā)送端仿真圖

圖14 接收端仿真圖

圖13 為發(fā)送端的仿真圖，按IEEE802.16d協(xié)議要求，發(fā)送端開始時發(fā)送長度為192 bit的隨機數(shù)據(jù)，經(jīng)過隨機化、RS編碼、卷積編碼和交織后，數(shù)據(jù)變換為長度為384 bit的編碼數(shù)據(jù)，此數(shù)據(jù)將進行信道傳輸。

圖14為接收端的仿真圖，將從信道接收的長度為384 bit數(shù)據(jù)進行解交織、Viterbi譯碼、RS譯碼和解隨機化后變換為長度為192 bit數(shù)據(jù)。接收端得到的譯碼后的數(shù)據(jù)應與發(fā)送端的起始數(shù)據(jù)一致，經(jīng)過數(shù)據(jù)對比后可知此192 bit數(shù)據(jù)即為發(fā)送端起始的192 bit數(shù)據(jù)。圖14中譯碼的時間要長于圖14中編碼的時間主要是因為RS譯碼耗時較長。

進一步對此信道編碼工程進行Matlab下的仿真，得到的誤碼率與信噪比的關系如圖15所示。

圖15 誤碼率與信噪比關系圖

在圖15中，藍色的ber1表示FPGA實現(xiàn)的信道編譯碼工程的誤碼率曲線，紅色的ber2表示Matlab仿真的信道編譯碼的誤碼率曲線。從圖中可以看到，實現(xiàn)的信道編譯碼工程的性能十分貼近理論性能，具有很高的糾錯性能。

4 結(jié)束語

基于IEEE802.16d協(xié)議，簡要介紹了信道編譯碼中各個功能模塊的原理，詳細說明了各模塊在FPGA實現(xiàn)中的算法和電路實現(xiàn)框圖原理，最終將IEEE802.16d協(xié)議要求的信道編譯碼在FPGA平臺上進行了實現(xiàn)，并通過Modelsim軟件進行了仿真驗證，證明此算法具有良好的可行性，具有一定的借鑒意義。

[1]普羅科斯. 數(shù)字通信[M].北京：電子工業(yè)出版社，2003：272-294.

[2]郭建花. 無線信道中聯(lián)合信源信道編碼的研究[D]. 大連：大連理工大學, 2009.

[3]I.S.Reed, G.Solomon. Polynomial Codes Over Ceertain Finite Fields[J]. Soc. Ind. Appl. Math., vol.8, 1960: 300-304.

[4]Chang-Seok Choi ,Hanho Lee. High Throughput Four-Parallel RS Decoder Architecture for 60GHz mmWAVE WPAN Systems[C]. Consumer Electronics (ICCE), 2010.

[5]萬力銘. RS譯碼器的研究與實現(xiàn)[D]. 長春：長春理工大學, 2008.

[6]劉文國. 基于FPGA的RS(255,223)編解碼器的高速并行實現(xiàn)[D]. 成都：電子科技大學，2009.

[7]劉 虎. 基于FPGA的Viterbi譯碼器的設計與實現(xiàn)[D].成都：電子科技大學，2009.

[8]鄭宇馳, 周曉方, 閔 昊. OFDM系統(tǒng)中Viterbi譯碼器的設計及FPGA驗證[J]. 復旦學報，2005，44（6）.

[9]王 琳 ,徐位凱. 高效信道編譯碼技術及其應用[M].北京：人民郵電出版社，2007：38-48.

[10]周 訓. 基于BM算法的RS譯碼器IP核設計[D]. 北京：電子科技大學，2009.

[11]I.S.Reed, M.T. Shih. VLSI design of inverse-free Berlekamp-Massey algorithm[C]. IEEE Proceedings-Computers and Digital Techniques, 1991.

[12]張學臻. 基于IEEE802.16d標準信道編譯碼技術的研究及FPGA實現(xiàn)[D]. 北京：北京交通大學，2011.

[13]丁忠義,袁國材. RS 編譯碼的FPGA實現(xiàn)[J]. 艦船電子工程，2008（11）.

[14]張普珩. Viterbi譯碼算法的研究與實現(xiàn)[D]. 長沙：國防科學技術大學，2008.