循环码的数据容错毕业论文.doc

《循环码的数据容错毕业论文.doc》由会员分享，可在线阅读，更多相关《循环码的数据容错毕业论文.doc（45页珍藏版）》请在三一办公上搜索。

1、毕业论文（设计）题 目：循环码的数据容错 毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；

2、学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规

3、定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日目录摘要1ABSTRACT2第一章 循环码容错概述31.1课题研究的目的和意义31.2课题在国内外的发展情况41.2.1单片机应用41.2.2网络应用4第二章 课题理论介绍62.1循环码编码原理62.2循环码的按模运算72.3循环码的生成矩阵82.4循环码的生成多项式10第三章 循环码容错系统需求分析12

4、3.1循环码内部容错123.1.1参数n、k的输入133.1.2生成矩阵G(x)的获得131.生成多项式的获得132.生成多项式的选择143.生成矩阵的生成153.1.3输出码组的生成163.1.4错码的产生及内部容错进行纠正171.干扰串的输入172.余数串的获得173.错码串的显示174.错码的内部容错纠正183.2循环码相互容错18第四章 循环码容错系统详细设计204.1开发环境说明204.2详细设计204.2.1参数输入设计201.算法实现202.算法说明204.2.2生成矩阵的设计201.生成多项式的获得202.生成矩阵的生成214.2.3生成码组设计221.算法实现222.算法说明

5、234.2.4错码的产生及内部容错进行纠正231.余数串的获得232.内部容错纠正错码234.2.5相互容错纠正错码241.check()函数242.bFinalData事件触发25第五章 具体实现及运行结果275.1 循环码内部容错285.1.1参数输入部分285.1.2生成多项式的获得295.1.3生成矩阵的获得295.1.4编码输出305.1.5干扰示例305.1.6内部容错纠正315.2 循环码相互容错315.2.1数据的录入315.2.2相互容错干扰单个数据325.2.3相互容错干扰多个数据33第六章 总结35第七章 致谢37参考文献38摘要在线性分组码中，有一种重要的码称为循环码。

6、这种码的编码和解码设备都不太复杂，且检（纠）错的能力较强。循环码具有循环性，任一码组循环一位以后，仍为该码中的一个码组。对于传输中造成的错误，通过查表对比错误图样的方法，可以很容易地找出错码的所在，并将它纠正。鉴于循环码的这些优势，目前它在理论上和实践中都有较大的发展。 本文主要介绍，通过循环码的编码，提高了数据的可靠性和有效性。在循环码的具体实现上，设计了自己的算法，实现了循环码的生成、编码、干扰和纠错，既体现了循环码作为线性分组码的一般特性，又表现了其可循环的特殊性。这改善了数据在不可靠信道中传输信息得不到保证的问题，完成数据的在不可靠信道的有效传输，验证了循环码编码的重要性。关键字：循环

7、码，封闭，纠错ABSTRACTAmong all those Linear-Block Codes, there is an important one which is called Cyclical Code. This kind of code only requires relatively simple Encoding and Decoding devices, but can provide a truly exceptional error-correcting ability. This so-called Cyclical Code has the ability of c

8、ycling, that each legal code block would turn into another legal one by cyclical-moving one single position. However, in order to recorrect the mistakes during the transporting process, we need a Mistake-Graphics Table to make sure where the mistake really is, and then make it right again. With all

9、these advantages, Cyclical Code currently becomes a new and fast-moving technology both theoretically and practically. This paper introduces that, after the encoding process by the Cyclical Code, boyh the reliability and validity of data have been proved. As for the realization part of the cyclic co

10、de, Some algorithms have been designed to achieve the formation, encoding, interference and error correction of Cyclical Code, not only show those general characteristics of Linear-Block Codes, but also demonstrat its unique recyclability. This process improves the problems during the data transmitt

11、ing process, which might be caused when transmitted through unreliable data channel, completes the process of reliable data-transmitting through unreliable data channel, reassures the importance of Cyclical Code Encoding.KEY WORDS- Cyclical Code, Incapsulating, Error-Correcting第一章 循环码容错概述本章主要介绍了数据容错

