乐趣区

技术栈CRC校验原理及C代码实现CRC16CRC32计算FCS校验码

jiezi

1.CRC、FCS 是什么

CRC，全称 Cyclic Redundancy Check，中文名称为循环冗余校验，是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。

FCS，全称 Frame Check Sequence，中文名称为帧校验序列，俗称帧尾，即计算机网络数据链路层的协议数据单元（帧）的尾部字段，是一段 4 个字节的循环冗余校验码。

注：CRC 循环冗余校验和 FCS 帧校验序列是单独的概念，CRC 是一种错误校验方法，FCS 是帧尾校验码，FCS 可以采用 CRC 校验方法，也可以采用其他校验方法。

2.CRC 算法原理

我们可以把任意的一串二进制数据表示为一个与之对应的多项式。比如：

二进制数据：1100101
多项式：$x^6 + x^5 + x^2+1$

多项式：$x^6 + x^4+x^3 + x^2+1$
二进制数据：1011101

有了这样的对应关系，对二进制数据的 CRC 校验就可以利用多项式运算规则进行校验计算。
CRC 校验算法正是采用了模 2 除法，在数据处理里的具体表现为异或运算。

CRC 的具体运算规则为：假设要传输的二进制数据为：10010110, 对应的 m 阶多项式为：$M =x^7+x^4+x^2+x^1$，除数为 h 阶的多项式为：$H=x^4+x$，对应的二进制码为：10010, 先将 M 乘以 $x^h$，即将 M 对应的二进制数据后面加 h 个 0，然后除以 h 阶的多项式 H，得到的 h - 1 阶的余数项 R 对应的二进制数据即为数据10010110 的 CRC 校验码。

3. 计算 CRC 校验

3.1. 手工计算 CRC 校验码

M和 H 的多项式除法运算，可以用模 2 除法运算计算。下面为以生成多项式为 H 求10010110的 CRC 校验码运算过程：

对应到异或运算：

通过示例即其他自定义的一些数据运算后，根据运算现象总结可以得到一些规律：

1. 每次异或运算，当从左到右首位为 1 的时候，就与生成多项式 H 异或运算，然后再左移 1 位；当首位为 0 的时候只将数据左移 1 位。

2. 每次异或运算后的数据，首位必定为 0，因为首位为 1 的时候进行异或运算，而生成多项式的首位也必定为 1。所以当需要进行异或运算时，可以舍弃 H 的首位，舍弃后为 H’，直接将数据左移一位后再与H’ 异或。

3. 每次运算，参与运算的是数据的前 h 位，可以用一个存储 h 位二进制数据的寄存器 S，将数据的前 h 位存储到这个寄存器中。每次运算先将寄存器的首位移除，然后将二进制数据后一位移入，然后再参与运算，最后寄存器中的值即为 CRC 校验码。

3.2.C# 代码计算 CRC 校验码

// 代码验证如下：static void Main(string[] args)
{
    int data = 0b10010110;
    int ploy = 0b0010;
    ploy <<= 4;
    Console.WriteLine($"第 0 次运算结果："+Convert.ToString(data, 2));
    for (int i = 0; i < 8; i++)
    {if ((data & 0b10000000) == 0b10000000)
        {data = (data << 1) ^ ploy;

        }
        else
        {data <<= 1;}

        Console.WriteLine($"第 {i+1} 次运算结果："+Convert.ToString(data, 2));
    }
    Console.WriteLine($"最终运算结果："+Convert.ToString(data, 2));          
    Console.ReadKey();}

这里用 int 的第 5 位到第 8 位作为一个四位寄存器，可以看到与手算一致，最后算得校验位1100。

4. 查表法

可以看到，参与运算的始终只有 4 位，所以在移位 D1 数据时，参与运算的数据只有 D1 和D2，经过四次移位运算，D1被移除寄存器，这个时候受到影响的只有 D2。而将D2 的初值经过四次异或运算后的值就可以获得四次移位后的新数据 $D2’=D2\bigoplus H1 \bigoplus H2\bigoplus H3\bigoplus H4 = D2 \bigoplus \sum{h}$。

每一次 D2 是异或 0 还是异或生成多项式 H’，与D2 本身的值无关，仅与 D1 中被移除的数据有关 (首位为 0 还是 1)，所以这里引入了一个查表法，即先将所有可能的D1 组合都计算出对应的 $\sum{h}$, 一次性移除四位，然后以 $D2\bigoplus{\sum{h}}$ 即可以获得D2′。

