-
-
[原创]循环冗余检验CRC
-
发表于: 2010-12-11 12:06
-
在学TCP/IP中，关于Ethernet帧结构中的最后一部分帧校验字段FCS（4B），在编程通信程序时，我们需对数据链路层通信Ethernet帧进行校验，即对帧校验字段FCS进行校验。FCS采用32位CRC校验。校验的范围包括目的地址、源地址字段、类型字段、数据字段。在接受段进行校验，如果发现错误，帧将被丢弃。
下面是关于CRC的循序渐进的知识：
循环冗余码校验（CRC=cyclic redundancy check），是一个信息字段和校验字段的长度可以任意选定的差错校验码。
原理：任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。发过来看：x8+ x2+x1+1= 1*x8+0*x7+ 0*x6+0*x5+0*x4+1*x2+1*x1+1*1，所得到的代码是100000111。
CRC码集选择的原则：若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得V(x)=A(x)g(x)=xRm(x)+r(x);其中: m(x)为K次信息多项式， r(x)为R-1次校验多项式，g(x)称为生成多项式：g(x)=g0+g1x1+ g2x2+...+g(R-1)x(R-1)+gRxR。发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。
CRC校验码软件生成方法：借助于多项式除法，其余数为校验字段。例如：信息字段代码为: 1011001；对应m(x)=x6+x4+x3+1 。假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为: 11001 。x4m(x)=x10+x8+x7+x4 对应的代码记为：10110010000；x4m(x)/ g(x)即采用多项式除法（如何运算见下段）: 得余数为: 1010 (即校验字段为：1010）。发送方：发出的传输字段为: 1 0 1 1 0 0 1 1010（信息字段 校验字段）。接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法）如果能够除尽，则正确。
给出余数（1010）的计算步骤：除法没有数学上的含义，而是采用计算机的模二除法，即，除数和被除数做异或运算。进行异或运算时除数和被除数最高位对齐，按位异或。
1011001 0000
-11001
--------------------------
=01111010000
1111010000
-11001
-------------------------
=0011110000
11110000
-11001
--------------------------
=00111000
111000
- 11001
-------------------
= 001010
以下是8位CRC校验为例：
关于CRC校验实现的方法有很多，简单起见，采用8位CRC校验，其生成多项式为G（x）= x8+ x2+x1+1。例：一个实现CRC-8的硬件电路：由8个移位寄存器和3个异或单元组成。
计算过程如下：
（1）开始编码解码前所有寄存器清0。
（2）输入位作为最左边异或或操作的输入之一，8个寄存器上的移位操作同时进行，均为左移一位。
（3）每次移位时寄存器R7的输出作为所有3个异或操作的输入之一，寄存器R0的输出作为中间异或操作的输入之一，寄存器R1的输出作为最左边异或操作的输入之一。
（4）各个异或操作的结果作为它左边那个寄存器的输入位。
（5）重复以上操作，每输入一位就做一次移位操作，直到输入了所有要计算的数据为止。这时，这个寄存器组中的数据就是CRC-8的结果。
以1010为例，将1010后补8个0所得的比特序列（即101000000000）当做输入值，8个移位寄存器组中的值为00110110。该结果与101000000000除以100000111（G（x）= x8+ x2+x1+1）所得的余数相同。
对上面计算过程分析可以得到，当寄存器R7的移出位为1时，寄存器组才和00000111进行XOR运算；移出位为0时，不做运算。每次寄存器中的数据左移后就需要从输入数据中读入一位新的数据，如果读入的新数据为1，则需要把寄存器R0置为1，然后再判断寄存器是否需要与00000111进行XOR运算。
思路：
//register8是一个8位的寄存器，把register8中的值置为0，在原始数据后添加8个0（因为校验字段为8位，得到的是x8 m(x)）
While(数据未处理完)
{
if(register8首位是1)
{
register8中的数据左移1位;
if(从输入中读入的新数据为1)
{
将register8的最低位置1;
}
register8= register8 XOR 00000111
}
else
{
register8中的数据左移1位;
if(从输入中读入的新数据为1)
{
将register8的最低位置1;
}
}
}
void checkCRC(int &chCurrByte, int chNextByte)
{
// CRC循环：每次调用进行8次循环，处理一个字节的数据。
for (int nMask = 0x80; nMask > 0; nMask >>= 1)
{
if ((chCurrByte & 0x80) != 0) // 首位为1：移位，并进行异或运算
{
chCurrByte <<= 1; // 移一位
if ( (chNextByte & nMask) != 0) // 补一位
{
chCurrByte |= 1;
}
chCurrByte ^= 7; // 首位已经移出，仅对低8位进行异或运算，7的二进制为0000,0111
}
else // 首位为0，只移位，不进行异或运算
{
chCurrByte <<= 1; // 移一位
if ( (chNextByte & nMask) != 0) // 补一位
{
chCurrByte |= 1;
}
}
}
}
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
|
|
|---|---|
