CRC字节算法

在研究CRC字节算法的时候参考了网上的一些博客,但是感觉写的不够透彻,有的也出现一些错误。本文的目的是详细讲解CRC字节算法。

有关CRC算法的介绍请参见:

参考链接一:最通俗的CRC校验原理剖析

参考链接二:CRC查找表法推导及代码实现比较

在此,强调一下CRC算法中两个重要的点:

1、 原始序列要左移n位,再除以生成多项式;

2、生成多项式所包含的比特数比CRC校验比特数多1。

以上两点注意事项可在最通俗的CRC校验原理剖析中的例子观察。

在证明之前,先复习一下取余运算的计算法则:

  1. (a+b)%p=(a%p+b%p)%p

  2. (a*b)%p=(a%p*b%p)%p

  3. [(a+b)*c]%p=[(a+b)%p*c%p]%p=[(a%p+b%p)%p*c%p]%p=[(a%p+b%p)*c]%p

  4. (a%p+b%p+c%p+…)%p=(a+b+c+…)%p=[(a+b)%p+b%p+c%p+…]%p

提示:取余运算符和乘除运算符的优先级相同。

接下来,将详细讲解CRC24的字节算法。

假设有一组比特数据流,将它们每8个分为一组,按照字节的方式表示为

表示成数学表达式为

现在要产生24位CRC校验比特,假设生成多项式为G25(共有25个比特,比校验比特多一个),那么生成的24位CRC校验比较可表示为

乘到括号里面,得到

使用取余公式1可得到下式

之后的公式的关注点都是红色部分,因为黑色部分没有发生变化。对上式的红色部分使用取余公式2,可得到下式

观察上式红色部分中的,可以发现它表示的24位CRC校验比特,记为,那么上式可写为

又因为包含24比特,那么必然有,因此,上式可化为

使用取余公式2可得到

使用取余公式4可得到

提出公因式2^(n-1)可得到

写成高8位和低16位的形式,可得到下式

去掉最内层括号并提取公因式2^24可得到

因为第一项是低16比特左移8位,只有24个有效比特,因此必然有,因此上式又可写成

经过上边的化简,可将第n个字节(8比特)删除,并将第n-1个字节修订为

因此,每经过一次迭代,就能删掉一个字节并修订下一个字节,经过n+1次迭代可将n+1个字节的数据全部计算完毕并得出最后的24位校验码。另外,上式中的第二项可通过查表的方法快速得到,大大提高了计算效率。

 

计算表项的MATLAB程序:

crc24Main.m

%--------------------------------------------------------------------------
% Function    : 本文档的功能生成CRC24A字节算法表项,调用了crcTableG_24函数,
%               来计算每种可能的24位CRC校验码
% Description : Main program to caculate CRC24A
% Input       : None
% Output      : None
% Version     : 1.0
% Author      : shgao, chengkai
% History     : When         Who                 What
%             17/05/31     chengkai     增加另外一种CRC24多项式
% Copyright (C) 2017, shgao, chengkai. All Rights Reserved.                                          
%--------------------------------------------------------------------------
clc,clear
close all
CRC24_polynomial = 'CRC24A'; % CRC24A CRC24B

% 因为要生成CRC字节算法的表项,一个字节是8个比特,共有
% 2^8 = 256种可能,因此要计算每种可能对应的CRC校验码
% 又因为我们要使用CRC24A的校验码算法
outData=zeros(256,24);
%============生成对应CRC项==================%
for i = 0:255 % 一定要注意,是0:255,不是1:256
    dataInChar = dec2bin(i); % 十进制转二进制,结果为char数组
    dataIn = dataInChar - '0'; % 将字符转化成数字
    [flag, outData(i+1,:)]=crcTableG_24(dataIn, CRC24_polynomial);
    if(flag == 0)
        break;
    end
end
%============格式转换======================%
if(flag == 1)
    fp=fopen('CRCoutTable.txt','wt'); 
    crcStr = num2str(outData);
    crcStr( find(crcStr == ' ')) = []; 
    crcStr = reshape(crcStr, 256, 24);
    crcDec = bin2dec(crcStr);
    crcHex = dec2hex(crcDec, 6);
    for i=1:1:256
        fprintf(fp,'0x%s, ',crcHex(i,:));
        if(rem(i, 8) == 0)
            fprintf(fp,'\n');
        end
    end
    fclose(fp);
end

crcTableG_24.m

%--------------------------------------------------------------------------
% Function    : 计算输入8比特二进制的CRC24A
% Description : A function to caculate CRC24A for each 8 bits info
% Input       : d - 8 bits info
%               CRC24_polynomial - Choose CRC24 type
% Output      : r - 24 bits CRC24A
% Version     : 1.0
% Author      : shgao, chengkai
% Reference   : 3GPP TS 36.212 v10.8.0 (2013-6) pp.
% History     : When         Who                 What
%             17/05/31     chengkai     增加另外一种CRC24多项式
% Copyright (C) 2017, shgao, chengkai. All Rights Reserved.                                          
%--------------------------------------------------------------------------

