摘 要：Reed-Solomon(RS)碼是IEEE 802.16d標準中信道編碼的重要組成部分。通過對標準中RS碼特點的分析，對傳統(tǒng)的RS譯碼器進行改進，提出了一種適用于該標準的RS譯碼方法。利用循環(huán)碼的性質(zhì)，改進伴隨式計算模塊，減少延遲時間；利用RS碼中已知刪除位置的特點，簡化刪除位置多項式計算電路；通過對RS碼實際應用環(huán)境的分析，減少利用迭代方法解關(guān)鍵方程時所需的基本單元數(shù)目。最終利用Verilog語言實現(xiàn)硬件電路，在FPGA上驗證通過并應用于WiMAX 802.16d系統(tǒng)。

關(guān)鍵詞：RS碼;IEEE 802.16d;信道編碼;FPGA

中圖分類號：TN911文獻標識碼：B

文章編號：1004-373X(2008)07-059-03

Design and Implementation of RS Decoder in IEEE 802.16d

GAO Qingfeng

(Embedded System Key Lab，Beijing University of Technology，Beijing，100022，China)

Abstract：Reed-Solomon code is an important part of the channel coding in IEEE 802.16d.An improved version of RS decoder is proposed based on the code characteristic in the standard.Reducing the latency of syndrome computation block by the cyclic property of RS code，simplifing the modified syndrome computation as all the erasure positions are known，reducing the number of basic cells in the key-equation solving block by analysis of the application environment.The design is also implemented with Verilog HDL，verified in FPGA and applied in WiMAX 802.16d system.

Keywords：RS;IEEE 802.16d;channel coding;FPGA

IEEE 802.16d^[1] 是固定寬帶無線接入接口的標準協(xié)議。Reed-Solomon 編碼是其中信道編碼的一部分，主要用于糾正信道中的突發(fā)錯誤。為了能夠適應不同的信道條件，協(xié)議中使用了截短和刪除的RS碼，以提供不同的碼率和糾錯能力。本文在傳統(tǒng)的RS譯碼的基礎(chǔ)上，提出了一種適用于IEEE 802.16d 標準的RS譯碼實現(xiàn)方式。

1 RS譯碼的原理

802.16d 中所有的RS碼都是由定義在GF(28)上的RS(N=255，K=239，T=8)碼得到的。

其中，N為編碼后碼字的字節(jié)長度，K為編碼前輸入信息的字節(jié)長度，T為能夠糾錯的最大字節(jié)數(shù)。

域本原多項式為:



p(x)=x8+x4+x3+x2+1



碼生成多項式為:



g(x)=(x+λ0)(x+λ1)(x+λ2)…(x+λ2T-1)，λ=02HEX



如果輸入的信息為m(x)，利用循環(huán)碼的編碼公式，可以得到碼字c(x)。



c(x)=m(x)xN-K+[x2Tm(x)]mod g(x)



得到的碼字經(jīng)過截短信息位和刪除校驗位后得到需要的RS碼。802.16d協(xié)議中支持的RS碼有RS(32，24，4)，RS(40，36，2)，RS(64，48，8)，RS(80，72，4)，RS(108，96，6)，RS(120，108，6)。

由于RS碼經(jīng)過了截短和刪除，所以不能適用普通的RS譯碼算法，而必須使用能夠糾錯糾刪的譯碼算法。RS譯碼的算法很多，有時域譯碼和頻域譯碼之分。本文采用基于修正的歐幾里德算法(MEA)的時域譯碼算法。

糾錯糾刪的RS譯碼算法通常分為以下幾步^[2]：

(1) 根據(jù)接收碼字R(x)計算出伴隨式S(x)；

(2) 根據(jù)刪除位置計算刪除位置多項式Λ(x)；

(3) 由伴隨式S(x)和刪除位置多項式Λ(x)計算出修正的伴隨多項式T(x)；

(4) 由Λ(x)和T(x)，通過MEA算法解關(guān)鍵方程，得到錯誤位置多項式σ(x)和錯誤值多項式ω(x)；

(5) 利用錢搜索(Chien search)計算出σ(x)的根，從而得出錯誤位置；

(6) 根據(jù)ω(x)和Λ(x)計算出錯誤/刪除位置多項式Ψ(x)，再利用Forney公式計算出錯誤值和刪除值，并與原來的碼字相加，得到正確的碼字。

2 RS譯碼器的硬件結(jié)構(gòu)

RS譯碼器使用四級流水線結(jié)構(gòu)，以提高系統(tǒng)的吞吐率，滿足實時性傳輸?shù)囊?。?/p>

RS譯碼器的硬件框圖如圖1所示。

圖1 RS譯碼器的硬件框圖

2.1 伴隨式計算

根據(jù)接收到的碼字R(x)，可以計算出伴隨多項式S(x)：



