基于C语言的RS(7,3) 编码器设计

分类号 编号

某 某 大 学

毕 业 论 文（设 计）

基于C语言的RS(7,3) 编码器设计

Design and Implementation of RS(7,3) Encoder Based on C

申请学位：工学学士 院 系：电子信息学院 专 业：通信工程 姓 名：李帅哥 学 号：200599999999 指导老师：晋（讲师）

2009年5月25日

某某大学

基于C语言的RS (7,3)编码器设计

姓 名：李帅哥 导 师：晋（讲师）

2009年5月25日

某某大学

某某大学毕业论文（设计）任务书

院（系）： 姓名 李帅哥 学号 200599999999 毕业届别 2009 专业 通信工程 毕业论文（设计）题目 指导教师 晋 学历 基于C语言的RS (7,3)编码器设计 研究生 职称 讲师 所学专业 通信与信息系统 具体要求(主要内容、基本要求、主要参考资料等)： 主要内容：研究纠错码的基本理论和数学基础，学习循环码，BCH码，RS码等几种常见的纠错码，研究它们的编码、解码原理。重点研究RS编码原理及实现方法。应用C语言进行RS编码器的软件设计，并选用MATLAB对编码结果进行验证。 基本要求：应用C语言进行有限域乘法器、RS编码器的仿真设计，并利用TLAB对编码结果进行验证，实现编码功能。 参考资料： 1.王新梅，肖国镇.纠错码——原理与方法.西安电子科技大学出版社.2002. 2.张鸣瑞，邹世开.编码理论.北京航空航天大学出版社.1990. 3.曹雪虹，张宗橙.信息论与编码.清华大学出版社.2004. 4.叶才炜,李式巨.RS编译码的c语言实现.无线电工程第33卷第8期. 5.孙屹，李妍.MATLAB通信仿真开发手册.北京：国防工业出版，2005 进度安排：2008-2009-1学期第8周—第16周，选定毕业论文题目、进行开题。 2008-2009-2学期第1周—第4周，查阅资料，完成相关文献翻译。 2008-2009-2学期第5周—第8周，有限域乘法器、RS编码器的软件设计。 2008-2009-2学期第8周—第13周，设计结果的Matlab验证，撰写论文。 2008-2009-2学期第14周—第15周，论文答辩。 指导教师（签字）： 年 月 日 院（系）意见： 教学院长（主任）（签字）： 年 月 日 备注：

[摘要]RS(Reed-Solomon)码是一种多进制的BCH码。既适宜纠正随机错误，更适宜纠正突发错误，因而被广泛地用于各种通信系统及数据存储中，如深空通信、移动通信、光纤通信、磁盘阵列、DRAM、光盘数字视频广播(DVB)等系统。

本论文重点介绍了纠错码基本理论，有限域乘法器、RS码编码原理。利用C语言实现了RS(7,3)码的编码器和伽罗华域GF(23)内的乘法器的设计，并通过Matlab仿真对编码器结果进行验证，程序输出结果与验证结果一致，表明所设计的编码器和乘法器算法能够满足设计要求。

[关键词]Reed-Solomon码；乘法器；编码器

[Abstract] RS (Reed-Solomon) code is an M-ary code of the BCH. Appropriate to correct random errors,and more appropriate to correct the unexpected error,it has been widely used in various communications systems and data storage, such as deep-space communication, mobile communication, optical fiber communication, disk array, DRAM, CD-ROMs Digital Video Broadcasting ( DVB) systems. The paper focuses on the basic theory of error-correcting codes,and finite field multiplier, RS coding principle. Then

3implement RS(7,3)encoder and GF(2)multiplier with language C.And tested by Matlab simulation.The results of RS encoder are correcr,which prove the design of the RS encoder and finite field multiplier can meet the requirement of the usement. [Key words] RS (Reed-Solomon) code；encoder；Multiplier

目录

1 绪论 ...................................................................... 1 1.1课题研究的意义及背景 .................................................... 1 1.2 RS码的国内外发展状况 ................................................... 2 2 纠错码的基本理论 .......................................................... 4 2.1 纠错码简介 .............................................................. 4 2.2循环码 .................................................................. 5 2.3 BCH码 .................................................................. 6 2.4 RS码 ................................................................... 6 3 有限域的乘法器设计 ........................................................ 8 3.1有限域（伽罗华域）的基本概念 ............................................ 8 3.2 有限域元素运算 ......................................................... 11

3.2.1．有限域GF(2)中的加法 ........................................ 11 3.2.2有限域GF(2)中的乘法 ......................................... 12

4 RS(7,3)码的编码器设计 .................................................... 15 4.1 RS码的编码原理 ........................................................ 15

4.1.1生成多项式的求解 .............................................. 15 4.1.2 RS(7，3)码的C语言实现 ....................................... 16

4.2 MATLAB验证 ............................................................ 20 总结与展望 ................................................................. 22 致 谢 ...................................................................... 23 参考文献 ................................................................... 24

mm某某大学毕业论文（设计）

1 绪论

1.1课题研究的意义及背景

信息的交换、处理和传输是现代通信的任务。数字信号经过传输，会产生错误。可靠的数字通信系统必须将差错率控制在允许的范围内。提高信息传输的可靠性和有效性，始终是通信工作所追求的目标。而纠错码技术是提高信息传输可靠性的一种重要手段。所有的数字通信系统如通信、雷达、遥控遥测、数字计算机的存储系统和内部运算以及数字计算机之间的数据传输等，都可归结成如图1-1所示模型

