CRC码原理详解

目录

前言

介绍

基本原理

CRC原理举例说明

s1:将多项式转化成二进制数

s2：计算得到CRC码

s3：接收端判断数据是否正确

常见的CRC多项式参数模型 

相关参数说明

CRC模型计算举例

 参考

前言

        某人，查阅和参考了大量博主的优质内容，总结一篇完整的CRC码详解，文字内容尽量做到最少。

介绍

        CRC码即循环冗余校验码（Cyclic Redundancy Check）是数据通信领域中最常用的一种查错校验码，其特征是数据字段和校验字段的长度可以任意选定。

基本原理

        CRC码中数据总长度为n，其中原始数据长度为k，CRC校验码长度为r，即n=k+r。

      将原始数据（如：1110010）+CRC校验码（如：101）组成新的数据（如：1110010101），发送到接收端。

        其中，CRC校验码由CRC多项式（如：f(x) = x^3 + 1）和原始数据（1110010）通过模2除法运算（即：两个数直接进行异或运算，不借位和进位）得到（下节将会举例说明）。

        同理，接收端同样通过接收到的数据（1110010101）和CRC多项式（如：f(x) = x^3 + 1）通过模2除法运算，判断接收到的数据是否正确（下节将会举例说明）。

        如下所示，假设1110010101与1001进行模2除法运算（一一异或）：

CRC原理举例说明

        假设生成CRC码的多项式为G(x) = x^4 + x + 1，求出二进制序列1011的CRC校验码。具体的计算过程如下：

s1:将多项式转化成二进制数

         多项式G(x) = x^4 + x + 1，对应的二进制数据为5-bit（总位数=最高位的幂次+1，即4+1=5），且二进制数据为：10011，即G(x) = 1*x^4 + 0*x^3 + 0*x^2 + 1*x^1 + 1*x^0（注：具体推导过程，我也不清楚）。

        多项式的二进制位数为5-bit，则CRC校验码的位数为4-bit（校验码的位数比生成多项式的位数少1位）。

s2：计算得到CRC码

        在原始数据1011的后面增加4个0（即：增加的位数与CRC位数一致），得到10110000，接着将数据10110000与多项式对应的二进制数据（10011），进行模2除法运算，如下所示：

         得到的余数“1110”，为对应的4-bit CRC校验码。因此，发送端需要送的数据为“10111110”。

s3：接收端判断数据是否正确

        当接收端，收到数据“10111110”后，与多项式G(x) = x^4 + x + 1对应的二进制“10011”，做模2除法运算。

        如果得到的余数为0，则证明数据传输没有问题；反之，则说明数据传输有问题，计算如下所示：

常见的CRC多项式参数模型 

         在上节中，说明了CRC码的计算原理，但在实际应用中，那只是其中的一个关键步骤。

        不同的多项式参数模型（G(x)），需要根据其初始参数来计算其CRC校验码。常见的CRC多项式参数模型如下表所示：

相关参数说明

1. NAME：参数模型名称。

2. WIDTH：生成的CRC数据位宽，如CRC-32，生成的CRC校验码为32-bit。

3. POLY：生成多项式所对于的二进制码，用16进制表示。例如：CRC-32/MPEG-2是0x04C11DB7，忽略了最高位的"1"，即完整的生成项是0x104C11DB7。

4. REFIN：在进行计算之前，原始数据是否翻转，True或False。如原始数据：0x34 = 0011 0100。如果REFIN为True，进行翻转之后为0010 1100 = 0x2c。

5. INIT：CRC校验码的初始值，十六进制表示，和WIDTH位宽一致。该参数的值有两种形式：全为0，全为1。

        在判定并执行REFIN（翻转）之后：

        1) 当INIT全为1时，表示在算法开始前对数据的前CRC位数（高位）先和对应位数个1进行异或，再在后面补上CRC位数个0，才进行后续计算。

        2) 当INIT全为0时，在算法开始前对数据后面补上CRC位数个0后，就可以进行后续计算。

6. REFOUT：在计算后之后，得到的CRC值是否进行翻转，如计算得到的CRC值：0x97 = 1001 0111。如果REFOUT为true，进行翻转之后为1110,1001 = 0xE9。

 注：RefIn和RefOut这两个值同时为TRUE或者同时为TRUE

7. XOROUT：计算结果与此参数异或后得到最终的CRC值，和WIDTH位宽一致。

8.注：通常如果只给了一个多项式，其他的没有说明，则INIT=0x00，REFIN=false，REFOUT=false，XOROUT=0x00。

CRC模型计算举例

        假设，原始数据0100 0011（注：原始数据必须是以字节为单位），采用CRC-5/USB（G(x) = x^5 + x^2 + 1）多项式。

s1：根据CRC-5/USB多项式，得到除数二进制：100101

s2：由于REFIN=TRUE，需要翻转输入数据：0100 0011 -> 1100 0010

s3：由于INIT=0x1F为全1，需要对s2中数据的前CRC位数（高位）（即5-bit）和CRC初值进行异

        或，得到数据：1100 0010 -> 0011 1010

s4：将s3中的数据的最低位补5位0，得到数据：0011 1010 00000

s5：将s4中的数据与多项式二进制（100101），进行模2除法运算，得到余数：01100

s6：由于REFOUT=TRUE，需要将s5中的结果（01100）进行翻转，得到数据：01100 -> 00110

s7：最后，s6中的值与XOROUT=0x1F进行异或，得到最终的CRC值：11001

最后，在CRC在线计算器上，验证结果是正确的：

 参考

         下面参考文章中，有C语言实现CRC校验码功能的代码。

        参考了很多优秀博主的文章，如下：

        （原创）CRC计算流程分析（RefIn，Init，RefOut，XorOut）

        CRC校验原理及其C语言实现

        CRC校验原理及步骤