数据通信

6 差错检测和纠正

2019-04-13 13:53 CST
2019-06-06 23:42 CST
CC BY-NC 4.0

6.1 差错类型

可能出现的差错分为两大类：

  • 单比特差错
  • 突发性差错

差错突发 一组比特中，任意两个连续的差错比特之间间隔的正确比特数总是小于$x$，$x$为一给定值。因此在差错突发时最后一个差错比特与下一次突发的第一个差错比特之间会有$x$个以上的正确比特间隔。

数据率越高，突发性差错的影响就越大。

6.2 差错检测

概率定义：

  • $P_b$：接收到一个差错比特的概率，也称为比特差错率(BER)。
  • $P_1$：无比特差错的帧到来的概率。
  • $P_2$：在使用某种差错检测算法的情况下，含有一个或多个未检测到的比特差错的到达概率。（也称为剩余差错率。）
  • $P_3$：在使用某种差错检测算法的情况下，含有一个或多个检测到的比特差错，并且没有未检测到的比特差错的帧到达的概率。

通过使用差错检测码来检测错误，也称为检验比特(check bit)。

6.3 奇偶校验

6.3.1 奇偶校验比特

注意：奇偶校验是指满足加上校验位后所有的1的数量为奇数或偶数。

如果有任意偶数个比特因错误而反转就会出现检测不到的差错。

奇偶校验并不是十分安全，因为噪声脉冲的长度经常足以破坏一个以上的比特，特别是在数据率比较高的情况下。

6.3.2 二维奇偶校验

每一行$i$添加该行的偶校验比特$r_i$，每一列添加该列的偶校验比特$c_j$，整个阵列的最后再添加一个整体的奇偶校验比特$p$。这种差错检验码由$i + j + 1$个奇偶校验比特构成。

具有一定的纠错能力，矩形的四个错误无法检测。

6.4 因特网检验和

因特网检验和的计算利用了二进制反码运算以及反码求和。

Checksum

首先将检验和字段全部置为0，然后对首部中所有的八位组执行反码求和，对计算结果进行反码运算。最后得到的结果被存放在检验和字段中。为了验证检验和，再一次对所有八位组（包括检验和字段）进行反码求和。如果得到的结果为全1（即负0），则验证成功。

注意：求和过程中如果最左边的比特有进位，则和再加1（循环进位(end-arround carry)）。

  • 相比于奇偶校验，因特网校验和差错检测能力更强
  • 涉及简单的加法和比较运算，开销小
  • 链路层使用循环冗余校验（CRC）情况下，因特网校验和作为补充到端到端的差错检测

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

给定一个$k$位的比特块，或者说报文，发送器会生成一个$(n-k)$位的比特序列，称为帧检验序列(Frame Check Sequence, FCS)。它必须使最后得到的含有$n$个比特的帧能够被一些预先设定的数值整除。然后，接收器用同样的数值对接收到的帧进行除法运算，如其结果没有余数，则认为没有差错。

6.5.1 模2运算

模2运算是实现循环冗余检验的一种处理方法，使用无进位的二进制加法（异或操作）。

现在定义：

  • $T$为要发送的$n$比特帧，
  • $D$为$k$比特数据块（报文），
  • $F$为$(n-k)$比特帧检验序列(FCS)，
  • $P$为$(n-k+1)$比特的预定比特序列，它是预定的除数。

（省去P135一大串数学运算），FCS是很容易生成的：只要用$P$去除$2^{n-k}D$，并且将其$(n-k)$比特的余数作为FCS。在接收时，接收方会用$T$除以$P$，并且如果传输没有差错，那么计算得到的结果就没有余数。

6.5.2 多项式

第二种观察CRC处理过程的方法是将所有的值表示成一个虚构变量$X$的多项式，其系数均为二进制数。这些系数与二进制数值中的每一位相互对应。例如$P=11001$，$P(X) = X^4 + X^3 + 1$。运算操作仍然是模2的，此时的CRC过程可描述如下： $$\dfrac{X^{n-k}D(X)}{P(X)} = Q(X) + \dfrac{R(X)}{P(X)}$$ $$T(X) = X^{n-k}D(X) + R(X)$$

  • 预定比特序列$P$要比要求的帧检验序列FCS多一个比特
  • 检测差错等价于选择$P$使得差错不能被$P$整除（只有在能被$P(X)$整除时才无法检测到差错）。

广泛使用的多项式序列：CRC-12、CRC-ANSI、CRC-CCITT、IEEE-802。

6.5.3 数字逻辑

CRC过程可以表示为由一些异或门和移位寄存器组成的除法电路：

Circuit

  • 寄存器含有$(n-k)$个比特，等于FCS的长度；
  • 总共有$(n-k)$个异或门；
  • 异或门是否存在，对应于多项式除数$P(X)$中的某一项是否存在，除了项$1$和$X^{n-k}$。

6.6 前向纠错

  • 差错检测需要数据块重传机制
  • 差错重传不适用于信道状态较差的链路：
    • 无线链路：高比特差错率导致大量重传
    • 卫星链路：长传播时延导致效率低下
  • 前向纠错(FEC)：接收器能够在接收过程中根据传输的比特来纠错。

FEC得到的四种可能输出：

  • 无差错：没有比特差错，解码器生成原数据块；
  • 可检测，可纠正差错：即使收到的数据块和被传输的码字不同，FEC解码器也能通过映射产生原数据块；
  • 可检测，不可纠正之差错：能够检测到差错，但无法纠正；
  • 不可检测之差错：未能检测到差错，产生与原数据块不一致的$k$比特数据块。

FEC算法以$k$比特块为输入，并向比特块增加$(n-k)$个检验比特，形成$n$比特数据块；原有$k$比特块内的比特都将在$n$比特块中出现。对于某些FEC算法，FEC算法将$k$比特输入映射到$n$比特码字，原始的$k$比特将不再在码字中出现。

6.6.1 块码原理

汉明距离 $d(v_1, v_2)$是指$v_1$和$v_2$之间不同比特的个数。

  • $(n, k)$块码：共有$2^n$个码字，其中合法码字为$2^k$个。
  • 冗余度：冗余比特与数据比特的比率$\dfrac{n-k}{k}$。
  • 编码率：数据比特与总比特数的比率$\dfrac{k}{n}$。
  • 最短距离：一个编码中码字之间的最短汉明距离。

如果$d_{\min} \geqslant 2t+1$，那么这个编码可以纠正高达（包括）$t$个比特的差错。如果$d_{\min} \geqslant 2t$，那么所有小于等于$t-1$个比特的差错都可以被纠正，并且能够检测出$t$个比特的差错，但通常无法纠正。

可纠正比特数：$t = \left\lfloor \dfrac{d_{\min} - 1}{2} \right\rfloor$，可检测比特数：$t = d_{\min} - 1$。

块码设计的要点：

  • 对于给定的$k$和$n$，希望$d_{\min}$尽可能大；
  • 编解码过程相对简单，内存开销和处理时间尽量少；
  • 希望附加比特数$(n-k)$比较少，以减少带宽；
  • 或希望附加比特数$(n-k)$比较多，以减少差错率。

（具体的纠错码可以参考数电的汉明码。）

编码增益(coding gain) 如果使用了相同的调制方法，要达到指定的BER（比特差错率），有纠错码的系统和无纠错码的系统相比较，所要求的$E_b/N_0$值（信噪比）的减小量，以分贝为单位。