数据通信

差错检验和纠正

2019-03-21 08:00 CST
2019-03-21 08:00 CST
CC BY-NC 4.0

差错类型

  • 单比特差错
  • 突发差错
概率值
$P_b$ BER, 接受到一个差错比特的概率
$P_1$ 无比特差错帧到达概率
$P_2$ 某种差错检测算法下,含有一个或多个未检测到的比特差错的帧的到达概率
$P_3$ 某种差错检测算法下,含有一个或多个且没有未检测到的比特差错的帧的到达概率

差错检测

奇偶检验

  • 两个比特错误无法检测
  • 同步传输:偶校验
  • 异步传输:奇校验

二维奇偶检验

  • $i+j+1$ 个
  • 矩形四个错误无法检测

因特网检验和

  • 发送方计算检验位
    • 将两个数字视为无符号二进制整数相加
    • 如果最左边有进位比特,则和再加1
    • 取反码
  • 接收方验证
    • 加上检验位后应全1

循环冗余检验 (CRC,Cyclic Redundancy Check)

  • 发送的数据:$T[D(k)|F(n-k)]$
    • $D$ 数据
    • $F$ 检验序列
    • $P(n-k+1)$ 除数
    • $T=2^{n-k}D+F\equiv0\pmod{P}$
  • $F=2^{n-k}D\bmod P$
    • 模2运算
    • 多项式表示
      • $11001 \rightarrow X^4+X^3+1$
    • 寄存器
      • Galois 域除法器

差错纠正

  • 汉明距离 $d(v_1,v_2)$

差错检测+差错重传

  • 无线链路:高比特差错率导致大量重传
  • 卫星链路: 长传播时延导致效率低下

前向纠错 (FEC)

  • 差错类型
    • 无差错
    • 可检测,可纠正差错
    • 可检测,不可纠正之差错
    • 不可检测之差错
  • 见《代数编码》