12、技术的背景及意义，并且讨论了该技术的现状和发展前景，就此提出问题并确定目标，最后就开发此系统所要用到的相关技术作简要的说明。1.1课题研究的目的和意义由于数字信号在传输过程中受到干扰的影响，使信号码元波形变坏，故传输到接收端后可能发生错误判决。由信道中乘性干扰引起的码间干扰，通常可以采用均衡的办法纠正，而加性干扰的影响则要从其他途径解决。通常，在设计数字通信系统时，首先应从合理地选择调制制度、解调方法以及发送功率等方面考虑。若采取上述措施仍难以满足要求，则就要考虑采用差错控制措施。在随机信道中，错码的出现是随机的，且错码之间是统计独立的6。例如，由正态分布白噪声引起的错码就具有这种性质。因此，

13、当信道中加性干扰主要是这种噪声时，就称这种信道为随机信道。在突发信道中，错码是成串集中出现的，也就是说，在一些短促的时间区间内会出现大量错码，面在这些短促的时间区间之间却又存在较长的无错码区间。对于不同类型的信道，应采用不同的差错控制技术。在实际应用中，数据传输一般采用系统码的编码方式，即在发送的信息序列之后附加上特定位数序列的冗余位，该冗余位称为所发送的信息序列的监督位。监督位一般是由所发送的信息序列经过恰当的变化而产生。若监督位由信息序列经过线性组合得到，则称得到的码为线性分组码。循环码是线性分组码的一个重要子类，具有严密的代数学理论2。循环码“线性”是指任意两个循环码模2相加所得的新码仍

14、为循环码。循环码具有线性码的一般性质（即封闭性，指一种线性分组码的任意两个码组这和仍是该分组码的另一个码组）外，还具有循环性，即循环码中任一码组循环一位（将最右端码元移至左端，或反之）以后，仍为该码组中的一个码组。（n，k）循环码表示其中信息位为k，监督位为n-k位。1.2课题在国内外的发展情况本节介绍相关技术在国内外的己有的发展。1.2.1单片机应用循环码为信道编码，具有很强的纠、检错功能，它是建立在严密的数学理论基础之上8。循环码具有固定的代数结构，可以用线性反馈移位寄存器实现编译码电路，所以可以找到很多简单的编译码方法，目前在数据通信上特别是在卫星通信中循环码得到了广泛应用。近年来随着计

15、算机软件的飞速发展，许多用实物实现的问题都可以在软件上得以实现。单片机就是软件发展的杰出产物。单片机具有内部资源丰富，性能全面，通用性强，可覆盖多种应用要求的优点4。基于单片机设计的电路十分广泛的应用在当今的各个领域中。以往循环码编译码电路大多用移位寄存器和模2和构成的线性时序网络来完成。基本电路简单，容易实现。但在体积和功能的扩展上受到了限制而不能发挥更大作用。使用软件编程方法实现编译码过程既有简化电路，可靠性高、运算速度快、体积小等优点，又可以扩展电路其它功能9。而且可以根据具体要求任意修改，这是其它硬件电路所无法相比的。是抛开传统模式的一种新的尝试。在由单片机组成的遥测、遥控系统中，大多

16、数直接利用单片机的串行通信功能进行数据的传输和控制。然而在实际通信过程中，大量的随机干扰严重影响了数据传输的准确性，破坏了系统的稳定性，使串行通信的误码率大到了不可容忍的程度。因此，有前人针对信道对于数据传输的影响，提出了基于单片机MCS-52单片机系统的软件纠错编码、译码方案，并详细介绍了其实现方法。1.2.2网络应用在网络编码中，还有一种称为CRC，即循环冗余校验码的多项式编码，这种编码的基本思想是：将位串看成是系数为0或1的多项式。一个k位的帧看作是一个k-1次多项式的系数列表，该多项式共有k项，从到。这样的多项式认为是k-1阶多项式。高次（最左边）位是项的系数：接下去的位是项的系数；依

17、此类推3。例如，110001有6位，因此代表了一个共有6项的多项式，其系数为1、1、0、0、0和1 ，即。多项式的算术运算采用代数域理论的规则，以2为模来完成。加法没有进位，减法没有借位。加法和减法都等同于异或9。当使用多项式编码时，发送方和接收方必须预先商定一个生成多项式1。生成多项的最高位和最低位必须是1。假设一帧有m位，它对应于多项式M(x)，为了计算它的校验和，该帧必须比生成多项式长。基本的思想是在帧的尾部追加一个校验和，使得追加这后的帧所对应的多项式能够被G(x)除尽。当接收方收到了带校验和的帧之后，它方式着用G(x)去除它。如果有余数的话，则表明传输过程中有错误5。第二章 课题理论