S(x)=∑2T-1k=0Skxk，Sk=R(x)|x=αk，α=02HEX



在計算之前需要先將截短的信息位位置和刪除的校驗位位置填充零，得到完整的RS(255，239)碼字，然后再去計算伴隨式。根據(jù)IEEE 802.16d的協(xié)議，輸入信息經(jīng)過編碼后，先發(fā)送校驗位信息，再發(fā)送信息位。所以接收端收到的碼字經(jīng)過填充后如圖2所示：

圖2 RS(n，k，t)碼字經(jīng)過補全后得到的

完整RS(255，239，8)碼字

對于普通的RS譯碼器，要求信息位在接收碼字R(x)的高次項，校驗位在低次項。但經(jīng)過觀察可知，圖2所示的排列順序可以看作正常順序的碼字經(jīng)過循環(huán)移位得到。因為RS碼是一種循環(huán)碼，根據(jù)循環(huán)碼的性質(zhì)，碼字經(jīng)過任意的循環(huán)移位后仍是對應碼的一個碼字。所以，可以把接收到的碼字按照原始順序輸入譯碼器，不需要將其轉(zhuǎn)換為正常順序。

伴隨式的計算可以通過脈動陣列實現(xiàn)^[3]。將補零后得到的完全的RS(255，239)碼字順序輸入脈動陣列，在全部輸入完成后寄存器中就是所要的伴隨多項式的系數(shù)。

在802.16d協(xié)議中，RS碼的碼長都比較短。對于RS(n，k)碼，會有255-n個時鐘周期電路的輸入為零，使伴隨式計算模塊的延時很大。文獻[4]提出了一種使硬件電路的延時只依賴于實際碼長n的方法。但是該方法需要對接收碼字的校驗位和信息位互換，需要額外的緩沖區(qū)，并且互換本身就增加了延時，使譯碼器和前面電路的接口變得復雜。我們注意到，對于每一個基本單元，在其輸入為零的情況下，經(jīng)過255-n個時鐘周期，寄存器的值連續(xù)和系數(shù)相乘255-n次。所以，在校驗位輸入完畢后，對于第一個信息位，將系數(shù)換成原系數(shù)的255-n次方即可。經(jīng)修改后的硬件結(jié)構(gòu)如圖 3所示，事先計算出每個系數(shù)的255-n次方值，和原系數(shù)作為選擇器的輸入端，在信息位的第一個字節(jié)時切換系數(shù)，在其他位置使用原系數(shù)。經(jīng)修改后使電路消除了空轉(zhuǎn)周期，可以允許碼字連續(xù)輸入，減少了255-n個時鐘延時。

圖3 修改后的伴隨多項式計算電路

2.2 刪除位置多項式計算

通常，刪除的位置由解調(diào)器給出，根據(jù)刪除位置，可以得到刪除位置多項式:



Λ(x)=∏α-i∈Λ(x-α-i)



其中i為刪除位置。

可以用多項式展開電路來計算此多項式，具體電路結(jié)構(gòu)參見文獻[2]。對于802.16d系統(tǒng)，所有RS碼的刪除位置都是確定的，所以每種模式下的刪除位置多項式可以通過事先計算確定，存于ROM中，在需要時讀入即可。在按照前述的碼字排列順序下，各種模式下的Λ(x)如表1所示。

表1 不同RS編碼模式下的刪除位置多項式

由表1可知，所有多項式的常數(shù)項都為1，不需要存儲；而且后兩種RS模式的Λ(x)相同，只需要存儲一個，所以，只需要32 B的存儲空間即可，省去了利用多項式展開電路計算刪除位置多項式的開支。

2.3 修正伴隨多項式計算

修正的伴隨多項式T(x)由下式得到：



T(x)=S(x)Λ(x)mod x2T



多項式相乘相當于其系數(shù)的卷積，所以可以通過卷積電路(FIR濾波器結(jié)構(gòu))實現(xiàn)T(x)的計算。S(x)由伴隨式模塊并行輸出，不需要做串并轉(zhuǎn)換，直接用來初始化濾波器的系數(shù)。然后，從ROM中順序載入Λ(x)的系數(shù)作為濾波器的輸入，濾波器的輸出便是T(x)的系數(shù)。同時，Λ(x)也順序輸出，恰好作為下一個模塊的輸入。該部分的結(jié)構(gòu)框圖如圖4所示。

圖4 修正的伴隨多項式計算電路

2.4 關(guān)鍵方程求解

錯誤位置多項式σ(x)和錯誤值多項式ω(x)可以通過解關(guān)鍵方程T(x)σ(x)=ω(x)mod x2T來得到。文獻[2]提供了一種采用修正的歐幾里德算法(MEA)解關(guān)鍵方程的實現(xiàn)方法，并且通過改變算法的初始值直接計算出錯誤/刪除位置多項式Ψ(x)。MEA算法本質(zhì)上是基于多項式分解原理，求兩多項式最大公因子的迭代算法。通過將迭代過程使用基本單元實現(xiàn)，可以使用脈動陣列實現(xiàn)整個計算過程。具體的算法過程可以參見文獻[2]。

