基于CycloneIII構成的RS編碼系統

苗 鑫，鄧 攀，殷奎喜

（南京師范大學 物理科學與技術學院，江蘇 南京210046）

基于CycloneIII構成的RS編碼系統

苗 鑫，鄧 攀，殷奎喜

（南京師范大學 物理科學與技術學院，江蘇 南京210046）

本文采用Altera公司的FPGA器件Cyclone III系列EP3C10作為核心器件構成了R-S（255，223）編碼系統；利用Quartus II 9.0作為硬件仿真平臺，用硬件描述語言Verilog_HDL實現編程，并且通過JTAG接口與EP3C10連接。R-S（Reed-Solomon）碼是一類糾錯能力很強的特殊的非二進制BCH碼，能應對隨機性和突發性錯誤，廣泛應用于各種通信系統中和保密系統中。R-S（255，223）碼能夠檢測32字節長度和糾錯16字節長度的連續數據錯誤信息。

Cyclone III；Quartus II 9.0；Verilog_HDL；R-S（255，223）碼

R-S碼是用其發明人的名字Reed和Solomon命名的。它是一類具有很強糾錯能力的多進制BCH碼，既可以糾正突發錯誤，也可以糾正隨機錯誤。目前，RS編碼作為許多通信系統的重要編碼方式，已經在數字通信、數字視頻廣播、衛星通信等領域得到廣泛的應用。現代通信系統中，糾錯碼技術是實現可靠通信的基本方法。RS（255，223）碼被CCSDS選為常規分包遙測信道糾錯編碼和高級在軌系統前向和反向鏈路的糾錯編碼，是實現CCSDS標準低差率信道糾錯編碼的關鍵部件。

目前，隨著大規模、超大規模集成電路的發展，現場可編程門陣列（FPGA）技術得到迅速的發展和廣泛的應用，其資源容量、工作頻率以及集成度都有很大的提高，基于FPGA實現的編解碼器便更具有優點，有著頻率分辨率較高，運算速度更快，性價比更高的優點。本文便是使用Altera公司的FPGA器件CycloneIII系列EP3C10作為核心器件。應用Verilog HDL這樣一種應用廣泛的硬件描述語言，也為實現硬件編程提供了很好的方法。RS編譯碼系統如圖1所示。

1 RS（255，223）編解碼原理

圖1 編譯碼系統圖Fig.1 Encoding and decoding system diagram

RS編碼是在代數編碼理論的總體理論框架上實現編碼過程的，中心思想是將原始數據流映射到抽象的代數多項式上，在映射的過程進行一系列的數學運算。若有有限個符號，其數目是一個素數的冪，并且定義有加法和乘法，則稱這個有限符號的域為有限域。若有限域中的符號數目為2m，則稱此有限域為伽羅華域，記為GF（2m）。

對于一個（n，k，t）RS 碼，表示此生成碼長n=2m-1 個符號或m（2m-1）比特，且RS編碼碼字中有k個數據信息符號或km比特數據，能監督n-k=2t個符號或m（n-k）比特數據或者糾正數據傳輸和處理中產生的t個符號錯誤或mt比特數據錯誤，最小碼距d=2t+1個符號或m（2t+1）比特，每個符號是m比特。

RS（255，223）碼是多進制BCH碼，編碼器將每接收 223字節的串行字符數據信息塊，編碼為255字節的碼字信息。碼字信息由223字節長度的數據塊和32字節長度的編碼校驗信息塊組成，能夠檢測和糾錯16字節長度的連續數據錯誤信息。

設輸入的信息序列為

k=223，mk-i為伽羅華域 GF（255）中的域元素，代表的是RS（255，223）碼中的數據信息，xk-i僅是數據碼元位置的標記。例如mk-1表示第223個數據的大小，xk-1表示第223個數據位置。

生成的碼字為

n=255，表示編碼生成255字節長度的碼字信息，同樣cn-i代表是碼字信息大小，cn-i到ck是數據信息，ck-1到c0是校驗信息。

對于一個信息碼多項式，RS校驗碼生成多項式的一般形式為：

由校驗碼生成多項式就可以生成校驗碼信息r（x）。k0是偏移量，通常取0或1，剩余多項式r（x）滿足

將生成的剩余多項式加到信息多項式后就是生成的碼字信息。

所以，實現RS編碼首先明確，在RS碼的運算過程中，所有的加減乘除的運算都是定義在伽羅華域上的模2運算。采集進來的數據，查找已生成的GF（2m）域與二進制代碼對照表，把數據轉化成GF（2m）域元素。根據以上公式算出校驗碼，再將校驗碼追加到信息碼后，完成編碼。

2 RS（255，223）編碼實現

2.1 GF（256）域的算術運算