信源信源编码器信道编码器调制器噪声源信道信宿信源译码器信道译码器图1-1通信系统模型

解调器

我们关心的是图中的信道编、译码器即纠错编、译码器两个方框。信道编码器对信息序列进行编码，增加冗余度。当码元经信道传输产生错误时，译码器可以检出或纠正错误。所编的具有检错或纠错能力的码就称为纠错码。

随着信息时代的到来和微电子技术的飞速发展，纠错码技术已成为一门标准技术而被广泛应用。研究纠错码是一项理论性与实践性均很强的工作。在通信领域中，CRC循环校验已成为各类线路传输中必不可少的一部分。在移动通信中，纠错码被广泛应用于模拟体制的信令传输及数字体制的整个传输，以提高传输的可靠性和节省珍贵的频谱资源；在电话网的数据传输中，纠错码、差错控制技术已是高速数据传输成为现实的关键技术。纠错码技术还广泛应用于计算机存储和运算系统中。

1

某某大学毕业论文（设计）

1.2 RS码的国内外发展状况

RS(Reed-Solomon)码是差错控制领域中一类重要的线性分组码，由于具有很强的纠错能力，具有同时纠正突发错误和随机错误的能力，因而被广泛地应用于各种现代通信系统中，以满足对信道可靠性的要求。很多国际标准采用了RS码例如空间数据系统咨询委员会在遥测信道编码的建议书中将RS（255，223）系统码作为标准使用。美国的蜂窝数字分组数据系统（CDPD）中采用了m=6的RS（63，47）码。RS码也是空间应用存贮器系统中的首选码。故自RS码出现以来，便一直是国际通信领域研究的热点问题之一。 对于RS码的编译码器，现有的专用集成电路(ASIC)大部分是数字电视广播(DVB)的RS(204,188)和深空卫星通信系统中用的RS(255,223)码。在可编程逻辑器件上做RS码编码器的很多，而把RS码译码器也做在可编程逻辑器件上的很少。对于低速率码流，国内外大部分都是用单片机和DSP来实现。究其原因，是因为RS码编码器比较简单，而译码器的算法比较复杂，而c语言对于算法的描述比用HDL(硬件描述语言)要方便的多。使用硬件描述语言设计高速执行的芯片，这种设计是富有挑战性和花费时间的，需要一定的硬件工程技巧，并且需要用到的芯片资源比较多(上万门)。以前的PLD或达不到所需的要求或价格昂贵，EDA软件功能也有限，往往对于复杂算法的综合能力很差。而现在，随着芯片价格的下调和集成的提高，以及功能强大的EDA软件的帮助，将有能力把译码器做在便宜的FPGA上。虽然可编程逻辑器件供应商Altera公司及Xilinx公司可提供IP软核，但它需要授权使用，并且它提供的软核也是在可实现DVB译码的基础上再考虑其它码率的RS码，所以效率低，器件资源消耗比较多。而且它只提供编译后的.vho文件，不提供源代码。从RS纠错编译码的设计到实现过程相当复杂，随着VLSI(超大规模集成电路)技术的发展，高集成度电路为其庞大的编译码设计提供了强大的硬件支撑。正因为有超大规模集成电路出现，RS码在通信领域被广泛应用。

目前实现RS编译码的方法有如下几种：

1．采用一些厂家提供的功能特定的RS编译码芯片。

这种方案用户可以不必关心RS编译码器的内部结构，只要了解如何使用这个芯片就行了。这种市售的RS芯片通常是为了满足特定的功能要求而设计的，其功能的配置虽也可做部分调整，但局限性较大，灵活性较差，而且资源浪费多，引脚数目也多。

2.利用可编程的数字信号处理(DSP)芯片实现RS编译码功能。

这种方案DSP芯片的设计者必须对RS编译码的算法有深入了解。这种方法灵活，用户通过修改软件代码的办法对RS编译码的参数和功能做出较大的调整。这种方法的缺点是DSP芯片的价格比较昂贵、编译码的速度受限制。

3.利用FPGA技术，以配置FPGA器件的方式实现RS编译码。 采用这种方案，即通过配置FPGA来完成RS编译码的方法，是目前看来最好的一种方法。因为FPGA作为一种高密度可编程逻辑器件，可以反复编程，具有很好的灵活性，便于修改RS编译码的参数。用FPGA实现的RS编译码器速度很快，运算速度远高于DSP编程的方法。另外这种方法还可以根据实际要求，把RS编译码器的周围的一些相关电路也

2

某某大学毕业论文（设计）

集成在同一片FPGA芯片里。这样一来既充分利用了器件资源，又提高了产品集成度和可靠性，减少了功耗，降低了成本，而且使电路性能得到明显提高。正因为基于FPGA的RS码实现方式有如此显著的优势。

随着研究与应用的不断发展，RS码硬件译码器的实现已呈现出模块化的设计形式。这样的设计形式一般可分为五个部分：1）计算校验子2）求解关键方程3）求取错误位置4）求取错误值5）纠正错误。上述五个部分的具体关系如图1-2：

计算校验子求解关键方程求取错误位置图1-2 RS译码原理

求取错误值纠正错误

3

某某大学毕业论文（设计）

2 纠错码的基本理论