18、介绍本章主要介绍循环码的相关理论依据及原理。2.1循环码编码原理在线性分组码中，有一种重要的码称为循环码。它是在严密的代数学理论基础上建立起来的。这种码的编码和解码设备都不太复杂，且检（纠）错的能力较强，目前在理论上和实践上都有了较大的发展。循环码除了具有线性码的一般性质外，还具有循环性，即循环码中任一码组循环一位（将最右端的码元移至左端，或反之）以后，仍为该码中的一个码组。在表2.1中给出一种（7，3）循环码的全部码组。由此表可以直观看出这种码的循环性。例如，表2.1中的第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。一般来说，若()是一个循环码组，则表2.1码组编号信息

19、位监督位码组编号信息位监督位1234000001010011000001111110100156781001011101111011110001010010()()()也是该编码中的码组。在代数编码理论中，为了便于计算，把这样的码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成 公式(2.1)表2.1中的任一码组可以表示为 公式(2.2)例如，表中的第7组可以表示为公式(2.3)这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中、和为“1”，其他均为零。因此我们并不关心的取值。这种多项式有时称为码多项式。2.2循环码的按模运算在整数运算中，有模n运算。例如，在模2运算中，

20、有1+1=20（模2），1+2=31（模2），2*3=60（模2）等。一般来说，若一整数m可以表示为 公式(2.4)式中Q整数。则在模n运算下，有(模) 公式(2.5)这就是说，在模n运算下，一整数m等于其被n除得这余数。在码多项式运算中也有类似的按模运算。若一任意多项式F(x)被一n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即 公式(2.6)则写为(模) 公式(2.7)这时，码多项式系数仍按模2运算，即只取值0和1。例如，被()除得余项1，所以有 (模) 公式(2.8)同理(模) 公式(2.9)因为 注意，由于在模2运算中，用加法代替了减法，故余项不是，是。在循环码

21、中，若是一个长为n的许用码组，则在按模运算下，亦是一个许用码组，即若(模) 公式(2.10)则也是一个许用码组。其证时是很简单的，因为若 公式(2.11)则 公式(2.12)所以这时有 公式(2.13)公式(2.13)中正是公式(2.11)中代表的码组向左循环移位i次的结果。因为原已假定为一循环码，所以也必为该码中一个码组。例如，式(2.3)中循环码其码长n=7。现给定i=3，则公式(2.14)其对应的码组为0101110，它正是表9-6中第3码组。由上述分析可见，一个长为n的循环码，它必为按模()运算的一个余式。2.3循环码的生成矩阵根据线性码的性质可知，有了生成矩阵G，就可以由k个信息位得

22、出整个码组，而且生成矩阵G的每一行都是一个码组5。例如，在式(2.17)中，若，则码组A就等于G的第一行；若，则码组A就等于G的第二行，等等。由于G是k行n列矩阵，因此，若能找到k个已知码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的，否则，给定的信息位与编出的码组就不是一一对应的。在循环码中，一个(n,k)码有个不同码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。在循环码中除全“0”码组外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能为(k-1)位2。否则，在经过若干次循环

23、移们后将得到一个k个信息位全为“0”，但监督位不全为“0”的码组，这在线性码中显然是不可能的。因此g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且，这个g(x)还是这种(n,k)码中次数为(n-k)的唯一的一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次将小于(n-k)，即连续“0”的个数多于(k-1)。显然，这是与前面的结论矛盾的，故是不可能的。我们称这唯一的(n-k)次多项式g(x)为码的生成多项式。一量确定了g(x)，则整个(n,k)循环码就被确定了2。因此，循环码的生成矩阵G可以写成 公式(2.15)例如，在表2.1所给出的循环码

24、中，n=7,k=3,n-k=4。可见，唯一的一个(n-k)=4次码多项式代表的码组是第二码组0010111，相对应的码多项项式（即生成多项式）将此g(x)代入上式，得到 公式(2.16)或 公式(2.17)由于上式不符合公式(2.15)所示的形式，所以此生成矩阵不是典型的。不过，将矩阵作线性变换，不难化成典型阵。类似公式(2.17)，我们可以写出此循环码组，即 公式(2.18)公式(2.18)表明，所有码多项式T(x)都可被g(x)整除，而且任一次数不大于(k-1)的多项式乘g(x)都是码多项式。2.4循环码的生成多项式由公式(2.18)可知，任一循环码多项式T(x)都是g(x)的倍式，故可以

