抗干扰编码技术

1、第四章通信中的抗干扰编码技术4.1 抗干扰编码简介信息在传送的过程中，受到干扰会发生差错，降低通信的可靠性。为提高所传送信息的可靠性，采取专门的编码方式，以提高其抗干扰能力。1、抗干扰编码：通过编码对要传送的数据进行改造，使其内部结构具有一定的规律性和相关性，当干扰破坏了码字的部分结构时，仍能根据码字原有的规律性和相关性，发现甚至纠正错误。也称为信道编码、差错控制。2、抗干扰编码的一般方法：对要传送的数据信息序列按照某种规律，添加一定的校验码元（监督位），由信息序列和校验码构成一个有抗干扰能力的码字。 添加校验码元的规律或规则不同，就形成了不同的抗干扰编码方法，传送数据抗干扰能力的提高，是以牺

2、牲通信效率为代价的。1山东大学研究生课程电气工程学院编码效率为： 其中：k为传送的有效数据码元数，n为总的传送码元数。（3）实现编码和译码的方法要简便。一、最小码距和码的检错、纠错能力 若用 k 表示要传送的数据序列 m 的长度，用n表示经抗干扰编码后的码字位数，则码字中的校验码位数就是（nk）位，一般写为：r nk，记做（n，k）码，任意一个（n，k）码可能包含的码字最多可以有2k个。 在接收端，对收到的每一个码字译码的时候，可以采用最大似然译码法，就是把收到的码字同抗干扰编码时可能出现的2k个码字比较，看其与哪个码字最相似，并将这个最相似的码字作为正确的接收码字。码字的相似程度可以用码距的

3、大小来判断。1、码距两个同样长度的码字之间，对应码位上不相同的码元数目，称为两个码字的汉明距离，简称码距。3、对抗干扰编码的基本要求是：（1）码的性能要好：能检出或纠正最可能出现的那些错误类型；（2）编码效率要高：所加监督位要尽可能的少，编码以后的传输效率要高；2山东大学研究生课程电气工程学院 在一种码的所有码字集合中，任意两个码字之间的码距并非相等，我们把所有可能的码字对之间码距的最小值，称为这个码字集合的最小码距，记为dmin。2、码重 码字中非零码元的个数，对于二进制码元，就是码字中“1”码元的个数，用 W 来表示。3、线形分组码： 对长度为k的数据，按一定规律增加 r 位监督位，组成长

4、度为nkr 的码元序列，Cn-1，Cn-2，C1，C0。这种按组进行编码，码的长度为n，其中有 k 位数据码元的码，叫做分组码，记做（n，k）码，rnk 是监督位的长度。 分组码中，监督位与数据位之间满足线性关系的（监督位与数据位之间的关系是由一组线性方程来确定），称为线性分组码。 在一组线性分组码中，任意两个码字相加（模2运算）得到的新码字也在这组线性分组码中。模 2 运算：当相加的两个码字中对应位的码元不同时，新码字中对应位的码元为“1”，否则为“0”。一组线性分组码中，任意两个码字之间的码距，正好等于这两个码字相加后所得新码字的的码重。 3山东大学研究生课程电气工程学院4、码的检错、纠错

5、能力： 根据码距的定义，两个码字的码距越小则越相似，所谓最大似然译码就是根据这一点来实现的，根据接收到的码字，与所有可能出现的码字比较，和哪个码字的码距最小，就译为哪个码字。 一种码的最小码距是衡量这种编码检错纠错能力的重要参数，它能纠正的码字中的错误个数 t 和能检出的错误个数 l 满足如下关系： 增加一种码的最小码距，可以提高这种码的检错纠错能力，这是以增加监督位的位数、牺牲传码效率为代价的。例： 要传送一个开关的状态量，只需要一位二进制数就可以了，其最小码距为1，因此它没有检错纠错能力。如果采用重复码，用“11”和“00”分别代表合闸与分闸，则其最小码距为2，它就能够检出一位错误，但还不