2.1 纠错码简介

纠错码的产生源于1948年Claude Shannon的著名论文“A mathematical theory of communication”的发表。而Shannon提出的信道编码定理正是为纠错码的发展奠定了理论基础。这是因为在Shannon提出信道编码定理之前，工程师们仅仅知道只有无限能量或无限带宽才能保证噪声信道中的消息能够可靠传输;但是，信道编码定理提出之后，工程师们意识到建立一条太好的通信信道是不值得的，而有效地使用纠错码的能力才是合理的。可惜的是，Shannon只是证明了合适码字的存在，而并没有阐述如何去获得合适的码字。所以，在上世纪的整个50年代，主要的工作在于寻找能够产生低误码率的码型构造方法，但结果却不如人意；到了60年代，纠错码研究开始从两个方向进行长期的发展。

纠错码研究的第一个方向是在码字的构造中引入代数结构，其中的研究成果集中在分组码的研究。在1950年，Hamming第一次描述了一类具有单个纠错能力的分组码——Hamming码。由于Hamming码存在一定的局限性，所以人们在往后的10年里坚持不断地向着Shannon指出的方向努力。尽管如此，在1960年以前，人们仍然无法找到比Hamming码更好的一类码型。同时，在这段岁月里，许多长度较短的分组码仍然不断地被人们发现了。但是，这些分组码都没有一般的理论基础。而到了1960年，重大的突破终于发生了。这就是Bose,Ray-Chaudhuri(1960)和Hocquenghem(1959)发现了一类具有多个纠错能力的分组码BCH码，以及Reed和Solomon(1960)发现了适用于非二元信道的分组码——Reed-Solomon码。至此以后，由于这个领域的理论得到了很大的发展，所以在往后的岁月中，新的码型也不断地被发现。BCH码的发现同时带动了在软件和硬件上设计有效编译码算法的研究。第一个好的译码算法是由Peterson提出的，接着，就是由Berlekamp和Messay提出的更加有效的迭代算法。随着研究地不断深入，更为有效的编译码算法也不断地得到改进，如在1972年由Chase提出的Chase算法。

纠错码研究的第二个方向是与概率统计相结合的研究方向。最初的研究是在最优码字未知的情况下去估计分组码中最好的码型的误码率。以这类研究为基础，人们开始尝试从概率的角度出发来了解编译码的原理，从而提出了序列译码的概念。从对序列译码的研究中，人们了解到一类具有高度结构化的有效的树型码——卷积码，其中卷积码是由Elias在1955年所发现的。在上世纪的五十年代末，卷积码已可以通过序列译码算法得到成功的译码。在1967年，由Viterbi提出的Viterbi算法成为了卷积码的译码工作中至今为止最常用的译码算法。

4

某某大学毕业论文（设计）

2.2循环码

循环码是一类最重要的线性码，它具有严格的代数结构，其性能易于分析。目前已发现的大部分线性分组码均与循环码有密切联系，它们之中的大部分都可归结于循环码的范畴。并且循环码具有循环特性，其编译码电路，特别是编码电路易于实现。基于这些特征，循环码特别引人注目，对它的研究也比较深入和系统。

循环码的定义：设有一个n重的k维子空间Vn,k?Vn,若对其中任意一个

Vn,k，则称Vn,k为循环子空间或循环码。 V??an?1,an?2,?,a0??Vn,k，恒有V1??an?2,an?3,?,a0,an?1??通常用多项式来表示循环码。将码矢表示成多项式的形式，即码元多项式C?x?为： C?x??Cn?1xn?1?Cn?2xn?2???C0 （2.1） 其i次循环移位所得的码矢也用多项式表示为：

i C???x??Cn?1?ixn?1?Cn?2?ixn?2??C0xi???Cn?i （2.2） 由式（2.2）乘以xi再除以xn?1得：

xiC?x?Cn?1?ixn?1??C0xi???Cn?ii?1i?2?Cx?Cx???C?n?1n?2n?inx?1xn?1?Cn?1xi?1?Cn?2xi?2???Cn?i?C?i??x?xn?1 (2.3)

由此可知：C?x?的i次循环移位是C?x?乘以xi后再除以xn?1的余式。即：

i C???x??xiC?x?mod?xn?1? (2.4) 根据循环码的循环特性，可由一个码字的循环移位特性得到其他的非零码字。在[n,k]循环码的2k个码字，取其前k-1位皆为0的码字g(x)(其次数为r=n-k)，在经过k-1次循环移位后，总共得到k个相互独立的码字：g?x?,xg?x?,?xk?1g?x?可作为码生成矩阵的k行，于是得到?n,k?循环码的生成矩阵G?x?：

?xk?1g?x???k?2?xgx???? G?x????? (2.5)

??xgx?????g?x????码的生成矩阵一旦确定，码就可以确定。这表明?n,k?循环码可以由它的一个r(r=n-k)

次码多项式g?x?来确定。每一个码多项式都是g?x?的倍式，每一个是g?x?倍式且次 数≤n-1的多项式都是码多项式。多项式g?x?称为码的生成多项式。

5

某某大学毕业论文（设计）

2.3 BCH码

