基于FPGA的RS碼譯碼器的設計

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

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

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

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

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

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

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

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

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


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

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

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

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

仿真采用時(shí)鐘為100 M，將正確的編碼后的碼字人為的輸入16個(gè)連續錯誤和16個(gè)分散錯誤，啟動(dòng)仿真，由波形中引出計算的所得的錯誤值和相應的錯誤位置，16個(gè)錯誤均得到了糾正。由圖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，錯誤的數據已經(jīng)得到了糾正，驗證了譯碼器的正確性。

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