生成多项式为H，则一共有 $2^h$ 种可能，代码如下：

class CalcByCrcTable
{private byte[] CrcTable;
    private void CteateTable()
    {
        int ploy = 0b0010;            
        CrcTable = new byte[(int)Math.Pow(2,4)];
        ploy <<= 4;
        for (int i = 0; i < CrcTable.Length ; i++)
        {
            int data = i<<4;
            for (int j = 0; j < 4; j++)
            {if ((data & 0b10000000) == 0b10000000)
                {data = (data << 1) ^ ploy;
                }
                else
                {data <<= 1;}                  
            }
            CrcTable[i] = Convert.ToByte((data & 0xf0)>>4);
        }
    }
    public byte CalcCrc()
    {CteateTable();
        int data = 0b10010110;
        byte crchigh4 = CrcTable[(data>>4)&0x0f];// 用查表法先查到 data 的高四位 1001 的 crc 值；byte value = Convert.ToByte((data & 0x0f) ^ crchigh4);// 将高四位的 CRC 与低四位异或，得到移位四次后的数据值；byte crc = CrcTable[value]; // 在用移位后的数据值查出数据的 CRC 校验码；return crc;

    }
}

 static void Main(string[] args)
 {CalcByCrcTable calcByCrcTable = new CalcByCrcTable();
        byte crc = calcByCrcTable.CalcCrc();           
        Console.WriteLine($"CRC 校验码为：" + Convert.ToString(crc, 2));
        Console.ReadKey();}

// 打印结果如下

CRC 校验码为：1100

可以看到与前面的计算法结果一致。

5. 反向校验

上面所诉的均为正向检验(Normal)，当然也有反向校验(Reversed)，反向校验是将数据和生成多项式均进行了一个镜像，当然算法也需要镜像，即镜像后从右往左运算。

5.1 手工计算 CRC 反向校验码

原二进制数据：10010110

原生成多项式：0010

正向 CRC 校验码：1100

镜像二进制数据：01101001

镜像生成多项式：0100

镜像算法：

反向 CRC 校验码：0011

5.2.C# 代码计算 CRC 反向校验码

class CalcByCrcTable
{private byte[] CrcTable;
    private void CteateReversedTable()
    {
        int ploy = 0b0100;
        CrcTable = new byte[(int)Math.Pow(2, 4)];           
        for (int i = 0; i < CrcTable.Length; i++)
        {
            int data = i;
            for (int j = 0; j < 4; j++)
            {if ((data & 1) == 1)
                {data = (data >> 1) ^ ploy;
                }
                else
                {data >>= 1;}
            }
            CrcTable[i] = Convert.ToByte((data & 0x0f));
        }
    }
 public byte CalcReversedCrc()
    {CteateReversedTable();
        int data = 0b01101001;
        byte crclow4 = CrcTable[data & 0x0f];// 用用查表法先查到 data 的低四位 1001 的 crc 值；byte value = Convert.ToByte(((data>>4) & 0x0f) ^ crclow4);// 将第四位的 CRC 与低四位异或，得到移位四次后的数据值；byte crc = CrcTable[value]; // 在用移位后的数据值查出数据的 CRC 校验码；return crc;

    }
}

 static void Main(string[] args)
{CalcByCrcTable calcByCrcTable = new CalcByCrcTable();
    byte crc = calcByCrcTable.CalcReversedCrc();           
    Console.WriteLine($"CRC 反向校验码为：" + Convert.ToString(crc, 2));
    Console.ReadKey();}

// 打印结果如下

CRC 反向校验码为：11

6.C# 查表法计算 CRC16 校验码

