張鵬泉，曹曉冬，范玉進(jìn)，褚孝鵬，劉　博

（天津光電集團(tuán)公司，300211）

一種基于FPGA的RS編譯碼器設(shè)計(jì)與實(shí)現(xiàn)

張鵬泉，曹曉冬，范玉進(jìn)，褚孝鵬，劉博

（天津光電集團(tuán)公司，300211）

RS碼是線性分組碼中具有很強(qiáng)糾錯(cuò)能力的多進(jìn)制BCH碼，其在糾正隨機(jī)錯(cuò)誤和突發(fā)錯(cuò)誤方面非常有效，因此被廣泛應(yīng)用于通信和數(shù)據(jù)存儲(chǔ)系統(tǒng)。本文提出了一種實(shí)現(xiàn)復(fù)雜度低、高效率的RS編譯碼器實(shí)現(xiàn)電路，包含RS編碼器、Horner準(zhǔn)則的伴隨式計(jì)算、BM算法、Chien搜索等模塊，以RS（15，9）為例運(yùn)用VHDL在ISE14.6軟件環(huán)境下進(jìn)行了功能仿真，結(jié)果與Matlab得到的理論結(jié)果一致。該方法適用于任意長度的RS編碼，有著重要的應(yīng)用價(jià)值。

Reed-Solomon碼；伽羅華域；BM算法；Chien搜索

0　引言

信號(hào)在傳輸過程中，可能會(huì)由于受到干擾或信道傳輸特性不理想等方面的原因?qū)е滦盘?hào)發(fā)生錯(cuò)誤，從而收到錯(cuò)誤的信息，所以為了保障數(shù)字信號(hào)在傳輸過程中的可靠性，我們需要對原始信息進(jìn)行信道編碼。RS碼由里得（Reed）和所羅門（Solomon）應(yīng)用MS多項(xiàng)式于1960年構(gòu)造出來，是一類具有很強(qiáng)糾錯(cuò)能力的編碼，是二進(jìn)制BCH碼的多進(jìn)制推廣，建立在GF（q）（q＞2，q屬于正整數(shù)）有限域上，且RS碼是MDS碼，具有極大最小距離特性，它不僅可以糾正突發(fā)錯(cuò)誤，還可以糾正隨機(jī)錯(cuò)誤，其卓越的糾錯(cuò)能力使得它在工程應(yīng)用中引人注目，已被多個(gè)國際、國內(nèi)標(biāo)準(zhǔn)采用。RS碼主要應(yīng)用于實(shí)時(shí)性較高的移動(dòng)通信系統(tǒng)、深空通信、數(shù)字衛(wèi)星電視、磁記錄系統(tǒng)等方面。RS碼已成為美國航天局（NASA）和歐洲空間局（ESA）在深空通信級(jí)聯(lián)系統(tǒng)中采用的標(biāo)準(zhǔn)碼。

1　RS編碼原理及實(shí)現(xiàn)

在GF（qm）域中，m=1的q進(jìn)制BCH碼稱為RS碼，RS編碼的表示形式為RS（n，k）。令α為GF（q）中的本原元，糾正t個(gè)錯(cuò)誤的RS碼的生成多項(xiàng)式g（X）以為其全部的根。由于是GF（q）中的元素，因此其最小多項(xiàng)式φi（X）即為X-。糾正t個(gè)錯(cuò)誤的q進(jìn)制RS碼的生成多項(xiàng)式為：g（ X）=LCM｛φ1（X），φ2（X），…，φ2t（X ）｝將X-帶入φi（X）得到：

其中g(shù)i∈GF（q） 0≤i＜2t 。由于是Xq-1-1的根，因此Xq-1-1能夠被g（X）整除。所以g（X）將生成恰好具有2t個(gè)奇偶校驗(yàn)符號(hào)、長度為n=q-1的q進(jìn)制循環(huán)碼，且由BCH界可知，該碼的最小距離至少為2t+1。以RS（15，9）為例，其編碼參數(shù)如下：

碼長n=15；信息位個(gè)數(shù)k=9；校驗(yàn)位：n-k =2t=6；糾錯(cuò)能力t=3；最小碼距δ=2t +1=7；

本原多項(xiàng)式：p（ X）=X4+X+1；

圖 1 RS編碼電路

碼生成多項(xiàng)式：g（ X）=X6+7X5+9X4+3X3+12X2+10X +12 RS編碼的方法是令編碼信息為：a（ X）=a+a X+a X2+…+aXk-1其中k=n-2t，在系統(tǒng)碼形式下，2t個(gè)奇偶校驗(yàn)符號(hào)恰是信息多項(xiàng)式X2ta（ X ）除以生成多項(xiàng)式得到的余式：b（ X）=b+b X+b X2+…+bX2t-1的系數(shù)。在硬件實(shí)現(xiàn)中，這可以通過圖1所示的除法電路來完成。

編碼時(shí)，信息位分為兩路送電路中，一路直接送入編碼結(jié)果，一路送入除法電路并進(jìn)行移位，k個(gè)時(shí)鐘結(jié)束后，信息位全部輸入，完成除法功能，此時(shí)移位寄存器中保留了余式b（x）的系數(shù)，即為校驗(yàn)位。再經(jīng)過2t個(gè)時(shí)鐘后數(shù)據(jù)全部移出，得到2t個(gè)校驗(yàn)位，接在k個(gè)信息位后，得到RS編碼。

2　RS譯碼原理及實(shí)現(xiàn)

