1. 编程号首页

CRC校验算法_crc校验算法原理及实现

编程小号 • • 未分类

CRC校验算法_crc校验算法原理及实现一、什么是CRC校验算法最近在学网络时在以太网的数据帧的末尾有一个叫CRC校验码的东西，遂不解

一、什么是CRC校验算法
最近在学网络时在以太网的数据帧的末尾有一个叫CRC校验码的东西，遂不解。于是便一起学习一下，什么是CRC校验码。
CRC就是循环冗余校验码（Cyclic Redundancy Check），是数据通信领域常见的差错校验码，特征是信息字段和校验字段的长度可以任意的选定。

循环冗余检查（CRC）是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接受设备也执行类似的算法来保证数据传输的正确性和完整性。
二、CRC校验算法的算法的原理
CRC校验算法的原理就是：原始帧数据发送之前，在n个bit位的原始数据后面加上通过特定运算得到的K位校验序列，组成新的帧来发送给接收端。接收端会根据原始数据后的校验序列再次进行特定的运算，若正确则接受，若结果错误则丢弃。
这里写图片描述
把上面的K位校验码序列就称为：FCS
CRC校验算法原理的示图如下：
这里写图片描述
我们把特定的运算就称为异或运算。
这样看来CRC校验算法也就是把原始数据通过异或运算得到FCS，接收端根据原始数据再次运算如果相等那么就接收。那么CRC算法的核心就是如何得到FCS。

假设要发送的数据是M，M里面有K个数据，现在要计算冗余码。冗余码的计算方法如下：
1、用二进制模2运算来进行2^n*M也就是M左移了n位，也即是在M的后面加上了n个0，现在M的长度就是K+n
2、用M去除收发双方事先商定的长度为n+1的除数p，得到余数是R
3、这个R就是FCS（帧检验序列），将这个FCS序列加到M后面发出去就行了。
最后接收端对数据进行CRC校验，若余数为R就表示这个帧没有错，就接受。若R不为0表示这个帧出错就丢弃。
一般在数据传输之前，发送端与接收端会相互约定好一个除数（也是一个二进制序列，用来进行模2算法）。这个除数就是生成多项式。这个多项式的最高位和最低位必须为1。
常见的生成多项式为：
CRC8=X8+X5+X4+1（100110001）
CRC-CCITT=X16+X12+X5+1（1001000000100001）
CRC16=X16+X15+X5+1（11000000000100001）
CRC12=X12+X11+X3+X2+1（1100000001101）
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1
（100000100110000010001110110011111）
给个栗子吧：
M= 101001，p = 1101，n = 3
M是要发送的数据，p是除数，n是在M后面差错检测的n位冗余码
发送端：
M=(2^n*M)，所以M=101001000
用M除以p：
这里写图片描述
得到的余数是FCS，将其加到M的后面就是要发送的帧
M = 101001000 + FCS = 101001001

接收端：
接收到的每一帧都要进行差错检验，假设收到的101001001，p=1101，具体如下：
这里写图片描述
我们可以看到最后的余数R=0，没有出错，所以信息是被接收的。
三、CRC算法的编程实现
下面我们通过一个栗子来说明是如何实现CRC校验的，生成多项式为：100110001（简记0x31）,也就是CRC-8
计算步骤如下：
（1） 将CRC寄存器（8-bits，比生成多项式少1bit）赋初值0
（2） 在待传输信息流后面加入8个0
（3） While (数据未处理完)
（4） Begin
（5） If (CRC寄存器首位是1)
（6） reg = reg XOR 0x31
（7） CRC寄存器左移一位，读入一个新的数据于CRC寄存器的0 bit的位置。
（8） End
（9） CRC寄存器就是我们所要求的余数。
程序实现的示图：
这里写图片描述
代码展示：（代码来自参考文章的链接里面）
代码是C++实现了CRC8、CRC16和CRC32，代码参考如下：

#ifndef CRCCOMPUTE_H  
#define CRCCOMPUTE_H  

#include <stdint.h>  

template <typename TYPE> class CRC  
{  
public:  
    CRC();  
    CRC(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value);  
    void build(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value);  
    /** * Compute the CRC checksum of a binary message block. * @para message, 用来计算的数据 * @para nBytes, 数据的长度 */  
    TYPE crcCompute(char * message, unsigned int nBytes);  
    TYPE crcCompute(char * message, unsigned int nBytes, bool reinit);  
protected:  
    TYPE m_polynomial;  
    TYPE m_initial_remainder;  
    TYPE m_final_xor_value;  
    TYPE m_remainder;  
    TYPE crcTable[256];  
    int m_width;  
    int m_topbit;  
    /** * Initialize the CRC lookup table. * This table is used by crcCompute() to make CRC computation faster. */  
    void crcInit(void);  
};  