通常，GF（2m）域的算術運算可處理2m個元素，且m表示數據信息字符的位寬。例如ASDL系統使用的就是GF（256）域的算術運算，其初等多項式p（x）可用下列式子表示：

利用初等多項式可產生GF（2m）中任意D階多項式f（x）其他各階的項，例如：

表1是GF（256）域的全部元素。

由表1中可以看出，GF（28）的所有元素都可以利用1，α，…，α7的和來表示，將各表示多項式中的系數排列起來，可以實現GF（28）中所有元素的8 bit二進制表示。

表1 GF（28）的全部元素Tab.1 All elements of GF（28）

多項式的加減乘除可以轉移到有限域上元素的加法和乘法運算，有限域上的加法和乘法遵循一定的法則，即加法遵循異或法則，乘法遵循與法則。例如GF（256）域上的兩個元素α2，α4相加，將α2和α4對應項進行模二加法，對應項進行異或運算；域上的元素乘法，遵循與法則，例如兩個元素α211，α223相乘，得到 α211·α223=α（211+233）mod255=α189。

GF（2m）域的任意多項式都可以利用其初等多項式得到一個唯一的 GF（2m）域中的對應多項式，因此，GF（2m）域的算術運算與 GF（2m）域相同。

2.2 RS（255，223）編碼器的 FPGA 實現

2.2.1 GF（256）域乘法的FPGA實現

GF（256）域乘法運算是編碼系統中最重要的算術運算，因此乘法運算的設計顯得尤為重要，其所占用FPGA芯片的資源和速度也就決定了編碼系統所占的資源和性能。本系統采用一種基于多項式乘法理論的8位串行乘法系統的設計方法，用Verilog_HDL硬件描述語言來描述乘法器的運算。

GF（256）域乘法運算算法可以表述為：將8位的乘數和被乘數用多項式表示，先按照多項式 乘法法則將此兩個多項式做乘法，再對乘積多項式按照以為底做取模運算，由于生成多項式已知，所以對其進行超前運算過后可以得到結果符號多項式各階系數對于輸入多項式的函數。

對于 GF（256）域的元素[7:0]a，[7:0]b，生成多項式為：

GF（256）域的元素[7:0]a，[7:0]b 多項式表示為：

將兩個有限域多項式按照多項式乘法規則作乘法，得到多項式：

將積多項式對生成多項式p（x）求模，可得化簡的及多項式為：

由乘積多項式系數和取模后的多項式c（x）對應的關系為

由上式可知，GF（256）域的乘法運算過程只使用到了異或邏輯和與邏輯，對應GF（2）域的加法運算和乘法運算。

端口定義：input[7:0]a:輸入的數據信息字符；input[7:0]b:輸入的生成多項式各項的加權系數；output[7:0]c:乘積輸出。

圖 2 GF（256）域的乘法Fig.2 GF （256） field multiplication

整個乘法計算過程只使用到了異或邏輯和與邏輯，對應GF（2）域的加法運算和乘法運算。

2.2.2 RS（255，223）編碼器的 FPGA 實現

RS（255，223）編碼器的生成多項式 g（x）為

RS（255，223）編碼器的電路主要部分有：線性反饋移位寄存器、有限域加法器、開關。該電路結構實際上是由32個加法器和32個乘法器構成的級聯電路，從時序設計的角度來說，RS（255，223）編碼器的電路結構具有32級流水線階段，每個階段包含了一個加法器、一個乘法器和一個D觸發器組。在RS（255，223）編碼器中，乘法器和加法器是主要的運算單元，因其所在域的特征為2.所以加法器可用異或邏輯來實現，乘法器是可用與邏輯來實現，因而大大的提高了硬件資源的使用效率。

圖 3 RS（255，223）編碼器電路結構Fig.3 RS （255，223） encoder circuit

Cyclone III是Altera公司開發的首款65 nm低成本FPGA，Cyclone III FPGA比競爭FPGA的功耗低75%，含有5 K至120 K邏輯單元（LE），比前一代產品每邏輯單元成本降低20%。使用Cyclone III來設計完成位寬為8 bit的RS（255，223）編碼系統，芯片資源和管腳資源都可以滿足其要求。

3 RS（255，233）編碼仿真實現

本系統設計是在Quartus II9.0環境下，使用Verilog_HDL語言描述整個編碼器模型，并且以Altera公司生產的EP3C10E144C8N FPGA芯片作為硬件平臺進行實現。

系統設計端口定義：

clk:芯片時鐘信號，編碼器在其上升沿處進行數據采樣并進行編碼運算。

clrn:編碼器異步復位控制信號。定義為1表示采樣數據有效，編碼器正常操作；定義為0表示采樣數據寄存器清零，編碼器復位清零。

