差错编码

1 差错检测：差错编码

差错编码基本原理：D→DR，其中R为差错检测与纠正比特（冗余比特）

差错编码不能保证100%可靠！

2 差错编码的检错能力

差错编码可分为检错码与纠错码

• 对于检错码，如果编码集的汉明距离ds=r+1，则该差错编码可以检测r位的差错

  • 例如，编码集 {0000,0101,1010,1111} 的汉明距离ds=2，可以100%检测1比特差错
    

• 对于纠错码，如果编码集的汉明距离ds=2r+1，则该差错编码可以纠正r位的差错

  • 例如， 编码集 {000000,010101,101010,111111} 的汉明距离ds=3， 可以纠正1比特差错，如100010纠正为101010。
    

3 奇偶校验码

• 1比特校验位:

  • 检测奇数位差错
    

• 二维奇偶校验:

  • 检测奇数位差错、部分偶数位差错
  • 纠正同一行/列的奇数位错

  

4 Internet校验和(Checksum)

发送端:

• 将“数据” (校验内容)划分为16位的二进制“整数”序列
• 求和(sum)：补码求和(最高位进位的“1”，返回最低位继续加）
• 校验和(Checksum)：sum的反码
• 放入分组(UDP、 TCP、 IP)的校验和字段

接收端:

• 与发送端相同算法计算
• 计算得到的”checksum”：
  
  • 为16位全0（或sum为16位全1）：无错
  • 否则：有错

5 循环冗余校验码(CRC)

• 检错能力更强大的差错编码
• 将数据比特， D，视为一个二进制数
• 选择一个r+1位的比特模式 (生成比特模式)， G
• 目标：选择r位的CRC比特， R，满足
  
  • (D,R)刚好可以被G整除(模2)
  • 接收端检错：利用G除(D,R)，余式全0，无错；否则，有错！
  • 可以检测所有突发长度小于r+1位差错。
• 广泛应用于实际网络 (以太网， 802.11 WiFi， ATM)

CRC举例