【作者】 辛明寿；

【导师】 刘明山；

【作者基本信息】 吉林大学 ， 信号与信息处理， 2006， 硕士

【摘要】 在现代数字电子技术领域中,纠错码保护技术已经得到了广泛的应用。纠错码技术是一种通过增加一定的冗余信息来提高信息传输可靠性的有效方法。RS码是多进制BCH纠错码的重要子类,是一种典型的纠错码。在线性分组码中,它具有最强的纠错能力,既能纠正随机错误,也能纠正突发错误。随着对RS码研究的深入,RS编译码算法的改进和VLSI技术的发展,以ASIC或FPGA为基础实现信道编码的研究得到了广泛地开展。。本文从Reed-Solomon(RS)码的结构出发,阐述了一种基于FPGA的RS(255,239)编、译码器的Verilog HDL设计方法。首先简单介绍了RS码的基本原理,并根据RS译码中的时域编、译码原理,将适合计算机仿真的伴随式计算算法、BM迭代算法、Chien搜索算法、Forney算法转换成Verilog语言。利用Altear公司的开发软件Quartus II将上述算法模块进行编译得到各电路功能模块,并进行了仿真。使用现场可编程门阵列Altera公司的FLEX系列芯片,设计实现了在FPGA上译码速率最高达到14M波特的RS(255,239)的硬件编、译码器,并以此为基础设计实现了可变长的RS编、译码器和动态RS编、译码器。随着信息技术的发展和工程施工科学化的进一步要求,施工现场机群(智能化工程机群)的调度控制变得越来越重要。本文将设计得到的可变长的RS编、译码器应用于智能化工程机群的无线通信中,并设计了车载无线通信系统中的无线收发模块部分系统。更多还原