6、能纠错；若用“111”和“000”分别代表合闸与分闸，其最小码距变为3，则发生一位错码时，不仅能检出来，还可以根据最大似然译码原则实现纠错。4山东大学研究生课程电气工程学院 抗干扰编码就是通过某种编码方法，对要传送的k为位数据序列，按照某种规律添加校验码元（监督位），以达到增大这种码的最小码距、提高其检错纠错能力的目的。 一种好的抗干扰编码方案，要既能最大程度的增加其检错纠错能力，又有比较高的传码效率，而且易于实现。4.2 奇偶校验码一、奇偶校验码： 奇偶校验码是一个（n，n1）分组码，它的编码规则是在 n1 位有效数据位的后面，添加一位奇校验或偶校验码元，使每个码字中“1”码元的个数恒为奇数

7、或偶数。 设码字cn-1，cn-2，c1，c0，其中cn-1，cn-2，c1 为数据位， c0 为校验码元（监督位）。当码字中的“1”码元的个数恒为偶数时（偶校验），满足： 或： 这种码称为偶校验码。由此可知：偶校验码的校验码元等于数据码元的模 2 和；5山东大学研究生课程电气工程学院如果码字中“1”的个数恒为奇数（奇校验），则满足： 或这种码称为奇校验码，奇校验码的校验码元等于数据码元的模2和再取非。 奇偶校验码是应用的最多的一种抗干扰编码方式，最大的好处是实现简单，编码效率高，其编码效率为： 但奇偶校验码的检错能力较差，不能纠错。当接收码字错奇数个码元时，它能够监测出有错码，但不能分辩究竟

8、是哪一位码元发生错误；若接收码字错偶数个码元时，则其失去检错能力，会误判为码字中没有错误发生。二、纵横奇偶校验： 纵横奇偶校验码是在纵向和横向两个方向上都进行奇偶校验的一种编码方法，也称为水平垂直奇偶校验码。下图是纵横奇偶校验码的构成图：6电气工程学院山东大学研究生课程校验位mk-1 mk-2 mk-jmk-(j+1) mk-(j+2) mk-2j| | | |mi-1 mi-2 m0 r1(j+1)r2(j+1)ri(j+1)|j列i 行r(i+1)1 r(i+1)2 r(i+1)j r(i+1)(j+1)校验位把数据序列mk-1、mk-2、 m0 排成 i行 j 列的矩阵，然后在每一行和每

9、一列各补充一位奇偶校验码，这样由行校验位r1(j+1)、r2(j+1)、 r(i+1)(j+1)和列校验位r(i+1)1、r(i+1)2、r(i+1)j 和数据位便构同时具有纵向奇偶校验位和横向奇偶校验位的纵横奇偶校验码。 在实际的操作中，我们可以把要传送的每一个字节做为一行，而把每个字节中的对应位做为一列，实现纵横奇偶校验，对于每一列的校验，可以采用每传送一个字节，做一次异或操作（偶校验）的办法来实现。（奇校验 ？）例：如有三个字节：第一个字节10110101第二个字节00011011第三个字节11100001纵向校验码01001111 1 0 1 1 0 1 0 1） 0 0 0 1 1

10、0 1 1 1 0 1 0 1 1 1 0） 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 17电气工程学院山东大学研究生课程 这种纵横奇偶校验方式具有较强的检错能力，当码字中出现一位、两位或三位错误时，不管错误位在上图中如何分布，接收端通过译码都会发现横向奇偶校验出错或纵向奇偶校验出错、或者横向、纵向奇偶校验同时出错，从而实现检错。如果码字中的错误位只有一位，这时同时会出现某一行和某一列的奇偶校验出错，则根据出错的行号和列号，便可以确定错误位的位置，实现纠错。因此，这种码可以纠正一位错误、检出三位以下的错误，是所谓的“纠一检三码”。除此之外，还可以检测出所有奇数个错误和绝大多数

