RS碼是多進(jìn)制BCH碼，是一種兼有糾正隨機(jī)錯(cuò)誤和突發(fā)錯(cuò)誤能力的性能優(yōu)越的循環(huán)碼，它已被多個(gè)國內(nèi)外標(biāo)準(zhǔn)所采用，極大的改善了通信系統(tǒng)的性能。目前，由于系統(tǒng)傳輸速度的要求，提高RS譯碼速度變得非常重要，采用得比較多的設(shè)計(jì)方法是并行處理和流水線設(shè)計(jì)。影響譯碼速度關(guān)鍵的模塊是求解關(guān)鍵方程模塊。

　　近年來，關(guān)于RS（255，223）碼譯碼器實(shí)現(xiàn)的算法得到了廣泛的關(guān)注，但這些算法的實(shí)現(xiàn)速度都不太快，并且占用硬件資源也較多；而一些占用硬件資源較少的算法速度卻很慢。這里給出基于ME算法的8倍并行設(shè)計(jì)方案，該方案所使用的硬件資源少，而且還能獲得較高的譯碼速度，具有較高的性價(jià)比。

　　1 RS（255，223）碼及其譯碼原理

　　1.1  RS（255，223）碼

　　因其碼元取自GF（q），RS編解碼過程中的所有運(yùn)算都是在GF（q）的有限域上面進(jìn)行。RS（n，k）碼的編碼過程是將k個(gè)輸入信息碼字，用生成多項(xiàng)式產(chǎn)生（n，k）個(gè)冗余的糾錯(cuò)信息碼字，與原碼字合成形成n個(gè)信息碼字進(jìn)行傳輸。譯碼是在接收端，對(duì)接收的n個(gè)碼字信息進(jìn)行糾錯(cuò)處理，恢復(fù)k個(gè)信息碼字。對(duì)于1個(gè)長(zhǎng)度為am-1符號(hào)的RS碼，每個(gè)碼字都可以看成是有限域GF（am）中的1個(gè)元素。碼距為d的碼字，其RS碼生成多項(xiàng)式具有如下形式：

　　其中ai是GF（am）中的1個(gè)元素。

　　對(duì)于RS（255，223）碼而言，q=256，a=2，碼字符號(hào)在GF（28）中。m=8，是每個(gè)RS符號(hào)的碼元數(shù)；n=28-1，是每個(gè)RS碼字的符號(hào)數(shù)；k=223，是RS碼中信息位的符號(hào)數(shù)；t=16，是RS碼字內(nèi)符號(hào)的糾錯(cuò)能力；d=33，是碼距。

　　1.2 RS（255，223）碼譯碼原理

　　由于RS碼為分組碼，所以其譯碼算法主要由伴隨式計(jì)算、關(guān)鍵方程求解和錢搜索和Forney算法3部分構(gòu)成，譯碼器結(jié)構(gòu)如圖1所示。

　　首先，根據(jù)接收碼字乘以校驗(yàn)矩陣得到其伴隨多項(xiàng)式，對(duì)于RS（225，223）碼，其伴隨式求解式可以表示為：

　　求得伴隨式以后，則利用伴隨多項(xiàng)式求解關(guān)鍵方程：錯(cuò)誤位置多項(xiàng)式σ（x）和錯(cuò)誤特征多項(xiàng)式ω（x），如下所示：

　　求解關(guān)鍵方程現(xiàn)可采用的算法主要有BM（Belekamp-Messey）算法和ME（Modified Euclidean）算法。之后便得到錯(cuò)誤位置多項(xiàng)式σ（x）與錯(cuò)誤特征多項(xiàng)式ω（x）。

　　此后，由錯(cuò)誤位置多項(xiàng)式與錯(cuò)誤特征多項(xiàng)式來求得錯(cuò)誤位置與錯(cuò)誤值。求解錯(cuò)誤位置本設(shè)計(jì)采用窮舉算法——錢搜索算法來完成。同時(shí)，使用Forney公式求得錯(cuò)誤值。，用延時(shí)后的接收值減去錯(cuò)誤值，得到的譯碼輸出。Forney公式可以表示為：

　　其中，ei代表發(fā)生在i位置上的錯(cuò)誤值，σodd（x）代表錯(cuò)誤位置多項(xiàng)式奇數(shù)次項(xiàng)之和。

　　2 并行流水結(jié)構(gòu)方案

　　本設(shè)計(jì)采用8倍并行流水方案。將255個(gè)碼元8倍并行后，只需要32個(gè)周期便完成所有32個(gè)伴隨多項(xiàng)式系數(shù)的求解。然后將32個(gè)伴隨多項(xiàng)式系數(shù)順序輸出到下，在此基礎(chǔ)上采用流水線結(jié)構(gòu)，周期剛好滿足且不會(huì)浪費(fèi)資源。本設(shè)計(jì)中所有乘法器都是采用GF（28）有限域乘法器。

　　2.1  伴隨式計(jì)算

