差错检测

基本概念

• 数据在传输过程中可能会产生比特差错
  • 数据传输过程中，因电磁干扰等，比特位发生反转
  • 传输错误的比特占传输比特总数的比率称为误码率(Bit Error Rate, BER)
• 差错检测的基本思想
  • 在数据帧中加入冗余信息来确定是否存在差错
• 当接收方检测到差错时，可以
  • 通知对方数据有差错，使其重传数据副本（重传机制）
  • 通过加入的冗余信息，重新构造正确的数据（纠错码）

奇偶校验

单向奇偶校验/单个位奇偶校验

• 使用单个奇偶校验位
• 分为奇校验 和 偶校验，假设信息有 d 比特
  • 偶校验：d 比特信息和 1 比特校验位中 1 的总数为偶数
  • 奇校验：d 比特信息和 1 比特校验位中 1 的总数为奇数
• 出现奇数个比特差错可检测出；偶数个则无法检查
  • 测量表明，差错往往以突发方式聚集在一起，而非独立发生
  • 突发差错下，该方案无法检测出差错的概率50%

二维奇偶校验

• 将 d 比特信息划分为i行j列，对每行和每列都计算奇偶值，产生 i+j+1 个奇偶校验位

校验和

基本思想

• 将传输的所有字加起来，相加的结果作为校验和，一起传输

• 接收端执行同样计算，结果与收到的校验和比较，若不同则判断出错

• TCP/IP 协议中采用的变种

• 发送方：将所有数据分为许多16位字的序列，将所有16位字相加，对结果取反，即为校验和

  • 注意求和的时候，最高位的进位需要回卷到最低位

• 接收方：将所有16比特字（包括校验和）相加，若结果为全1则认为无差错

差错检验能力

• 冗余少，仅16比特，对任意长度数据进行检测，检测能力较弱

  • 例如一对单比特错，1个使某个字增加1，另一个使另一个字减少1，校验和不变

• 易于软件实现，用于上层端到端协议，下层由链路层提供更强的检错能力

循环冗余检验（CRC）

差错检测算法设计目标

• 使用最少的冗余比特检测最多的错误
• CRC使用很强的数学算法实现
  • 二进制除法
  • 非标准除法，用异或代替相减（无借位）

CRC的基本思想

• \(n\)次的多项式可以表示\(n+1\)比特的信息
  • 1代表该指数存在，0代表不存在
• 为计算CRC，收发双方商定一个k次幂的除数\(C(x)\)
• 对于\(n\)比特消息\(M(x)\)，实际发送加上\(k\)比特冗余的消息\(P(x)\)，使得\(P(x)\)能被\(C(x)\)整除；若接收方收到的消息不能被\(C(x)\)整除，则判断出错
• 计算\(P(x)\)
  • \(x^k\)乘\(M(x)\)，即消息末尾加上\(k\)个0，得到零扩展消息\(T(x)\) //T = M << k
  • \(C(x)\)除\(T(x)\)，得到余数\(S(x)\) // S = T % C
  • $P(x) = T(x) - S(x) $ // P = T XOR S

C(x)的选择

• \(x^k\) 和 \(x^0\)项的系数不为0，则可以检测所有单比特错
• \(C(x)\)含有一个至少3项的因子，可检测所有双比特错
• \(C(x)\)含有因子\(x+1\)，可检验任意奇数个错

检错还是纠错

• 检错：发现错误，重传
• 纠错：发现错误，纠正
  • 纠错码的冗余位要比检错码长，编码效率低
  • 使用纠错码的场景
    • 差错发生的可能性高：无线环境
    • 重传代价高：卫星链路
    • 无法重传：单工信道