11、偶数个错误（互相补偿的偶数个错误除外）。三、校验和CS（Check Sum）： 从这种纵向奇偶校验方法我们可以得到启发，我们可以采用校验和的办法实现纵向校验。 把m个长度位 l 的数据组作为二进制数按模 L 相加，形成校验和，把校验和附在 m 个数据位后一起发送，通常取 L = 2l 。在接收端，将收到的前面 m 个数据以同样的方式按模 L 相加，得到接收端计算的校验和，并且与收到的校验和比较，如果二者一致，则说明没有错误，如果不一致，则表明传送过程中有错误。8电气工程学院山东大学研究生课程例：1 0 1 0 1 1 0 11 0 0 1 1 1 0 00 1 0 1 0 0 1 10 0 1

12、 0 1 0 0 11 0 0 1 0 1 0 127 26 25 24 23 21 2012341校验和28与码元位对应的权数据组 表中；再与相加，得1，再与 相加得1，由于是模2加，红色的数位溢出丢弃。 1 0 0 1 1 1 0 0） 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1） 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0 0 0） 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 表中每个信息组长度l 8，共有4组，以L = 2l 28为模（也就是28 0），溢出位舍弃。9电气工程学院山东大学研究生课程表21 RS-232C 25针

13、连接器引脚信号分配4.3 循环码 循环码是线性分组码的一个重要子集，它由严格的代数结构，用近世代数方法可以找出许多编码效率高、检错纠错能力强的循环码。由于它的编码和检错方法比较简单易行，而且找到了许多有效的纠错方法，因此，循环码得到了广泛的应用。一、循环码的定义： 一个（n，k）循环码是码长为 n，有 k 位数据位的线性分组码，它的特点是其任意一个码字 C 的每次循环移位，得到的是另一个码字。设： C = | cn-1，cn-2，c1，c0 | 是循环码的一个码字，则 C(1) = | cn-2 ，cn-3，c0 ，cn-1 | C(2) = | cn-3 ，cn-4，cn-1 ， cn-2

14、| C(i) = | cn-I-1 ，cn-I-2， c0 ，cn-1 ， ， cn-I+1 ， cn-i | C(n-1) = | c0 ，cn-1，c2 ，c1 |也都是该循环码的码字。10电气工程学院山东大学研究生课程例如：所示的线性分组码就是一个（7，3）循环码，由3位数据位、4位监督码元组成。二、码组的多项式表示： 为了便于分析，常用码多项式来描述码元序列，如一个（n，k）线性分组码用码元序列 C 描述时为： C = | cn-1，cn-2，c1，c0 | 相应地用码多项式表示时，则可以表示为： 式中 x 的幂次对应于各码元的位置，系数则对应于各码元的取值，在二元制中系数 Ci 取值

15、为“0”或“1”。码多项式 C （x） 与码元序列相对应。（n，k）线性分组码的码长为 n ，所以其码多项式 C （x） 的最高次数不超过 n1。数 据码 字数 据码 字0 0 00 0 0 0 0 0 0 1 0 01 0 0 1 1 1 00 0 10 0 1 1 1 0 11 0 11 0 1 0 0 1 10 1 00 1 0 0 1 1 11 1 01 1 0 1 0 0 10 1 10 1 1 1 0 1 01 1 11 1 1 0 1 0 011电气工程学院山东大学研究生课程例：有一码元序列C，写成多项式形式就是： 两个多项式之间的运算是其对应项系数的运算，在二进制中系数只取0和