25、写成 公式(2.19)而生成多项式g(x)本身也是一个码组，即有 公式(2.20)由于码组为一次多项式，故为一n次多项式。由公式(2.10)可知，在模运算下亦为一码组，故可以写成 公式(2.21)上式左端分子和分母都是n次多项式，故商式Q(x)=1，因此，上式可化成 公式(2.22)将公式(2.19)和公式(2.20)代入上式，并化简后可得 公式(2.23)公式(2.23)表明，生成多项式g(x)应该是()的一个因式。这一结论为我们寻找循环码的生成多项式指出了一条道路，即循环码的生成多项式应该是()的一个()次因式。例如，可以分解为 公式(2.24)为了求(7,3)循环码的生成多项式g(x)，

26、要从上式中找到一个(n,k)=4次的因子。不难看出，这样的因子有两个，即 公式(2.25) 公式(2.26)以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出的循环码组也不同。用公式(2.25)作为生成多项式产生的循环码即为表2.1所列。第三章 循环码容错系统需求分析本章主要介绍本次设计需要完成的工作及初步系统设计。分循环码内部容错和循环码相互容错两部分。3.1循环码内部容错对于循环码的实际应用，前人做过很多的尝试。但在本次设计中，无法将所有前人的工作全部实现。我要做的工作是，实现循环码的生成过程，输出码组，并采用内部容错和相互容错两种方式对错误的数据进行纠正。工作如下：a.参数

27、n、k由人工输入，可自动判断是否正确；b.依据因式分解，自行产生G；c.对于任意给定的输入码组，可产生正确的输出码组；d.对于任意给定的输入码组，可检纠错；e. 基于循环码的数据容错，采用内部容错、相互容错两种模式。开始输入n,kn,k合乎标准得到生成矩阵产生码组结束YN图3.1 整体流程图接下来，我将按照设计方案的设计顺序依次说明。3.1.1参数n、k的输入此模块内部又包括两个部分。一是数据输入部分，负责数据的接收；二是数据判断部分，负责断判输入数据是否合理，如果合理，直接进行下面部分，如果不合理，要重新输入，并继续判断。输入部分要求输入两个数据n和k，n是循环码的总码长，k是码中信息位的长

28、度。通过计算，得到监督位数为r=n-k。判断依据是或，如果此式成立，则n，k符合要求，可以继续进行下面的操作；如果此式不成立，则要重新输入。流程图如下：开始输入n,kn,k合乎标准YN结束图3.2 输入部分流程图3.1.2生成矩阵G(x)的获得然而，要得到生成矩阵G(x)，首先要得到的是生成多项式g(x)。每一个生成矩阵G(x)和其生成多项式g(x)是一一对应的关系，也就是说，有一个生成多项式，就有一个对应的生成矩阵。因此，我们要先想办法得到生成矩阵。对于每一组符合条件的n，k组合，它们可以得到的生成多项式可能不是唯一的。因此，我们要把符合条件的生成多项式全部列出来供人选择。这个模块包括三个部

29、分。一部分是生成多项式的获得；一部分是从生成的众多生成多项式中选择一个进行下面的操作；一部分是根据所选生成多项式生成相应的生成矩阵。其中最重要的是第一部分，生成多项式的生成。1.生成多项式的获得为了解释方便，我们这里取n=7，k=3的n,k组合进行解释。若要得到(7,3)循环码的生成多项g(x)，由2.1节的理论介绍，我们知道，就需要找到的次因子，而这种多项式除最高次项项和最低次项项的系数不能为0外，其它项的系数均可以为0。因此，所有可能符合条件的这种多项式共有个。我们下面的工作就是在这8个可能符合条件的多项式中筛选出真正符合条件的备选生成多项式。要找到的次因子，其中一个可行的办法就是用去依次

30、除上面提到的8个多项式，判断余数，如果有余数，也就是说所得到的不余数为0，那这个多项式不符合条件；相反，如果没有余数，也就是说所得到的余数为0，那这个多项式符合条件，可以作为备选的生成多项式。流程图如下：开始i=0itotali+rem.n=0列入备选NNYY结束 图3.3获得生成多项式流程图2.生成多项式的选择从上一步生成的备选生成多项式中选择一个进行下面的步骤。选择的方式为1、2、3 。经过此步骤后，会有一个生成多项式被出选出，这个生成多项式的长度n为n-k+1。3.生成矩阵的生成根据上一步的选择，生成相应的生成矩阵。具体做法就是，先在所选生成多项式的前面加上(k-1)个0，也就是先把它的

