T O P

[资源分享]     CRC基础原理详解

  • By - 楼主

  • 2019-09-19 15:25:05
  • 一.生成多项式

    以比特流 11001001为例,其生成多项式为:
    G(x) = x^7 + x^6 + x^3 + 1
    至于为何使用指数的形式,是因为生成多项式引用了多项式运算,x^n在n不同时不可以合并,这样可以保证一个多项式与比特流的关系是一一对应的,不同比特位不会合并。
    CRC校验使用的生成多项式的最高位与最低位必须为1,由于最高位一定为1,所以CRC校验使用的多项式的位宽 = 总比特数 - 1。
    例如,G(x) = x^7 + x^6 + x^3 + 1的多项式位宽 = 8 - 1 = 7,省去最高位,其余位简记为
    7’b1001001 ( 0x49 ), 该CRC运算称为CRC-7。

    二.CRC运算

    1.基本介绍

    CRC校验,就是在一串比特流之后添加一定比特数的CRC校验位(冗余信息),使得整个比特流除以某个特定的生成多项式,就可得到余数为0。
    如果余数不为0,则说明数据传输过程中有错误发生。

    在CRC运算空间中,加减法使用“按位异或”运算(即模2加),乘数法可以由多步加减法(按位异或)实现,以下异或运算符均用⊕表示。

    2.运算实例

    例如: 原始比特流:101
    生成多项式:10011 (保留最高位)(去掉最高位后为4bits的0011,即0x3)
    CRC-4
    运算流程如下:

    为101后面补4个0,之后除10011

    在这里插入图片描述

    算出校验值后(此例中为4位),添加至比特流101尾部,得到
    1011111,发送方将该比特流发送出去,接收方接收到后,如果除以10011后的余数为0,则接收方判定接收到的比特流无错误。

    三.CRC算法解析(零填充)

    1.C代码

    以CRC运算中的例子(需要在比特流末尾填充4个0)为例,C代码如下:

    u8 fun( bool bitArray[], int bitArrayNum )//bitArray[]已经在末尾添加4个0
    {
    	u8 crcRes = 0;//初始化为0,有效比特空间设为4比特
    	
     	int i;
    	for ( i = 0; i < bitArrayNum; i ++ )
    	{
    		u8 curBit = bitArray[ i ] ;
    		u8 msb = (crcRes & 0x8)>>3;//取出最高位crcRes[3]
    
    		crcRes  = (crcRes << 1)| curBit ; //左移1位( crcRes[3:0] = { crcRes[2:0], curBit  }),
                                               //低比特进入最低位
    		if (  msb  )//最高位为1
    		{
    			crcRes  = crcRes  ^ 0x3;//0x3为生成多项式去掉最高位,4比特
    		}
    	}
    }
    

    2.流程图(可用FPGA实现)

    在这里插入图片描述
    图中的4位reg 对应crcRes 的4位存储空间。

    3.原理分析

    接下来进行代码详细原理分析:
    一开始,crcRes [3:0] 的最高位为0,因此,只需左移。
    经过4次左移运算后,输入比特流第一位的‘1’抵达最高位,
    此时,crcRes [3:0] = 1010。
    当最高位为1时,被减数10100需要减去(异或)10011,由于最高位相减为0,所以可以无视它,因此,在获取crcRes [3:0] = 1010中的最高位后,将crcRes 左移,并添加新比特0。这时crcRes =0100,恰好为被减数的低4位。因此10100⊕10011只需要低4位进行异或运算(0100⊕0011),就可以得到新的CRC运算结果(0111),这就是为什么经常将生成多项式最高位省略的原因。
    之后如果再碰到最高位为1的情况,以此类推。
    如果又碰到最高位为0的情况,只需要左移crcRes ,添加新比特进入低比特。

    至此,算法已剖析完毕。

    四.CRC算法解析(无需零填充)

    我在研究SD卡的SDIO接口时,接触到CRC-7与CRC-16。
    由于查到的原理图的算法不需要在比特流后面进行0填充,所以,我对这种不需0填充的
    CRC算法进行研究:

    1.C代码

    u8 fun( bool bitArray[], int bitArrayNum )//bitArray[]无需填充0
    {
        u8 crcRes = 0;//初始化为0,有限空间设为4比特
        int i;
        for ( i = 0; i < bitArrayNum; i ++ )
        {
            u8 curBit = bitArray[ i ] ;
            u8 msb = (crcRes & 0x8)>>3;//取出最高位crcRes [3]
            
            crcRes  = (crcRes   << 1); //左移1位( crcRes[3:0] = { crcRes[2:0], 1'b0 } )
            
            if (  msb ^ curBit )//最高位⊕新输入比特 == 1
            {
                crcRes  = crcRes ^ 0x3;//0x3为生成多项式去掉最高位,4比特   
            }
        }
     }
    

    2.流程图(可用FPGA实现)

    在这里插入图片描述
    图中的4位reg 对应crcRes 的4位存储空间。

    3.原理证明(数学归纳法)

    (1) 起点:(n=0)

    当没有数据需要检验时(0个比特),为了使余数为0,校验位必定全为0。

    (2) n个比特 => n+1个比特

    设已经有n个比特(XXXXXX)(n>=0)已经检验,CRC检验位为4’bABCD。
    因此,XXXXXXABCD必定可以整除10011,
    用 XXXXXXABCD 乘多项式 10(x^1 + x^0 = x),
    得到的 XXXXXXABCD0 也可以被 10011 整除,
    此时,将XXXXXXABCD0 ⊕ 10011 后的结果仍然可以整除10011。
    在 XXXXXXABCD0 中,新比特(第n+1比特)位置与A比特位相同,
    为此,我们只需讨论不同的A与加不加10011会在原A比特位置产生新的0还是1

    A = 0 ⊕10011 新比特为1
    A = 0 ⊕00000 新比特为0
    A = 1 ⊕10011 新比特为0
    A = 1 ⊕00000 新比特为1

    归纳可得,

    新比特 ⊕ A == 1 (n+1)个比特的CRC校验值 = “ABCD0⊕ 10011” 的后4位
    新比特 ⊕ A == 0 (n+1)个比特的CRC校验值 = “ABCD0⊕ 00000” 的后4位

    其中,A为上一步计算得到的n个比特的CRC校验值的最高位。

    又如之前带0填充CRC校验的算法,该无需0填充的CRC算法,利用最高位判断完条件后舍弃最高位,只需生成多项式的后4位参与异或运算。

    因此,第n步的CRC校验值左移1位,
    之后根据newBitIn ⊕ A的值进行选择。
    当 newBitIn ⊕ A == 1时,BCD0 与 4’b0011(0x3) 进行异或运算,就可得到第n+1步的CRC校验值;否则,BCD0 就是第n+1步的CRC校验值。

    五.其他

    1.总结

    以上就是本人最近研究CRC基础的心得。共讨论了两种串行CRC算法的原理。
    从填充0到不填充0的算法改进,我认为是质的飞越,因为后者可以根据当前的CRC直接算出多一个比特的CRC,不必重新进行0填充,并且计算周期更短。
    不填0的CRC结构学名为LFSR(线性反馈移位寄存器),运行效率很高,同时继承填0算法中节省reg空间资源的优点(本例中,不需要5个比特的reg,只需要4个比特的reg)。

    希望大家通过我的文章,能够深入理解CRC算法的真谛。把握原理后就可以轻松的应对其他各式各样的生成多项式,也能够独立的画出流程图。

    2.快速查表法

    关于查表法计算CRC,大家可参考其他博主的文章,本文章只提供一个依据:
    n个比特的CRC可以直接算出加入新比特后,(n+1)比特的CRC,
    因此,用n个比特的CRC也可以算出(n+8)个比特的CRC,此时将新的8比特制成查找表,就可以进行快速CRC算法。

    3.串行CRC应用场合

    并非串行的CRC计算一定不好。首先,某些偏底层硬件的场合,比如SD卡读写的CRC校验,数据以串行方式传输,所以不需要非常快的速度,可以来一个比特算一次CRC。其次,使用串行方式可以节省存储空间,还可节省FPGA的逻辑资源,结构简单。

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册