16、1，系数之间按照模 2 运算。 如果给码多项式乘以 x，则相当于将码序列左移一位。例如将上式乘以 x 以后，就变为： 而与 C（x） 对应的码元序列为C，恰好是原码元序列C左移一位。同理，对于码多项式乘以 x i ，相当于将相应的码元序列 C 左移 i 位。 （n，k）线性分组码的码多项式 C（x） 在乘以 x i 后， x i .C（x）的最高幂次可能超过 n1。在（n，k）线性分组循环码多项式运算中，以 xn1 为模，码多项式的最高幂次不会超过 n1，给码多项式C（x）乘以 x i 时就可以实现对应码元序列的 i 位循环左移。12电气工程学院山东大学研究生课程三、按模运算：1、整数按模运算

17、 一个整数 m 被非零整数 n 除后，得到商数 q 和余数 r。r 是小于 n 的一个整数: mq nr （r n） 按模 n 运算时将小于 n 的整数0，1，2，n1，共 n 个，称为按模 n 的剩余类。若只关心被 n 除后所得的余数，则所有整数可按 n 划分成 n 个剩余类。例如 n5时有5个剩余类，分别表示|0|，|1|，|2|，|3|，|4|。任一整数，譬如8，被5 整除后余数为3，故按模5运算时8属于剩余类|3|，表示成83（模5）。符号“”表示左右两边的余数相同（同余）。按模5运算时所有整数分属下列5个剩余类： |0| |1| |2| |3| |4| 0 1 2 3 4 5 6 7

18、 8 9 10 11 12 13 14 按模 n 运算时整数之间的相加、相乘等运算可按常规进行，但所得结果应按模 n 处理。例如按模5运算时，4312 2（模5）。 13电气工程学院山东大学研究生课程2、多项式按模运算 与整数按模运算类似，对于任意多项式F（x），可以用一个次数为 n 的多项式N（x）去除，得到商式Q（x）和余式R（x）， R（x）的次数小于 n ，即： F（x）= Q（x） N（x）+ R（x）表示为： F（x） R（x） 模N（x）上式符号“”表示左右两边的余式相同。这称为模 N（x）运算，在二进制情况下，多项式的系数只取0或者1。码多项式运算时，其系数按模2运算。任意多项

19、式F（x）在按模 N（x）的运算下，其结果是F（x）除以 N（x）所得的余式。例：F（x）=x5，N（x）=x4+x3+x2+1，则有： x5 x2+x+1 （模 x4+x3+x2+1） （ x4+x3+x2+1）x5x 1x5+x4+x3+xx4+x3+ xx4+x3+x2+ 1x2+x+1注意：所有运算均为模2运算14电气工程学院山东大学研究生课程 有时如果已经约定了N（x），模N（x）可以省略不写，只写出同余符号“”，对于上例中，如果已经约定N(x)=x4+x3+x2+1，则可以写为： x5 x2 + x + 1 若用 xn+1 去除任意多项式F（x），所得余式次数小于n。在二进制中多项

20、式系数只取0或者1，因而这种 余式共可以有 2n 种，构成 2n个剩余类，称为按模 xn+1 的剩余类。四、循环码的按模xn1 运算 给码多项式C（x）乘以x，相当于将原来的码元序列C左移一位。对于循环码来说：设（n，k）线性分组循环码的码多项式C（x）为：码长为n，C（x）的最高次数不超过n1。对C（x）乘以x后得：在（n，k）线性分组码中，码多项式按模 xn1运算， xn1 0，xn 1，故上式可以写为：15电气工程学院山东大学研究生课程（模 xn +1） 可见在模 xn+1运算下，码多项式 所对应的的是将原来的码元序列C循环左移一位。（n，k）线性分组循环码按模 xn+1运算， xn+1

21、 0， xn 1 x0, x0位与xn等效，其物理意义可以看作时移位时高端溢出的码元被返送到低端，首尾相接，从而形成了循环移位。 同理，给码多项式C（x）乘以 xi 时，设：则若以 xn1为模， xn 1，上式可写为：（模 xn +1）16电气工程学院山东大学研究生课程 可见在按模 xn+1 的运算下，码多项式 所对应的是将原来的码元序列 C 循环左移 i 位。 也可以写成如下形式：式中：17电气工程学院山东大学研究生课程按模 xn1运算时，就可以得到：（模 xn1） 因而对于（n，k）线性分组循环码，若C（x）是一个码字，则在按模 xn1运算下，就是以xn1除多项式 所得的余式C（i）（x）