template <typename TYPE>  
CRC<TYPE>::CRC()  
{  
    m_width = 8 * sizeof(TYPE);  
    m_topbit = 1 << (m_width - 1);  
}  

template <typename TYPE>  
CRC<TYPE>::CRC(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value)  
{  
    m_width = 8 * sizeof(TYPE);  
    m_topbit = 1 << (m_width - 1);  
    m_polynomial = polynomial;  
    m_initial_remainder = init_remainder;  
    m_final_xor_value = final_xor_value;  

    crcInit();  
}  

template <typename TYPE>  
void CRC<TYPE>::build(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value)  
{  
    m_polynomial = polynomial;  
    m_initial_remainder = init_remainder;  
    m_final_xor_value = final_xor_value;  

    crcInit();  
}  

template <typename TYPE>  
TYPE CRC<TYPE>::crcCompute(char * message, unsigned int nBytes)  
{  
    unsigned int offset;  
    unsigned char byte;  
    TYPE remainder = m_initial_remainder;  
    /* Divide the message by the polynomial, a byte at a time. */  
    for( offset = 0; offset < nBytes; offset++)  
    {  
        byte = (remainder >> (m_width - 8)) ^ message[offset];  
        remainder = crcTable[byte] ^ (remainder << 8);  
    }  
    /* The final remainder is the CRC result. */  
    return (remainder ^ m_final_xor_value);  
}  

template <typename TYPE>  
TYPE CRC<TYPE>::crcCompute(char * message, unsigned int nBytes, bool reinit)  
{  
    unsigned int offset;  
    unsigned char byte;  
    if(reinit)  
    {  
        m_remainder = m_initial_remainder;  
    }  
    /* Divide the message by the polynomial, a byte at a time. */  
    for( offset = 0; offset < nBytes; offset++)  
    {  
        byte = (m_remainder >> (m_width - 8)) ^ message[offset];  
        m_remainder = crcTable[byte] ^ (m_remainder << 8);  
    }  
    /* The final remainder is the CRC result. */  
    return (m_remainder ^ m_final_xor_value);  
}  

class CRC8 : public CRC<uint8_t>  
{  
public:  
    enum CRC8_TYPE {eCRC8, eAUTOSAR, eCDMA2000, eDARC, eDVB_S2, eEBU, eAES, eGSM_A, eGSM_B, eI_CODE,  
                    eITU, eLTE, eMAXIM, eOPENSAFETY, eROHC, eSAE_J1850, eWCDMA};  
    CRC8(CRC8_TYPE type);  
    CRC8(uint8_t polynomial, uint8_t init_remainder, uint8_t final_xor_value)  
        :CRC<uint8_t>(polynomial, init_remainder, final_xor_value){}  
};  

class CRC16 : public CRC<uint16_t>  
{  
public:  
    enum CRC16_TYPE {eCCITT, eKERMIT, eCCITT_FALSE, eIBM, eARC, eLHA, eSPI_FUJITSU,  
                     eBUYPASS, eVERIFONE, eUMTS, eCDMA2000, eCMS, eDDS_110, eDECT_R,  
                     eDECT_X, eDNP, eEN_13757, eGENIBUS, eEPC, eDARC, eI_CODE, eGSM,  
                     eLJ1200, eMAXIM, eMCRF4XX, eOPENSAFETY_A, eOPENSAFETY_B, ePROFIBUS,  
                     eIEC_61158_2, eRIELLO, eT10_DIF, eTELEDISK, eTMS37157, eUSB,  
                     eCRC_A, eMODBUS, eX_25, eCRC_B, eISO_HDLC, eIBM_SDLC, eXMODEM,  
                     eZMODEM, eACORN, eLTE};  
    CRC16(CRC16_TYPE type);  
    CRC16(uint16_t polynomial, uint16_t init_remainder, uint16_t final_xor_value)  
        :CRC<uint16_t>(polynomial, init_remainder, final_xor_value){}  
};  

class CRC32 : public CRC<uint32_t>  
{  
public:  
    enum CRC32_TYPE {eADCCP, ePKZIP, eCRC32, eAAL5, eDECT_B, eB_CRC32, eBZIP2, eAUTOSAR,  
                     eCRC32C, eCRC32D, eMPEG2, ePOSIX, eCKSUM, eCRC32Q, eJAMCRC, eXFER};  
    CRC32(CRC32_TYPE type);  
};  


#endif // CRCCOMPUTE_H


#include "crcCompute.h"  

