基于FPGA的RS碼譯碼器的設(shè)計(jì)

摘要：介紹了符合CCSDS標(biāo)準(zhǔn)的RS(255，223)碼譯碼器的硬件實(shí)現(xiàn)結(jié)構(gòu)。譯碼器采用8位并行時(shí)域譯碼算法，主要包括了修正后的無逆BM迭代譯碼算法，錢搜索算法和Forney算法。采用了三級流水線結(jié)構(gòu)實(shí)現(xiàn)，減小了譯碼器的時(shí)延，提高了譯碼的速率，使用了VHDL語言完成譯碼器的設(shè)計(jì)與實(shí)現(xiàn)。測試表明，該譯碼器性能優(yōu)良，適用于高速通信。
關(guān)鍵詞：RS碼；FPGA；譯碼器；有限域；改進(jìn)的BM算法

在數(shù)字通信中，信號在有噪信道中傳輸，不可避免的會(huì)受到噪聲的干擾，引起誤碼。在已知信噪比的情況下要達(dá)到一定的誤碼率指標(biāo)，在合理設(shè)計(jì)基帶信號，選擇調(diào)制解調(diào)方式，及時(shí)域均衡或頻域均衡的基礎(chǔ)上，使用差錯(cuò)控制技術(shù)可以使誤碼率進(jìn)一步的降低。RS碼屬于分組碼，是BCH碼的一個(gè)子類，是最大距離可分碼，它是由Reed和Solomon于1960年構(gòu)造出來。由于它具有很強(qiáng)的糾正隨機(jī)錯(cuò)誤和突發(fā)錯(cuò)誤的能力，以及極低的不可探測的差錯(cuò)率，所以RS碼已經(jīng)廣泛應(yīng)用于深空通信、衛(wèi)星通信、存儲(chǔ)介質(zhì)、數(shù)字視頻廣播和擴(kuò)頻數(shù)字通信中。
在一些特定應(yīng)用域中，RS碼的設(shè)計(jì)和實(shí)現(xiàn)是比較困難的，RS碼是在有限域上進(jìn)行的代數(shù)運(yùn)算，不同于常用的二進(jìn)制系統(tǒng)，現(xiàn)實(shí)相對復(fù)雜一些，其復(fù)雜度主要決定于有限域的大小、碼字的長度，采用的編碼算法等。FPGA能夠快速和經(jīng)濟(jì)的將電路描述轉(zhuǎn)化為硬件實(shí)現(xiàn)，而且對設(shè)計(jì)的修訂也比較方便。文中使用VHDL語言設(shè)計(jì)了RS(255，223)譯碼器，并經(jīng)過了PFGA芯片上的驗(yàn)證。整個(gè)設(shè)計(jì)采用流水線結(jié)構(gòu)，提高譯碼器的數(shù)據(jù)吞吐量，同時(shí)對電路結(jié)構(gòu)進(jìn)行優(yōu)化，減少體積和時(shí)延，非常有利于微小衛(wèi)星中應(yīng)用。

1 RS碼譯碼原理及實(shí)現(xiàn)
1．1 RS(255，223)碼的參數(shù)
RS(255，223)是在有限域GF(28)中計(jì)算得到的，其具體參數(shù)為：
1)每個(gè)符號的bit數(shù)：m=8；
2)每個(gè)碼字包含的符號個(gè)數(shù)：n=28-1=255；
3)每個(gè)碼字包含的信息位的符號個(gè)數(shù)：k=223；
4)碼字中校驗(yàn)位的符號個(gè)數(shù)：2t=255-223=32；
5)一個(gè)碼字所能糾錯(cuò)的最大符號數(shù)：t=16；
6)GF(28)域的本原多項(xiàng)式：f(x)=x8+x7+x2+x+1；
7)生成多項(xiàng)式：

1．2 RS碼譯碼原理
RS譯碼算法有兩類：時(shí)域譯碼和頻域譯碼。在實(shí)際工程中，由于RS碼符號通常取自有限域GF(28)上，采用時(shí)域系統(tǒng)碼編碼方式，系統(tǒng)碼編碼方式可較容易縮短，滿足工程應(yīng)用的需求。如圖1所示，RS碼時(shí)域譯碼器主要分為四個(gè)模塊：伴隨式計(jì)算模塊、錯(cuò)誤位置多項(xiàng)式計(jì)算模塊、錢搜索模塊、錯(cuò)誤值計(jì)模塊。其中錯(cuò)誤位置多項(xiàng)式計(jì)算采用修正后的無逆BM迭代算法，錯(cuò)誤值計(jì)算采用Forney算法，還需要一個(gè)FIFO來
緩存所接受的碼字，使與經(jīng)過譯碼后計(jì)算出的錯(cuò)誤值同步。

