二. 差错检测 1.差错检测的基本原理 差错控制的根本措施：采用抗干扰编码(即纠错编码)。 码组：由n个码元(0,1)构成的每一组合。 二. 差错检测 1.差错检测的基本原理 差错控制的根本措施：采用抗干扰编码(即纠错编码)。 码组：由n个码元(0,1)构成的每一组合。 信息码：代表报文的0和1； 监督码：插入的“0”和“1” 纠错编码的检错、纠错原理 假设要传送的消息为 A和B A：0 B：1 即没有检错也纠错能力。

二. 差错检测 1.差错检测的基本原理 纠错编码的检错、纠错原理 A：00 B：11 信息码：代表消息的0和1； 二. 差错检测 1.差错检测的基本原理 纠错编码的检错、纠错原理 A：00 B：11 信息码：代表消息的0和1； 监督码：插入的“0”和“1”； 准用码组：{ 00，11 } 禁用码组：{ 01，10 } 具有了检出一位错码的能力；没有纠错能力。

二. 差错检测 1.差错检测的基本原理 纠错编码的检错、纠错原理 A：000 B：111 信息码：代表信息的0和1; 二. 差错检测 1.差错检测的基本原理 纠错编码的检错、纠错原理 A：000 B：111 信息码：代表信息的0和1; 监督码：插入的“00”和“11”; 准用码组＝{000，111} 禁用码组＝{001,010,100,011,101,110} 具有检出两位及两位以下错码的能力； 具有纠正一位错码的能力；

二. 差错检测 1.差错检测的基本原理 纠错编码的检错、纠错能力 一般来说，监督码引入越多，检错纠错能力越强，但信道的传输效率下降也越快。 二. 差错检测 1.差错检测的基本原理 纠错编码的检错、纠错能力 一般来说，监督码引入越多，检错纠错能力越强，但信道的传输效率下降也越快。 码距：指两个码组对应码位码元不同的个数。 (000)与(010) 的码距为1 (000)与(110) 的码距为2 (000)与(111) 的码距为3 汉明距离： 在一个码组的集合中，任意两个码组间的最小码距。

二. 差错检测 1.差错检测的基本原理 编码关系式 为了检出e个错码，要求码集的汉明距离 d≥e+1 为纠正t个错码，要求码集的汉明距离 二. 差错检测 1.差错检测的基本原理 编码关系式 为了检出e个错码，要求码集的汉明距离 d≥e+1 为纠正t个错码，要求码集的汉明距离 d≥2t+1 为了检出e个错码，同时能纠正t个错码，则应满足 d≥e+t+1 (e>t)

二. 差错检测 1.差错检测的基本原理 例1 if e = 2, t = 1, then d≥e+t+1=4 能检2个错码能纠1个错码 二. 差错检测 1.差错检测的基本原理 例1 if e = 2, t = 1, then d≥e+t+1=4 能检2个错码能纠1个错码 A：0000 B：1111 d = 4 0011，0101，0110， 1001，1010，1100 肯定能检2位错 0001，0010，0100，1000 1110，1011，1101，0111 肯定能纠1位错

二. 差错检测 2.奇偶校验编码 编码规则 先将所要传送的数据码元分组。在各组的数据后面附加一位校验位，使得该组码连校验位在内的码字中： 二. 差错检测 2.奇偶校验编码 编码规则 先将所要传送的数据码元分组。在各组的数据后面附加一位校验位，使得该组码连校验位在内的码字中： “1”的个数为偶数—偶校验 “1”的个数为奇数—奇校验 垂直奇偶校验、水平奇偶校验、垂直水平奇偶校验、斜奇偶校验 检错能力逐渐加强 能检出码字中任意奇数个错误； 随机错误十分有效;

二. 差错检测 2.奇偶校验编码 垂直奇偶校验 发送端在k位表示字符的信息位上，附加一个第k+1位的校验位； 二. 差错检测 2.奇偶校验编码 垂直奇偶校验 发送端在k位表示字符的信息位上，附加一个第k+1位的校验位； 接收端根据收到的k位重新产生校验位，并与第k+1位作比较。如相同则无错，否则存在错误。 设b1 b2 … bm-1是同一码组内的数据码元，bm为校验位 偶校验：b1 b2  …. bm-1 bm = 0 bm = b1 b2  …. bm-1 奇校验：b1 b2  …. bm-1 bm = 1 bm = b1 b2  …. bm-1 1