【Abstract】 RS is the abbreviation of Reed-Solomon code, a nonbinary BCH code that hasstrong capacity to correct outburst of errors. As an important means to improve datastorage and transmission reliability, RS is widely used for error control in datacommunications and storage system. It is one of the most effective and widely usedapplications of error control coding.Since the day of its birth, RS has played an important role in the digital storageequipment (hard disks, CD, DVD, etc.), digital communications systems (cellularphone, microwave-, etc.), digital television, DVB, satellite communications (includingdeep-space communication systems), and broadband modems demodulate (xDSL, etc.).RS is also recommended to be standard codes of different industries, such as deepspace communications, CD and CD-ROM, digital television transmission system.As to encoders of RS, currently in most ASIC, digital television broadcasting(DVB) uses RS (204,188);and deep-space satellite communications systems, RS(255,223) code. In programmable logic devices, RS encoders are widely applied;whileRS decoders are seldom used. Low-rate code flow is commonly achieved by singlechip processor and DSP. It is because RS encoding devices are simpler, while thealgorithms of decoders are more complex;besides C language is more convenient indescribing algorithm than HDL (hardware description language). To design a chipunder rapid implementation by HDL is challenging and time consuming. It needshardware engineering skills and more chip resources (over 10,000).Previously, PLD fell short of the requirements or was too expensive. EDAsoftware also had limited functions. Their integrated capabilities in complexalgorithms were often poor. Now, with the decrease of chip prices and the increase ofintegration, and also the help of powerful EDA software, decoders can be applied incheap FPGA/CPLD. Though Altera Co. and Xilinx Co., programmable logic devicesuppliers, can provide IP soft core, it needs authorization;plus, the soft core it providesis built on the basis of DVB coding and then put other coding rates into consideration.Thus it’s inefficient and consumes more resources. Moreover, it only providescompiled .vho documents but no source code.With the development of information technology and further requirement onproject automation, the onsite control of construction fleet (intelligent engineeringgroup) becomes increasingly important. Writer once participated in an intellectualizedmechanical engineering vehicle-mounted wireless systems, during which priorcorrection RS encoding has been involved. Taking into account the costs, andaccording to the RS principles, writer designed (255,239) coding devices based onFPGA. And we also brought out variable length RS and dynamic RS coding devices.1. Design and implement of the RS (255,239) encoder and decoderFundamental parameters of RS (n, k) in GF ( 2m):code length: n = 2 m?1message section: kintendance section: n ? k=2tminimum distance: d = 2t +1Fundamental parameters of RS (255, 239) in GF ( 28):m =8 , t =8code length: n =28 ?1=255message section: k =239intendance section: n ? k=2t =16minimum distance: d = 2t +1=17(1)Design and Realization of RS encoderThere are two RS coding theories. One is time domain encoding, and the other isfrequency domain encoding. This thesis only discusses time domain encoding. RScoding is mainly about generator polynomial g(x) of code. Its encoder can be dividedinto two basic categories: N-K level encoder and K-level encoder. Generally speaking,the coding circuit of cyclic codes is a N-K level encoder, which can also be dividedinto two categories: one is g(x) multiplicative circuit, and the other is g(x) divisioncircuit.①Polynomial multiplication circuits based coding devices: the coding charactersare for non-system code. So in decoding, the first thing is to retrieve information fromreception code. Its coding efficiency is markedly lower than system coding, which isused in actual application.②Polynomial division circuit coding devices: Information Group m(x) multipliedby x n? k equals m(x) x n? k. The result is divided by g(x) to get corresponding residualr(x), then forming codes with original message group. This thesis uses division circuitto achieve RS coding, as shown in diagram 1.g 0 g 1 g 15encoding output 21encoding inputFig.1 The RS encoder of N-K level composed by division circuitPrimitive polynomial and generator polynomial were adopted in this article asfollowing:f ( x)= x8 +x4+x3+x2+1 (1)reg1 reg2 reg16feedback816365412299850365959131041896820930()87654321615141312111093891719161475169418231942225112016120151041410713109121021116110769+++++++++=++++++++++++++++=+++++++xxxxxxxxxxxxxxxxaxaxaxaxaxaxaxaxagxxaxaxaxaxaxaxax(2)N-K level RS encoder is primarily composed by a group of pictographic feedbackshift register and control circuits. It is n-k=16 level encoder. g 15 ,,g1,g0 arefeedback coefficients of linear feedback register, which are corresponding tocoefficients in g(x), namely, coefficient of x 15 is a 120 =59;…;x 1, a 225 =36;x 0, a 120 =59.The value attained by reg16 register XOR currentinput message coded is the value in feedback register.Coding steps:① Reset all registers, switch to 1, then 239 message codes will enter divisioncircuit one by one for easy output in turn;② When the final code enters, switch to 2, then the first check digit exports;③ Check digits are imported into register by clock rhythms, and then exported inone batch. Coding ends when last check digit is exported.(2)Design and realization of RS decoderIn 1960, Peterson laid the theoretical basis of binary BCH decoding system andlater extended to nonbinary by Gorensten and Zierler. In 1965, Forney resolved theBCH decodes of correcting errors and erasures. In 1966, Berlekamp made theBerlekamp-Massey algorithm. Since then, many authors had constantly set newdecoding methods such as Euclid decoding algorithm, Continued Fraction decodingalgorithm, etc. In 1978, based on codes of MS polynomial, Hart proposed frequencydomain decoding by applying spectrum analysis which is commonly used in digitalsignal processing techniques.RS decoding can be divided into two categories: time domain decoding andfrequency domain decoding.Frequency domain decoding is to treat coding characters as serial numbers,change it into frequency domain by implementing DFT in limited field, and then useits frequency domain characteristics when decoding. Because of increased complexityby DFT, frequency domain decoding is usually more complex than time domaindecoding, and therefore FFT is only applied in certain exceptional circumstances, say,decoding of specific long codes (for example n equals to exponentials of 2).Time domain encoding is to treat coding characters as the signal sequence on timeaxis, and encode by utilizing the algebraic structure of codes. Currently the mostwidely used and important method is Berlekamp-Massey algorithm of time domain.Due to the importance of RS codes, research in this area is most detailed andthorough. In this thesis, we adopt the classic iterative decoding algorithms.Decoding process can be divided into the following steps :① by receiving R (x), we get =∑ =++?ijs j Yixi, jm0 ,m01,,m02t1。 .② Derive error location polynomialσ(x) from s j.③ Seekσ(x), get the number of wrong locations, and identify positions.④ Derive deficient values by positions and get deficient drawing E (x).⑤ R (x) -E (x) =C (x), rectification process is completed.Principle of decoder shown in diagram 2R(x) C(x)Fig.2 The principle of RS decoderSyndromecalculationErrorpolynomialBMalgorithmError locationChien searchErrormagnitudesForneyalgorithmDelayDelay2. Advancement of RS decoderRS (255,239) have received widespread application in many areas. However, inmost applications, the length of data frame is less than 239 bytes. If RS (255,239)remains unchanged, it will lead to decreased efficiency in the transmission of dataframes, while increase possibilities of inaccuracy due to interference in transmission.So in practice, RS (255,239) shortened code is more applicable.2 types of improved methods can be proposed based on RS (255,239) encoders:(1)Variable length RS coding devices (coding length can be preset)Code length: 17-255 bytes;message space length: 1-239 bytes, check digits spacelength: 16 bytes, correction capacity t=8.(2)Dynamic RS coding devices (coding length is dynamic)Code length: 17-255 bytes;message space length: 1-239 bytes, check digits spacelength: 16 bytes, correction capacity t=8.更多还原