自1950年汉明发表了纠正单个错误的码以来，几乎过了10年的时间，才于1959年由霍昆格姆（Hocquenghem），1960年由博斯(Bose)和雷一查得胡里（Ray-Chaudhuri）分别提出了纠正多个随机错误的循环码—BCH码的构造方法。BCH码是目前所发现的一类很好的线性纠错码类，它的纠错能力很强，特别是在短和中等码长下，其性能接近理论值，并且构造方便，编码简单。特别是它具有严格的代数结构，因此它在编码理论中起着重要的作用。BCH码是迄今为止研究得最为详尽，分析得最为透彻，取得成果也最多的码类之一。1960年彼得逊伊（Peterson）从理论上解决了二进制BCH码的译码算法，奠定了BCH码译码的理论基础。稍后，格林斯坦（Greenstein）和齐勒尔（Ziegler）把它推广到多进制。1966年伯利坎谱（Berlekamp）利用迭代法译码BCH码，从而大大地提高了译码速度，从实际上解决了BCH码的译码问题。

BCH码的定义：给定任一有限域GF?q?及其扩域GF?qm?，其中q是素数或素数之幂，m为某一正整数。若码元取自GF?q?上的一个循环码，它的生成多项式g?x?的根集合R中含有以??1个连续根，则由g?x?生成的循环码称为q进制BCH码。在实际中应用的最多的是二进制BCH码，将二进制BCH码的概念进行扩展可以得到多进制BCH码。因为码元符号取自二元域GF?2?、纠t个错误的二元BCH码的生成多项式是以GF?2?的扩域GF?2m?上2t个相邻元素为根的多项式。那么，多元BCH码的码元符号取自多元域GF?q?，其中q为某一素数或素数之幂，而纠正t个错误的多元BCH码的生成多项式是以GF?q?的扩域GF?qm?上2t个元素为根的多项式为

g?x???x???x??2?x??2t (2.6)

????多元BCH码的校验矩阵：

??n?1?n?2??1???2n?12n?22????????1?? H??? (2.7)

????????d?1n?1?d?1n?2d?1????1????????式中，?为GFqm本原元：码长n?qm?1；d为设计距离，d=2t+1。由g?x?确定的BCH

??码是q元本原BCH码。RS码是多元BCH码的一种特例，即取m=1，故RS码的生成多项式的根和码元符号在同一域上。下面将讨论RS码。

2.4 RS码

RS码是线性分组BCH 码中一个重要的子类。在同样编码冗余度下,RS 码具有最强的纠错能力。在q进制BCH 码的码字中, 每个码元的取值在GF(q)上,但码的g(x)的根却在GF(q)

6

某某大学毕业论文（设计）

的扩域GF?qm?中,若码元取值的域与码的g(x)的根所在的域相同, 则称这类BCH码为RS码。

RS码是非二进制循环码,每一个码元由m个比特构成,m是大于2的任意正整数.只有所有的n和k都满足以下条件时，m比特码元的RS?n,k?码才存在。

0?k?n?2m (2.8) 其中,k是已编码分组的数据码元数目,n是已编码分组中总的码元数。对于大多数

RS?n,k?码

?n,k???2m?1,2m?1?2t? (2.9)

其中,t是RS码能够纠正的错误码元个数,n?k?2t是监督码元个数。扩展的RS码由

n?2m,或n?2m?1组成, 但n不能再大。对任何相同输入输出分组长度的线性编码, 里德

-索罗蒙码可以达到最大可能的码元最小距离。对于非二进制编码, 两个码字间的距离(类似于汉明距离)定义为序列间的不同码元数目。里德-索罗蒙码最小码本距离为

dmin?n?k?1 (2.10) 这种编码可以纠正少于t的任意多个错误组合。t可以表示为:

d?1n?kt?[min]?[]

22(2.11)

其中:[x] 表示小于或等于x的最大正整数。上式表明,对于RS码,纠正t个错误需要不超过2t个的监督码元。式(2.11)具有以下直接含义，我们可以认为译码器花费n-k个冗余码元，它是可纠正码元数的2倍。对于每个错误，一个冗余码元用于定位此错误，另一个用于找到其正确的取值。由于RS的编码比较简单，实现起来也很容易。RS码的编码原理分为时域编码和频域编码2种，本文中仅讨论时域编码。

7

某某大学毕业论文（设计）

3 有限域的乘法器设计

3.1有限域（伽罗华域）的基本概念

首先介绍一下域的概念。域:非空元素集合Q，若在Q中定义了加和乘两种运算且满足下述公理：

1）Q关于加法构成阿贝尔群，其加法恒等元（单位元）记为0。 2）Q中非零元素全体对乘法构成阿贝尔群。其乘法恒等元(单位元)记为1。 3）加法和乘法间有如下分配律:

???????????? （3.1） ???????????? （3.2）

则称Q是一个域。域中元素的个数为域的阶。

元素个数有限的域称有限域，用GF(q)表示q阶有限域。有限域也称为伽罗华域，在编码理论中起着非常重要的作用。有限域的一个重要性质是每个有限域GF(q)至少要包含一个叫做a的本原元素，它能生成该域中的每个元素。可以将GF(q)延伸为一个含有qm个元素的域，这称为GF(q)的扩展域，表示为GF(qm),m是一个非零正整数。GF(q)是GF(qm)的子集。扩展域GF(qm)中的码元用于构造RS码。二进制域GF(2)是GF(2n)的一个子域，类似于实数是复数的一个子域一样。除了数字0和1，在扩展域中还有特殊的元素，用一个新的符号a表示。GF(2n)中任何非零元素都可以由a的幂次表示。元素的无限集G，就是根据元素{0,1,a}而形成的，后一个元素通过前一项乘以a而得:

