11循环冗余校验码[中章]

循环冗余校验码

总览

循环冗余校验(Cyclic Redundancy Check，CRC)

基本思想

数据传输的时候,数据的双方约定一个除数,然后最终如果结果的余数相同的话那说明我们的数据没有出错，如果余数不同说明数据出错了

我们在后面加上一些校验位,来确保数据被除后余数为零

循环校验码

例子:
$$
设多项式为 G(x)=x^3+x2+1 ,信息码为101001\
求对应的CRC码
$$

我们可以把$G(x)=x^3+x2+1$换一种写法

$$
\begin{align*}
x^3+x2+1 &= 1x^3 + 1x^2 + 1*x^0\
&=\underbrace{1}*x^3 + \underbrace{1}*x^2 + \underbrace{0}*x^1 + \underbrace{1}x^0
\end{align}
$$

此时我们把他们前面的系数提取出来就得出一个数字 $1101$

开始计算

1. 确定一共有多少R(校验位)
   K = 信息码的长度 = 6
   R = 多项式最高次幂 = 3(x³)
   所以我们一共有3个校验位，于是我们现在需要传输的数据除了原本的信息位，现在还需要传输校验位
   $$
   \begin{align*}
   生成的&CRC码用N表示\
   N &= K + R \
   &= 6 + 3\
   &= 9
   \end{align*}
   $$

2. 移位
   信息码左移R位，地位补0
   $$
   101001 = 01001\color{yellow},{000}
   $$

模二除

3. 相除

对移位后的信息码，用生成多项式进行模2除法，产生余数

最终我们得到了我们的CRC校验码:$$101001,001$$

---

4. 检验错误和纠错

CRC码有纠错能力，但是非常弱，只能纠正一位错误

$$
当我们的数据满足下列关系式可以纠错\
2^R \geq K + R + 1\
但是一般情况下，CRC还是用作校验而非纠错
$$

回顾和总览