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

　　由于本文采用的是RS(255,239)碼，故碼組長(zhǎng)n=255字節(jié)，信息字節(jié)長(zhǎng)k=239,校驗(yàn)字節(jié)長(zhǎng)m=16，糾錯(cuò)數(shù)t=8，最大距離d=2t+1=17。
　　該碼對(duì)應(yīng)的本原元多項(xiàng)式為：
　　

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

???

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

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

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

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

　　本文提出一種RS碼時(shí)域譯碼的流水線結(jié)構(gòu)的FPGA實(shí)現(xiàn)，它采用分時(shí)復(fù)用技術(shù)對(duì)譯碼器的關(guān)鍵模塊——解關(guān)鍵方程模塊的結(jié)構(gòu)進(jìn)行了改進(jìn)。在ALTERA公司APEX 20k系列芯片EP20K1500EFC33-1上的實(shí)現(xiàn)表明，改進(jìn)后的解方程關(guān)鍵模塊占用的邏輯單元數(shù)減少了1406個(gè)，并經(jīng)綜合、布局布線后，工作頻率最大可達(dá)71.01MHz。該結(jié)構(gòu)有如下特點(diǎn)：無多項(xiàng)式次數(shù)計(jì)算，迭代次數(shù)恒定，控制單元簡(jiǎn)單；結(jié)構(gòu)非常規(guī)則，易于用Verilog語言實(shí)現(xiàn)；復(fù)用錯(cuò)誤位置和錯(cuò)誤值多項(xiàng)式的PE單元后，仍可應(yīng)用于高速通信場(chǎng)合。
參考文獻(xiàn)
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