跳到主要内容

校验码

码距​

就单个编码 A： 00 而言，其码距为 1， 因为其只需要改变一位就变成另一个编码。在两个编码中，从 A 码到 B 码转换所需要改变的位数称为码距，如 A:00 要转换为 B:11 ,码距为 2。一般来说码距越大，越利于纠错和检错。

奇偶校验码​

在编码中 增加 1 位校验位来使编码中 1 的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变为 2。例如：

  • 奇校验：编码中，含有奇数个 1 ，发送给接收方，接收方收到后，会计算收到的编码有多少个 1 ，如果是奇数个，则无误，是偶数个，则有误。
  • 偶校验：编码中有偶数个 1 。
奇偶校验只能检 1 位错，并且无法纠错。

CRC 校验码​

CRC 只能检错，不能纠错。使用 CRC 编码，需要先约定一个生成多项式 G(x)G(x)。生成多项式的最高位和最低位必须是 1 。假设原始信息有 m 位，则对应多项式 M(x)M(x)。 生成多项式的思想就是 在原始信息位后追加若干校验位，使得追加的信息能被 G(x)G(x) 整除。接收方接收到带校验位的信息，然后用 G(x)G(x) 整除。余数位 0 ，则没有错误；反之则发生错误。，

例： 假设原始信息串为 10110，CRC 的生成多项式为 G(x)=x4+x+1G(x)=x^4+x+1，求 CRC 校验码。

  1. 在原始信息后面添 0，假设生成多项式的阶为 r，则在原始信息位后添加 r 个 0，本题中，G(x)G(x)的阶为 4 ，则在原始信息串后加 4 个 0 ，得到的新串为 101100000，作为被除数。

  2. 由多项式得到除数(除数为 r+1 个)，多项式中的 x 的幂指数存在的位置为 1 ，不存在的位置为 0。本题中，x 的幂指数为 0,1,4 de 变量都存在，而幂指数为 2,3 的不存在，因此得到除数为 10011。

  3. 生成 CRC 校验码，将前两步得到的被除数与除数进行模 2 运算（即不进位也不借位的除法运算，异或运算）。除法过程如下所示。

  4. 得到余数 1111。余数不足 r，则余数左边用若干个 0 补齐。如求得余数为 11，r = 4，则补两个 0 得到 0011。

  5. 生成最终发送信息串，将余数添加到原始信息后。上例中，原始信息为 10110，添加余数 1111后，结果为 101101111。发送方将此数据发送给接收方。

  6. 接收方进行校验。接收方的 CRC 校验过程与生成过程类似，接收方接受了带校验和的帧后，用多项式 G(x)G(x)来除。余数为 0，则表示信息无错；否则要求发送方进行重传。

注意：收发双方需使用相同的生成多项式。