苗 鑫，鄧 攀，殷奎喜

（南京師范大學(xué) 物理科學(xué)與技術(shù)學(xué)院，江蘇 南京210046）

基于CycloneIII構(gòu)成的RS編碼系統(tǒng)

苗 鑫，鄧 攀，殷奎喜

（南京師范大學(xué) 物理科學(xué)與技術(shù)學(xué)院，江蘇 南京210046）

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

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

R-S碼是用其發(fā)明人的名字Reed和Solomon命名的。它是一類具有很強(qiáng)糾錯能力的多進(jìn)制BCH碼，既可以糾正突發(fā)錯誤，也可以糾正隨機(jī)錯誤。目前，RS編碼作為許多通信系統(tǒng)的重要編碼方式，已經(jīng)在數(shù)字通信、數(shù)字視頻廣播、衛(wèi)星通信等領(lǐng)域得到廣泛的應(yīng)用?，F(xiàn)代通信系統(tǒng)中，糾錯碼技術(shù)是實現(xiàn)可靠通信的基本方法。RS（255，223）碼被CCSDS選為常規(guī)分包遙測信道糾錯編碼和高級在軌系統(tǒng)前向和反向鏈路的糾錯編碼，是實現(xiàn)CCSDS標(biāo)準(zhǔn)低差率信道糾錯編碼的關(guān)鍵部件。

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

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

圖1 編譯碼系統(tǒng)圖Fig.1 Encoding and decoding system diagram

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

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

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

設(shè)輸入的信息序列為

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

生成的碼字為

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

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

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

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

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

2 RS（255，223）編碼實現(xiàn)

2.1 GF（256）域的算術(shù)運(yùn)算

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

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

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

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

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

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

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

2.2 RS（255，223）編碼器的 FPGA 實現(xiàn)

2.2.1 GF（256）域乘法的FPGA實現(xiàn)

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

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

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

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

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

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

由乘積多項式系數(shù)和取模后的多項式c（x）對應(yīng)的關(guān)系為

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

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

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

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

2.2.2 RS（255，223）編碼器的 FPGA 實現(xiàn)

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

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

圖 3 RS（255，223）編碼器電路結(jié)構(gòu)Fig.3 RS （255，223） encoder circuit

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

3 RS（255，233）編碼仿真實現(xiàn)

本系統(tǒng)設(shè)計是在Quartus II9.0環(huán)境下，使用Verilog_HDL語言描述整個編碼器模型，并且以Altera公司生產(chǎn)的EP3C10E144C8N FPGA芯片作為硬件平臺進(jìn)行實現(xiàn)。

系統(tǒng)設(shè)計端口定義：

clk:芯片時鐘信號，編碼器在其上升沿處進(jìn)行數(shù)據(jù)采樣并進(jìn)行編碼運(yùn)算。

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

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

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

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

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

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

圖4 編譯結(jié)果Fig.4 Compiles the results

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

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

編碼系統(tǒng)在前223個字符信息輸入時，直接輸出x端得數(shù)據(jù)信息字符。此外，由于芯片內(nèi)部的寄存器延遲效應(yīng)，y端較x端滯后一個時鐘周期；當(dāng)223個字符信息（十六進(jìn)制為DF）輸出完畢后，有效字符輸入控制信號data值由1變成0，編碼系統(tǒng)開始進(jìn)入冗余校驗信息輸出階段，編碼系統(tǒng)完成輸出接收到的數(shù)據(jù)信息字符后，緊接著輸出32個校驗字符。輸出數(shù)據(jù)字符是從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 結(jié)束語

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

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

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

[3]王金明.數(shù)字系統(tǒng)設(shè)計與Verilog HDL[M].北京：電子工業(yè)出版社，2011.

[4]田耕，徐文波，張延偉.無線通信FPGA設(shè)計[M].北京：電子工業(yè)出版社，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]許春風(fēng)，李健，武文紅.基于FPGA的RS（255，223）編碼器的設(shè)計[J].微計算機(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實現(xiàn)[J].無線通信技術(shù)，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實現(xiàn)[D].南京：東南大學(xué)，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—），男，江蘇南京人，碩士研究生。研究方向：電路與系統(tǒng)。