二. 差错检测 1.差错检测的基本原理 差错控制的根本措施：采用抗干扰编码(即纠错编码)。 码组：由n个码元(0,1)构成的每一组合。

Presentation on theme: "二. 差错检测 1.差错检测的基本原理 差错控制的根本措施：采用抗干扰编码(即纠错编码)。 码组：由n个码元(0,1)构成的每一组合。"— Presentation transcript:

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

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

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

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

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

6 二. 差错检测 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： B： d = 4 0011，0101，0110， 1001，1010，1100 肯定能检2位错 0001，0010，0100，1000 1110，1011，1101，0111 肯定能纠1位错

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

8 二. 差错检测 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

9 二. 差错检测 2.奇偶校验编码 能发现奇数个差错 无法发现偶数个差错 编码效率： R = k/(k+1) k为码元的位数
二. 差错检测 2.奇偶校验编码 b b b b b b b 字符 位 偶 奇 b8 H Q Z K T 能发现奇数个差错 无法发现偶数个差错 编码效率： R = k/(k+1) k为码元的位数

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

11 二. 差错检测 2.奇偶校验编码 示例 b b b b b b b 字符 位 偶 奇 H Q Z K T

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

13 二. 差错检测 2.奇偶校验编码 b b b b b b b 字符 位 偶 奇 b8 1 水 平 H Q Z K T

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

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

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

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

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

19 二. 差错检测 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 m1xn-k+1+m0xn-k+rn-k-1xn-k-1+rn-k-2xn-k r1 x+r0 ( mk-1, mk-2, ….m1, m0, rn-k-1, rn-k-2, …. ,r1, r0 ) 不加改变的k个信息位 (n-k)个监督位

20 二. 差错检测 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 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 信息码 校验码

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

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

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

24 二. 差错检测 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)的突发错

25 二. 差错检测 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位错码的不同位置

26 二. 差错检测 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)码。

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

28 二. 差错检测 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 )

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

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