基于FPGA的RS(255，239)編譯碼器

摘要 RS(Reed—Solomon)編碼是一種具有較強(qiáng)糾錯(cuò)能力的多進(jìn)制BCH編碼，其既可糾正隨機(jī)錯(cuò)誤，又可糾正突發(fā)錯(cuò)誤。RS編譯碼器廣泛應(yīng)用于通信和存儲(chǔ)系統(tǒng)，為解決高速存儲(chǔ)器中數(shù)據(jù)可靠性的問(wèn)題，文中提出了RS編碼的實(shí)現(xiàn)方法，并對(duì)編碼進(jìn)行了時(shí)序仿真。仿真結(jié)果表明，該譯碼器可實(shí)現(xiàn)良好的糾錯(cuò)功能。

RS(Reed—Solomon)碼是差錯(cuò)控制領(lǐng)域中的一種重要線性分組碼，既能糾正隨機(jī)錯(cuò)誤，又能糾正突發(fā)錯(cuò)誤，且由于其出色的糾錯(cuò)能力，已被NASA、ESA、CCSDS等空間組織接受，用于空間信道糾錯(cuò)。本文研究了RS碼的實(shí)現(xiàn)方法，并基于Xilinx的FPGA芯片Spartan-6 XC6SLX45完成了RS編譯碼器的設(shè)計(jì)，同時(shí)對(duì)其進(jìn)行了仿真和在線調(diào)試，并給出了功能仿真圖和測(cè)試結(jié)果。時(shí)序仿真結(jié)果表明，該編譯碼器能實(shí)現(xiàn)預(yù)期功能。

1 RS編碼的實(shí)現(xiàn)方法

RS碼是一種多進(jìn)制BCH(Bose—Chaudhuri—Hocquenghem)碼，在給定每個(gè)碼字所具有多少冗余量的情況下，RS碼具有極大的最小距離。即RS碼的最小距離d、信息長(zhǎng)度k以及碼字長(zhǎng)度n滿足d=n-k+1。而RS(255 239)碼是在伽羅華(Galois Field)GF(28)中運(yùn)算得到的，編碼器實(shí)現(xiàn)的關(guān)鍵是伽羅華域乘法器的設(shè)計(jì)。設(shè)計(jì)中的乘法是2個(gè)有限域中元素的指數(shù)相加與255取模。GF(28)編碼參數(shù)如下：碼長(zhǎng)n=255;信息位個(gè)數(shù)k=239;校驗(yàn)位r=n-k=16;糾錯(cuò)能力t=8;碼距d=17。生成多項(xiàng)式為

根據(jù)式(3)畫(huà)出RS編碼的電路圖，如圖1所示。

n-k級(jí)RS編碼器主要由一組線性反饋移位寄存器和控制電路組成，其是n-k=16級(jí)編碼器，亦是線性反饋寄存器的反饋系數(shù)，reg16寄存器的值與當(dāng)前輸入的信息碼元異或得到的結(jié)果即為feedback寄存器的值。

編碼步驟：

步驟1 將所有寄存器清零，開(kāi)關(guān)放到1上，則239個(gè)信息碼元一邊依次進(jìn)入除法電路，一邊依次輸出。

步驟2 當(dāng)最后一個(gè)信息碼進(jìn)入電路后，將開(kāi)關(guān)放到2上，第一個(gè)校驗(yàn)位輸出。

步驟3 校驗(yàn)碼按時(shí)鐘節(jié)拍載入寄存器，并依次輸出。當(dāng)最后一個(gè)校驗(yàn)位輸出時(shí)，編碼結(jié)束。

2 RS編碼的仿真結(jié)果及分析

設(shè)計(jì)的RS(255 239)編碼器使用Verilog HDL對(duì)整個(gè)模型進(jìn)行描述，以Xilinx FPGA芯片Spartan-6XC6SLX45為硬件平臺(tái)進(jìn)行實(shí)現(xiàn)，并利用ISim仿真工具對(duì)RS編碼進(jìn)行仿真。

設(shè)計(jì)的RS(255，239)編碼器，信息位239位編碼為0，1，2，…，238，則16位校驗(yàn)位的值為58，236，152，44，88，31，20，168，121，60，32，10，191，166，4，101。設(shè)計(jì)的RS(255，239)編碼器的仿真圖如圖2所示，當(dāng)DI_VAL=0時(shí)，輸出239個(gè)信息位;當(dāng)DI_VAL=1時(shí)，輸出16個(gè)校驗(yàn)位。該編碼器實(shí)現(xiàn)了預(yù)期的編碼功能。

3 RS譯碼的實(shí)現(xiàn)方法