RS的時(shí)域譯碼可分為4步：1） 根據(jù)接收碼多項(xiàng)式R（x）計(jì)算伴隨式S（x）；2） 用BM算法求解錯(cuò)誤位置多項(xiàng)式σ（x）的系數(shù)；3） 用Chien搜索算法求錯(cuò)誤位置多項(xiàng)式σ（x）的根；4） 計(jì)算錯(cuò)誤值與錯(cuò)誤位置并進(jìn)行糾錯(cuò)。迭代譯碼的關(guān)鍵在于運(yùn)用BM算法和Chien搜索電路加快求解σ（x），下面將詳細(xì)介紹。

2.1伴隨式計(jì)算模塊

式中b0=0表示初始化時(shí)所有寄存器置0。圖2位計(jì)算伴隨式系數(shù)的實(shí)現(xiàn)電路，15個(gè)時(shí)鐘周期后可接收完所有15個(gè)符號(hào)，同時(shí)得到全部6個(gè)伴隨式系數(shù)。

2.2BM迭代算法

2.3Chien搜索算法

在RS碼的譯碼過程中，求σ（X）的根的目的是判斷碼元出錯(cuò)的位置，Chien搜索實(shí)際上是一種試探性窮舉的計(jì)算方法，逐個(gè)試探各個(gè)碼元位置是否有錯(cuò)。對于（n，k）RS碼，要判斷第i位是否出錯(cuò)，相當(dāng)于要確定是否是錯(cuò)誤未知數(shù)，即檢驗(yàn)α-i是不是錯(cuò)誤位置多項(xiàng)式σ（X）的根。若σ（ α-i）=0或，則第i位為錯(cuò)誤位置，在譯碼過程中，依次檢查α-i是否是錯(cuò)誤位置多項(xiàng)式σ（X ）的根就是Chien搜索過程。Chien搜索可以用圖3所示電路結(jié)構(gòu)實(shí)現(xiàn)。

從緩存中讀取第一個(gè)碼元Rn-1前，t個(gè)乘法器執(zhí)行乘法運(yùn)算后移位，且保存σiαi，并送入求和判斷模塊，若和為-1，則判斷模塊輸出，從接受碼元中減去相應(yīng)的錯(cuò)誤值yn-1，實(shí)現(xiàn)對該碼元的糾錯(cuò)譯碼。在譯完第一個(gè)碼元Rn-1后，再進(jìn)行乘法運(yùn)算，存儲(chǔ)σiαi，然后由求和判斷模塊決定輸出。依此類推，直到最后一個(gè)碼元R0的譯碼。

綜上所述，RS碼的BM-Chien譯碼器的結(jié)構(gòu)設(shè)計(jì)如圖4所示。

3　仿真結(jié)果

圖 2 RS伴隨式計(jì)算電路

圖 3 Chien搜索電路

RS（15，9）編解碼器及所有模塊均在Xilinx公司的ISE14.6開發(fā)環(huán)境中成功調(diào)試和綜合下載，器件選用Xilinx公司Spartan6系列中的XC6SLX9，仿真工具采用ISIM。編解碼系統(tǒng)仿真中的輸入輸出均為流水線工作模式，在譯碼仿真中已加入誤碼測試糾錯(cuò)能力，仿真結(jié)果如圖5圖6所示。

編碼前的數(shù)據(jù)由高位到地位送入din端口，im是輸入有效信號(hào)，oe是輸出有效信號(hào)，從im置1的第n個(gè)時(shí)鐘后編碼完成，得到結(jié)果與Matlab仿真結(jié)果對比，完全一致，證明編碼正確。

在輸入有效后的第n+4t+7個(gè)時(shí)鐘后開始輸出譯碼結(jié)果，en為輸出有效信號(hào)，譯碼之后的輸出數(shù)據(jù)dout與din相同，且能夠糾正之前加入的誤碼。

4　總結(jié)

RS編碼的所有運(yùn)算都是建立在有限域v的基礎(chǔ)上的，其中除法電路的設(shè)計(jì)、BM迭代算法和Chien搜索是核心模塊。本文實(shí)現(xiàn)了以（15，9）為例的RS編解碼設(shè)計(jì)與仿真，仿真的輸出結(jié)果與理論分析一致，且基于相同原理，本方法可實(shí)現(xiàn)任意長度的RS編解碼設(shè)計(jì)。

［1］ 曹雪虹，張宗橙. 信息論與編碼［M］. 清華大學(xué)出版社，2005.

［2］ ShuLin Jr，何元智. 差錯(cuò)控制編碼［M］. 機(jī)械工業(yè)出版社，2007.

［3］ 張宗橙. 糾錯(cuò)編碼原理和應(yīng)用［M］. 電子工業(yè)出版社，2005.

［4］ 劉東華，向良軍. 信道編碼與Matlab仿真［M］. 電子工業(yè)出版社，2014.

Design and implementation of a RS encoder and decoder based on FPGA

Zhang Pengquan，Cao Xiaodong，F(xiàn)an Yujin，Zhu Xiaopeng，Liu Bo
（Tianjin photoelectric group company 300211）

RS code is a linear block code with a strong error correction ability of the multi band BCH code，which is very effective in correcting random errors and burst errors，so it is widely used in communication and data storage systems. In this paper， the results are consistent with a theory to achieve low complexity and high efficiency of the RS compiled code realization circuit，with computing，BM algorithm，Chien search module that contains a RS encoder， Horner criteria，to RS （15，9） as an example using VHDL in ISE14.6 software under the environment of the function simulation，the results with MATLAB software.This method can be applied to any length RS code， and it has important application value.

Reed-Solomon code； Galois field； BM algorithm；Chien search

圖 4 RS碼譯碼器硬件結(jié)構(gòu)圖

圖5　RS編碼仿真結(jié)果

圖 6 RS譯碼仿真結(jié)果