% CRC24A 生成多项式 shgao
% 多项式: G(X)=X^24+X^23+X^18+X^17+X^14+X^11+X^10+X^7+X^6+X^5+X^4+X^3+X+1 

function [flag, r] = crcTableG_24(d, CRC24_polynomial)
    %d = [0 0 1 0 0 1 0 0];
    flag = 1;
    L   = size(d,2);
    da  = [d zeros(1,24)]; % 添了24个零
    if(strcmp(CRC24_polynomial, 'CRC24A'))
        for i=1:L
          if da(i)
            % 注意:在数据流中,高位在左,低位在右
            % 如:1   0   1   1   0   1
            %    高位                低位
            % 修改if中的这些项目即可达到修改生成多项式的目的(注意同时修改长度24)
            % 相当于某个数对1异或,即取反
            da(i   ) = ~da(i   ); % X^24,对应最高位
            da(i+1 ) = ~da(i+ 1);
            da(i+6 ) = ~da(i+ 6);
            da(i+7 ) = ~da(i+ 7);
            da(i+10) = ~da(i+10);
            da(i+13) = ~da(i+13);
            da(i+14) = ~da(i+14);
            da(i+17) = ~da(i+17);
            da(i+18) = ~da(i+18);
            da(i+19) = ~da(i+19);
            da(i+20) = ~da(i+20);
            da(i+21) = ~da(i+21);
            da(i+23) = ~da(i+23);
            da(i+24) = ~da(i+24); % X^0 = 1,对应最低位
          end
        end
    elseif(strcmp(CRC24_polynomial, 'CRC24B'))
        for i=1:L
          if da(i)
            % 注意:在数据流中,高位在左,低位在右
            % 如:1   0   1   1   0   1
            %    高位                低位
            % 修改if中的这些项目即可达到修改生成多项式的目的(注意同时修改长度24)
            % 相当于某个数对1异或,即取反
            da(i   ) = ~da(i   ); % X^24,对应最高位
            da(i+1 ) = ~da(i+ 1);
            da(i+18) = ~da(i+18);
            da(i+19) = ~da(i+19);
            da(i+23) = ~da(i+23);
            da(i+24) = ~da(i+24); % X^0 = 1,对应最低位
          end
        end
    else
        fprintf('CRC24_polynomial取值有误,请重新选取。\n');
        flag = 0;
    end
    if(flag == 1)
        r = da(L+[1:24]); % 取出24位CRC校验比特
    else
        r = 0;
    end
end

 

计算一组信息比特的CRC24A校验码的C程序:

/********************************************************************************************
Copyright (C), 2009, Starpoint Comm. Software Co., Ltd.
Function name: Dl_Crc24A
Author: Wangnan
Version: 0.0
Date: 2009.9.9
Description:
 1、函数调用形式 :Dl_Crc24A(UCHAR *p_ucInputData,UINT uiByteLen,)
 2、入口参数说明:
 UCHAR * p_ucInputData :待编码的数据,整字节数
 UINT uiByteLen :输入数据的长度
 3、功能: 计算输入数据的CRC(24A)码,并返回所得CRC码
 所用多项式为G(X)=X^24+X^23+X^18+X^17+X^14+X^11+X^10+X^7+X^6+X^5+X^4+X^3+X+1
 4、返回值 :返回值中的低24位为计算所得CRC(24A)码,高8位为0
 5、可以开-o2优化功能
***********************************************************************************************/