template <typename TYPE>  
void CRC<TYPE>::crcInit(void)  
{  
    TYPE remainder;  
    TYPE dividend;  
    int bit;  
    /* Perform binary long division, a bit at a time. */  
    for(dividend = 0; dividend < 256; dividend++)  
    {  
        /* Initialize the remainder. */  
        remainder = dividend << (m_width - 8);  
        /* Shift and XOR with the polynomial. */  
        for(bit = 0; bit < 8; bit++)  
        {  
            /* Try to divide the current data bit. */  
            if(remainder & m_topbit)  
            {  
                remainder = (remainder << 1) ^ m_polynomial;  
            }  
            else  
            {  
                remainder = remainder << 1;  
            }  
        }  
        /* Save the result in the table. */  
        crcTable[dividend] = remainder;  
    }  
}  

CRC8::CRC8(CRC8_TYPE type)  
{  
    switch (type)  
    {  
    case eCRC8:  
        m_polynomial = 0x07; //http://reveng.sourceforge.net/crc-catalogue/all.htm 
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    case eAUTOSAR:  
        m_polynomial = 0x2f;  
        m_initial_remainder = 0xff;  
        m_final_xor_value = 0xff;  
        break;  
    case eCDMA2000:  
        m_polynomial = 0x9b;  
        m_initial_remainder = 0xFF;  
        m_final_xor_value = 0x00;  
        break;  
    case eDARC:  
        m_polynomial = 0x39;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    case eDVB_S2:  
        m_polynomial = 0xd5;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    case eEBU:  
    case eAES:  
        m_polynomial = 0x1d;  
        m_initial_remainder = 0xFF;  
        m_final_xor_value = 0x00;  
        break;  
    case eGSM_A:  
        m_polynomial = 0x1d;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    case eGSM_B:  
        m_polynomial = 0x49;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0xFF;  
        break;  
    case eI_CODE:  
        m_polynomial = 0x1d;  
        m_initial_remainder = 0xFD;  
        m_final_xor_value = 0x00;  
        break;  
    case eITU:  
        m_polynomial = 0x07;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x55;  
        break;  
    case eLTE:  
        m_polynomial = 0x9b;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    case eMAXIM:  
        m_polynomial = 0x31;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    case eOPENSAFETY:  
        m_polynomial = 0x2f;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    case eROHC:  
        m_polynomial = 0x07;  
        m_initial_remainder = 0xff;  
        m_final_xor_value = 0x00;  
        break;  
    case eSAE_J1850:  
        m_polynomial = 0x1d;  
        m_initial_remainder = 0xff;  
        m_final_xor_value = 0xff;  
        break;  
    case eWCDMA:  
        m_polynomial = 0x9b;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    default:  
        m_polynomial = 0x07;  
        m_initial_remainder = 0x00;  
        m_final_xor_value = 0x00;  
        break;  
    }  
    crcInit();  

}  

CRC16::CRC16(CRC16_TYPE type)  
{  
    switch (type)  
    {  
    case eCCITT_FALSE:  
    case eMCRF4XX:  
        m_polynomial = 0x1021;  
        m_initial_remainder = 0xFFFF;  
        m_final_xor_value = 0x0000;  
        break;  
    case eIBM:  
    case eARC:  
    case eLHA:  
    case eBUYPASS:  
    case eVERIFONE:  
    case eUMTS:  
        m_polynomial = 0x8005;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    case eSPI_FUJITSU:  
        m_polynomial = 0x1021;  
        m_initial_remainder = 0x1d0f;  
        m_final_xor_value = 0x0000;  
        break;  
    case eCCITT:  
    case eKERMIT:  
    case eXMODEM:  
    case eZMODEM:  
    case eACORN:  
    case eLTE:  
        m_polynomial = 0x1021;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    case eCDMA2000:  
        m_polynomial = 0xc867;  
        m_initial_remainder = 0xffff;  
        m_final_xor_value = 0x0000;  
        break;  
    case eCMS:  
    case eMODBUS:  
        m_polynomial = 0x8005;  
        m_initial_remainder = 0xffff;  
        m_final_xor_value = 0x0000;  
        break;  
    case eDDS_110:  
        m_polynomial = 0x8005;  
        m_initial_remainder = 0x800d;  
        m_final_xor_value = 0x0000;  
        break;  
    case eDECT_R:  
        m_polynomial = 0x0589;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0001;  
        break;  
    case eDECT_X:  
        m_polynomial = 0x0589;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    case eDNP:  
    case eEN_13757:  
        m_polynomial = 0x3d65;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0xffff;  
        break;  
    case eGENIBUS:  
    case eEPC:  
    case eDARC:  
    case eI_CODE:  
    case eX_25:  
    case eCRC_B:  
    case eISO_HDLC:  
    case eIBM_SDLC:  
        m_polynomial = 0x1021;  
        m_initial_remainder = 0xffff;  
        m_final_xor_value = 0xffff;  
        break;  
    case eGSM:  
        m_polynomial = 0x1021;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0xffff;  
        break;  
    case eLJ1200:  
        m_polynomial = 0x6f63;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    case eMAXIM:  
        m_polynomial = 0x8005;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0xffff;  
        break;  
    case eOPENSAFETY_A:  
        m_polynomial = 0x5935;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    case eOPENSAFETY_B:  
        m_polynomial = 0x755b;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    case ePROFIBUS:  
    case eIEC_61158_2:  
        m_polynomial = 0x1dcf;  
        m_initial_remainder = 0xffff;  
        m_final_xor_value = 0xffff;  
        break;  
    case eRIELLO:  
        m_polynomial = 0x1021;  
        m_initial_remainder = 0xb2aa;  
        m_final_xor_value = 0x0000;  
        break;  
    case eT10_DIF:  
        m_polynomial = 0x8bb7;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    case eTELEDISK:  
        m_polynomial = 0xa097;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    case eTMS37157:  
        m_polynomial = 0x1021;  
        m_initial_remainder = 0x89ec;  
        m_final_xor_value = 0x0000;  
        break;  
    case eUSB:  
        m_polynomial = 0x8005;  
        m_initial_remainder = 0xffff;  
        m_final_xor_value = 0xffff;  
        break;  
    case eCRC_A:  
        m_polynomial = 0x1021;  
        m_initial_remainder = 0xc6c6;  
        m_final_xor_value = 0x0000;  
        break;  
    default:  
        m_polynomial = 0x8005;  
        m_initial_remainder = 0x0000;  
        m_final_xor_value = 0x0000;  
        break;  
    }  
    crcInit();  
}  


