检错码与纠错码 检错码：在发送数据中加入一定的冗余位，使接收方 能知道数据是否出错，但不知道是哪里出错，这种编 码方法叫差错检测码，或简称检错码 纠错码：在要发送的数据中加入足够多的冗余位，使 接收方能纠正出错的位，这种编码方法叫差错校正码， 或简称纠错码 ■纠删码：既能检错，又能纠错 注：在数据通信中，位和比特、bt是同一个概念，可以混用 16
16 检错码与纠错码 ◼ 检错码：在发送数据中加入一定的冗余位，使接收方 能知道数据是否出错，但不知道是哪里出错，这种编 码方法叫差错检测码，或简称检错码 ◼ 纠错码：在要发送的数据中加入足够多的冗余位，使 接收方能纠正出错的位，这种编码方法叫差错校正码， 或简称纠错码 ◼ 纠删码：既能检错，又能纠错 注：在数据通信中，位和比特、bit是同一个概念，可以混用
3.2.1海明距离 一帧由个数据位（即报文）和r个冗余位 即校验位)组成，总长度n=m+r,此长度 ( 为n的单元称为n位码字 两个码字不同的位的数目称为海明距离 (Hamming Distance) 例如，10001001与10110001它们的海明距离为3 对于n位码字的集合，只有2m个码字是有效的， 在任意两个有效码字间找出具有最小海明距离 的两个码字，该海明距离便定义为全部码字的 海明距离。 17
17 3.2.1海明距离 ◼ 一帧由m个数据位（即报文）和r个冗余位 （即校验位）组成，总长度n=m+r，此长度 为n的单元称为n位码字 ◼ 两个码字不同的位的数目称为海明距离 (Hamming Distance) 例如，10001001 与10110001它们的海明距离为3 ◼ 对于n位码字的集合，只有2m个码字是有效的， 在任意两个有效码字间找出具有最小海明距离 的两个码字，该海明距离便定义为全部码字的 海明距离
一种编码的检错和纠错能力取决于编码后码字的海明 距离的大小 检错 纠错 C2 d dmin=d+1 dmin=2d+1 为了检测出d位的错， 需要使用距离为d+1的编码 例如：数据后加奇偶校验位，编码后的海明距离为2，能检测1位错 ■ 为了纠正d位的错，必须用距离为2d+1的编码 例如有4个有效码字：它们是0000000000,0000011111， 1111100000,1111111111,海明距离为5，能纠正2位错
18 ◼ 一种编码的检错和纠错能力取决于编码后码字的海明 距离的大小 ◼ 为了检测出d位的错，需要使用距离为d+1的编码 例如：数据后加奇偶校验位，编码后的海明距离为2，能检测1位错 ◼ 为了纠正d位的错，必须用距离为2d+1的编码 例如有4个有效码字：它们是0000000000，0000011111， 1111100000，1111111111，海明距离为5，能纠正2位错 C d 1 C1 d 1 C2 d dmin=d+1 dmin=2d+1 检错 纠错
3.2.2单比特纠错码 设计一种编码，它有个信息位和r个校验位， 当满足什么条件时，能纠正所有单比特错？ 对2m个有效码字的任何一个而言，有n(n=m+r)个与 该码字距离为1的无效码字 →2m个有效码字每一个都对应有n+1个各不相同的位模 式 而n位码字的总的位模式数量为2n个 →(n+1)2m≤2n 将n=m+r代入 →(m+r+1)2m≤2m+r →m+r+1≤2"纠正单比特错误所需校验位数量下界 19
19 3.2.2单比特纠错码 ◼ 设计一种编码，它有m个信息位和r个校验位， 当r满足什么条件时，能纠正所有单比特错？ 对2m个有效码字的任何一个而言，有n(n=m+r)个与 该码字距离为1的无效码字 →2m个有效码字每一个都对应有n+1个各不相同的位模 式 而n位码字的总的位模式数量为2n个 →(n+1)2m ≤ 2n 将n=m+r代入 →(m+r+1)2m ≤ 2m+r →m+r+1 ≤ 2r 纠正单比特错误所需校验位数量下界
海明编码 达到了纠正单比特错误的校验位数量下界！ m+r+1≤2 码字内编号为2的幂的位是校验位，其余为信息位 ■对编号为K的信息位来说，K可以分解成2的幂的和 每个校验位的取值应使得包括自己在内的集合的奇偶值为偶数（或者奇数) ○har. AS○II ○neck bits 按列 H a 1100001 1101 01 1101 ●1 i 110 度于 1101 )1 g 110 11 010( 100 11 1111 11 01 1 d 11 错误 1111 11001 01 00111C 11 ●rcer of bit transmission m=7,r=4,n=11,显然11+1≤24，采用偶校验 只能纠正单比特错！ 3=1+2 5=1+4 校验位：1∈（3,5,7,9,11) 在接收方，如果校验 6=2+4 7=1+2+4 2∈(3,6,7,10,11) 位1不满足偶校验，而 9=1+8 10=2+8 4∈(5， 6,7) 其他校验位都满足， 11=1+2+8 8∈(9， 10,11) 则第1位出错，.…
20 校验位：1 （3，5，7，9，11） 2 （3，6，7，10，11） 4 （5，6，7） 8 （9，10，11） 3=1+2 5=1+4 6=2+4 7=1+2+4 9=1+8 10=2+8 11=1+2+8 海明编码 m=7，r=4，n=11，显然11+1 ≤ 24 ，采用偶校验 ◼ 达到了纠正单比特错误的校验位数量下界！ ◼ 码字内编号为2的幂的位是校验位，其余为信息位 ◼ 对编号为K的信息位来说，K可以分解成2的幂的和 ◼ 每个校验位的取值应使得包括自己在内的集合的奇偶值为偶数（或者奇数） m+r+1 ≤ 2r 只能纠正单比特错！ 在接收方，如果校验 位1不满足偶校验，而 其他校验位都满足， 则第1位出错，… 按列 传输 纠正 长度 等于 或小 于列 长的 突发 错误