RS譯碼主要有時(shí)域譯碼和頻域譯碼，時(shí)域譯碼一般采用BM迭代算法或歐式算法(Euclid's Algorithm)。RS譯碼中最重要的環(huán)節(jié)是求解關(guān)鍵方程，歐式算法在求解關(guān)鍵方程時(shí)需進(jìn)行多項(xiàng)式次數(shù)的判斷，因此造成硬件電路復(fù)雜，譯碼速度下降，BM迭代算法具有快速、消耗資源少、控制電路較為簡(jiǎn)單等優(yōu)點(diǎn)。文中改進(jìn)后的BM迭代原理及以該算法為基礎(chǔ)的RS譯碼器的FPGA實(shí)現(xiàn)。RS譯碼可分為4步：(1)由接收到的碼組計(jì)算伴隨式。(2)求關(guān)鍵方程。(3)計(jì)算出錯(cuò)誤圖樣。(4)由錯(cuò)誤圖樣和接收碼組計(jì)算出可能發(fā)送的碼字。圖3給出了RS譯碼器的一般步驟框圖。

設(shè)錯(cuò)誤圖樣為E(x)，則R(x)=C(x)+E(x)。RS碼的譯碼可分為3步：(1)由接收到的R(x)計(jì)算出伴隨多項(xiàng)式S。(2)由伴隨式計(jì)算出錯(cuò)誤圖樣E(x)。(3)由C(x)=及(x)-E(x)計(jì)算得到發(fā)送碼字，并完成譯碼。伴隨式是對(duì)接收序列R(x)進(jìn)行奇偶校驗(yàn)的結(jié)果，用以判斷R(x)是否為有效碼字，若R(x)為有效碼字則伴隨式S為零，任何S的非零值表示R(x)有錯(cuò)誤。為譯出一個(gè)糾正t個(gè)錯(cuò)誤的RS碼，伴隨式S是2t重的，即S=(s1，s2，…，s2t-1，s2t)。

以上運(yùn)算均可用流水線結(jié)構(gòu)硬件實(shí)現(xiàn)。

初始化時(shí)，所有寄存器置零。經(jīng)255個(gè)周期，接收完所有255個(gè)符號(hào)后，便可得到全部16個(gè)伴隨式。因整個(gè)譯碼器采用流水線結(jié)構(gòu)，所以在伴隨式計(jì)算完后，產(chǎn)生一個(gè)時(shí)鐘周期有效的“sc_done”信號(hào)，用以啟動(dòng)后續(xù)電路進(jìn)行新的計(jì)算。由于在BM模塊中，用到了A(x)與S的卷積求和，因此本模塊將計(jì)算出的伴隨式序列串行輸出。

關(guān)鍵方程的計(jì)算采用BM算法，BM算法不僅在RS碼的譯碼中起著關(guān)鍵作用，且也是目前已知的求序列線性復(fù)雜度最快且最佳的方法之一。該算法采用規(guī)整的脈動(dòng)陣列，硬件實(shí)現(xiàn)更為方便。通過(guò)求解關(guān)鍵方程，得到A0～A8，其為后續(xù)的Chien搜索模塊提供了參數(shù)。

A(x)可用來(lái)搜索錯(cuò)誤位置，具體方法為：依次將

，則在該位置出現(xiàn)誤碼。Chien搜索模塊框圖如圖5所示。

從上式可看出，兩個(gè)多項(xiàng)式的相乘實(shí)質(zhì)就是兩個(gè)多項(xiàng)式對(duì)應(yīng)的系數(shù)卷積求和。因此，該運(yùn)算也可采用FIR濾波技術(shù)來(lái)實(shí)現(xiàn)，當(dāng)初始化時(shí)，所有寄存器置零。然后每個(gè)時(shí)鐘周期，伴隨式從S1，S2，…，S2t依次移入寄存器。最終2t個(gè)Ωi移位寄存器的內(nèi)容從左向右依次為Ω2t-1，…，Ω1，Ω0。錯(cuò)誤多項(xiàng)式可得，整個(gè)譯碼過(guò)程如圖6所示。

該過(guò)程完全實(shí)現(xiàn)流水線結(jié)構(gòu)，其中包括伴隨式計(jì)算、關(guān)鍵方程求解、Chien搜索、Forney算法等模塊并行工作。在經(jīng)過(guò)295個(gè)固有延遲后，每個(gè)時(shí)鐘周期均可連續(xù)輸出經(jīng)校正的碼字。

4 RS譯碼的仿真結(jié)果及分析

因設(shè)計(jì)的譯碼器最大糾錯(cuò)能力為8個(gè)符號(hào)，該文設(shè)定錯(cuò)誤情況是第140位到第147位全錯(cuò)，正確值為140，141，142，143，144，145，146，147，錯(cuò)誤值為5，11，56，98，35，15，132，159，圖7是輸入到譯碼器中含8個(gè)連續(xù)錯(cuò)誤碼字的255位編碼序列，圖8是譯碼器輸出全部糾錯(cuò)以后的編碼序列，由ISim仿真波形圖可知，Err_Indicator表示錯(cuò)誤標(biāo)志，設(shè)計(jì)的譯碼器能實(shí)現(xiàn)最大的糾錯(cuò)能力。

FPGA的RS(255，239)編譯碼器" width="392" height="96" />

5 結(jié)束語(yǔ)

文中闡述了RS(255,239)編譯碼器的設(shè)計(jì)原理，并對(duì)編碼器給出了在ISim中的時(shí)序仿真結(jié)果，其結(jié)果證明了該編碼器設(shè)計(jì)的正確性。而在對(duì)譯碼器的設(shè)計(jì)中，假定出現(xiàn)連續(xù)8個(gè)誤碼的情況，并用ISim對(duì)所設(shè)計(jì)的譯碼器進(jìn)行驗(yàn)證，由時(shí)序仿真結(jié)果表明，設(shè)計(jì)的RS(255,239)譯碼器能實(shí)現(xiàn)最大的糾錯(cuò)能力。設(shè)計(jì)的RS(255,239)編譯碼器達(dá)到了預(yù)定的目標(biāo)，且該編譯碼器可應(yīng)用于數(shù)據(jù)通信和數(shù)據(jù)存儲(chǔ)系統(tǒng)的差錯(cuò)控制中。