摘 要: 結(jié)合流水線技術(shù)， 對一種新提出的RS譯碼的歐幾里德迭代算法及其VLSI結(jié)構(gòu)，給出了基于時域譯碼的FPGA實(shí)現(xiàn)和驗(yàn)證，并采用分時復(fù)用" title="復(fù)用">復(fù)用技術(shù)對譯碼器" title="譯碼器">譯碼器的關(guān)鍵模塊——解關(guān)鍵方程" title="關(guān)鍵方程">關(guān)鍵方程模塊的結(jié)構(gòu)加以改進(jìn)，使其錯誤位置和錯誤值多項(xiàng)式單元能面積復(fù)用。該結(jié)構(gòu)的特點(diǎn)是：控制單元" title="控制單元">控制單元簡單；模塊結(jié)構(gòu)非常規(guī)則，易于用Verilog HDL實(shí)現(xiàn)；可應(yīng)用于高速通信場合。
關(guān)鍵詞: RS譯碼 FPGA 流水線 關(guān)鍵方程 規(guī)則結(jié)構(gòu)
RS碼是Reed-Solomon碼的簡稱，它是線性分組糾錯碼中的一種。與同類糾錯碼比較，在同樣編碼冗余度下，RS碼具有較強(qiáng)的糾錯能力，目前主要應(yīng)用于深空通信、存儲系統(tǒng)(如VCR、DVD光盤)、數(shù)字廣播電視等領(lǐng)域中。RS碼的譯碼相對于編碼難度更大，且隨著碼長的增加，譯碼電路的復(fù)雜性也隨之巨增。近年來，由于大規(guī)模集成電路技術(shù)及EDA技術(shù)的發(fā)展，使得研究譯碼器的硬件實(shí)現(xiàn)成為國內(nèi)外信道編碼技術(shù)的一個熱點(diǎn)。
RS譯碼算法根據(jù)解關(guān)鍵方程的不同，主要可分為兩大類：BM迭代算法和Euclid迭代算法(以下簡稱歐氏算法)。對這兩類迭代算法的RS譯碼器硬件結(jié)構(gòu)的設(shè)計(jì)，國外已有不少文獻(xiàn)提出了一些好的設(shè)計(jì)方法[1～3]，其核心都是為了減少硬件結(jié)構(gòu)的復(fù)雜性和提高工作效率。本文主要也是圍繞這個核心介紹一種新改進(jìn)的歐幾里得算法[5]，并針對RS(255,239)碼給出基于時域譯碼的流水線結(jié)構(gòu)的FPGA實(shí)現(xiàn)。
1 RS時域譯碼算法介紹
1.1 RS碼的時域譯碼步驟
RS碼的時域譯碼步驟一般分為如下三步：
(1)由接收到的碼組r計(jì)算伴隨式：
由于本文采用的是RS(255,239)碼，故碼組長n=255字節(jié)，信息字節(jié)長k=239,校驗(yàn)字節(jié)長m=16，糾錯數(shù)t=8，最大距離d=2t+1=17。
該碼對應(yīng)的本原元多項(xiàng)式為：
Sj和g(x)兩式中都取m0=0。
(2)由伴隨式計(jì)算錯誤位置多項(xiàng)式和錯誤值多項(xiàng)式
主要是通過解關(guān)鍵方程Ω(x)=Λ(x)S(x) mod x2t求出錯誤位置多項(xiàng)式Λ(x)和錯誤值多項(xiàng)式Ω(x)。對于糾錯數(shù)較多的RS碼，解方程的算法主要有兩類：BM迭代算法和歐氏算法。本文將在后面詳細(xì)介紹歐氏算法。
(3)根據(jù)第二步的結(jié)果計(jì)算出錯誤圖樣，然后由錯誤圖樣和接收碼組在GF(2)域上進(jìn)行加法操作，恢復(fù)出正確的碼組。
此外錯誤圖樣的計(jì)算需要利用Chien搜索電路、存放逆運(yùn)算查找表的ROM存儲器，以及Forney公式Y(jié)j=Ω(α i)/Λodd(α i)[2]。
另外，該算法還要通過C語言進(jìn)行仿真，以便減少FPGA實(shí)現(xiàn)過程中調(diào)試、查錯的工作量，從而使上述步驟中每一步FPGA實(shí)現(xiàn)的正確性都能得到進(jìn)一步的保證。
1.2 新改進(jìn)的歐氏算法基本原理
歐氏算法的主要原理是通過歐幾里德多項(xiàng)式除法多次相除，得到所求錯誤位置多項(xiàng)式和錯誤值多項(xiàng)式。其中，除法電路實(shí)現(xiàn)非常復(fù)雜，要耗費(fèi)較多的硬件資源，故改進(jìn)的歐氏算法以減法(在GF(2m)迦羅華域中減法即加法)替代除法，從而消除除法電路。其具體算法步驟如下： (1)賦初值
??? 
(3)回到步驟(2)
這種新改進(jìn)歐氏算法的特點(diǎn)是：迭代次數(shù)恒定，最高次項(xiàng)系數(shù)的位置固定。這些特點(diǎn)將使其硬件結(jié)構(gòu)控制單元更簡單，數(shù)據(jù)處理單元更規(guī)則，易于用Verilog HDL實(shí)現(xiàn)。
2 譯碼器的FPGA實(shí)現(xiàn)及仿真
2.1流水線式譯碼器的的整體結(jié)構(gòu)
譯碼器的流水線結(jié)構(gòu)(見圖1)由三級流水線構(gòu)成，在時域上實(shí)現(xiàn)前面所述譯碼算法的三個步驟。其中第一級流水線和第三級流水線各需255個數(shù)據(jù)處理時鐘周期" title="時鐘周期">時鐘周期和一個寄存器初始化時鐘周期，而第二級流水線在不考慮 EL(錯誤位置多項(xiàng)式)和 EE(錯誤值多項(xiàng)式)單元復(fù)用的情況下，只需16個數(shù)據(jù)處理時鐘周期和一個寄存器初始化時鐘周期，這樣它會有239個時鐘周期處于空閑狀態(tài)。這里時鐘周期是指碼組中每個碼元的傳輸時間。
采用流水線的優(yōu)點(diǎn)是：能提高譯碼器的工作效率，加快其數(shù)據(jù)處理速度，使之適用于高速通信場合。但缺點(diǎn)是：可能需要耗費(fèi)額外的流水線寄存器，以保留中間結(jié)果。不過，在RS譯碼器中，由于可以利用其本身特有結(jié)構(gòu)中的寄存器，故不會增加過多的硬件資源。
圖1譯碼器中關(guān)鍵方程求解模塊是限制整個譯碼器工作速度的瓶頸，并占用了譯碼器硬件資源的很大部分，故下面著重介紹該模塊的硬件實(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ì)算錯誤值和錯誤位置多項(xiàng)式，兩者的多項(xiàng)式最高次項(xiàng)系數(shù)δ，γ都由EE中寄存器R15(b)，R15(a)提供，其硬件結(jié)構(gòu)相同，非常規(guī)則，分別由2t+1個 完全相同的基本單元PE構(gòu)成。當(dāng)KES模塊開始工作時，先對EE、EL中的寄存器初始化，即完成歐氏算法步驟(1)。然后在控制單元的控制下，迭代16次就得到結(jié)果。迭代中需要多次調(diào)用加法器、乘法器來完成迦羅華域的乘、加運(yùn)算，加法器可由簡單的位異或操作實(shí)現(xiàn)，而乘法器的實(shí)現(xiàn)則較復(fù)雜，要占用較多的硬件資源，有多種實(shí)現(xiàn)方法。本文根據(jù)文獻(xiàn)[4]設(shè)計(jì)了一種基于對偶基的乘法器，其占用的門電路數(shù)較少，且延時也較少。該算法實(shí)現(xiàn)的另一特點(diǎn)是：控制單元(見圖2(b))很簡單，無需普通歐式算法中多項(xiàng)式次數(shù)計(jì)算等復(fù)雜操作。
最后，使用QuartusII3.0軟件，在ALTERA公司的APEX 20k系列的芯片EP20K1500EFC33-1上實(shí)現(xiàn)整個譯碼器，占用LE (邏輯單元)的總數(shù)為4972個，其中EE單元占LE數(shù)為1847個，EL單元占LE數(shù)為1670個，故關(guān)鍵方程求解模塊的數(shù)據(jù)處理單元占用了3517個LE。
2.3 關(guān)鍵方程求解模塊的改進(jìn)
由以上分析可知，因?yàn)榻Y(jié)構(gòu)相同的EE和EL都使用了大量的組合邏輯部件：乘法器、加法器、多選器，故可以采用分時復(fù)用技術(shù)對它們進(jìn)行復(fù)用，以節(jié)省硬件資源。分時復(fù)用的一種方法具體如下：將EE和EL中對應(yīng)位置的PE合并為一個基本單元，并通過增加復(fù)用器，在不同的時鐘節(jié)拍，有選擇地對不同的寄存器操作，從而達(dá)到面積復(fù)用的目的。但是，過多的復(fù)用器一方面增加了每次迭代的計(jì)算延時，降低了工作速度，另一方面也要耗費(fèi)硬件資源。為了克服這些缺點(diǎn)，本文采用了一種特殊結(jié)構(gòu)對PE單元進(jìn)行改進(jìn)。PE單元的硬件結(jié)構(gòu)如圖4所示。改進(jìn)后PE結(jié)構(gòu)與改進(jìn)前比較，其寄存器分別被替換為一循環(huán)移位寄存器和一左移寄存器，這樣就避免了加入額外的復(fù)用器。同時為了保持與譯碼器中其它模塊的同步，KES模塊的時鐘信號頻率提高為原來的兩倍，利用奇數(shù)時鐘節(jié)拍計(jì)算錯誤位置多項(xiàng)式，利用偶數(shù)節(jié)拍計(jì)算錯誤值多項(xiàng)式。改進(jìn)后的譯碼器在QuartusII軟件上編譯,并經(jīng)綜合、布局布線后，最大工作頻率可達(dá)71.01MHz，占用LE的總數(shù)為3517個，其中KES模塊中的數(shù)據(jù)處理單元僅占用LE數(shù)2111個。
2.4 FPGA仿真
為了驗(yàn)證譯碼結(jié)果的正確性，可將編碼后的數(shù)據(jù)人為地加入不超過8個的錯誤字符，將接收后譯碼得到的碼組與編碼所得的原始碼組相比較，若一致，則說明譯碼正確。QuartusII編、譯碼仿真波形如圖5所示，data為239字符長的信息符號，code為編碼后得到的255字符長碼組。這里為便于觀察，取data的前236字節(jié)為全0，后三字節(jié)分別為1、2、3。fout為人為噪聲干擾后經(jīng)過緩沖器延時所接收的碼組，err_pattn為錯誤圖樣，dout為譯碼后所得正確編碼。
本文提出一種RS碼時域譯碼的流水線結(jié)構(gòu)的FPGA實(shí)現(xiàn)，它采用分時復(fù)用技術(shù)對譯碼器的關(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個，并經(jīng)綜合、布局布線后，工作頻率最大可達(dá)71.01MHz。該結(jié)構(gòu)有如下特點(diǎn)：無多項(xiàng)式次數(shù)計(jì)算，迭代次數(shù)恒定，控制單元簡單；結(jié)構(gòu)非常規(guī)則，易于用Verilog語言實(shí)現(xiàn)；復(fù)用錯誤位置和錯誤值多項(xiàng)式的PE單元后，仍可應(yī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