　　8倍并行伴隨多項(xiàng)式的求解算法，是在迭代算法的基礎(chǔ)上展開實(shí)現(xiàn)，其推導(dǎo)過程如下：

　　式（6）中，R255=0；i=1，2，…，2t-1，2t。其電路結(jié)構(gòu)如圖2所示。

　　2.2  關(guān)鍵方程求解

　　本設(shè)計(jì)中關(guān)鍵方程的求解采用ME算法。BM算法具有反饋結(jié)構(gòu)，不適合使用流水結(jié)構(gòu)，而ME算法可采用流水結(jié)構(gòu)。其算法描述如下：

　　其中，S（x）為輸入的伴隨多項(xiàng)式。

　　ME算法為1種迭代算法，目的在于求i階余式Ri（x），相應(yīng)的多項(xiàng)式ri（x）與Li（x）滿足：

　　ri（x）A（x）+Li（x）S（x）=Ri（x）（8）

　　當(dāng)i階余式Ri（x）的階數(shù)小于t時(shí)，迭代算法結(jié)束。算法結(jié)束時(shí)的Ri（x）即為錯(cuò)誤特征多項(xiàng)式ω（x），而Li（x） 即為所求的錯(cuò)誤位置多項(xiàng)式δ（x）。

　　ME算法在每迭代時(shí)進(jìn)行的運(yùn)算為：

　　單級(jí)迭代電路結(jié)構(gòu)如圖3所示。

　　由ME算法推導(dǎo)可知，使用脈動(dòng)電路結(jié)構(gòu)實(shí)現(xiàn)ME算法時(shí)，至多使用2級(jí)迭代電路即可降低R（x）多項(xiàng)式階數(shù)1階。因此，脈動(dòng)電路結(jié)構(gòu)采用32階流水結(jié)構(gòu)電路即可保證迭代算法完成收斂得到結(jié)果。電路結(jié)構(gòu)如圖4所示。

　　2.3 錢搜索和Forney算法

　　錢搜索模塊接收KES模塊的錯(cuò)誤位置多項(xiàng)式信號(hào)δ（x），利用錢搜索算法逐個(gè)檢查符號(hào)位是否發(fā)生錯(cuò)誤，輸出錯(cuò)誤位置和錯(cuò)誤位置多項(xiàng)式的奇數(shù)項(xiàng)之和，供EE模塊計(jì)算錯(cuò)誤圖案和糾錯(cuò)。

　　設(shè)錯(cuò)誤位置多項(xiàng)式δ（x）可以表達(dá)為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)之和：

　　并行錢搜索電路子結(jié)構(gòu)如圖5所示。圖中m表示并行模塊編號(hào)數(shù)，m=1，2，…，8。所有的乘法器均是常數(shù)乘法器，8倍并行結(jié)構(gòu)由圖5所示的8個(gè)同樣的結(jié)構(gòu)組成。

　　EE（錯(cuò)誤值計(jì)算）模塊根據(jù)CS模塊輸出的δodd（x）以及KES模塊輸出的ω（x）計(jì)算出錯(cuò)誤圖案。

　　EE模塊需要求解w（ai），電路結(jié)構(gòu)推導(dǎo)過程和求解δ（ai）的過程一樣，電路結(jié)構(gòu)也基本相同，這里不再累述。

　　3  仿真驗(yàn)證與綜合

　　上述譯碼器采用自頂向下的設(shè)計(jì)流程劃分模塊，用Verilog HDL完成RTL代碼的編寫，然后在Mentor公司的ModelSim SE 6.1b仿真驗(yàn)證工具下編寫測(cè)試代碼進(jìn)行仿真驗(yàn)證。仿真結(jié)果如圖6所示，譯碼器能正確實(shí)現(xiàn)譯碼功能。

　　因本譯碼器可糾正16個(gè)錯(cuò)誤，超過16個(gè)錯(cuò)誤便不可糾正，在仿真時(shí)譯碼輸入樣本采用了2種：一種樣本不超過16個(gè)錯(cuò)誤，另一種樣本超過16個(gè)錯(cuò)誤。仿真結(jié)果表明，此譯碼器能在不超過16個(gè)錯(cuò)誤的樣本下正常譯碼。

　　譯碼器在Quartus II 8.0上進(jìn)行綜合和優(yōu)化，采用Altera公司Cyclone系列的EP2C15AF256C8芯片為目標(biāo)器件。譯碼器的工作時(shí)鐘頻率可達(dá)85 MHz，數(shù)據(jù)吞吐率可達(dá)5 440 Mb／s，占用邏輯單元數(shù)為13 947個(gè)（片內(nèi)共14 448，占用率為97％），RAM占用16 698位（片內(nèi)共239 616位，占用率為7％）。譯碼器性能對(duì)比如表1所列。

　　本文所采用的并行流水譯碼結(jié)構(gòu)在增加了不到3倍的硬件資源的情況下，吞吐率時(shí)鐘比（吞吐率／時(shí)鐘）提高了8倍，且縮短了3／4的澤碼延遲。