RS碼是Reed-Solomon碼的簡稱，它是線性分組糾錯碼中的一種。與同類糾錯碼比較，在同樣編碼冗余度下，RS碼具有較強的糾錯能力，目前主要應用于深空通信、存儲系統(如VCR、DVD光盤)、數字廣播電視等領域中。RS碼的譯碼相對于編碼難度更大，且隨著碼長的增加，譯碼電路的復雜性也隨之巨增。近年來，由于大規模集成電路技術及EDA技術的發展，使得研究譯碼器的硬件實現成為國內外信道編碼技術的一個熱點。
　　RS譯碼算法根據解關鍵方程的不同，主要可分為兩大類：BM迭代算法和Euclid迭代算法(以下簡稱歐氏算法)。對這兩類迭代算法的RS譯碼器硬件結構的設計，國外已有不少文獻提出了一些好的設計方法[1～3]，其核心都是為了減少硬件結構的復雜性和提高工作效率。本文主要也是圍繞這個核心介紹一種新改進的歐幾里得算法^[5]，并針對RS(255,239)碼給出基于時域譯碼的流水線結構的FPGA實現。
1 RS時域譯碼算法介紹
1.1 RS碼的時域譯碼步驟
　　RS碼的時域譯碼步驟一般分為如下三步：
　　(1)由接收到的碼組r計算伴隨式：

　　由于本文采用的是RS(255,239)碼，故碼組長n=255字節，信息字節長k=239,校驗字節長m=16，糾錯數t=8，最大距離d=2t+1=17。
　　該碼對應的本原元多項式為：
　　

　　S_j和g(x)兩式中都取m0=0。
　　(2)由伴隨式計算錯誤位置多項式和錯誤值多項式
　　主要是通過解關鍵方程Ω(x)=Λ(x)S(x) mod x^2t求出錯誤位置多項式Λ(x)和錯誤值多項式Ω(x)。對于糾錯數較多的RS碼，解方程的算法主要有兩類：BM迭代算法和歐氏算法。本文將在后面詳細介紹歐氏算法。
　　(3)根據第二步的結果計算出錯誤圖樣，然后由錯誤圖樣和接收碼組在GF(2)域上進行加法操作，恢復出正確的碼組。
　　此外錯誤圖樣的計算需要利用Chien搜索電路、存放逆運算查找表的ROM存儲器，以及Forney公式Y_j=Ω(α ⁱ)/Λodd(α ⁱ)^[2]。
　　另外，該算法還要通過C語言進行仿真，以便減少FPGA實現過程中調試、查錯的工作量，從而使上述步驟中每一步FPGA實現的正確性都能得到進一步的保證。
1.2 新改進的歐氏算法基本原理
　　歐氏算法的主要原理是通過歐幾里德多項式除法多次相除，得到所求錯誤位置多項式和錯誤值多項式。其中，除法電路實現非常復雜，要耗費較多的硬件資源，故改進的歐氏算法以減法(在GF(2^m)迦羅華域中減法即加法)替代除法，從而消除除法電路。其具體算法步驟如下： (1)賦初值
　　

???

　　(3)回到步驟(2)
　　這種新改進歐氏算法的特點是：迭代次數恒定，最高次項系數的位置固定。這些特點將使其硬件結構控制單元更簡單，數據處理單元更規則，易于用Verilog HDL實現。
2 譯碼器的FPGA實現及仿真
2.1流水線式譯碼器的的整體結構
　　譯碼器的流水線結構(見圖1)由三級流水線構成，在時域上實現前面所述譯碼算法的三個步驟。其中第一級流水線和第三級流水線各需255個數據處理時鐘周期" title="時鐘周期">時鐘周期和一個寄存器初始化時鐘周期，而第二級流水線在不考慮 EL(錯誤位置多項式)和 EE(錯誤值多項式)單元復用的情況下，只需16個數據處理時鐘周期和一個寄存器初始化時鐘周期，這樣它會有239個時鐘周期處于空閑狀態。這里時鐘周期是指碼組中每個碼元的傳輸時間。