G?0,1,a,a2,a3,?an??0,a0,a1,a2,a3,?an? （3.3） 为了从G中得到有限元素的集合GF(2n)，必须对G域施加一个条件，使它只能含有2n个元素，并且对乘法封闭。域元素对乘法封闭的条件可由下面的不可约多项式表

2m?1?2m?1????1?0即a示:a?1?a0???? （3.4）

根据这个多项式限制条件，任何幂次等于或超2m?1的域元素都可降阶为如下表示 的幂次小于2m?1的元素。

有限域的本原多项式： 有限域GF(2m)可用一组本原多项式来定义，有限域是定义RS码所必需的，所以研究RS码须研究本原多项式。本原多项式可定义为:一个m阶的不可约多项式f(x)。如果f(x)能整除xn?1的最小整数n，其中n?2m?1，则该多项式是本原多项式。不可约多项式是指一个多项式不能因式分解为更低幂次的多项式，B整除A是指A除以B得到非0商并且余数为0。

表3-1中列举了一些常用的本原多项式。

8

某某大学毕业论文（设计）

表3—1常用本原多项式

M 2 3 4 5 6 7 8 本原多项式g(x)具有以下的性质:

本原多项式 1?X?X2 1?X?X3 1?X?X4 1?X2?X6 1?X?X6 1?X3?X7 1?X2?X3?X4?X8 (1)在[n,k]循环码中，生成多项式g(x)是唯一的(n-k)次多项式，且次数是最低的。 (2)在[n,k]循环码中，每个码字多项式C(x)都是g(x)的倍式，而每个为g(x)倍式 且次数<(n-1)的多项式必为一个码字多项式。

(3)[n,k]循环码的生成多项式g(x)是xn?1的因式，即xn?1?h?x?g?x?。

(4)若g(x)是一个(n-k)次多项式，且为xn?1的因式，则由g(x)可以生成一个[n-k]循环码。

本文设计的是RS(7,3)码编码器，由表3-1可以查出本原多项式是：f?x??1?x?x3， 用本源多项式表示的基本元素可映射为域元素图2.1的线性移位反馈寄存器(LFSR)电路的形式。例如，电路产生了域中的2m?1?m?3?个非0的域元素,注意在图3-1中线路反馈连接是与本源多项式f?x??1?x?x3的系数相对应的，类似于二进制循环码的情况。置线路初始状态非零，例如为100，每个时钟实现一次右移，可以证明，图3-1中所示的每个域元素(除了全0元素)将周期性地出现在移位寄存器的状态上。两种算术运算即加法和乘法可以用来定义这个GF(23)有限域。

X X X X

0123

图3-1由本源多项式表示的基本元素映射为域元素的电路

根据本源多项式可得GF(23)域元素表如表3-2所示。

3表3-2 GF(2)域中的元素映射表 指数形式 二进制形式 001 010 9

十进制形式 1 2 ?0 ?1

某某大学毕业论文（设计）

?2 ?3 100 011 110 111 101 001 4 3 6 7 5 1 ?4 ?5 ?6 ?7 根据图3-1可以通过c语言求出在域GF(23)中的所有元素。 源程序代码如下： #include void main() {

int GF[7]={1}; int i;

for(i=0;i<=6;i++)

{if(GF[i]<=3)

GF[i+1]=GF[i]<<1; else

GF[i+1]=((GF[i]<<1)&7)^3; }

for(i=0;i<=6;i++) printf(\}

程序运行结果图3-2。

10

某某大学毕业论文（设计）

图3-2 GF(23)域十进制元素生成

图3-2中所示的7位十进制数字就是GF(23)域中的十进制形式的元素。

3.2 有限域元素运算

了解了有限域后，看看如何用高级语言编写出有限域上的加法器和乘法器。这里以GF?23?为准。可以看出，多项式加法器的实现比较简单，可以直接将2个多项式对应的系数异或即可，而多项式乘法器的实现比较复杂，这里重点介绍用高级语言编写出有限域上的乘法器原理和方法。

3.2.1．有限域GF(2)中的加法

有限域中两个元素的加法定义为两个多项式中同幂次项系数进行模2加，即 ai?aj??ai.0?aj.0???ai.1?aj.1?x????ai.m?1?aj.m?1?xm?1 （3.5）

m已知GF(2)上的两个多项式

A?x??an?1xn?1?an?2xn?2???a1x1?a0

B?x??bn?1xn?1?bn?2xn?2???b1x1?b0

由有限域中两个元素的加法定义得两多项式相加

m

11

某某大学毕业论文（设计）

C(x)?A(x)?B(x)?(an?1?bn?1)xn?1???(a1?b1)x?(a0?b0) （3.6）

?cn?1xn?1?cn?2xn?2???c1x?c0

c?ai?bi;i?0,1,2,?,n?1其中i

m若为A(x)-B(x)，则只要把B(x)系数以GF(2)中的加法逆元代替得到- B(x)，再作- B(x)+ A(x)运算即可，在二进制情况下“-”与“+”运算相同，以此相加和相减的运算结果一样。

3.2.2有限域GF(2)中的乘法

