CRC:(Cyclic Redundancy Cheak)
【概念】:循环冗余检验(CRC)检错技术
【原理】:
发送端:
M是一个n位的二进制数据,将M向左平移k位,得到一个新的M。
用这个新的M除以一个k+1位的多项式P(多项式最高次数为k+1),会得到一个商Q和k位的余数R。(余数位数不足k位的时候,前边的零不能省略)。
所以可以得到如下的式子。
M=P*Q+R;->(M-R)=P*Q->在模二的运算下(M-R)=(M+R),所以可以将M=M+R发送给接收端
接受端
接收端此时可以根据如下的公式通过判断接受到的M是否出现bit位的错误。
M%P=0(M=M+R)
通过数学理论,在理论上传输没有发生错误的时候,M%P=(M+R)%P=(P*Q)%P=0;
生成多项式:可以使用固定的几个多项式。(标准给出的多项式)
【实现】:
1,发送端将数据帧M向左移位,空出K个位置。即。
2,用(接收端和发送端已知的多项式:k+1位生成多项式)去除M,得到k位余数。
3,将(此时),并将M发送给接收端。
4,接受端接收到M之后,用去除M,得到余数R
结果判断:
如果R是零,则表示传输过程中没有发生bit位的错误。
如果R不是零,则表示传输过程中出现了bit位的传输错误。[帧中某一个bit位出现了错误]。
【CRC的检错能力】
举个小例子说明为什么可以检查1~k位错位。
例如:假设此时应该接收到的数据M为1111,此时的P(x)多项式为1111。在传输没有错误的情况下,用M去模p(x)结果应该为0;
而此时接收到的数据为1110,用1110去模p(x)结果为1。则表示对应的接收到的数据的最低位出错;如果接收的数据为1010,用1010去模1111,结果为0101,则表示数据最低位和次高位出错。这个特性是由于模二下的除法运算决定的。【模二除法:对应位的异或运算】。
CRC除了能检查出离散的错误外,还能检查出突发错。突发错是指在接收的二进制比特流中突然出现连续的几位或更多位数的错误。
CRC具有以下检错能力:
1,能检查出全部离散的1位错。
2,能检查出全部离散的2位错。
3,能检查出全部奇数位错。
4,能够检查出全部长度小于或等于k位的错误。
5,能以[]的概率检查出长度为k+1的突发错。
【例子】
选取p(x)为,则p(x)对应的二进制为11001。要传输的数据M为110011,计算CRC校验的校验码。
校验码:
1,将M左移4位,可以得到M的值为110010000。
2,用M的值去除以p(x)所对应的二进制可以得到余数R(校验码)为1001。
带有校验码的比特序列:
3,将M的值与R进行模二下的加法,得到结果为110011001。
验证:
1,将接收到的110011001与p(x)的二进制1101进行模二下的除法运算,得到余数R为0。