22、也是一个码字，它对应于将原来的码字循环左移 i 位。余式是次数小于 n 的码多项式。每一个码长为 n 的循环码必属于以 xn1为模的某一剩余类。五、循环码的生成多项式1、生成多项式的定义： 一般来说，生成多项式 g（x）是（n，k）循环码中最低次非零码多项式，其次数为nk。可把 g（x）写成：式中：gi 为生成多项式的系数，为0或者1。 g(x)的首项系数为1，末项系数也必须为1。首项系数为1是显而易见的，否则其次数就不是nk了，而若末项系数为0的话，则 g（x）就变成了18电气工程学院山东大学研究生课程当g（x）循环移位 n1次后得到的码多项式为：其次数低于nk，定义中“码字中非零码多项式的

23、最低次数为nk”矛盾了。所以首项和末项系数都必须是1。2、生成多项式g（x）的性质（1）在一个（n，k）循环码中，有且仅有一个（nk）次的生成多项式 g（x），该（n，k）循环码中的每一个码多项式 C（x）都是生成多项式的倍式，并且每个为 g（x）倍式的、次数不大于（n1）次的多项式，一定是一个码多项式。设： g（x）是（n，k）循环码的生成多项式。因为 g（x）是循环码的一个码字，所以x g（x）， x2 g（x），xk-i g（x）也都是码字。设 mi 为信息位，i0，1，2，k1， mi 取值0或1，则 g（x）的任意次移位组成的C（x）为：这里C（x）仍是一个码字。19电气工程学院山东

24、大学研究生课程把信息组（mk-1，mk-2， m0）写成信息多项式m（x）根据以上两式，得：C（x）m（x）g（x）这说明：任一循环码的码多项式都是生成多项式的倍式。 由这一性质可知：如果用信息多项式 代表 k 位信息序列，（n，k） 循环码中的每个码多项式C（x）都可以表示成： 对信息序列的编码，相当于用信息多项式m（x）乘以生成多项式g（x）。所以生成多项式g（x）确定了由 2k 个信息序列生成的 2k 个码字的编码。 g（x）的次数（nk）等于码字中校验码元的个数。（2）（n，k）循环码的生成多项式g（x）是（xn1）的一个因式。即 xn1g（x）h（x）20电气工程学院山东大学研究生课

25、程式中： 正是g（x）左移 k 次的结果，它必为一个码字，而且是g（x）的倍式。可以写成：Ck（x）g（x）。所以：得：这说明（n，k）循环码的生成多项式是xn1的因式。据此我们可以知道：为得到（n，k）循环码的生成多项式，可以先对xn1进行因式分解，然后取nk次因式，就得到生成多项式g（x）（3）若g（x）是一个（nk）次多项式，且是xn1的因式，则g（x）生成一个（ n，k ）循环码。将生成多项式g（x）乘以xk，得：21电气工程学院山东大学研究生课程根据生成多项式的性质，我们可以知道：（1）要生成一个（n，k）循环码，必须首先找到生成多项式g（x），它的次数是（nk）次；（2）寻找生成多

26、项式的方法 根据想要生成一个码长为 n 位，信息位为 k 位的（n，k）循环码，首先将因式xn1进行因式分解，式中的 n 是码长的取值；在以上分解时，找出一个次数为（nk）次的因式；最后以这个（nk）次的因式为生成多项式，用它分别乘以2k 个不同的信息序列，便可以得到（n，k）循环码的2k 个码字。22电气工程学院山东大学研究生课程例1：有一（7，3）循环码如表所示: 就是该（7，3）循环码的生成多项式。信息组码 字信息组码字0 0 0 0 0 0 0 0 0 01 0 01 0 0 1 1 1 00 0 1 0 0 1 1 1 0 11 0 11 0 1 0 0 1 10 1 00 1 0

