差错从何而来

概括来说，传输中的差错都是由于噪声引起的。

  • 全局性：由于线路本身的电气特性所产生的随机噪声（热噪声），是信道固有的，随机存在的。
  • 局部性：外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。解决办法：通常利用编码技术来解决。

差错种类：

位错

比特位出错，1变成0，0变成1

帧错（[#1]-[#2]-[#3]）

  • 丢失：收到[#1]-[#3]
  • 重复：收到[#1]-[#2]-[#2]-[#3]
  • 失序：收到[#1]-[#3]-[#2]

    检错编码

    奇偶校验码

    image.png
    如果一个字符的ASCll编码从低到高依次为1100101，采用奇偶校验码，在下述收到的传输后字符中，哪种错误不能检测？(D)
    A:11000011
    B:11001010
    C:11001100
    D:11010011

奇偶校验码特点：只能检查出奇数个比特错误，检错能力50%（错误的比特码不能相互抵消了）

CRC循环冗余码

image.png

接收端检错过程
把收到的每一个帧都除以同样的除数，然后检查得到余数R。

  • 余数为0，判定这个帧没有差错，接受
  • 余数不为0，判定这个帧有差错（无法确定到位），丢弃

FCS的生成以及接受端CRC校验都是由硬件实现，处理很迅速，因此不会延误数据的传输

在数据链路层仅仅使用循环冗余校验码检验CRC差错检测技术，只能做到对帧的无差错接受，即“凡是接收端数据链路层接受的帧，我们都能以非常接近1的概率认为这些帧在传输过程中没有产生差错”。接收端丢弃的帧虽然曾接收到了，但是最终还是因为有差错被丢弃。“凡是接收端数据链路层接收的帧均无差错”。

纠错编码

海明码

发现双比特错，纠正单比特错😳

工作流程

  • 确定校验码的位数R
  • 确定校验码和数据的位置
  • 求出校验码的值
  • 检错并纠错

确定校验码的位数R

海明不等式：2≥k+r+1 r为冗余信息位，k为信息位

要发送的数据：101101
数据的位数k=6
满足不等式的最小r为4
也就是101101的海明码应该有6+4=10，
其中原数据6位，校验码4位。

确定校验码和数据的位置

D=101101
假设这4位校验码分别为P、P、P、P；数据从左到右为D、D、。。。。D

二进制位 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010
数据位 1 2 3 4 5 6 7 8 9 10
代码 P P D P D D D P D D
实际值 0 0 1 0 0 1 1 1 0 1

令所有要校验的的位异或为0

  • 确定冗余码的位置：依次为2，2，2，2
  • 确定冗余码的值：根据冗余码位置的二进制位1的位置，选出数据位置二进制位1相同的位置，统一进行异或处理为0

    检错并纠错

    | 二进制位 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 数据位 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | 代码 | P | P | D | P | D | D | D | P | D | D | | 实际值 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |

故101101的海明码为0010011101
假设第五位出错，因此接收到的数据位0010111101
令所有要校验的位进行异或运算，从P开始取其结果：0101 = 5
故错误的位置为第五位，将其位置取异或即可。