苗 鑫，鄧 攀，殷奎喜

（南京師范大學(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作為硬件仿真平臺(tái)，用硬件描述語言Verilog_HDL實(shí)現(xiàn)編程，并且通過JTAG接口與EP3C10連接。R-S（Reed-Solomon）碼是一類糾錯(cuò)能力很強(qiáng)的特殊的非二進(jìn)制BCH碼，能應(yīng)對(duì)隨機(jī)性和突發(fā)性錯(cuò)誤，廣泛應(yīng)用于各種通信系統(tǒng)中和保密系統(tǒng)中。R-S（255，223）碼能夠檢測(cè)32字節(jié)長(zhǎng)度和糾錯(cuò)16字節(jié)長(zhǎng)度的連續(xù)數(shù)據(jù)錯(cuò)誤信息。

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

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

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

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

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

RS編碼是在代數(shù)編碼理論的總體理論框架上實(shí)現(xiàn)編碼過程的，中心思想是將原始數(shù)據(jù)流映射到抽象的代數(shù)多項(xiàng)式上，在映射的過程進(jìn)行一系列的數(shù)學(xué)運(yùn)算。若有有限個(gè)符號(hào)，其數(shù)目是一個(gè)素?cái)?shù)的冪，并且定義有加法和乘法，則稱這個(gè)有限符號(hào)的域?yàn)橛邢抻颉Ｈ粲邢抻蛑械姆?hào)數(shù)目為2m，則稱此有限域?yàn)橘ち_華域，記為GF（2m）。

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

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

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

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

生成的碼字為

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

對(duì)于一個(gè)信息碼多項(xiàng)式，RS校驗(yàn)碼生成多項(xiàng)式的一般形式為：

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

將生成的剩余多項(xiàng)式加到信息多項(xiàng)式后就是生成的碼字信息。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對(duì)于 GF（256）域的元素[7:0]a，[7:0]b，生成多項(xiàng)式為：

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

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

將積多項(xiàng)式對(duì)生成多項(xiàng)式p（x）求模，可得化簡(jiǎn)的及多項(xiàng)式為：

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

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

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

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

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

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

RS（255，223）編碼器的生成多項(xiàng)式 g（x）為

RS（255，223）編碼器的電路主要部分有：線性反饋移位寄存器、有限域加法器、開關(guān)。該電路結(jié)構(gòu)實(shí)際上是由32個(gè)加法器和32個(gè)乘法器構(gòu)成的級(jí)聯(lián)電路，從時(shí)序設(shè)計(jì)的角度來說，RS（255，223）編碼器的電路結(jié)構(gòu)具有32級(jí)流水線階段，每個(gè)階段包含了一個(gè)加法器、一個(gè)乘法器和一個(gè)D觸發(fā)器組。在RS（255，223）編碼器中，乘法器和加法器是主要的運(yùn)算單元，因其所在域的特征為2.所以加法器可用異或邏輯來實(shí)現(xiàn)，乘法器是可用與邏輯來實(shí)現(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比競(jìng)爭(zhēng)FPGA的功耗低75%，含有5 K至120 K邏輯單元（LE），比前一代產(chǎn)品每邏輯單元成本降低20%。使用Cyclone III來設(shè)計(jì)完成位寬為8 bit的RS（255，223）編碼系統(tǒng)，芯片資源和管腳資源都可以滿足其要求。

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

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

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

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

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

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

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

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

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

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

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

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

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

編碼系統(tǒng)在前223個(gè)字符信息輸入時(shí)，直接輸出x端得數(shù)據(jù)信息字符。此外，由于芯片內(nèi)部的寄存器延遲效應(yīng)，y端較x端滯后一個(gè)時(shí)鐘周期；當(dāng)223個(gè)字符信息（十六進(jìn)制為DF）輸出完畢后，有效字符輸入控制信號(hào)data值由1變成0，編碼系統(tǒng)開始進(jìn)入冗余校驗(yàn)信息輸出階段，編碼系統(tǒng)完成輸出接收到的數(shù)據(jù)信息字符后，緊接著輸出32個(gè)校驗(yàn)字符。輸出數(shù)據(jù)字符是從01到223，32個(gè)校驗(yàn)碼字符為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ā)展，各個(gè)FPGA生產(chǎn)廠家都已有自己的IP核可以使用，例如，Altera公司提供的Reed-Solomon編譯器MegaCoreTM功能的IP核供給用戶使用。本文介紹了一種基于Altera公司Cyclone III系列的RS編解碼系統(tǒng)，可以實(shí)現(xiàn) RS（255，223）的編解碼。

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

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

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

[4]田耕，徐文波，張延偉.無線通信FPGA設(shè)計(jì)[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].微計(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實(shí)現(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實(shí)現(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 稿件編號(hào)：201112121

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