下面討論需要的基本單元的個數(shù)。MEA算法迭代完成，需要(2T)2=256個時鐘周期。如果能夠連續(xù)解碼，在最差的情況下，需要的基本迭代單元的個數(shù)為 256/n=256/32=8個。但是，根據(jù)IEEE 80216d協(xié)議，不論哪種RS編碼方式，每個RS塊都恰好對應一個OFDM符號，而且每個OFDM符號含有256個子載波，即使在取最小的保護間隔1/32的情況下，每個OFDM符號至少含有264個子載波。所以從整體系統(tǒng)考慮，解調(diào)模塊給出的RS碼流并不是嚴格連續(xù)的。每個RS分組至少持續(xù)264個時鐘周期，在解調(diào)和解碼模塊采用相同時鐘的條件下，只需要一個基本單元足以完成整個迭代過程。

2.5 錯誤位置和錯誤值計算

通過對Ψ(x)求根可以得到錯誤位置。工程上通常用錢搜索算法求根，即將有限域中每個元素代入多項式求值，判斷多項式的值是否為零。如果Xi是方程的根，則代入Forney公式ei=-ω(X-1i)Ψ′(X-1i)，可得到相應的錯誤值。將錯誤值加到接收碼字的相應位置，便得到正確的碼字。

錢搜索模塊和錯誤值計算模塊的硬件結(jié)構(gòu)與計算伴隨多項式相似，都是對多項式求值，具體實現(xiàn)方法可以參見文獻[2]。

和2.1所述的方法類似，在計算之前，先將第i個寄存器初始化為αi(255-n)，可以減少255-n個時鐘周期的延時。

3 RS譯碼器性能分析

3.1 譯碼延時

對于RS(n，k，t)碼，伴隨式計算模塊延時n個時鐘周期；修正伴隨式計算模塊延時(16-2t)個時鐘周期；關(guān)鍵方程求解模塊延時256個時鐘周期；錢搜索和錯誤值計算模塊延時k個時鐘周期，再為流水線的設計和硬件實現(xiàn)20個時鐘余量，可得總的延時為(n+16-2t+256+k+20)個時鐘周期。

3.2 譯碼速度

由于采用了流水線結(jié)構(gòu)，整個譯碼器的數(shù)據(jù)處理速度取決于流水線中最慢模塊的處理速度。在本設計中，MEA模塊的速度最慢，處理完一個RS塊需要256個時鐘周期。

對于不同的系統(tǒng)時鐘，譯碼器的實際延時和譯碼速度會有所不同。

本設計實際應用于8 M帶寬的WiMAX系統(tǒng)中，系統(tǒng)時鐘為32 M。在該應用環(huán)境下，在RS(120，108，6)模式下系統(tǒng)延時最大，為(120+16-2*6+256+108+20)/32=15.9 μs。在RS(32，24，4)模式下處理速度最低，為[(24*8)/256]*32 M=24 Mb/s。

4 結(jié) 語

本文通過對IEEE 802.16d協(xié)議中RS碼的特點分析，提出了一種適用于該標準的RS譯碼實現(xiàn)方法。本文所設計的RS譯碼器使用Verilog語言實現(xiàn)，在ModelSim 6.0環(huán)境下仿真通過。使用Synplify 8.1綜合，ISE 8.1布局布線，并在Xilinx VirtexⅡ-8000系列FPGA上驗證通過。該模塊單獨綜合布線時可以達到80 M工作時鐘，占用資源9%，滿足系統(tǒng)要求。

參 考 文 獻

［1］IEEE Standard 802.16d.Air Interface for Fixed Broadband Wireless Access Systems[S].New York Institute of Electrical and Electronics Engineers，2004.

［2］Shao H M，Reed I S.On the VLSI Design of a Pipeline Reed Solomon Decoder Using Systolic Arrays[J].IEEE Transactions on Computer，1988，37(10):1 273-1 280.

［3］Shao H M，Truong T K.A VLSI Design of a Pipeline Reed-Solomon Decoder[J].IEEE Transactions on Computer，1985，34:393-403.

［4］Shin Lin Shieh，Shuenn Gi Lee，Wern Ho Sheen.A Low-Latency Decoder for Punctured/Shortened Reed-Solomon Codes[A].Personal，Indoor and Mobile Radio Communications，2005.PIMRC 2005.IEEE 16th International Symposium on Volume，2005，11(4):2 547-2 551.



作者簡介

高慶峰 男，1982年出生，碩士，研究生。主要研究方向為數(shù)字通信和信道編碼。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。