循环码的数据容错毕业论文(编辑修改稿)

循环码的数据容错毕业论文(编辑修改稿)内容摘要：

d when transmitted through unreliable data channel, pletes the process of reliable datatransmitting through unreliable data channel, reassures the importance of Cyclical Code Encoding. KEY WORDS Cyclical Code, Incapsulating, ErrorCorrecting 循环码的数据容错 第一章 循环码容错概述 3 第一章 循环码容错概述 本章主要介绍了数据容错技术的背景及意义，并且讨论了该技术的现状和发展前景，就此提出问题并确定目标，最后就开发此系统所要用到的相关技术作简要的说明。 由于数字信号在传输过程中受到干扰的影响，使信号码元波形变坏，故传输到接收端后可能发生错误判决。 由信道中乘性干扰引起的码间干扰，通常可以采用均衡的办法纠正，而加性干扰的影响则要从其他途径解决。 通常，在设计数字通信系统时，首先应从合理地选择调制制度、解调方法以及发送功率等方面考虑。 若采取上述措施仍难以满足要求，则 就要考虑采用差错控制措施。 在随机信道中，错码的出现是随机的，且错码之间是统计独立的 [6]。 例如，由正态分布白噪声引起的错码就具有这种性质。 因此，当信道中加性干扰主要是这种噪声时，就称这种信道为随机信道。 在突发信道中，错码是成串集中出现的，也就是说，在一些短促的时间区间内会出现大量错码，面在这些短促的时间区间之间却又存在较长的无错码区间。 对于不同类型的信道，应采用不同的差错控制技术。 在实际应用中，数据传输一般采用系统码的编码方式，即在发送的信息序列之后附加上特定位数序列的冗余位，该冗余位称为所发送的信息序 列的监督位。 监督位一般是由所发送的信息序列经过恰当的变化而产生。 若监督位由信息序列经过线性组合得到，则称得到的码为线性分组码。 循环码是线性分组码的一个重要子类，具有严密的代数学理论 [2]。 循环码“线性”是指任意两个循环码模 2 相加所得的新码仍为循环码。 循环码具有线性码的一般性质（即封闭性，指一种线性分组码的任意两个码组这和仍是该分组码的另一个码组）外，还具有循环性，即循环码中任一码组循环一位（将最右端码元移至左端，或反之）以后，仍为该码组中的一个码组。 （ n， k） 循环码表示其中信息位为 k，监督位为 nk 位。 循环码的数据容错 第一章 循环码容错概述 4 本节介绍相关技术在国内外的己有的发展。 单片机应用 循环码为信道编码，具有很强的纠、检错功能，它是建立在严密的数学理论基础之上 [8]。 循环码具有固定的代数结构，可以用线性反馈移位寄存器实现编译码电路，所以可以找到很多简单的编译码方法，目前在数据通信上特别是在卫星通信中循环码得到了广泛应用。 近年来随着计算机软件的飞速发展，许多用实物实现的问题都可以在软件上得以实现。 单片机就是软件发展的杰出产物。 单片机具有内部资源丰富，性能全面，通用性强，可覆盖多种应用要求的优点 [4]。 基于单片机设计的电路十分广泛的应用在当今的各个领域中。 以往循环码编译码电路大多用移位寄存器和模 2 和构成的线性时序网络来完成。 基本电路简单，容易实现。 但在体积和功能的扩展上受到了限制而不能发挥更大作用。 使用软件编程方法实现编译码过程既有简化电路，可靠性高、运算速度快、体积小等优点，又可以扩展电路其它功能 [9]。 而且可以根据具体要求任意修改，这是其它硬件电路所无法相比的。 是抛开传统模式的一种新的尝试。 在由单片机组成的遥测、遥控系统中，大多数直接利用单片机的串行通信功能进行数据的传输和控制。 然而在实际通信 过程中，大量的随机干扰严重影响了数据传输的准确性，破坏了系统的稳定性，使串行通信的误码率大到了不可容忍的程度。 因此，有前人针对信道对于数据传输的影响，提出了基于单片机 MCS52单片机系统的软件纠错编码、译码方案，并详细介绍了其实现方法。 网络应用 在网络编码中，还有一种称为 CRC，即循环冗余校验码的多项式编码，这种编码的基本思想是：将位串看成是系数为 0 或 1的多项式。 一个 k位的帧看作是一个 k1次多项式的系数列表，该多项式共有 k 项，从 1kx 到 0x。 这样的多项式认为是 k1阶多项式。 高次（最左边）位是 1kx 项的系数：接下去的位是 2kx 项的系数；依此类推 [3]。 例如， 110001有 6 位，因此代表了一个共有 6项的多项式，其系数为 0、 0、 0 和 1 ，即 045 xxx 。 循环码的数据容错 第一章 循环码容错概述 5 多项式的算术运算采用代数域理论的规则，以 2为模来完成。 加法没有进位，减法没有借位。 加法和减法都等同于异或 [9]。 当使用多项式编码时，发送方和接 收方必须预先商定一个生成多项式 [1]。 生成多项的最高位和最低位必须是 1。 假设一帧有 m位，它对应于多项式 M(x)，为了计算它的校验和，该帧必须比生成多项式长。 基本的思想是在帧的尾部追加一个校验和，使得追加这后的帧所对应的多项式能够被 G(x)除尽。 当接收方收到了带校验和的帧之后，它方式着用 G(x)去除它。 如果有余数的话，则表明传输过程中有错误 [5]。 循环码的数据容错 第二章 课题理论介绍 6 第二章 课题理论介绍 本章主要介绍循环码的相关理论依据及原理。 在线性分 组码中，有一种重要的码称为循环码。 它是在严密的代数学理论基础上建立起来的。 这种码的编码和解码设备都不太复杂，且检（纠）错的能力较强，目前在理论上和实践上都有了较大的发展。 循环码除了具有线性码的一般性质外，还具有循环性，即循环码中任一码组循环一位（将最右端的码元移至左端，或反之）以后，仍为该码中的一个码组。 在表 中给出一种（ 7， 3）循环码的全部码组。 由此表可以直观看出这种码的循环性。 例如，表 中的第 2 码组向右移一位即得到第 5码组；第 5码组向右移一位即得到第 7码组。 一般来说，若( 021 aaa nn  )是一个循环码组，则 表 码组编号 信息位 监督位 码组编号 信息位 监督位 456 aaa 0123 aaaa 456 aaa 0123 aaaa 1 2 3 4 000 001 010 011 0000 0111 1110 1001 5 6 7 8 100 101 110 111 1011 1100 0101 0010 ( 1032   nnn aaaa ) ( 2143   nnnn aaaa ) ( 1210 aaaa n  ) 也是该编码中的码组。 在代数编码理论中，为了便于计算，把这样的码组中各码元当作是一个多项式的系数，即把一个长度为 n 的码组表示成 012211)( axaxaxaxT nnnn   公式 () 表 中的任一码组可以表示为 012233445566)( axaxaxaxaxaxaxT  公式 () 例如，表中的第 7组可以表示为 循环码的数据容错 第二章 课题理论介绍 7 11010011)( 25623456  xxxxxxxxxxT 公式 () 这种多项式中， x仅是码元位置的标记，例如上式表示第 7 码组中 6a 、 5a 、2a 和 0a 为“ 1”，其他均为零。 因此我们并不关心 x 的取值。 这种多项式有时称为码多项式。 在整数运算中，有模 n 运算。 例如，在模 2 运算中，有 1+1=2 0（ 模 2） ，1+2=3 1（模 2）， 2*3=6 0（模 2）等。 一般来说，若一整数 m 可以表示为 npQnm  np 公式 () 式中 Q—— 整数。 则在模 n运算下，有 pm (模 n ) 公 式 () 这就是说，在模 n运算下，一整数 m等于其被 n 除得这余数。 在码多项式运算中也有类似的按模运算。 若一任意多项式 F(x)被一 n 次多项式 N(x)除，得到商式 Q(x)和一个次数小于 n的余式 R(x)，即 )()()()( xRxQxNxF  公式 () 则写为 )()( xRxF  (模 )(xN ) 公式 () 这时，码多项式系数仍按模 2 运算，即只取值 0 和 1。 例如， 3x 被 ( 13x )除得余项 1，所以有 13x (模 13x ) 公式 () 同理 11 224  xxxx (模 13x ) 公式 () 因为 xxxxxx4243 11 12 xx 注意，由于在模 2运算中，用加法代替了减法，故余项不是 12 xx ，是 12  xx。 循环码的数据容错 第二章 课题理论介绍 8 在循环码中，若 )(xT 是一个长为 n 的许用码组，则 )(xTxi  在按模 12 xx运算下，亦是一个许用码组，即若 )()( 39。 xTxTxi  (模 1nx ) 公式 () 则 )(39。 xT 也是一个许用码组。 其证时是很简单的，因为若 012211)( axaxaxaxT nnnn   公式 () 则 )1()( 1102211 011112211  nininininniniinininninnixaxaxaxaxa xaxaxaxaxaxTx 模 公式 () 所以这时有 1110221139。 )(   ninininnin axaxaxaxaxT 公式 () 公式 ()中 )(39。 xT 正是公式 ()中 )(xT 代表的码组向左循环移位 i 次的结果。 因为原已假定 )(xT 为一循环码，所以 )(39。 xT 也必为该码中一个码组。 例如，式 ()中循环码 1)( 256  xxxxT 其码长 n=7。 现给定 i=3，则 )1()1()( 723535892563  xxxxxxxxxxxxxxTx i 模 公式 () 其对应的码组为 0101110，它正是表 96中第 3码组。 由上述分析可见，一个长为 n 的循环码，它必为按模 ( 1nx )运算 的一个余式。 根据线性码的性质可知，有了生成矩阵 G，就可以由 k 个信息位得出整个码组，而且生成矩阵 G 的每一行都是一个码组 [5]。 例如，在式 ()中，若10003456 aaaa ，则码组 A就等于 G的第一行；若 01003456 aaaa ，则码组 A 就等于 G的第二行，等等。 由于 G是 k行 n列矩阵，因此，若能找到 k个已知码组，就能构成矩阵 G。 如前所述，这 k 个已知码组必须是线性不相关的，否则，给定的信息位与编出的码组就不是一一对应的。 在循环码中，一个 (n,k)码有 k2 个不同码组。 若用 g(x)表示其中前 (k1)位循环码的数据容错 第二章 课题理论介绍 9 皆为“ 0”的码组，则 )(,),(),(),( 12 xgxxgxxxgxg k 都是码组，而且这 k 个码组是线性无关的。 因此它们可以用来构成此循环码的生成矩阵 G。 在循环码中除全“ 0”码组外，再没有连续 k 位均为“ 0”的码组，即连“ 0”的长度最多只能为 (k1)位 [2]。 否则，在经过若干次循环移们后将得到一个 k 个信息位全为“ 0”，但监督位不全为“ 0”的码组，这在线性码中显然是不可能的。 因此 g(x)必须是一个常数项不为“ 0” 的 (nk)次多项式，而且，这个 g(x)还是这种 (n,k)码中次数为 (nk)的唯一的一个多项式。 因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次将小于 (nk)，即连续“ 0”的个数多于 (k1)。 显然，这是与前面的结论矛盾的，故是不可能的。 我们称这唯一的 (nk)次多项式 g(x)为码的生成多项式。 一量确定了 g(x)，则整个 (n,k)循环码就被确定了 [2]。 因此，循环码的生成矩阵 G可以写成 )()()()()(21xgxxgxgxxgxxGkk 公式 () 例如，在表 所给出的循环码中， n=7,k=3,nk=4。 可见，唯一的一个 (nk)=4次码多项式代表的码组是第二码组 0010111，相对应的码多项项式（即生成多项式） 1)( 24  xxxxg 将此 g(x)代入上式，得到 )()()()(2xgxxgxgxxG 公式 () 或 0010 1110101 1101011 100)(xG 公式 () 由于上式不符合公式 ()所示的  QIG k 形式，所以此生成矩阵不是典型的。 不过，将矩阵作线性变换，不难化成典型阵。 类似公式 ()，我们可以写出此循环码组，即 循环码的数据容错 第二章 课题理论介绍 10      )()()()()()()()( 45262456456 xgaxxgaxgxaxgxxgxgxaaaxGaaaxT )()( 4526 xgaxaxa  公式 () 公式 ()表明，所有码多项式 T(x)都可被 g(x)整除，而且任一次数不大于 (k1)的多项式乘 g(x)都是码多项式。 环码的生成多项式 由公式 ()可知，任一循环码多项式 T(x)都是 g(x)的倍式，故可以写成 )()()( xgxhxT  公式 () 而生成多项式 g(x)本身也是一个码组，即有 )()(39。 xgxT  公式 () 由于码组 )(39。 xT 为一 )( kn 次多项式，故 )(39。 xTxk 为一 n次多项式。 由公式 ()可知， )(39。 xTxk 在模 )1( nx 运算下亦为一码组，故可以写成 1)()(1 )(39。  nnk x xTxQx xTx 公式 () 上式左端分子和分母都是 n次多项式，故商式 Q(x)=1，因此，上式可化成 )()1()(39。 xTxxTx nk  公式 () 将公式 ()和公式 ()代入上式，并化简后可得  )()(1 xhxxgx kn  公式 () 公式 ()表明，生成多项式 g(x)应该是 ( 1nx )的一个因式。