27、0 1 1 11 1 01 1 0 1 0 0 10 1 10 1 1 1 0 1 01 1 11 1 1 0 1 0 0对于（7，3）循环码来讲：n7，k3，则可以对x71进行因式分解： x71（x+1）（x3x21）（x3x1）取其nk734次因式，得： g1（x）（x+1）（x3+x2+1）x4x2x1，由于该码字对应的码元序列为：0 0 1 0 1 1 1不在上述码组中，因此，得到的g1（x）不是所求的生成多项式g（x）而： g2（x）（x1）（x3x1）x4x3x21 才是我们要找的生成多项式g（x） 根据生成多项式的定义，取其前面k1312位都是0的码字（最低次的非零码），写成码多

28、项式就是：23电气工程学院山东大学研究生课程例2：如何形成一个（7，4）循环码：首先，分解x71，找出nk743次的因式。 x71（x4x2x1）(x3x1）生成多项式为：g（x）=x3x1。对信息多项式 ，取m3 m2 m1 m0为十六种不同二进制序列，分别完成运算：运算结果即是（7，4）循环码的十六个码字（见下表）24电气工程学院山东大学研究生课程由g（x）=x3x1生成的（7，4）循环码信息序列码 多 项 式C（x）m（x）g（x）码 字m3 m2 m1 m0c6 c5 c4 c3 c2 c1 c00 0 0 00（ x3x1 ）00 0 0 0 0 0 00 0 0 11（ x3x1

29、） x3x1 0 0 0 1 0 1 10 0 1 0 x（ x3x1 ）=x4x2x0 0 1 0 1 1 00 0 1 1（x1）（x3x1）=x4x3x210 0 1 1 1 0 10 1 0 0 x2（ x3x1 ）x5x3x20 1 0 1 1 0 00 1 0 1（x21）（ x3x1 ）x5x2x10 1 0 0 1 1 1 0 1 1 0（x2x）（ x3x1 ）x5x4x3x0 1 1 1 0 1 00 1 1 1（x2x1）（ x3x1 ）x5x410 1 1 0 0 0 11 0 0 0 x3（ x3x1 ）x6x4x31 0 1 1 0 0 01 0 0 1（x31）（

30、 x3x1 ）x6x4x11 0 1 0 0 1 11 0 1 0（x3x）（ x3x1 ）x6x3x2x1 0 0 1 1 1 01 0 1 1（x3x1）（ x3x1 ）x6x211 0 0 0 1 0 11 1 0 0（x3x2）（ x3x1 ）x6x5x4x21 1 1 0 1 0 01 1 0 1（x3x21）（ x3x1 ）x6x5x4x3x2x11 1 1 1 1 1 11 1 1 0（x3x2x）（ x3x1 ）x6x5x1 1 0 0 0 1 01 1 1 1 （x3x2x1）（ x3x1 ）x6x5x311 1 0 1 0 0 125电气工程学院山东大学研究生课程六、循环码

31、的抗干扰能力1、伴随式计算及纠错假设发送端发送的码字多项式是：而接收端收到的码字多项式是：如果用接收到的码多项式R（x）除以生成多项式g（x）时，如果得商式为P（x），余式为s（x），则有： 多项式s（x）称为接收码字R（x）的伴随式。如果伴随式s（x）为零，表明接收码字多项式R（x）是生成多项式g（x）的倍式，译码判断时认为接收码字就是发送端发来的码字C（x）（接收没有错误）。若伴随式不为零，则认为收到的码字中有错误！ s（x）的次数必然不大于（nk1），所以伴随式是 nk 位的序列，它最多可以取2nk种不同的取值。 如果把发送码字在信道种受干扰的错误图样用多项式表示为：26电气工程学院山东

32、大学研究生课程则接收到的码字为：R（x）C（x）E（x）计算伴随式时需要完成的除法运算是：R（x）/ g（x）C（x）E（x） / g（x）C（x）/ g（x）E（x）/ g（x）注意：上式中，发送码字C（x）必为g（x）的倍式，如果C（x）除以g（x）的商式为q（x）， E（x）除以 g（x）的商式是p（x），余式是s（x），得：R（x）q（x）g（x）+ p（x） g（x） s（x）Q（x） g（x） s（x）其中： Q（x） q（x） p（x） 对比该两式可以看出：接收码字R（x）的伴随式s（x）等于错误图样E（x）除以生成多项式g（x）所得的余式s（x）。可见伴随式中包含有叠加在发送码

33、字上的错误图样的信息，所以不仅可以利用伴随式进行检错，还可以用伴随式完成一定范围内的纠错。 按照最小码距 dmin和码的检错、纠错能力之间的关系，伴随式和错误图样之间的关系为：27电气工程学院山东大学研究生课程1、当接收码字R（x）中的错误码元数为 t 位，并且满足 t （ dmin-1）/2时，对于任何一种重量为 t 的错误图样，唯一地对应一个伴随式。从而可以根据错误图样与伴随式之间的对应关系，由伴随式确定错误图样并实现纠错；即：用伴随式可以检出并纠正 t 位错误，条件是t （ dmin-1）/2。2、当接收码字中的错误码元数为 l ，且满足（ dmin-1）/2 l dmin-1时，可以出

34、现多个错误图样对应同一个伴随式的情况，这时不能由伴随式确定唯一的一个错误图样，因此不能完成纠错，但根据伴随式不为零可以实现检错；即：用伴随式可以检出 l 位错误，条件是（ dmin-1）/2 nk 时，检测不出的突发错误占同样长度的可能的突发错误总数的百分比为： 2（nk） 当b1 nk 2（nk1） 当b1 nk 在突发错误E（x）xiB（x）中， B（x）是 b1 次多项式。由于突发错误的首尾两位必有错，故B（x）的x0项及xb1项的系数必为1，可以知道B（x）总共可取2b2个不同的多项式，即：突发长度为 b 时，可能的突发错误总数为2b2个。33电气工程学院山东大学研究生课程只有当B（x

35、）能被g（x）除尽时， E（x）的错误才检测不出来，这时满足： B（x）q（x）g（x）其中q（x）为b1（ nk ），则q（x）为零次多项式，即q（x）1。这时存在唯一的不可检测的错误图样B（x） g（x）。在这种情况下，不可检测的突发错误数为1，可能的突发错误总数为2b2 2nk1，它们的比为：若b1 nk ， q（x）共可能有2b2（nk）个不同的多项式，即不可检测的错误图样总共可以有2b2（nk）个，它与可能的突发错误总数之比为： 可见，由nk 次多项式g（x）生成的循环码，不仅能检测出所有长度不大于nk 的突发错误，而且可以检测出绝大部分更长的突发错误。同理，还可以分析出更多的检错情

36、况。34电气工程学院山东大学研究生课程七、循环冗余校验码（CRC） 循环冗余校验码是循环码的一种，是最常用的一种差错控制校验方式，它具有较强的检错能力和一定的纠错能力，编码和解码实现起来也比较简单，在串行通信、磁盘文件读写、文件的压缩/解压、多媒体技术、网络技术、密码技术等方面，得到较为普遍的应用。 CRC Cyclic Redundancy Check 循环冗余校验1、CRC校验码的检错方法：CRC码由两部分组成，其中，左面有 k 位信息位，右面是 r 位校验位，字长是 n 位，n = k + r。如下图所示： 1 2 3 k 1 r信息位（k 位）校验位（r 位）CRC码（kr 位）CRC

37、码格式35电气工程学院山东大学研究生课程 CRC校验是将要发送的数据多项式m（x）在发送端除以一个预先约定的生成多项式 g（x），求得一个余数多项式 r（x），将余数多项式加到数据多项式之后，形成一个发送多项式 f（x）发送到接收端。在接受端用同样的生成多项式g（x）去除接收到的多项式 f（x），得到计算余数多项式，如果计算余数多项式与接收余数多项式相同，则表示传输无差错；如果计算余数多项式不等于接收余数多项式，则表示传输有错误，从而实现了检错。2、CRC校验码的编码方法首先，将待发送的 k 位信息位写为多项式形式C（x）Ck-1xk-1Ck-2xk-2Cixi+C1xC0 为将信息位左移 r

38、 位，可以表示为：C（x）xr 这样在信息组的右边就空出了 r 位，以便拼接 r 位校验位。CRC码是用多项式C（x）xr 除以生成多项式 g（x）所得的余数作为校验位的，为了得到 r 位校验位（余数），生成多项式g（x）必须是 r1位。设所得的余数表达式为 r（x），商为q（x），将余数拼接在信息组左移空出的 r 位 上，就构成了这个有效信息的CRC码。因此，这个CRC码可以用多项式表达为： 36电气工程学院山东大学研究生课程C（x）xr r（x） q（x）g（x）r（x）r（x） q（x）g（x） r（x） r（x） q（x）g（x）因此，所得的CRC码是可以被生成多项式除尽的。例：对4位

39、有效信息组（1100）求CRC码，选择生成多项式为（1011），即： C（x）x3x2 1100 C（x）xr x6x5 g（x）x3x1 1011x3+x+1 x6 + x5x3+x2+xx6 + x4 + x3 x5 + x4 + x3 x5 + x3 + x2 x4 + x2 x4 + x2 + x x这是一个（7，4）循环码的例子。37电气工程学院山东大学研究生课程3、CRC的译码与纠错 将收到的循环校验码用约定的生成多项式 g（x）去除，如果码字正确则余数应为0，如果有某一位出错，则余数不为0，不同位数出错则余数不同。通过上例求出其出错模式如下表所示。更换不同的待测码字可以证明：余数

40、与出错位的对应关系是不变的，只与码制和生成多项式有关。因此该表可以作为（7，4）码的判别依据。对于其他码制或选用其他生成多项式，出错模式将会发生变化。（7，4）循环码的出错模式【生成多项式 g（x）1011】38电气工程学院山东大学研究生课程 如果循环码有一位出错，用 g（x）作模 2 除将得到一个不为 0 的余数。如果对余数补一个 0 继续除下去，我们将发现一个现象：各次余数将按照上表顺序循环。如：第6位出错，余数是 001，补 0 再除，第二次余数为 010，以后依次为100，011，.，反复循环，这是 CRC 校验码的一个有价值的特点。如果我们在求出余数不为 0 后，一边对余数补 0 继

41、续做模2除，同时让被检测的校验码字循环左移，上表说明，当出现余数（101）时，出错位也移到 C0 的位置。可以通过异或操作将它纠正后在下一次移位时送回 C6 。继续移满一个循环（对于7，4码共需移七次），就得到了一个纠正后的码字。通过这种方式，可以实现 CRC 码的纠错。 也就是说，当信息传输出现错误时，循环冗余校验码被生成多项式整除所得到的余数与出错位有一一对应的关系，据此，可以确定出错的位置，从而实现纠错。39电气工程学院山东大学研究生课程4、循环冗余校验码的检错能力： 可以证明，循环冗余校验码可以：（1）能检查出全部单个错误；（2）能检查出全部离散的二位错误；（3）能检查出全部奇数个错误；（4）能检查出全部长度小于或等于 r 位的突发错误；（5）能以1（1/2）r-1的概率检查出长度为（r+1）位的突发错误。 例如，如果 r 16，则该CRC校