二. 差错检测 2.奇偶校验编码 能发现奇数个差错 无法发现偶数个差错 编码效率： R = k/(k+1) k为码元的位数 二. 差错检测 2.奇偶校验编码 b1 0 1 0 1 0 1 0 1 0 1 b2 0 0 1 1 0 0 0 1 0 0 b3 0 0 0 0 1 1 1 1 0 0 b4 1 0 1 1 0 0 0 0 1 1 b5 0 1 1 0 1 1 1 1 1 1 b6 0 0 0 0 1 1 0 1 1 1 b7 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 1 字符 位 偶 奇 b8 H Q Z K 4 5 T 7 8 9 能发现奇数个差错 无法发现偶数个差错 编码效率： R = k/(k+1) k为码元的位数

二. 差错检测 2.奇偶校验编码 水平奇偶校验 在传送数据时，常将若干个字符组成一组信息。当对一组内的各字符的同一位进行奇偶校验时，就称为～。 可检测出组内各字符同一位上的奇数个错 可检测出突发长度≤字符长度的所有突发错误 编码效率： R = m/(m+1) m为参与校验的字符数

二. 差错检测 2.奇偶校验编码 示例 b1 0 1 0 1 0 1 0 1 0 1 b2 0 0 1 1 0 0 0 1 0 0 b3 0 0 0 0 1 1 1 1 0 0 b4 1 0 1 1 0 0 0 0 1 1 b5 0 1 1 0 1 1 1 1 1 1 b6 0 0 0 0 1 1 0 1 1 1 b7 1 1 1 1 0 0 1 0 0 0 字符 位 偶 奇 1 0 0 1 H Q Z K 4 5 T 7 8 9

二. 差错检测 2.奇偶校验编码 垂直水平奇偶校验 把垂直和水平两个方向的奇偶校验结合起来使用。 可检出3位或3位以下的全部错误 二. 差错检测 2.奇偶校验编码 垂直水平奇偶校验 把垂直和水平两个方向的奇偶校验结合起来使用。 可检出3位或3位以下的全部错误 可检出所有的奇数个错 可检出大部分偶数个错 可检出长度＜k+1的突发错误 编码效率： mk/[(m+1)(k+1)] k为码元的位数 m为参与校验的字符数