RS碼時(shí)域譯碼的一般步驟為：
1)根據(jù)接收的碼字計(jì)算伴隨式，如果計(jì)算出來的2t個(gè)伴隨式都等于0，那么表示接收的碼字沒有錯(cuò)誤，不再進(jìn)行下面的步驟，否則進(jìn)行下面的步驟；
2)利用計(jì)算好的伴隨式計(jì)算錯(cuò)誤位置多項(xiàng)式和錯(cuò)誤值多項(xiàng)式；
3)計(jì)算錯(cuò)誤位置和錯(cuò)誤值；
4)根據(jù)計(jì)算的錯(cuò)誤位置和錯(cuò)誤值可得到錯(cuò)誤多項(xiàng)式E(x)，將接收的碼字R(x)與E(x)相加，即可譯碼。
1．2．1 域內(nèi)加法器和乘法器
有限域GF(2m)中的元素都可以用二元域GF(2)中的元素的m重來表示，域中的任意元素都可以用次數(shù)小于m的多項(xiàng)式表示，加法和乘法運(yùn)算是有限域GF(2m)中最簡單的運(yùn)算。
有限域上的加法比較簡單，只需要對m維并行數(shù)據(jù)進(jìn)行異或即可。
有限域上的乘法通常認(rèn)為是時(shí)延較大，結(jié)構(gòu)復(fù)雜的運(yùn)算操作。有限域的乘法器，即對于域內(nèi)的任意兩個(gè)元素，可以用m-1次多項(xiàng)式來表示，這樣兩個(gè)元素的乘積為2m-2次多項(xiàng)式，再把乘積對有限域的本原多項(xiàng)式求余，所得的結(jié)果即為兩個(gè)元素的乘積。文中的乘法器是采用八位并行與門和異或門來實(shí)現(xiàn)的，這種有限域乘法器的設(shè)計(jì)充分利用了特征為2的有限域元素的加減法運(yùn)算即為異或運(yùn)算的特征，大大簡化了設(shè)計(jì)，同時(shí)也使算法描述更簡單，且容易實(shí)現(xiàn)。
1．2．2 計(jì)算伴隨式模塊
BS(255，223)譯碼的第一步就是計(jì)算2t個(gè)伴隨式Si：

其實(shí)現(xiàn)結(jié)構(gòu)如圖2所示，在初始階段，寄存器被清零，輸入第一個(gè)碼字(接收的碼字高位)在與零相加后被送入寄存器，再乘以與第二個(gè)輸入的碼字相加，如此循環(huán)，直到255個(gè)碼字全部進(jìn)去寄存器經(jīng)過計(jì)算后，寄存器內(nèi)的值便是我們需要的伴隨式Si。

1．2．3 修正后的無逆BM迭代算法模塊
求解關(guān)鍵方程是解碼器實(shí)現(xiàn)中最復(fù)雜和占用資源最多的模塊，其目的是為了求出錯(cuò)誤位置多項(xiàng)式σ(x)，根是錯(cuò)誤位置的t次多項(xiàng)式：

關(guān)于求解關(guān)鍵方程的算法的已有很多，例如，Euclid算法，非二進(jìn)制的BM算法等。文中采用修正后的無逆BM迭代算法實(shí)現(xiàn)。傳統(tǒng)的BM迭代譯碼算法，每次迭代都有一個(gè)求逆的運(yùn)算，求逆是比較復(fù)雜且對硬件要求高的算法。無逆BM迭代算法避免了進(jìn)行繁瑣耗時(shí)的求逆運(yùn)算，但是迭代過程中只計(jì)算了錯(cuò)誤位置多項(xiàng)式，最后還需要根據(jù)關(guān)鍵方程和得到的錯(cuò)誤位置多項(xiàng)式來求的錯(cuò)誤值多項(xiàng)式，這樣也增加了譯碼的時(shí)延。改進(jìn)后的無逆BM迭代算法，在計(jì)算了錯(cuò)誤位置多項(xiàng)式的同時(shí)也計(jì)算了錯(cuò)誤值多項(xiàng)式，減少了時(shí)鐘的損耗，提高了譯碼的速率。具體實(shí)現(xiàn)流程如圖3所示。

圖3中λ(x)是計(jì)算錯(cuò)誤位置多項(xiàng)式σ(x)的輔助多項(xiàng)式，α(x)是計(jì)算錯(cuò)誤值多項(xiàng)式ω(x)的輔助多項(xiàng)式，k為迭代的次數(shù)，δ為前一次迭代和這次迭代的修正項(xiàng)。
1．2．4 錢搜索和Forney算法模塊
錯(cuò)誤位置多項(xiàng)式σ(x)和錯(cuò)誤值多項(xiàng)式ω(x)確定后，錯(cuò)誤位置可以通過求解錯(cuò)誤位置多項(xiàng)式的根求得的，工程上用的最多的是錢搜索算法。譯碼器通過錢搜索算法檢查當(dāng)x=α0，α1，…，αn時(shí)，代入錯(cuò)誤位置多項(xiàng)式σ(x)中，若σ(αi)=0，則表示αi為出錯(cuò)的位置。
利用Forney算法可以求得錯(cuò)誤位置上的錯(cuò)誤值，在已求得錯(cuò)誤位置多項(xiàng)式和錯(cuò)誤值多項(xiàng)式前提下：


