CRC的串行及并行实现原理

CRC的串行及并行实现原理1. 编码中的几个概念1.1多项式：二进制数据作为多项式的系数。1.2生成多项式：通信双方约定的多项式。1.3多项式除法：与普通代数多项式的除法相同。1.4模2加减法：以2为模，力。减时不进错位或进位，与逻辑异或运算一致，模2加法 与减法是等价的。2. CRC编码算法2.1设待发送的数据块是m位的二进制多项式K(x),生成多项式是r阶的G(x)。在数据 块的末尾添加r个0，数据块的长度增加到m+r位，对应的二进制多项式为xK(x)。2.2用生成多项式G(x)去除xrK(x)，求得余数为r-1阶的二进制多项式R(x)。此二进制 多项式R(x)就是K(x)经过生成多项式G(x)的 CRC生成多项式。2.3用xrK(x)以模2的方式减去R(x)，则对应的二进制序列就是包含了 CRC校验码的待 发送字符串。2.4接收方校验时，用同样的生成多项式去除接受到的数据多项式，如果除的尽表明无 差错，如果除不尽表明有差错。3. 数学表达xrK(x) = Q(x) * G(x) + R(x)xrK(x) - R(x) = Q(x) * G(x)4. 实现方式4.1串行实现CRC-CCITT算法生成多相式为：x人16+x人12+x人5 + 1。计算CRC实际上是将数据通过线性反馈移位寄存器，所有数据移入后CRC寄存器的值即为16位CRC值。Polynomial; xA16 + xA12 + xA5 + xA0Note： C15 represents CO represents xA154.2并行实现并行CRC运算模块每次输入8位数据，相当于一次并行运算就得到了串行移位运算时 需要8位移位所得的结束。由以下4个表可以知道并行CRC实现的原理：每个时钟到来时 完成8bit数据CRC值计算；下一个8bit数据到来时，把上一个8bit数据的CRC值C15 C0作为初值，继续完成并行CRC计算。即每次处理1byte。表1. 移位前CRC寄存器值（初值）R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0C15C14C13C12C11C10C9C8C7C6C5C4C3C2C1C0表2.1次移位后CRC寄存器值R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0X0C15C14C13C12C11X0C10C9C8C7C6C5C4X0C3C2C1表3.2次移位后。日。寄存器值R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0X1X0C15C14C13C12X1C11X0C10C9C8C7C6C5X1C4X0C3C2表43次移位后CRC寄存器值R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0X2X1X0C15C14C13X2C12X1C11X0C10C9C8C7C6X2C5X1C4X0C3表54次移位后CRC寄存器值R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0X3X2X1X0C15C14X3C13X2C12X1C11X0C10C9C8C7X3C6X2C5X1C4X0表65次移位后CRC寄存器值R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0X4X0X3X2X1X0C15X4X0C14X3C13X2C12X1C11X0C10C9C8X4X0C7X3C6X2C5X1表76次移位后CRC寄存器值R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0X5X1X4X0X3X2X1X0X5X1C15X4X0C14X3C13X2C12X1C11X0C10C9X5X1C8X4X0C7X3C6X2表87次移位后CRC寄存器值R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0X6X5X4X3X2X1X0C15C14C13C12C11C10C9C8C7X2X1X0X6X5X4X3X2X1X0X6X5X4X3X2X1X0X2X1X0表98次移位后CRC寄存器值R15R14R13R12R11R10R9R8R7R6R5R4R3R2R1R0X7X6X5X4X3X2X1X0C15C14C13C12X0C10C9C8X3X2X1X0X7X3X6X2X5X1X4X0X3X2X1X3X7C11X6X2X5X1X4X0表中参数说明：Ri为CRC移位寄存器值（R0为低位），Ci为CRC移位寄存器初值（C0为低位），Di为输入数据（D0 为低位），Xi = Di人Ci，同一栏中数据的运算关系是异或。每次并行数据到来时，各CRC寄存器值按表4运算关系更新。最后一个字节数据输 入后CRC寄存器的值（R0 R15）即为该数据组的CRC值。从表中看出，一次CRC计算 最多完成4组异或运算。如：R3=C11 人 D7 人 C7 人 D0 人 C0;R15 = D7 人 C7 人 D3 人 C3