CRC32::CRC32(CRC32_TYPE type)  
{  
    switch (type)  
    {  
    case eADCCP:  
    case ePKZIP:  
    case eCRC32:  
    case eBZIP2:  
    case eAAL5:  
    case eDECT_B:  
    case eB_CRC32:  
        m_polynomial = 0x04c11db7;  
        m_initial_remainder = 0xFFFFFFFF;  
        m_final_xor_value = 0xFFFFFFFF;  
        break;  
    case eAUTOSAR:  
        m_polynomial = 0xf4acfb13;  
        m_initial_remainder = 0xFFFFFFFF;  
        m_final_xor_value = 0xFFFFFFFF;  
        break;  
    case eCRC32C:  
        m_polynomial = 0x1edc6f41;  
        m_initial_remainder = 0xFFFFFFFF;  
        m_final_xor_value = 0xFFFFFFFF;  
        break;  
    case eCRC32D:  
        m_polynomial = 0xa833982b;  
        m_initial_remainder = 0xFFFFFFFF;  
        m_final_xor_value = 0xFFFFFFFF;  
        break;  
    case eMPEG2:  
    case eJAMCRC:  
        m_polynomial = 0x04c11db7;  
        m_initial_remainder = 0xFFFFFFFF;  
        m_final_xor_value = 0x00000000;  
        break;  
    case ePOSIX:  
    case eCKSUM:  
        m_polynomial = 0x04c11db7;  
        m_initial_remainder = 0x00000000;  
        m_final_xor_value = 0xFFFFFFFF;  
        break;  
    case eCRC32Q:  
        m_polynomial = 0x814141ab;  
        m_initial_remainder = 0x00000000;  
        m_final_xor_value = 0x00000000;  
        break;  
    case eXFER:  
        m_polynomial = 0x000000af;  
        m_initial_remainder = 0x00000000;  
        m_final_xor_value = 0x00000000;  
        break;  
    default:  
        m_polynomial = 0x04C11DB7;  
        m_initial_remainder = 0xFFFFFFFF;  
        m_final_xor_value = 0xFFFFFFFF;  
        break;  
    }  
    crcInit();  
}  


#include <iostream> 
#include <stdio.h> 
#include "crcCompute.h" 

using namespace std;  

int main(int argc, char *argv[])  
{  

    CRC16 crc16(CRC16::eCCITT_FALSE);  
    char data1[] = {
  
  '1', '2', '3', '4', '5', '6', '7', '8', '9'};  
    char data2[] = {
  
  '5', '6', '7', '8', '9'};  
    unsigned short c1, c2;  
    c1 = crc16.crcCompute(data1, 9);  
    c2 = crc16.crcCompute(data1, 4, true);  
    c2 = crc16.crcCompute(data2, 5, false);  


    printf("%04x\n", c1);  
    printf("%04x\n", c2);  

    return 0;  
}


参考文章：
CRC校验算法

今天的文章CRC校验算法_crc校验算法原理及实现分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/69213.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注