unsigned int total_puiCRCTbl24A[256] ={
 0x000000, 0x864cfb, 0x8ad50d, 0x0c99f6, 0x93e6e1, 0x15aa1a, 0x1933ec, 0x9f7f17,
 0xa18139, 0x27cdc2, 0x2b5434, 0xad18cf, 0x3267d8, 0xb42b23, 0xb8b2d5, 0x3efe2e,
 0xc54e89, 0x430272, 0x4f9b84, 0xc9d77f, 0x56a868, 0xd0e493, 0xdc7d65, 0x5a319e,
 0x64cfb0, 0xe2834b, 0xee1abd, 0x685646, 0xf72951, 0x7165aa, 0x7dfc5c, 0xfbb0a7,
 0x0cd1e9, 0x8a9d12, 0x8604e4, 0x00481f, 0x9f3708, 0x197bf3, 0x15e205, 0x93aefe,
 0xad50d0, 0x2b1c2b, 0x2785dd, 0xa1c926, 0x3eb631, 0xb8faca, 0xb4633c, 0x322fc7,
 0xc99f60, 0x4fd39b, 0x434a6d, 0xc50696, 0x5a7981, 0xdc357a, 0xd0ac8c, 0x56e077,
 0x681e59, 0xee52a2, 0xe2cb54, 0x6487af, 0xfbf8b8, 0x7db443, 0x712db5, 0xf7614e,
 0x19a3d2, 0x9fef29, 0x9376df, 0x153a24, 0x8a4533, 0x0c09c8, 0x00903e, 0x86dcc5,
 0xb822eb, 0x3e6e10, 0x32f7e6, 0xb4bb1d, 0x2bc40a, 0xad88f1, 0xa11107, 0x275dfc,
 0xdced5b, 0x5aa1a0, 0x563856, 0xd074ad, 0x4f0bba, 0xc94741, 0xc5deb7, 0x43924c,
 0x7d6c62, 0xfb2099, 0xf7b96f, 0x71f594, 0xee8a83, 0x68c678, 0x645f8e, 0xe21375,
 0x15723b, 0x933ec0, 0x9fa736, 0x19ebcd, 0x8694da, 0x00d821, 0x0c41d7, 0x8a0d2c,
 0xb4f302, 0x32bff9, 0x3e260f, 0xb86af4, 0x2715e3, 0xa15918, 0xadc0ee, 0x2b8c15,
 0xd03cb2, 0x567049, 0x5ae9bf, 0xdca544, 0x43da53, 0xc596a8, 0xc90f5e, 0x4f43a5,
 0x71bd8b, 0xf7f170, 0xfb6886, 0x7d247d, 0xe25b6a, 0x641791, 0x688e67, 0xeec29c,
 0x3347a4, 0xb50b5f, 0xb992a9, 0x3fde52, 0xa0a145, 0x26edbe, 0x2a7448, 0xac38b3,
 0x92c69d, 0x148a66, 0x181390, 0x9e5f6b, 0x01207c, 0x876c87, 0x8bf571, 0x0db98a,
 0xf6092d, 0x7045d6, 0x7cdc20, 0xfa90db, 0x65efcc, 0xe3a337, 0xef3ac1, 0x69763a,
 0x578814, 0xd1c4ef, 0xdd5d19, 0x5b11e2, 0xc46ef5, 0x42220e, 0x4ebbf8, 0xc8f703,
 0x3f964d, 0xb9dab6, 0xb54340, 0x330fbb, 0xac70ac, 0x2a3c57, 0x26a5a1, 0xa0e95a,
 0x9e1774, 0x185b8f, 0x14c279, 0x928e82, 0x0df195, 0x8bbd6e, 0x872498, 0x016863,
 0xfad8c4, 0x7c943f, 0x700dc9, 0xf64132, 0x693e25, 0xef72de, 0xe3eb28, 0x65a7d3,
 0x5b59fd, 0xdd1506, 0xd18cf0, 0x57c00b, 0xc8bf1c, 0x4ef3e7, 0x426a11, 0xc426ea,
 0x2ae476, 0xaca88d, 0xa0317b, 0x267d80, 0xb90297, 0x3f4e6c, 0x33d79a, 0xb59b61,
 0x8b654f, 0x0d29b4, 0x01b042, 0x87fcb9, 0x1883ae, 0x9ecf55, 0x9256a3, 0x141a58,
 0xefaaff, 0x69e604, 0x657ff2, 0xe33309, 0x7c4c1e, 0xfa00e5, 0xf69913, 0x70d5e8,
 0x4e2bc6, 0xc8673d, 0xc4fecb, 0x42b230, 0xddcd27, 0x5b81dc, 0x57182a, 0xd154d1,
 0x26359f, 0xa07964, 0xace092, 0x2aac69, 0xb5d37e, 0x339f85, 0x3f0673, 0xb94a88,
 0x87b4a6, 0x01f85d, 0x0d61ab, 0x8b2d50, 0x145247, 0x921ebc, 0x9e874a, 0x18cbb1,
 0xe37b16, 0x6537ed, 0x69ae1b, 0xefe2e0, 0x709df7, 0xf6d10c, 0xfa48fa, 0x7c0401,
 0x42fa2f, 0xc4b6d4, 0xc82f22, 0x4e63d9, 0xd11cce, 0x575035, 0x5bc9c3, 0xdd8538
};

unsigned int Total_Dl_Crc24A(UCHAR * pucInputData,int uiByteLen){
	unsigned int  total_t_uiCrc; // 保存每字节计算所得的中间变量以及最后所得CRC码
	total_t_uiCrc = 0;
	while(uiByteLen--!=0) // 循环直到源数据都已计算,每次循环计算1字节{
	  	//根据公式计算CRC
		total_t_uiCrc =(total_t_uiCrc << 8) ^ total_puiCRCTbl24A[((unsigned char)(total_t_uiCrc>>16) ^ *pucInputData)];
 		pucInputData++;// 指向下一字节
	}
    return total_t_uiCrc;
}

 

发表评论

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

4 + 9 =

− 1 = 3