　　采用流水線的優點是：能提高譯碼器的工作效率，加快其數據處理速度，使之適用于高速通信場合。但缺點是：可能需要耗費額外的流水線寄存器，以保留中間結果。不過，在RS譯碼器中，由于可以利用其本身特有結構中的寄存器，故不會增加過多的硬件資源。
　　圖1譯碼器中關鍵方程求解模塊是限制整個譯碼器工作速度的瓶頸，并占用了譯碼器硬件資源的很大部分，故下面著重介紹該模塊的硬件實現及其改進結構(其余模塊的硬件實現可參考相關文獻)。
2.2 關鍵方程求解(KES)模塊的FPGA實現
　　圖2為前面介紹的歐氏迭代算法(即KES模塊)的硬件實現電路，它由數據處理單元和控制單元兩部分構成。其中數據處理單元中的EE(如圖3)和EL(同圖3)采用寄存器分組并行方式計算錯誤值和錯誤位置多項式，兩者的多項式最高次項系數δ，γ都由EE中寄存器R₁₅^(b)，R₁₅^(a)提供，其硬件結構相同，非常規則，分別由2t+1個 完全相同的基本單元PE構成。當KES模塊開始工作時，先對EE、EL中的寄存器初始化，即完成歐氏算法步驟(1)。然后在控制單元的控制下，迭代16次就得到結果。迭代中需要多次調用加法器、乘法器來完成迦羅華域的乘、加運算，加法器可由簡單的位異或操作實現，而乘法器的實現則較復雜，要占用較多的硬件資源，有多種實現方法。本文根據文獻^[4]設計了一種基于對偶基的乘法器，其占用的門電路數較少，且延時也較少。該算法實現的另一特點是：控制單元(見圖2(b))很簡單，無需普通歐式算法中多項式次數計算等復雜操作。

　　最后，使用QuartusII3.0軟件，在ALTERA公司的APEX 20k系列的芯片EP20K1500EFC33-1上實現整個譯碼器，占用LE (邏輯單元)的總數為4972個，其中EE單元占LE數為1847個，EL單元占LE數為1670個，故關鍵方程求解模塊的數據處理單元占用了3517個LE。
2.3 關鍵方程求解模塊的改進
　　由以上分析可知，因為結構相同的EE和EL都使用了大量的組合邏輯部件：乘法器、加法器、多選器，故可以采用分時復用技術對它們進行復用，以節省硬件資源。分時復用的一種方法具體如下：將EE和EL中對應位置的PE合并為一個基本單元，并通過增加復用器，在不同的時鐘節拍，有選擇地對不同的寄存器操作，從而達到面積復用的目的。但是，過多的復用器一方面增加了每次迭代的計算延時，降低了工作速度，另一方面也要耗費硬件資源。為了克服這些缺點，本文采用了一種特殊結構對PE單元進行改進。PE單元的硬件結構如圖4所示。改進后PE結構與改進前比較，其寄存器分別被替換為一循環移位寄存器和一左移寄存器，這樣就避免了加入額外的復用器。同時為了保持與譯碼器中其它模塊的同步，KES模塊的時鐘信號頻率提高為原來的兩倍，利用奇數時鐘節拍計算錯誤位置多項式，利用偶數節拍計算錯誤值多項式。改進后的譯碼器在QuartusII軟件上編譯,并經綜合、布局布線后，最大工作頻率可達71.01MHz，占用LE的總數為3517個，其中KES模塊中的數據處理單元僅占用LE數2111個。

2.4 FPGA仿真
　　為了驗證譯碼結果的正確性，可將編碼后的數據人為地加入不超過8個的錯誤字符，將接收后譯碼得到的碼組與編碼所得的原始碼組相比較，若一致，則說明譯碼正確。QuartusII編、譯碼仿真波形如圖5所示，data為239字符長的信息符號，code為編碼后得到的255字符長碼組。這里為便于觀察，取data的前236字節為全0，后三字節分別為1、2、3。fout為人為噪聲干擾后經過緩沖器延時所接收的碼組，err_pattn為錯誤圖樣，dout為譯碼后所得正確編碼。

　　本文提出一種RS碼時域譯碼的流水線結構的FPGA實現，它采用分時復用技術對譯碼器的關鍵模塊——解關鍵方程模塊的結構進行了改進。在ALTERA公司APEX 20k系列芯片EP20K1500EFC33-1上的實現表明，改進后的解方程關鍵模塊占用的邏輯單元數減少了1406個，并經綜合、布局布線后，工作頻率最大可達71.01MHz。該結構有如下特點：無多項式次數計算，迭代次數恒定，控制單元簡單；結構非常規則，易于用Verilog語言實現；復用錯誤位置和錯誤值多項式的PE單元后，仍可應用于高速通信場合。
參考文獻
1 H.M.SHAO,T.K.troung,L.J.Dentsch.A VLSI Design of a Pipeline Reed-Solomon Decoder[J].IEEE Transactions on Computers.1985;C-34(5):393～403
2 S.Kwon and H.Shin.An Area-efficient VLSI Architechure of a Reed-Solomon Decoder/Encoder for Digital VCR′s[J].IEEE Transaction on Consumer Electron,1997;43(4):1019～1027
3 H.M.Shao, IS.Reed. On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays[J].IEEE Trans-actions on Computers.1988;37(10):1273～1280
4 S.T.J.Fenn，Benaissa,D.Taylor.GF(2m) Multimpilication and Division Over the Dual Basis[J].IEEE Transactions on Com-puters,1996;C-34(3):319～327
5 Y.W.Chang，T.K.Troung，J.H.Jeng.VLSI Architechure of Modified Euclidean Algorithm for Reed-Solomon Code[DB]. http://elsevier.lib.tsinghua.edu.cn/pdflinks/04052214422103738.pdf,2003