一種基于FPGA的RS編譯碼器設計與實現

張鵬泉，曹曉冬，范玉進，褚孝鵬，劉　博

（天津光電集團公司，300211）

一種基于FPGA的RS編譯碼器設計與實現

張鵬泉，曹曉冬，范玉進，褚孝鵬，劉博

（天津光電集團公司，300211）

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

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

0　引言

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

1　RS編碼原理及實現

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

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

碼長n=15；信息位個數k=9；校驗位：n-k =2t=6；糾錯能力t=3；最小碼距δ=2t +1=7；

本原多項式：p（ X）=X4+X+1；

圖 1 RS編碼電路

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

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

2　RS譯碼原理及實現

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

2.1伴隨式計算模塊

式中b0=0表示初始化時所有寄存器置0。圖2位計算伴隨式系數的實現電路，15個時鐘周期后可接收完所有15個符號，同時得到全部6個伴隨式系數。

2.2BM迭代算法

2.3Chien搜索算法

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

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

綜上所述，RS碼的BM-Chien譯碼器的結構設計如圖4所示。

3　仿真結果

圖 2 RS伴隨式計算電路

圖 3 Chien搜索電路

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

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

在輸入有效后的第n+4t+7個時鐘后開始輸出譯碼結果，en為輸出有效信號，譯碼之后的輸出數據dout與din相同，且能夠糾正之前加入的誤碼。

4　總結

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

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

［2］ ShuLin Jr，何元智. 差錯控制編碼［M］. 機械工業出版社，2007.

［3］ 張宗橙. 糾錯編碼原理和應用［M］. 電子工業出版社，2005.

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

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

Zhang Pengquan，Cao Xiaodong，Fan 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碼譯碼器硬件結構圖

圖5　RS編碼仿真結果

圖 6 RS譯碼仿真結果