二. 差错检测 2.奇偶校验编码 b1 0 1 0 1 0 1 0 1 0 1 b2 0 0 1 1 0 0 0 1 0 0 b3 0 0 0 0 1 1 1 1 0 0 b4 1 0 1 1 0 0 0 0 1 1 b5 0 1 1 0 1 1 1 1 1 1 b6 0 0 0 0 1 1 0 1 1 1 b7 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 1 字符 位 偶 奇 b8 1 水 平 H Q Z K 4 5 T 7 8 9

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 将要传送的信息分成码组M，然后按某一种约定的规律对每一个信息码组附加一些校验的码元R，形成新的码组C，使得C中的码元之间具有一定的相关性(即码组中“1”和“0”的出现彼此相关)，再传输到接收端； 接收端根据这种相关性或规律性来校验码组C是否正确，还可对出错码组的错定位加以相应的纠正，最后将码组C还原成信息码组M。

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 线性分组码与循环码 分组码：码组内的码元之间的相关性只局限在本码组内 线性分组码：码组结构规则或规律性可用线性方程来描述 循环码：具有循环移位特性的线性分组码 奇偶校验码 循环码移位特性 封闭性 码集中任何码字向左/右移位得到的是码集中的另一个码子。 码集中任何两个码子相加后仍然是该码集中的一个码子。

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 码多项式及其算术运算 假设循环码 C = Cn-1 Cn-2…. C2 C1 C0 长度为n C的码多项式（称为n-1次多项式） C(x) = Cn-1 xn-1 + Cn-2xn-2 + …. C2 x2 +C1 x + C0 例1： C = 1100101 C(x) =1x6 + 1x5 +0x4 +0x3 + 1x2 +0 x + 1 = x6 + x5 +x2 + 1 码多项式的算术运算：模2加、模2减、模2乘、模2除

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 模2加，减，乘，除举例……… 在模2运算的基础上，xn+1 总能够被x+1整除。 奇数个项的多项式不能够被x+1整除。 xj(xi-j+1) 不能被g(x)整除的充分必要条件是。 xi-j+1不能够被g(x)整除。

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 循环码的编码 对于一个码长为n，信息码元为k位的循环码(n，k),其构成形式为： n位 信息码元 k位 校验码元 r位 1 2 k n k+1 k+2 每个码多项式的前面k项与待编码的信息多项式相同 后面的r=n-k项与校验码元序列对应的校验多项式相同

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 设要编码的k位信息元为：m = (mk-1,mk-2,….m1,m0) m(x) = mk-1 xk-1+ mk-2xk-2+ …. +m1 x+m0 xn-k·m(x) = mk-1 xn-1+ mk-2xn-2+ …. +m1 xn-k+1+m0 xn-k = q(x)·g(x) + r(x) g(x)是(n-k)次多项式 q(x)是商式 r(x)是余式且次数不高于n-k-1 r(x) = rn-k-1 xn-k-1+ rn-k-2xn-k-2+ …. +r1 x+r0 xn-k·m(x) + r(x) = q(x)·g(x) mk-1xn-1+mk-2xn-2+ ...+m1xn-k+1+m0xn-k+rn-k-1xn-k-1+rn-k-2xn-k-2+... +r1 x+r0 ( mk-1, mk-2, ….m1, m0, rn-k-1, rn-k-2, …. ,r1, r0 ) 不加改变的k个信息位 (n-k)个监督位

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) CRC-12=x12+x11+x3+x2+x+1 CRC-16=x16+x15+x2+1 CRC-CCITT=x16+x12+x5+1 校验码的产生 (1)设生成多项式g(x)的最高幂次为r=n-k (2)将待编码码元序列表示为m(x)，乘以xr，结果左移r位xr·m(x) (3)用g(x)去除 xr·m(x)，求得商式q(x)和余式r(x) [xr·m(x)]/g(x) = q(x) + r(x)/g(x) xr·m(x) = q(x)·g(x) + r(x) xr·m(x) + r(x) = q(x)·g(x) 校验多项式。其系数Cr-1，Cr-2，….C1，C0为校验码 为除法运算后变成的循环多项式C(x)的表示式 C(x) = Cn-1xn-1+Cn-2xn-2+ . +Cn-kxn-k+Cn-k-1xn-k-1+…C2x2+C1x+C0 = Cn-1 xn-1+Cn-2xn-2+ … +Cn-kxn-k+Cr-1xr -1+Cr-2xr -2 …C2x2+C1x+C0 信息码 校验码

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 校验码的应用 在接收端本来应该收到： c(x) = xr·m(x) + r(x) = q(x)·g(x) 用协商好的生成多项式g(x)去除c(x),从余数来判断是否出错

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 例2 设编码的信息码元为1101011011 m(x) = x9 + x8 + x6 + x4 + x3 + x + 1, k = 10 (1)假设 g(x) = x4 + x + 1 系数形成的位串为10011 r=4 ——>n = 14 r(x)的最高幂次为 r-1=3 (2) x4·m(x) = 1101011011，0000 (3) 1101011011.0000 10011 商数：1100001010 余数：1110 r(x) = x3 + x2 + x + 0 所需的循环编码C(x)为 C(x) = xr·m(x) + r(x) = 1101011011，1110

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 多项式除法 1101011011.0000 10011 商数 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1,0 0 0 0 1 0 0 1 1 被除数 m(x) 1 0 0 1 1 除数 g(x) 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 模2加=模2减 模2乘 模2除=乘的可逆运算 1 0 1 0 0 1 0 0 1 1 1 1 1 0 余数 r(x)

二. 差错检测 3.循环冗余校验码(CRC，Cyclic Redundancy check) 循环码的检错能力 假定在接收端实际收到c(x)+e(x) 检查全部单个错（1位错） e(x)=xi 检查全部离散的二位错（双错）e(x)=? 检查全部的奇数个错（1，3，5，…个错） 检查全部长度等于(n-k)或小于(n-k)的突发错 e(x)=? 以[1-2-(r-1)]的概率检查出长度为(r+1)的突发错以及以[1-2-r]的概率检查出多于(r+1)的突发错