31、长度变为n。然后将这个得到的多项式进行移位操作，并且把每一次移位的结果都记录下来。从这n个多项式中选出k个符合条件的多项式构成生成矩阵G(x)，条件是使得这k个式子的前三列能够组成k*k的单位方阵。流程图如下：开始i=0jtem.nnj=tem.n-tem.ktem=leftSlip(dividercho-1,i);idividercho-1.ntem.contentj=1len+;tem.gxsitio=j;j+len=1len=0;i+YNYYYN结束图3.4生成生成矩阵流程图3.1.3输出码组的生成这部分功能，简单的说，就是把输入的长度为k的纯信息位码转化为长度为n的加上监督位的码。从计

32、算上来说，就是用1行k列的输入码乘以k行n列的生成矩阵G(x)。即： 公式(3.1)比如： 公式(3.2)3.1.4错码的产生及内部容错进行纠正在实际应用中，错码产生的原因以及错码的形式多种多样。在这里，我只是简单地将现实中的情况进行模拟。这一模块包括四个部分。1.干扰串的输入这部分是以0和1的组合形式进行输入，但是总长度要等于n。比如，一个n为7的码组，若输入0010000就是将第五位人为改错，其他位不变。2.余数串的获得由于任一码组多项式T(x)都应能被生成多项式g(x)整除，所以在接收端可以将接收码组R(x)用原生成多项式g(x)去除。当传输中未发生错误时，接由码组与发送码组相同，即R(

33、x)=T(x),故接收码组R(x)必定能被g(x)整除；若码组在传输中发生错误，则，R(x)被g(x)除时可能除不尺面有余项，即有 因此，我们就以余项是否为零来判别码组中有无错码。计算的运算结果，若余项为零，则认为码组R(x)无错；若运算结果余项不等于零，则认为R(x)中有错，但此时我们还不能知道错的位到底是哪一位。这一部分工作，我把它放到其他部分去做，这里要做的只是把这个余数显示出来。 3.错码串的显示这一部分就是把受到干扰后的错码显示出来。具体操作也比较简单，就是把原数据串和干扰串做异或操作。4.错码的内部容错纠正在接收端为纠错而采用的解码方法比检错要复杂一些。为了能够纠错，要求每个纠正的

34、错误图样必须与一个特定余式有一一对应关系。这里所说的错误图样是指错码矩阵E的各种具体取值的图样，余式是指接收码组R(x)被生成多项式g(x)除所得的余式。因为只有存在上述一一对应的关系时，才可能从上述余式唯一地决定错误图样，从而纠正错码。因此，原则上纠错可按下述步骤进行：(1)用生成多项式g(x)除接收码组R(x)=T(x)+E(x)，得出余式r(x)；(2)按余式r(x)用查表的方法或通过某种运算得到错误图样E(x)，例如，通过计算校正子S和利用类似表3.1的关系，就可确定错码的位置；(3)从R(x)中减去E(x)，便得到已纠正错误的原发送码组T(x)现在问题就集中到了这个“表”，对于(7,

35、3)循环码，错码位置与余数串的关系是这样的：表3.1余数串错误位置余数串错误位置100001000010000112341011111001110000567无错因此，在这个程序中，纠错的相关工作就是根据这个表来做的。3.2循环码相互容错在工程设计中，容错设计又叫做失败安全设计(fail-safe design)，这种系统不会因为错误而停止运行，仅仅会带来吞吐量的减少或响应时间的延长。也就是说，系统做为一个整体不会因为软件或硬件的问题而受到种种影响。 而在考虑为数据做冗余备份时，我们又一定考虑下列问题： 1.数据对于系统有多么重要。 如果一个数据的存在与否直接关乎系统是否可以正常运行，那么，我们就需要把这个数据做冗余备份。如果一个数据不是很重要，我们可以根据实际情况选择是否要将这一数据进行备份。 2.数据出错的可能性有多大。 如果一个数据不易出错，或者这个数据本身已经有了很强的纠正错误的能力，即使出现错误，系统自身也能够发现并改正错误，那么我们也无需再为这个数据做备份。 3.为数据做备份的代价有多大。如果系统为某一数据做备份