为了找到一种遵守有限域内全部乘法性质的多项式乘法，将构成一个元素为qm的有限域。首先，我们要求在一个集合内的任何两个多项式之积是本集合中的另一个多项式，以满足封闭性。只要该乘积是一个次数等于或低于m-1的多项式，就可以满足这一要求。对于次数等于或大于m的乘积多项式，可以取它相对于一个m次固定多项式的余项多项式。这里所需要的m次固定多项式就是本原多项式q(x)。它的最高次幂为m，而系数在GF(q)上，它是不可约多项式。一般地说，系数取自GF(q)的不可约多项式在GF(q)中无根，但在扩张域GF(qm)内有根。具体说，m次q(x)在扩张域GF(qm)内必有m个根。在有限域GF(2m)中，2m个元素中的任意一个都可由阶数小于或等于m-1的不同多项式来表示。多项式的阶数是它的最高幂指数。当m=3时，有限域表示为GF(23)。由于a0?a7，所以在该域中有7个非零元素，或者说总共7个元素。GF(23)是GF(2)的扩展域，GF(23)中8个元素都可以用GF(2)中的两个元素0，1组合来表示，例如100，110，011等等。 扩展域元素代替二进制元素的一个好处就是表达的紧密性，使得非二进制编码和译码过程的数学表示变得简单。

有限域中的乘法运算规则是把两个元素表示成指数形式，将指数直接相加取模2m?1，如下式所示：

?i?j?mod?2m?1?ij a?a?a （3.7） RS码定义在有限域上,其编码译码运算都是有限域上的算术运算。在有限域的各种算术运算中,乘法研究最多。乘法器按实现方法分为比特串行乘法器和比特并行乘法器两种，比特串行乘法器的硬件实现比较简单,但是由于运算逐比特进行,实现高速的难度较大,不易达到较高的吞吐率。在高速应用时一般考虑用比特并行乘法器。所谓比特并行乘法器 是指通过连接,直接实现输出结果的多位运算 , 最后结果并行输出,这样可以显著提高处理速度。

在GF?2m?域中 , 两个以自然基表示的元素直接相乘时,约需要m3?m个模2加法器 , 这样实现的电路复杂度较高 , 而且缺乏规范性 , 因此一般釆用对偶基下的乘法器。现以乘?2为例，说明八进制常乘器的组成，GF(23)中每个元素都可表示成它的自然基

2底1，?，?2的线性组合：a2?2?a1??a01，再乘以?后，则

12

m某某大学毕业论文（设计）

?2?a2?2?a1??a01??a2?4?a1?3?a0?2?a2??2????a1???1??a0?2??a2?a0????a2?a1???a1?a2???a1???a0?22

式中

a2??a2?a0a1??a2?a1 a0??a1所以，乘?2电路如下图3-3所示

a2? a1?a0? a 0 a1 a 2

图3-3 乘?电路

2用c语言实现有限域GF(23)中乘法器源程序代码如下

#include int MUL(a，b) {int i,j,k,n,m; int GF[7]={1};

for(i=0;i<=6;i++)//生成GF[2]域// {if(GF[i]<=3) GF[i+1]=GF[i]<<1;

else GF[i+1]=((GF[i]<<1)&7)^3; }

for(n=0;n<=6;n++) { if(GF[n]==a) i=n;}

for(m=0;m<=6;m++) {if(GF[m]==b)

13

某某大学毕业论文（设计）

j=m;}

