计算机网络——32差错检测和纠正

差错检测和纠正

错误检测

EDC = 差错检测和纠错位（冗余位）
D = 数据由差错检测保护，可以包含头部字段
错误检测不是100%可靠的

• 协议会泄露一些错误，但是很少
• 更长的EDC字段可以得到更好的检测和纠正效果

奇偶校验

单bit奇偶校验

检测单个bit级错误

二维奇偶校检

检测和纠正单个bit错误

Internet校检和

目标：检测在传输报文时的错误（如位翻转），（注：仅仅用在传输层）
发送方

• 将报文段看成16-bit整数
• 报文段的校检和：和（1’的补码和）
• 发送方将checksum的值放在’UDP校检和’字段

接收方

• 计算接收到的报文段的校检和
• 检查是否与携带校检和字段值一致
  • 不一致：检出错误
  • 一致：没有检出错误，但可能还是有错误

有更简单的检查方法：全部加起来看是不是全1

检验和：CRC（循环冗余校检）

• 强大的差错检测码
• 将数据比特 D 看成是二进制的数据
• 生成多项式 G ：双方协商r + 1模式（r次方）
  • 生成和检查所使用的位模式
• 目标：选择r位CRC附加位R，使得
  • <D,R>正好被G整除（modulo 2）
  • 接收方知道G，将<D,R>除以G，如果非0余数：检查出错误
  • 能检出所有少于r + 1位的突发错误
• 实际中广泛使用（以太网、802.11 WiFi、ATM）

CRC例子

需要：
$D\cdot 2^r\times ORR=nG$
等价于：
$D\cdot 2^r=nG\times ORR$
等价于：
两边同除G
得到余数$R=\dots$

$R=remainder\left[\begin{array}{c}\frac{D\cdot 2^r}{G}\end{array}\right]$

最后求得：

CRC性能分析

• 突发错误和突发长度
• CRC检错性能描述
  • 能够检查出所有的1bit错误
  • 能够检查出所有的双bit的错误
  • 能够检测出所有长度 = r或者 <r 位的错误
  • 出现长度为r + 1的突发错误，检查不出的概率是
    $\frac{1}{2^{r-1}}$
  • 出现长度大于r + 1的突发错误，检查不出的概率
    $\frac{1}{2^r}$