73循环码编译码软件实现.docx

摘要循环码是目前研究最成熟的一类码，并且有严密的代数理论，它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。当然它还具有循环性。本说明书介绍了（7，3）循环码的定义，以及编码与译码原理，用C语言编程实现其编码与译码功能。通过C语言平台运行所编写的程序，输入任意的数字信息序列，得出了编码结果。另外还分别在无差错和部分差错的情况下进行了译码。关键词：循环码；编码与译码；检错纠错；C语言目录前言1一、循环码编码、译码的基本原理21.1、循环码21.1.1、循环码定义21.1.2、循环码的特点21.1.3、码多项式31.1.4、生成多项式41.1.5、生成矩阵51.1.6、监督多项式与监督矩阵61.1.7、系统循环码61.1.8、循环码的编码71.1.9、循环码的译码81.1.10、循环码检错与纠错能力9二、设计过程及运行112.1 c语言的介绍112.1.1 C语言的发展112.1.2 C语言特点11 2.2 循环码编码的设计122.3循环码译码的设计132.4运行结果及仿真152.4. 1.正确编码界面152.4.2无差错编码仿真结果15 2.4.3部分差错编码图15 2.5运行结果及理论分析16 2.6软件可行性分析17 参考文献18总结19 附录2030前言在计算机通信信息码中循环码是线性分组码的一个重要子集，它的循环码的编码和译码电路比较简单，纠错能力也较强，是目前研究得最成熟的一类码。因此本文运用C语言对（7，3）循环码的编码与译码进行编程及运行仿真。C语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。C语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址，进行位(bit)一级的操作。由于C语言实现了对硬件的编程操作，因此C语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发，也适合于应用软件的开发。此外，C语言还具有效率高，可移植性强等特点。因此广泛地移植到了各类各型计算机上，从而形成了多种版本的C语言。一、循环码编码、译码的基本原理信道编码：信道编码又称差错控制编码或纠错编码，它是提高信息传输可靠性的有效方法之一。一类信道编码是对传输信号的码型进行变换，使之更适合于信道特性或满足接收端对恢复信号的要求，从而减少信息的损失；另一类信道编码是在信息序列中人为的增加冗余位，使之具有相关特性，在接收端利用相关性进行检错或纠错，从而达到可靠通信的目的。1.1、循环码循环码是线性分组码中一个重要的分支。它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。循环码是目前研究得最成熟的一类码，并且有严密的代数理论基础，故有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现，所以循环码受到人们的高度重视，在FEC系统中得到了广泛应用。1.1.1、循环码定义定义：一个线性分组码，若具有下列特性，则称为循环码。设码字 （1）若将码元左移一位，得 （2） 也是一个码字。由于（）线性分组码是维线性空间中的一个维子空间，因此循环码是维线性空间中的一个维循环子空间。注意：循环码并非由一个码字的全部循环移位构成。1.1.2、循环码的特点循环码有两个数学特征： （1）线性分组码的封闭型； （2）循环性，即任一许用码组经过循环移位后所得到的码组仍为该许用码组集合中的一个码组。即若为一循环码组，则、还是许用码组。也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。以3号码组（0100111）为例，左移循环一位变成5号码组（1001110），依次左移一位构成的状态图如图1所示。 图1（7，3）循环码中的循环圈 可见除全零码组外，不论循环右移或左移，移多少位，其结果均在该循环码组的集合中（全零码组自己构成独立的循环圈）。1.1.3、码多项式为了用代数理论研究循环码，可将码组用多项式表示，循环码组中各码元分别为多项式的系数。长度为的码组用码多项式表示则为 （3）式中，的幂次是码元位置的标记。若把一个码组左移位后的码组记为，其码多项式为 （4）可以根据按模运算得到，即 （5）或 （6）式中，为除以的商式，而等于被除得之余式。以码组1011100为例，若将此码左移两位，则由式（6）可得 (7)易有其余式为 ，对应的码组为1110010，它与直接对码组进行循环左移的结果相同。码多项式之间可以进行代数运算，在二元码中遵循模2运算的规则。根据线性码的封闭性，任意两码字经模运算后仍为本码组中的码字。1.1.4、生成多项式（n,k）循环码码组集合中（全“0”码除外）幂次最低的多项式（n-k）阶称为生成多项式。它是能整除且常数项为1的多项式，具有唯一性。集合中其他码多项式，都是按模（）运算下的倍式，即可以由多项式产生循环码的全部码组。假设信息码多项式为，则对应的循环码多项式为 （8）式中，为次数不大于的多项式，共有个（）循环码组。考查表1.1-1，其中阶的多项式只有编号为2的码组（0011101），所以表中所示（7，3）循环码组的生成多项式，并且该码组集合中的任何码多项式都可由信息位乘以生成多项式得到 （9）式中，为信息码元。对于（7，k）循环码，的因式分解为 （10）由该式可以构成表1所示几种（7，k）循环码。 (7,k) g(x) (7,1) (7,3) (7,4) (7,6) 表1（7，3）循环码的生成多项式 从表1中可以看出，即使n,k均已确定，也可能由多种生成多项式供选择，选用的多项式不同，产生出的循环码组也不同。1.1.5、生成矩阵根据各码组集合中生成多项式的唯一性，可以构造生成矩阵G。由于g（x）的次数为，则都是码多项式，而且线性无关，因此以这k各多项式对应的码组作为k行就能构成该循环码的生成矩阵，因此循环码的生成矩阵多项式可以写成 (11) 以生成多项式构造，相应的矩阵形式为 （12）则 (13)则G为g(x)升幂排列时的G为 (14)对式（14）作线性变换，整理成典型形式的生成矩阵 (15) 若信息码元与式（14）相乘，得到的就是系统循环码。1.1.6、监督多项式与监督矩阵如前所述，在（n，k）循环码中，由于g(x)能除尽,因此可分解成g(x)和其他因式的乘积，记为即可写成 （16）由于g(x)是常数项为1的r次多项式，所以h(x)必为k次多项式。称h(x)为监督多项式或一致校验多项式，与式（15）给出的G(x)相对应，监督矩阵多项式可表示为 （17） 式中，式h(x)的逆多项式。由式（17）可知，前述生成多项式的g(x)的一致校验多项式为，所以其一致校验矩阵（监督矩阵）为 (18) 1.1.7、系统循环码循环码也可以构成为系统循环码。为方便系统码的构造，将消息多项式和码式都记为高位在前，即的消息多项式为m(x)， （19）又设码式的高幂次部分等于m(x)，即 （20） 其中p(x)称为校验位多项式，由于码式是生成式的倍式，所以 (21)因此循环码的系统码码式为 （22）将循环码的系统码构造步骤总结为（1） 多项式乘（2） 多项式求模（余式） （3） 多项式减如果令为单项式， （23）那么容易看到，对应的向量，是线性无关的，从而得到循环码系统码的生成矩阵为 （24）故由式（24）可以求得前述（7，3）循环码系统码的生成矩阵为 (1.1.23) （25）1.1.8、循环码的编码1.利用生成多项式实现编码：如上所述，但循环码的生成多项式确定时，码就完全确定了。现在讨论生成多项式给定以后，如何实现循环码的编码问题。若已知 （26）并设信息元多项式 （27）要编码成系统循环码形式，即码字的最左边k位是信息元，其余n-k位是校验元，则要用乘以，再加上校验元多项式,这样得到的码字多项式为 (28)其中 一定是的倍式，即有 (29)注意到为n-k次多项式，而最多为n-k-1次多项式，必有 （30）即必是除以的余式。式(28)指出了系统循环码的编码方法：首先将信息元多项式乘以成为，然后将除以生成多项式得到余式，该余式就是校验元多项式，从而得到码字多项式 (31) 综上所述，系统循环码的编码问题，可以归结为两个多项式的除法运算，即将除以生成多项式得到余式的运算，因此研究多项式除法的电路实现是必要的。 由前面得叙述以求得循环码的生成矩阵等，故对于生成式为的（7，3）循环编码器，其编码原理图如图1.1-2。 图2（7，3）循环码编码器原理图 1.1.9、循环码的译码当码字c通过噪声信道传送时，会受到干扰而产生错误。如信道产生 。上式也可以写成多项式形式 （32）译码器的任务就是从中得到，然后求得估值码字,并从中得到信息组。循环码的译码可按以下三个步骤进行：接收到的计算伴随式式;根据伴随式找到对应的估值错误图样;计算, ，得到估值码字。若,则译码正确，否则，若,则译码错误。译码器实现的复杂程度，往往是一个纠错码能否使用的关键。利用循环码的循环特性，经常会使其译码运算变得简单，这也是循环码受到关注和重视的重要原因。对于本报告讨论的（7，3）循环码，其译码器原理图如图3。 图3（7，3）循环码译码器原理图 1.1.10、循环码检错与纠错能力由于循环码是一种线性分组码，所以其纠检错能力与线性分组码相当。而线性分组码的最小距离可用来衡量码的抗干扰能力，那么一个码的最小距离就与它的纠检错能力有关。定理： 对于任一个（n,k）线性分组码，若要在码字内检测e个错误，要求码的最小距离；纠正t个错误，要求码的最小距离；纠正t个错误同时检测个错误，则要求；循环码的译码分检错译码与纠错译码两类。在无记忆信道上，对码字c，差错图案和接收向量的多项式描述为 （33）定义的伴随多项式为 （34）由于所以 (35) 由此可见，则一定有差错产生，或说满 足的差错图样产生，它满足。循环码的检错译码即是计算并判断是否为0。二、设计过程及运行 2.1 c语言的介绍 C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。 具体应用比如单片机以及嵌入式系统开发。2.1.1 C语言的发展总的来说，C语言发展大概可以分为三个阶段：第一阶段从80年代到1995年。这一阶段C语言基本上是传统类型上的面向对象语言，并且凭借着接近C语言的效率，在工业界使用的开发语言中占据了相当大份额；第二阶段从1995年到2000年，这一阶段由于标准模板库(STL)和后来的Boost等程序库的出现，泛型程序设计在C中占据了越来越多的比重性。当然，同时由于Java、C#等语言的出现和硬件价格的大规模下降，C受到了一定的冲击；第三阶段从2000年至今，由于以Loki、MPL等程序库为代表的产生式编程和模板元编程的出现，C出现了发展历史上又一个新的高峰，这些新技术的出现以及和原有技术的融合，使C已经成为当今主流程序设计语言中最复杂的一员。2.1.2 C语言特点C是中级语言，它把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以像汇编语言一样对位、字节和地址进行操作， 而这三者是计算机最基本的工作单元。 C是结构式语言，结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。 C语言功能齐全，具有各种各样的数据类型，并引入了指针概念，可使程序效率更高。另外C语言也具有强大的图形功能，支持多种显示器和驱动器。而且计算功能、逻辑判断功能也比较强大，可以实现决策目的的游戏。 C语言适用范围大，适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。 C语言对编写需要硬件进行操作的场合，明显优于其它解释型高级语言，有一些大型应用软件也是用C语言编写的。 2.2 循环码编码的设计 由信息码构成信息多项式,其中高幂次为k-1;用乘以信息多项式，得到的最高幂次为n-1,该过程相当于把信息码（，）移位到了码字的前k个信息位，其后是r个全为零的监督位。用除得到余式,其次数必小于g(x)的次数，即小于（n-k）,将此r(x)加于信息位后做监督位，即将r(x)与相加，得到的多项式必为一码多项式。根据上面的讨论，可得到在（7，3）循环码编码的程序流程图如图2.2-1 所示： 初始化 确定余式r(x) 确定c(x) 储存c(x) 图4 编码程序框图2.3循环码译码的设计纠错码的译码是该编码能否得到实际应用的关键所在。译码器往往比编码较难实现，对于纠错能力强的纠错码更复杂。根据不同的纠错或检错目的，循环码译码器可分为用于纠错目的和用于检错目的的循环码译码器。 通常，将接收到的循环码组进行除法运算，如果除尽，则说明正确传输；如果未除尽，则在寄存器中的内容就是错误图样，根据错误图样可以确定一种逻辑，来确定差错的位置，从而达到纠错的目的。用于纠错目的的循环码的译码算法比较复杂，感兴趣的话可以参考一些参考书。而用于检错目的循环码，一般使用ARQ通信方式。检测过程也是将接受到的码组进行除法运算，如果除尽，则说明传输无误；如果未除尽，则表明传输出现差错，要求发送端重发。用于这种目的的循环码经常被成为循环冗余校验码，即CRC校验码。CRC校验码由于编码电路、检错电路简单且易于实现，因此得到广泛的应用。在通过MODEM传输文件的协议如ZMODEM、XMODEM协议中均用到了CRC校验技术。在磁盘、光盘介质存储技术中也使用该方法。 当码字c通过噪声信道传送时，会受到干扰而产生错误。如果信道产生的错误图样是e，译码器收到的n，重接受矢量是y,则表示为： （36）上式也可以写成多项式形式： （37）译码器的任务就是从中得到，然后求的估值码字 （38） 并从中得到信息组。 循环码译码可按以下三个步骤进行：（1）由接收到的计算伴随式;（2）根据伴随式找出对应的估值错误图样；（3）计算，得到估计码字。若,则译码正确，否则，若，则译码错误。由于g(x) 的次数为n - k 次，g(x) 除E(x) 后得余式（即伴随式）的最高次数为n-k-1次，故S(x) 共有2n-k 个可能的表达式，每一个表达式对应一个错误格式。可以知道(7,4）循环码的S(x) 共有2(7-4) = 8个可能的表达式，可根据错误图样表来纠正(7,4）循环码中的一位错误，其伴随式如表2所示。BCH（7，3）循环码错误图样表：表2 循环码错误图样错误图样错误图样码字伴随式S(x)伴随式E6(x)=x61000000x2100E5(x)=x50100000x2+x110E4(x)=x40010000x2+x+1111E3(x)=x30001000x+1011E2(x)=x20000100x2+1101E1(x)=x10000010x010E0(x)=x000000011001E(x)=000000000000上式指出了系统循环码的译码方法：将收到的码字 用去除，如果除尽则无错；否则有错。如果有错，可由余式 一一找出对应图样，然后将错误图样与模2和，即为所求码字，从而实现纠错目的。根据前面的讨论，可得（7，3）循环码译码的程序流程图如图2.3-1所示初始化 由R(x)确定S(x)：S(x)=0，无误码误码 是 由S(x)确定错误图样E(x) 否纠错C(x)=E(x)+R(x)存储C(x)图 5 译码程序框图2.4运行结果及仿真 2.4. 1.正确编码界面图6 正确编码界面 在C环境下，输入“c”,再输入3位信息位，软件执行后输出7位循环编码。例如输入的是010，系统输出的是0101110. 2.4.2无差错编码仿真结果图7 无差错编码仿真结果图输入“e”,系统将进行译码操作，当输入的译码信息和编码结果一样时，系统就会把正确将信息位从该码组译出来。输入7位为1101000，与编码输入的3个信息位的结果相同，检验无错误。 2.4.3部分差错编码图图8 一位差错编码图 当输入的译码信息与编码的结果错一位码时，系统就会检测出该错误并将其纠正过来，从而译出真确的信息位。 输入7位0101100，译码结果为010，译码信息与编码结果出现1位错误，系统自动将错误改正，输出为0101110。2.5运行结果理论分析 由循环码性质可知，（7,3）循环码的最小码距d=4,可以检测出小于等于3位错误，纠正1位错误，编码效率为42.8%。设传输正确概率为p,据此设定信道模型存在如下关系：传输正确概率为，信息传输错误概率为，每帧仅发生1位错误的概率为： (39) 0.521703 0.372009 71.30 0.0679347 0.0659036 97.01 0.00697903 0.0069581 99.70 0.00069979 0.00069958 99.97 0.000069979 0.00069958 99.97 表2 模拟结果 综合上表的模拟结果和理论结果可以看出，通信系统的帧传输具有以下性质：（1）在n一定的情况下，信息帧错误传输概率随着比特误码率的增加而增加，最坏情况下帧错误概率几乎为100%，此时系统失去通信能力。（2）在典型的通信环境下，当比特误码率足够小时，绝大多数信息帧错误时每帧1位错误，因此纠正每帧错误有实用价值。2.6软件可行性分析由上述结果可知，该软件的操作方法为程序通过编译运行后，在C环境下，当输入c后按回车键，然后就会提示输入信息，当输入3位的信息位再按回车键，系统就会输出7位的循环编码。当输入d后按回车键，系统会进行译码的操作，当输入的译码信息和编码结果一样时，系统就会正确将信息位从该码组译出来。当输入的译码信息与编码的结果错一位码时，系统就会检测出该错误并将其纠正过来，从而译出真确的信息位。当输入e后按回车，就会退出系统。由此可知，该系统能够实现（7，3）循环码的编码与在无差错和部分差错情况下的译码，因此该软件具有可行性。参考文献1樊昌信 著.通信原理M.国防工业出版社，1999,10.2 宋祖顺 著.现代通信原理M.电子工业出版社,2001,23 黄亚新，米央著.信息编码技术及其应用大全M.电子工业出版社1994.84 孙丽华 著.信息论与纠错编码M.电子工业出版社，2005,35 Proakis 著，张力军 译.数字通信（第四版）M.电子工业出版社，2004,76 潘新民 著.计算机通信技术M.电子工业出版社，2003,7 7 贾世楼 著.信息论理论基础(第二版).哈尔滨工业大学出版社总结通过本次课设，我对循环码的编码和译码的基本原理有了较深的理解，学到了很多的知识。循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码。它有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现；同时循环码的性能也较好，具有较强的检错和纠错能力。我的题目是（7,3）循环码编译码的软件设计，在这一周中遇到了好多问题，由于以前学习C语言没有用心，编程的过程中出现了很多问题。通过同学的帮助，发现并改正了这个错误，最终实现了循环码编译码的软件设计。这次课设让我受益匪浅，让我理解了纠错码的原理和循环冗余码CRC的原理。真正地做到了输入任意的数字信息序列，得出编码结果。还学会了在无差错和部分差错的情况下进行译码。 最后感谢老师对我们的精心指导和帮助，感谢同学们对我的帮助。附录循环码编码译码软件设计程序/*(7,3)循环码的编译及纠检错*/#include#include #include/*函数声明*/void Begin();void Code();void Decoding();/*主函数*/void main() printf(n This software main function is carries on the code and the decoding to (7,3) cyclic code .n); Begin();/*进行编码*/void Code() int input3; int output7; int reg3=0, 0, 0; int temp,i,j,t; printf(Please input the information code :); for(i=0;i3;i+) scanf(%d,&input i); /*输入3位信息码*/ for(i=0;i3;i+) /*进行除法操作*/ temp=reg2+inputi; /*生成多项式为g(x)=x4+x3+x2+1*/ if(temp=2)temp=0; reg2=reg1+temp; if(reg2=2)reg2=0; reg1=reg0; reg0=temp; for (i=0;i3;i+)outputi=inputi;/*进行编码操作*/for (i=3;i0;j-) regj=regj-1; reg0=0; outputi=temp; printf( );printf(n);printf(The information code output is:n);for(i=0;i7;i+)printf (%d,outputi);/*输出编码结果*/printf(n);printf( );printf(n);Begin();/*译码并进行纠检错*/void Decoding()int input 7,output7; int