二. 差错检测 4.汉明纠错码 基本原理 发送端计算监督位 bm = b1 b2  …. bm-1 二. 差错检测 4.汉明纠错码 基本原理 发送端计算监督位 bm = b1 b2  …. bm-1 接收端计算 S = b1 b2  …. bm-1bm 校正子S = 0：无错 1：有错 监督关系式 如果监督增加一位，变成2位，则增加一个监督关系式 00 01 10 11 表示无错 SS = 表示1位错码的不同位置

二. 差错检测 4.汉明纠错码 一般地，r个监督关系式指示一位错码的(2r-1)种可能位置。 对(n, k)分组码，监督位数 r =n-k； 二. 差错检测 4.汉明纠错码 一般地，r个监督关系式指示一位错码的(2r-1)种可能位置。 对(n, k)分组码，监督位数 r =n-k； 若希望用r个监督位构造出r个监督关系式用来指示一位错误的n种可能位置， 则 2r –1  n 即 2r  k+r+1 汉明不等式 编码效率 R=k/n = (n-r)/n = 1-r/n 汉明码： 码长为n = 2r –1的线性分组码，即(2r –1, 2r –1–r)码。

二. 差错检测 4.汉明纠错码 描述(7，4)汉明码 mi为信息码元 ri为监督码元 编码结构：m3m2m1m0r2r1r0 二. 差错检测 4.汉明纠错码 描述(7，4)汉明码 mi为信息码元 ri为监督码元 编码结构：m3m2m1m0r2r1r0 假设：S1S2S3是三个监督关系式的校正子 S1S2S3与错码位置的对应关系 S1 S2 S3 错码位置 0 0 1 r0 0 1 0 r1 1 0 0 r2 0 1 1 m0 1 0 1 m1 1 1 0 m2 1 1 1 m3 0 0 0 无错 四个码元构成偶数监督关系： S1 = m3 m2 m1 r2 S2 = m3 m2 m0 r1 S3 = m3 m1 m0 r0

二. 差错检测 4.汉明纠错码 发送端 m3m2m1m0取决于输入信号； r2r1r0取决于m3m2m1m0的取值； 二. 差错检测 4.汉明纠错码 发送端 m3m2m1m0取决于输入信号； r2r1r0取决于m3m2m1m0的取值； r2r1r0应使S1 ,S2 和S3为0 m3 m2 m1 r2 = 0 m3 m2 m0 r1 = 0 m3 m1 m0 r0 = 0 r2 = m3 m2 m1 r1 = m3 m2 m0 r0 = m3 m1m0 解出监督位： 从而构成系统码 (m3, m2, m1, m0, r2, r1, r0 )

二. 差错检测 4.汉明纠错码 接收端 收到每个码组后，先计算出S1 ,S2 和S3 ； 再按关系表判别错码的位置； 二. 差错检测 4.汉明纠错码 接收端 收到每个码组后，先计算出S1 ,S2 和S3 ； 再按关系表判别错码的位置； 最后将错码取反加以纠正。 例如：接收码组为 0000011 计算： 查表知m0位错，将其取反 0001011 即为正确的码组。 S1 = m3 m2 m1 r2 = 0； S2 = m3 m2 m0 r1 = 1； S3 = m3 m1 m0 r0 = 1 ；

二. 差错检测 4.汉明纠错码 可以去掉查表的过程 1 2 3 4 5 6 7 红色 检验位；蓝色 数据位 二. 差错检测 4.汉明纠错码 可以去掉查表的过程 1 2 3 4 5 6 7 红色 检验位；蓝色 数据位 发送方产生各个检验位，使得特定的位满足齐偶校验关系 1 3 5 7 3=1+2 5=1+4 7=1+2+4 2 3 6 7 5 6 7 在接收方： c1=c3  c5  c7 s1=c1  c3  c5  c7 c2=c3  c6  c7 s2=c2  c3  c6  c7 c4=c5  c6  c7 s3=c4  c5  c6  c7 S1S2S3就是错码的位置