// 多线程使用时请注意干扰 
class CalcOnCrc16
 {private ushort[] Crc16NormalTable;

     private ushort[] Crc16ReversedTable;

     private void CreateNormalCrc16Table(ushort ploy)
     {
       ushort data;
       Crc16NormalTable = new ushort[256];
       int i, j;
       for (i = 0; i < 256; i++)
       {data = (ushort)(i << 8);
           for (j = 0; j < 8; j++)
           {if ((data & 0x8000) == 0x8000)
                   data = Convert.ToUInt16((ushort)(data << 1) ^ ploy);
               else
                   data <<= 1;                    
           }
           Crc16NormalTable[i] = data;
       }
     }

     private void CreateReversedCrc16Table(ushort ploy)
     {
       ushort data;
       Crc16ReversedTable = new ushort[256];
       int i, j;
       for (i = 0; i < 256; i++)
       {data = (ushort)i;
           for (j = 0; j < 8; j++)
           {if ((data & 1) == 1)
                   data = Convert.ToUInt16((ushort)(data >>1) ^ ploy);
               else
                   data >>= 1;
           }
           Crc16ReversedTable[i] = data;
       }
     }

    /// <summary>
    /// 正向计算 CRC16 校验码
    /// </summary>
    /// <param name="bytes"> 校验数据 </param>
    /// <param name="poly"> 生成多项式 </param>
    /// <param name="crcInit"> 校验码初始值 </param>
    /// <returns></returns>
    public ushort CalcNoemalCrc16(byte[] bytes,ushort poly,ushort crcInit)
    {CreateNormalCrc16Table(poly);
   
        ushort crc = crcInit;
        for (int i = 0; i < bytes.Length; i++)
        {crc = Convert.ToUInt16((ushort)(crc << 8) ^ Crc16NormalTable[((crc >> 8) & 0xff) ^ bytes[i]]);
        }
        return crc;
    }

     /// <summary>
     /// 反向计算 CRC16 校验码
     /// </summary>
     /// <param name="bytes"> 校验数据 </param>
     /// <param name="poly"> 反向生成多项式 </param>
     /// <param name="crcInit"> 校验码初始值 </param>
     /// <returns></returns>
    public ushort CalcReversedCrc16(byte[] bytes, ushort poly, ushort crcInit)
    {CreateReversedCrc16Table(poly);
   
        ushort crc = crcInit;
        for (int i = 0; i < bytes.Length; i++)
        {crc = Convert.ToUInt16((ushort)(crc >> 8) ^ Crc16ReversedTable[(crc & 0xff) ^ bytes[i]]);
        }
        return crc;
    }
 }

7.C# 查表法计算 CRC32 校验码

class CalcOnCrc32
{private uint[] Crc32NormalTable;
    
    private uint[] Crc32ReversedTable;

    private void CreateNormalCrc32Table(uint ploy)
    {
        uint data;
        Crc32NormalTable = new uint[256];
        int i, j;
        for (i = 0; i < 256; i++)
        {data = (uint)(i << 24);
            for (j = 0; j < 8; j++)
            {if ((data & 0x80000000) == 0x80000000)
                    data = Convert.ToUInt32((uint)(data << 1) ^ ploy);
                else
                    data <<= 1;
            }
            Crc32NormalTable[i] = data;
        }
    }

    private void CreateReversedCrc32Table(uint ploy)
    {
        uint data;
        Crc32ReversedTable = new uint[256];
        int i, j;
        for (i = 0; i < 256; i++)
        {data = (uint)i;
            for (j = 0; j < 8; j++)
            {if ((data & 1) == 1)
                    data = Convert.ToUInt32((uint)(data >> 1) ^ ploy);
                else
                    data >>= 1;
            }
            Crc32ReversedTable[i] = data;
        }
    }

    /// <summary>
    /// 正向计算 CRC32 校验码
    /// </summary>
    /// <param name="bytes"> 校验数据 </param>
    /// <param name="poly"> 生成多项式 </param>
    /// <param name="crcInit"> 校验码初始值 </param>
    /// <returns></returns>
    public uint CalcNoemalCrc32(byte[] bytes, uint poly, uint crcInit)
    {CreateNormalCrc32Table(poly);
        uint crc = crcInit;
        for (int i = 0; i < bytes.Length; i++)
        {crc = Convert.ToUInt32((uint)(crc << 8) ^ Crc32NormalTable[((crc >> 24) & 0xff) ^ bytes[i]]);
        }
        return crc;
    }

    /// <summary>
    /// 反向计算 CRC32 校验码
    /// </summary>
    /// <param name="bytes"> 校验数据 </param>
    /// <param name="poly"> 反向生成多项式 </param>
    /// <param name="crcInit"> 校验码初始值 </param>
    /// <returns></returns>
    public uint CalcReversedCrc32(byte[] bytes, uint poly, uint crcInit)
    {CreateReversedCrc32Table(poly);
        uint crc = crcInit;
        for (int i = 0; i < bytes.Length; i++)
        {crc = Convert.ToUInt32((uint)(crc >> 8) ^ Crc32ReversedTable[(crc & 0xff) ^ bytes[i]]);
        }
        return crc;
    }
}

参考资料

循环冗余检验 (CRC) 算法原理

CRC 查找表法推导及代码实现比较

CRC（循环冗余校验）在线计算

退出移动版