【校验码 - 循环冗余校验码CRC】

水善利万物而不争，处众人之所恶，故几于道💦

目录

循环冗余校验码

  1.多项式

  2.CRC编码的组成

  3.校验码的生成

  4.例题：

循环冗余校验码

广泛地在网络通信及磁盘存储时采用。

1.多项式

在循环冗余校验(CRC)码中，无一例外地要提到多项式的概念。一个二进制数可以以一个多项式来表示。如1011表示为多项式X ³+X ¹+X ⁰，如果把这里的x替换为2，这个多项式的值就是该数的值。从这个转换可以看出多项式最高幂次为R则转换为二进制数有R+1位。

2.CRC编码的组成

CRC编码的组成是由K位信息码，加上R位的校验码。

3.校验码的生成

校验码的生成步骤如下:

(1) 将K位数据C(x)左移R位，给校验位留下空间，得到移位后的多项式为C(x)×X^R（×这个不是乘号，代表连接）。

(2) 将移位后的信息多项式除以生成多项式所对应的二进制数(也就是和生成多项式进行模2运算-异或)，得到R位的余数多项式。

(3) 将余数作为校验码嵌入信息位左移后的空间。

4.例题：

信息位为 1010 0110，生成多项式为：a(x)=X5+X4+X+1，则CRC码为：

解题步骤：
①将信息码左移R位，R是生成多项式的最高次幂。
②将最高次幂为R的生成多项式G(X)转换为R+1位的二进制数
③将移位后的信息码除以②中生成的二进制数（这里的除是进行异或运算），得到R位的余数
④将余数作为校验码拼接到信息码左移后空出的位置，得出完整的CRC码

答：
①生成多项式的最高次幂是５，所以将信息码左移５位：
 1010 0110 0000 0

②将生成多项式转换为5+1位二进制数为：
 110011

③进行异或运算：
 1010 0110 0000 0
 1100 11
 -----------------------------
 0110 10   <----第一次运算结果

  110 1010 0000 0   <----补全结果，剩余位从上面拉下来
  110 011
 -----------------------------
  000 1100 0000 0   <----第二次运算结果
    1100 11
 -----------------------------
    11000   <----第三次运算结果
可以看出已经得到了5位余数，11000

④拼接，得出完整的CRC码：
1010 0110 11000