for(k=0;k

a=((a<<1)&7)^3; } return a; } main() {

int x,y,z;

scanf(\ z=MUL(x,y); printf(\ }

有限域GF(23)中4*6的运行结果如图3-4所示。

图3-4 有限域GF(2)中4*6的运算结果

3通过图3-4可以看出，当输入十进制数4和6时，表示在GF(23)域中作4*6的运算，结果输出为5，运算结果正确。

14

某某大学毕业论文（设计）

4 RS(7,3)码的编码器设计

4.1 RS码的编码原理

4.1.1生成多项式的求解

GF(2m)域上RS码一般写成(n,k)形式,其中n为码长n=2m-1,k为信息位的长度,码的最小距离d=n-k+ 1。每个符号表示m比特,可纠t=(d-1)2个错误。设A为GF(2m)的本原元,码的生成多项式为

g(x)=(x-?1)?(x-?2t) （4.1）

由g(x)所生成的系统码的生成矩阵G为

G=[Ik,R]=

?1??0????0??1?0??2?x?? （4.2） ???????0?1???k?x?????0?0???1?x??式中Ik为k×k阶单位方阵,R为k×(n-k)级矩阵,元素系数，而?H??kx??i?1,?k?表示?k?x?的

x??xn?kxk?i?xn?i?modg?x?,i?1,?k?对于RS码的校验矩阵H,可以由上式得到?k??RT,I??????x?T???n?k???1??? （4.3） X????x?I?2kn?k???2?4?设信息组为m?m0,m1,m2?mk?1,生成的码字为C?c1,c2,?cn?1, 则C?mG??, 本设

????计方案中, 选择RS(7,3)码的生成多项式为

g?x??x4??3x3?x2??x??3 （4.4）

由g(x)所生成的系统生成矩阵G为

?100?41?4?5??? G??010?21?6?6? （4.5）

?001?41??3???由生成矩阵G易得校验矩阵H。所以编码的关键是首先得出生成矩阵G, 而且为了得到

15

某某大学毕业论文（设计）

G, 必须首先找到生成多项式g(x)。

RS（7，3）编码程序的主要部分是移位法求校验元C?3?,?C?7?。它由两个步骤构成, 首先完成每次移位时校验元的求解, 然后完成码元的移位。本程序算法中根据校验元多项式

h?x??nx?1g?x?kk?1?hkx?hk?1x???h1x?h0来构造校验元。设系统码的多项式

C?x??cn?1xn?1???c1x?c0 （4.6）

其前kcn?1?cn?k位系数是已知的信息位,后n-k位系数cn?k?c0是需求的校验元,C(x)为g (x)倍式, 即C?x??q?x?g?x?, 而h?x?C?x??q?x?g?x?h?x??q?x??xn?1??q?x?xn?q?x?, 由于C?x?最高次数为n-1次, g(x)最高次数为n-k次,q(x)最高次数为k-1次,q?x?xn最低次数为n次, 即q?x?x?q?x?中x即

k?Ch?0n?j?jjj?0nn?1?xk次项系数为0。而xn?1?i的系数由

k?Chn?k?ijj?0组成,

, 因hk?1, 从而有cn?i?k???cn?j?ihj?i?1,2,?n?k?, 即

cn?k?i??cn?1h0?cn?2h1???cn?khk?1?,cn?k?2???cn?2h0?cn?3h1???cn?k?1hk?1?,?,

c?c0???ckh0?ck?1h1???c1hk?1? （4.7）n?k??n?k?这表明码字C的第一个校验元cn?k?1可由k 个信息元cn?1,?,cn?k与h(x)的系数相乘得

?到, 而由,cn?2,cn?3,?,cn?k,cn?k?1可得到第二个校验元, 以此类推可得到所有n-k个检验元cn?k?i,?,c0从而完成RS 码的编码过程。

4.1.2 RS(7，3)码的C语言实现

RS编码的步骤：

RS编码主要是围绕码的生成多项式g?x?进行的，其编码器基本可分为2类：N-K级编码

器和K级编码器。一般的循环码的编码电路是一个N-K级编码器，该编码器又可分为2类：一种是g?x?的乘法电路，另一种是g?x?除法电路。

1．基于多项式乘法电路的编码器，编出来的码字是非系统码，因此在译码时，首先要将信息从接收码中选出，其编码效率明显低于系统码，实际应用中都采用系统码。

2．基于多项式除法电路的编码器，将信息组m?x?乘以xn?k，得到m?x?xn?k，在除以g?x?，求得相应的余式r（x），在加原来的信息组组成了码字。本文中采用除法电路来实现RS编码，实现框图如图4-1所示。本文中RS码采用的本原多项式和生成多项式分别为：

f?x??x3?x?1 (4.8)

g?x??x4??3x3?x2??x1??3 (4.9)

16

某某大学毕业论文（设计）

N-K级RS编码器主要由一组线性反馈移位寄存器和控制电路组成，是n-k=4级编码器，是线性反馈寄存器的反馈系数，reg4寄存器的值和当前输入的信息码元异或得到的值的就是feedback寄存器的值。编码步骤:

1.将所有寄存器清零，门关闭，则3个信息码元一边依次进入信道，一边依次输出。 2.当最后一个信息码进入电路后，将门开启，第一个校验位输出，同时寄存器中码元依次右移一位，产生的第一个校验码存入c0。

3.校验码按时钟节拍载入寄存器c0，并依次输出。如此循环7次，当最后一个校验位输出时，编码结束。

门 ?c0 3 ?c1 2 ?4 c2 m(x) c(x)

图4-1 RS（7，3）码编码器实现电路

RS码的编码算法虽比较复杂，但用高级语言来实现不是很难的事，可以撇开硬件单纯从逻辑上考虑。RS(7，3)编码程序流程图如图4-2所示：

17

某某大学毕业论文（设计）

开始 输入参数及信息位 计算机生成多项式g（x）的系数 以g（x）为模，求余式r（x）的系数 求生成矩阵G 读信息位数据并送入编码器编码 校验元求解 码元移位 完成所有信息编码 编码输出 结束

图4-2 RS(7，3) 编码程序流程图

C语言程序源代码如下： #include \

int MUL(a，b) {int i,j,k,n,m; int GF[7]={1};

for(i=0;i<=6;i++)//生成GF[2]域// {if(GF[i]<=3)

18

某某大学毕业论文（设计）

GF[i+1]=GF[i]<<1;

else GF[i+1]=((GF[i]<<1)&7)^3; }

for(n=0;n<=6;n++) { if(GF[n]==a) i=n;}

for(m=0;m<=6;m++) {if(GF[m]==b)

j=m;}

for(k=0;k

a=((a<<1)&7)^3; } return a; }

void main()

{

int i,c0,c1,c2,c3;

scanf(\ for(i=0;i<=6;i++) {

c3=MUL(c0,6)^MUL(c1,4)^MUL(c2,3); printf(\ c0=c1;c1=c2;c2=c3; } }

程序中的函数MUL()是第三章实现GF(23)域中乘法器所定义的函数。 输入4 3 6运行结果如图4-3所示。

19

某某大学毕业论文（设计）

图4-3 输入4 3 6的编码结果

通过图4-3可以看出当输入3位信息位4、3、6时，程序输出一个7位的码组，其中前三位是信息位，后四位是校验位。

4.2 Matlab 验证

Matlab具有强大的计算功能，通信仿真是它的重要应用领域之一。在Malab通信工具箱中，有很多通信仿真的函数和模块，MATLAB通信工具箱不仅支持普通的线性分组码，而且包含了处理循环码，BCH码和RS码的函数，MATLAB通信工具箱包含的这些函数可以完成以下功能：

（1） 按照编码原理进行编码。

（2） 确定各编码方法的特性，如纠错能力，有效信息长度。

（3） 完成各编码方法的低级计算，如计算译码表，计算生成矩阵和校验矩阵，在生

成矩阵和校验矩阵之间进行转换以及计算生成多项式。 （4） 有限域的运算，包括求有限域元素，有限域的加法和乘法。

关于RS码的有关的函数有：rsenc，rsdec，rsencode，rsdecode，rspoly，rsencof，rsdecof，syndtable，其中rsenc是RS编码器函数，能实现RS编码，所以可以用于验证上边C语言实现的RS编码器是否符合RS的编码原理。 在M文件中输入以下语句： m = 3; % 域的限定

20

某某大学毕业论文（设计）

n = 2^m-1; k = 3; % 码字长度控制

msg = gf([4 3 6],m); % 设定输入的三位信息位 code = rsenc(msg,n,k) %RS编码并输出

Matlab仿真输出结果如图4-4所示：

图4-4 信息位是4 3 6时MATLAB的编码结果

由图4-4可以看出，以上用C语言实现的RS(7,3)编码器输入为4 3 6时的输出结果(图4-3)与Matlab仿真的结果完全一致，经过多次输入随机信息位，编码器输出的结果和MATLAB仿真的结果都完全一致，说明C语言实现的RS编码器是符合RS码编码原理的。

21

某某大学毕业论文（设计）

总结与展望

本文首先介绍了与RS码相关的有限域基本理论和循环码、BCH码等基本编码的相关知识。然后分别对有限域基本运算的相关算法进行了研究分析，重点对RS编码算法作了详细的分析，提高了系统性能并降低了系统硬件复杂性。

RS码的编码算法比较复杂，但用高级语言来实现不是很难的事，可以撇开硬件单纯从逻辑上考虑。要想进一步提高编码的性能，必须加长编码。对于线性分组码就是加长n，但很快我们就会陷于复杂度不可接受的窘境。为了解决这个问题，级联码把两个编码以串联或者并联的方式结合在一起，这两个码的复杂度在可接受的范围内，它们整体构成了一个更强大的编码。论文的下一步工作打算把另一种新兴的纠错能力同样出色LDPC码与RS码进行级联，这也是未来通信系统中很有前景的一种信道编码。本文因为作者能力、时间有限，没能完成RS码于其它码的级联。实际上，要提高系统的纠错能力，采用纠错能力更强的码型作为内外码是非常必要的。

通过一年多的学习和实践，对纠错码技术有了较多的了解，然而现在这一领域比较宽广，与其他一些领域的交叉逐渐增多，还有许多实际的问题有待进一步探求。可以预见，随着科学技术的进步和实际需要的增加，纠错码理论还将进一步地发展，其应用范围也将进一步地拓展。

22

某某大学毕业论文（设计）

致 谢

本课题在选题及研究过程中得到晋老师的悉心指导。晋老师多次询问研究进程，并为我指点迷津，帮助我开拓研究思路，精心点拨、热忱鼓励。晋老师一丝不苟的作风，严谨求实的态度，踏踏实实的精神，给以我终生受益无穷之道，对晋老师的感激之情是无法用言语表达的。

感谢我的室友们，从遥远的家来到这个陌生的城市里，是你们和我共同维系着彼此之间兄弟般的感情，维系着寝室那份家的融洽。四年了，仿佛就在昨天。四年里，我们没有红过脸，没有吵过嘴，没有发生上大学前所担心的任何不开心的事情。只是今后大家就难得再聚在一起吃顿饭了吧，没关系，各奔前程，大家珍重。

在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我无言的帮助，在这里请接受我诚挚的谢意！再次感谢晋刚老师对我的指导帮助！

23

某某大学毕业论文（设计）

参考文献

[1] 王新梅，肖国镇.纠错码—原理与方法.西安电子科技大学出版社，2002 [2] 张鸣瑞，邹世开.编码理论.北京航空航天大学出版社，1990 [3] 曹雪虹，张宗橙.信息论与编码.清华大学出版社，2004

[4] 叶才炜,李式巨.RS编译码的c语言实现.无线电工程第33卷第8期 [5] 孙屹，李妍.MATLAB通信仿真开发手册.北京：国防工业出版，2005 [6] 曹志刚,钱亚生.现代通信原理.北京:清华大学出版社,1992

[7] 张小平.RS码迭代译码算法分析.现代电子技术2005年第2期总第193期

[8] 单方骥，张力军.时域ReedSolomon译码器及其在FPGA上的实现.南京邮电学院学报

(自然科学版)21卷第3期

[9] 吴彬彬，顾斌.移动通信系统中RS码编译码器的DSP实现.电子工程师第30卷第6

期

[10] 王进祥，张乃通，来逢昌等.流水线结构RS(255,223)译码器的VLSI设计.计算机研

究与发展第37卷第1期

[11] 马红学，刘青.RS编码器的CPLD实现.集成电路与应用，2002.10

24

本文来源：https://www.bwwdw.com/article/4fdr.html