CRC校验原理简介及C代码实现说明


1 原理

参考文档:CRC校验 (qq.com)

参考书籍:《计算机网络(第7版)-谢希仁》

1.1 原理简介

CRC是一种检错方法。

在发送端,先把数据划分为组,假定每组k个比特。现假定待传送的数据M = 101001(k = 6)。CRC运算就是在数据M的后面添加供差错检测用的n位冗余码,然后构成一个帧发送出去,一共发送(k + n)位。

数据:k比特

冗余码:n比特

这n位冗余码可用以下方法得出。在数据M后面添加n个0。得到的(k + n)位的数除以收发双方事先商定的长度为(n + 1)位的除数p(多项式),得出商是Q而余数是R(n 位,比P 少一位,校验码)。

这个余数R就作为冗余码拼接在数据M的后面发送出去。这种为了进行检错而添加的冗余码常称为帧检验序列FCS (Frame Check Sequence) 。

循环冗余检验CRC 和帧检验序列FCS 并不是同一个概念。CRC 是一种检错方法,而FCS 是添加在数据后面的冗余码。

模二运算:也就是异或运算,相同异或为0,不同异或为1。

在接收端把接收到的数据以帧为单位进行CRC检验:把收到的每一个帧都除以同样的除数P(模2运算),然后检查得到的余数R 。如果在传输过程中无差错,那么经过CRC检验后得出的余数R肯定是0。

1.2 计算步骤

(1)先选择CRC多项式,得到多项式的位宽。

例如:选择G(x) = X4 + X3 + 1,对应的二进制编码为:2b'11001,多项式位宽为4。

(2)选择计算的数据。

(3)计算。

计算方式为:在要发送的数据帧(假设为m位)后面加上k-1位“0”(k:多项式位宽),然后使用模二运算得到余数,这个余数就是CRC校验码。

例如:多项式为G(x) = X4 + X3 + 1,计算的数据帧为:2b'10110011,计算过程如下:

得到的CRC校验码为:2b'0100。

2 代码实现

参考链接:数据帧CRC32校验算法实现 - 没落骑士 - 博客园 (cnblogs.com)

在线生成工具:CRC Generation Tool - easics

还是以多项式为G(x) = X4 + X3 + 1,计算的数据帧为:2b'10110011来进行说明。

这里直接说实现,首先使用在线生成工具,得到一个VHDL或者Verilog的CRC校验源码。

然后对下载的代码进行一些改动即可。这里直接给出最后实现的C代码。

#include <stdio.h>

#define int32_t  signed int
#define uint32_t unsigned int
#define uint8_t  unsigned char

#define GET_BIT_N_VAL(data, n)   (0x1 & (( *((data) + (n)/8) & (0x1 << ((n)%8)) ) >> ((n)%8)))

#define BITS_TO_BYTES_ARRAY(entry_key, entry_key_bits, bytes_array)   \
    do                                                                \
    {                                                                 \
        uint32_t i = 0;                                               \
        for(i = 0; i < (entry_key_bits); i++)                         \
        {                                                             \
            bytes_array[i] = GET_BIT_N_VAL((entry_key), i);           \
        }                                                             \
    } while (0)

#define HASH_KEY_WRITE_BITS 8

uint8_t crc_4_d8(const uint8_t *d) // only use the last one bit
{
    /*
    -- polynomial: x^4 + x^3 + 1
    -- data width: 8
    -- convention: the first serial bit is D[7]
    */
    int32_t i;
    uint8_t ret=0;
    uint8_t lfsr_c[4] = {0};
    uint8_t c[4] = {0};
    
    lfsr_c[0] = d[7] ^ d[5] ^ d[3] ^ d[2] ^ d[1] ^ d[0] ^ c[1] ^ c[3];
    lfsr_c[1] = d[6] ^ d[4] ^ d[3] ^ d[2] ^ d[1] ^ c[0] ^ c[2];
    lfsr_c[2] = d[7] ^ d[5] ^ d[4] ^ d[3] ^ d[2] ^ c[0] ^ c[1] ^ c[3];
    lfsr_c[3] = d[7] ^ d[6] ^ d[4] ^ d[2] ^ d[1] ^ d[0] ^ c[0] ^ c[2] ^ c[3];
    
    for(i = 0; i < 4; i++) 
    {
        ret |= (lfsr_c[i]<<i);
    }
    return ret;
}


int main(void)
{
    uint8_t d = 0xb3;
    uint8_t ret = 0;
    uint8_t bytes_array[8] = {0};

    BITS_TO_BYTES_ARRAY(&d, HASH_KEY_WRITE_BITS, bytes_array);

    ret = crc_4_d8(bytes_array);

    printf("ret = 0x%x\n", ret);

    return 0;
}

编译,运行,结果和之前手动计算的一致。

[grace@localhost] ~/c/crc
$ gcc test_crc.c 
[grace@localhost] ~/c/crc
$ ./a.out        
ret = 0x4

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。

  • 分享:
评论
还没有评论
    发表评论 说点什么