在實(shí)現(xiàn)過程中，錢搜索和Forney算法是在一個(gè)模塊中實(shí)現(xiàn)的。對αi進(jìn)行錢搜索的同時(shí)，也把αi輸入Forney算法實(shí)現(xiàn)結(jié)構(gòu)中，采用流水線結(jié)構(gòu)，這樣可以減少時(shí)鐘周期，經(jīng)過t+1個(gè)時(shí)鐘后即可以輸出第一個(gè)糾錯(cuò)后的結(jié)果。結(jié)構(gòu)如圖4所示，σ0，σ1，…，σ16分別表示σ(x)的系數(shù)，ω0，ω1，…，ω16表示ω(x)的系數(shù)，x1，…，x16表示αi，…，α16i，對于求σ’(x)時(shí)，中間需要等一個(gè)時(shí)鐘，流水線結(jié)構(gòu)一定要注意同步，錯(cuò)開一個(gè)時(shí)鐘都會(huì)產(chǎn)生錯(cuò)誤。這部分有一個(gè)求逆的運(yùn)算，本文中的求逆運(yùn)算是用的查表法實(shí)現(xiàn)的，查表法的基本思想是GF(28)域上的元素的逆元先計(jì)算出來存儲(chǔ)到ROM中，將待求逆元作為讀取ROM的地址，讀出ROM的存儲(chǔ)值，該值便是所求結(jié)果，這種方法的計(jì)算速度非?？?。使用這種結(jié)構(gòu)提高了譯碼的速率。

1．2．5 糾錯(cuò)模塊
當(dāng)確定可誤碼的位置及具體的誤碼值后，也就確定了錯(cuò)誤多項(xiàng)式，將得到的錯(cuò)誤多項(xiàng)式與接收多項(xiàng)式相加，即完成誤碼的糾正。

糾錯(cuò)的硬件實(shí)現(xiàn)結(jié)構(gòu)如圖5所示，是一個(gè)二選一的多項(xiàng)選擇器，如果代入錯(cuò)誤位置多項(xiàng)式后得到的值為0，那么需要將接收值與計(jì)算得到的錯(cuò)誤值相加，如果不等以0，則直接輸出接收值。接收碼字需要經(jīng)過一個(gè)緩存器，這樣接收值才能與經(jīng)過譯碼算法輸出的錯(cuò)誤值同步，達(dá)到糾錯(cuò)的目的。

2 FPGA實(shí)現(xiàn)及測試結(jié)果
運(yùn)用上文提出的硬件實(shí)現(xiàn)結(jié)構(gòu)框架，采用VHDL輸入，在FPGA上實(shí)現(xiàn)了RS(255，223)碼的連續(xù)譯碼，使用了XilinxISE10．1編譯，采用了xc4vsx55芯片綜合，Slice個(gè)數(shù)為5 209個(gè)，占用芯片總數(shù)的21％，最高速率達(dá)到了149．836 MHz。通過Modelsim6．2驗(yàn)證，采用了三級流水線結(jié)構(gòu)，譯碼所需時(shí)鐘周期為255+2*t+2+t+1，文中譯碼器的時(shí)鐘周期為306個(gè)時(shí)鐘。

仿真采用時(shí)鐘為100 M，將正確的編碼后的碼字人為的輸入16個(gè)連續(xù)錯(cuò)誤和16個(gè)分散錯(cuò)誤，啟動(dòng)仿真，由波形中引出計(jì)算的所得的錯(cuò)誤值和相應(yīng)的錯(cuò)誤位置，16個(gè)錯(cuò)誤均得到了糾正。由圖6可以看到輸入信號rs_data_in，人為的將27—42改為30、35、128、60、167、250、75、43、108、89、135、40、79、191、2、9。由圖7可以看到輸出信號rs_data_out，錯(cuò)誤的數(shù)據(jù)已經(jīng)得到了糾正，驗(yàn)證了譯碼器的正確性。

3 結(jié)束語
文中實(shí)現(xiàn)了RS碼時(shí)域譯碼器結(jié)構(gòu)，根據(jù)該結(jié)構(gòu)完成了符號取自有限域GF(256)上的RS(255，223)碼譯碼器。這種RS碼譯碼器硬件實(shí)現(xiàn)結(jié)構(gòu)具有功能模塊化、結(jié)構(gòu)規(guī)則化的特點(diǎn)，采用了流水線結(jié)構(gòu)，最大限度提高譯碼數(shù)據(jù)的吞吐量，提高了譯碼速度，適用于高速通信。并且在此基礎(chǔ)上只需進(jìn)行少量更動(dòng)就可以較容易實(shí)現(xiàn)其它碼型的譯碼器，該方案已應(yīng)用于多個(gè)軍事通信設(shè)備中。