enable:編碼器使能控制信號。定義為1表示芯片對輸入字符進行RS（255，223）編碼；定義為0表示編碼器繼續采樣，但不對其進行編碼。

data:有效字符輸入控制信號。定義為1表示輸入字符無效；定義為0表示輸入字符有效，編碼繼續進行。

x:數據信息塊得字符輸入端口，其位寬為8 bit。

y：編碼碼字輸出端口，其位寬為8 bit。

打開 Quartus II 9.0， 使用 File菜單中的 “New Project Wizard”命令創建一個工程，然后新建一個Verilog_HDL語言文件，輸入程序。編譯通過以后，創建波形仿真文件，加入輸入輸出信號，進行仿真得到編碼結果。

圖4 編譯結果Fig.4 Compiles the results

由編譯結果可以看出，RS（255，223）編碼使用 Cyclone III芯片的相關信息。芯片總的資源為10 320個邏輯單元，本設計使用了其中的303個；芯片總管腳有95個，本設計使用了其中的20個，占21%。

圖 5 RS（255，223）編碼系統仿真波形Fig.5 RS （255，223） coding system simulation waveform

編碼系統在前223個字符信息輸入時，直接輸出x端得數據信息字符。此外，由于芯片內部的寄存器延遲效應，y端較x端滯后一個時鐘周期；當223個字符信息（十六進制為DF）輸出完畢后，有效字符輸入控制信號data值由1變成0，編碼系統開始進入冗余校驗信息輸出階段，編碼系統完成輸出接收到的數據信息字符后，緊接著輸出32個校驗字符。輸出數據字符是從01到223，32個校驗碼字符為184，32，247，171，36，60，227，188，154，55，147，106，94，94，20 3，163，227，48，127，207，53，23，106，196，188，77，106，51，16 7，148，14，65.

4 結束語

目前，隨著電子技術的不斷發展，各個FPGA生產廠家都已有自己的IP核可以使用，例如，Altera公司提供的Reed-Solomon編譯器MegaCoreTM功能的IP核供給用戶使用。本文介紹了一種基于Altera公司Cyclone III系列的RS編解碼系統，可以實現 RS（255，223）的編解碼。

[1]樊昌信，曹麗娜.通信原理[M].6版.北京：國防工業出版社，2007.

[2]陳亮，楊吉斌，張雄偉.信號處理算法的實時DSP實現[M].北京：電子工業出版社，2008.

[3]王金明.數字系統設計與Verilog HDL[M].北京：電子工業出版社，2011.

[4]田耕，徐文波，張延偉.無線通信FPGA設計[M].北京：電子工業出版社，2008.

[5]CHANG Xiao-jun，GUO Jun，LI Zhi-hui.RS encoder design based on FPGA[C]//ICACC 2010，2010:419-421.

[6]YAN Lai-jin，LI Ming.Design and implementation of RS（255，223） decoder on FPGA[J].Control&Automation，2005（1）:76.

[7]Seroussi G A.systolic reed-solomon encoder[J].IEEE Trans information Theory，1991，37（4）:45-48.

[8]許春風，李健，武文紅.基于FPGA的RS（255，223）編碼器的設計[J].微計算機信息，2006，22（9）：175-176.

XU Chun-feng，LI Jian，WU Wen-hong.Design of the RS（255，223） encoder based on FPGA [J].Microcomputer Information ，2006，22（9）:175-176.

[9]張怡，韓維.高速RS編碼算法及FPGA實現[J].無線通信技術，2005（1）：23-30.

ZHANG Yi，HAN Wei.High speed reed-solomon encode algorithm and FPGA realization[J].Wireless Communications Technology，2005（1）:23-30.

[10]余旋.RS編碼的FPGA實現[D].南京：東南大學，2008.

A RS coding system based on Cyclone III

MIAO Xin，DENG Pan，YIN Kui-xi
（School of Physics and Technology of Nanjing Normal University，Nanjing210046，China）

This paper uses Altera company FPGA Cyclone III series EP3C10 devices as a core component of R-S （255223）coding system；Using Quartus II 9.0 as a hardware emulation platform， using hardware description language Verilog_HDL programming，and through the JTAG interface and EP3C10 connection.R-S （Reed-Solomon）code is a kind of special non binary BCH code which's error correction capability is very strong， can deal with random and burst error， widely used in all kinds of communication systems and security systems.R-S （255223）code is capable of detecting and correcting the length of 32 bytes 16 byte length of continuous data error information.

Cyclone III； Quartus II 9.0； Verilog_HDL； R-S（255，223） code

TN911.22

A

1674－6236（2012）04-0189-04

2011-12-21 稿件編號：201112121

苗 鑫（1987—），男，江蘇南京人，碩士研究生。研究方向：電路與系統。