`
freesoftman
  • 浏览: 319765 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

探究CRC32算法实现原理

阅读更多

该文章来自于http://www.cppblog.com/kevinlynx/archive/2008/04/01/45952.aspx

Author : Kevin Lynx
email  : zmhn320@163.com

 

什么是CRC:CRC的英文全称为Cyclic Redundancy Check(Code),中文名称为循环冗余校验(码)。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制

-------------------

以下是原文:

What's CRC ?

简而言之,CRC是一个数值。该数值被用于校验数据的正确性。CRC数值简单地说就是通过让你需要做
处理的数据除以一个常数而得到的余数。当你得到这个数值后你可以将这个数值附加到你的数据后,
当数据被传送到其他地方后,取出原始数据(可能在传送过程中被破坏)与附加的CRC数值,然后将这里
的原始数据除以之前那个常数(约定好的)然后得到新的CRC值。比较两个CRC值是否相等即可确认你的
数据是否在传送过程中出现错误。

那么,如何让你的数据除以一个常数?方法是对你的数据进行必要的编码处理,逐字节处理成数字。
那么这个常数是什么?你不必关注它是什么,也不需要关注它是如何获得的。当你真的要动手写一个
CRC的实现算法时,我可以告诉你,CRC的理论学家会告诉你。不同长度的常数对应着不同的CRC实现算法。
当这个常数为32位时,也就是这里所说的CRC32。

以上内容你不必全部理解,因为你需要查阅其他资料来获取CRC完整的理论介绍。

The mathematics behind CRC ?

很多教科书会把CRC与多项式关联起来。这里的多项式指的是系数为0或1的式子,例如:
a0 + a1*x + a2*x^2 + ... + an*x^n。其中a0, a1, ..., an要么为0要么为1。我们并不关注x取什么值。
(如果你要关注,你可以简单地认为x为2) 这里把a0, a1, ..., an的值取出来排列起来,就可以表示比特
流。例如 1 + x + x^3所表示的比特流就为:1101。部分资料会将这个顺序颠倒,这个很正常。

什么是生成多项式?

所谓的生成多项式,就是上面我所说的常数。注意,在这里,一个多项式就表示了一个比特流,也就是一堆
1、0,组合起来最终就是一个数值。例如CRC32算法中,这个生成多项式为:
c(x) = 1 + x + x^2 + x^4 + x^5 + x^7 + x^8 + x^10 + x^11 + x^12 + x^16 + x^22 + x^23 + x^26 + x^32。
其对应的数字就为:11101101101110001000001100100000(x^32在实际计算时隐含给出,因此这里没有包含它
的系数),也就是0xEDB88320(多项式对应的数字可能颠倒,颠倒后得到的是0x04C11DB7,其实也是正确的)。

由此可以看出,CRC值也可以看成我们的数据除以一个生成多项式而得到的余数。

如何做这个除法?

套用大部分教科书给出的计算方法,因为任何数据都可以被处理成纯数字,因此,在某种程度上说,我们可以
直接开始这个除法。尽管事实上这并不是标准的除法。例如,我们的数据为1101011011(方便起见我直接给二进制
表示了,从这里也可以看出,CRC是按bit进行计算的),给定的生成多项式(对应的值)为10011。通常的教科书
会告诉我们在进行这个除法前,会把我们的数据左移几位(生成多项式位数-1位),从而可以容纳将来计算得到
的CRC值(我上面所说的将CRC值附加到原始数据后)。但是为什么要这样做?我也不知道。(不知道的东西不能含糊
而过)那么,除法就为:
            1100001010
       _______________
10011 ) 11010110110000 附加了几个零的新数据
        10011......... 这里的减法(希望你不至于忘掉小学算术)是一个异或操作
        -----.........
         10011........
         10011........
         -----........
          00001....... 逐bit计算
          00000.......
          -----.......
           00010......
           00000......
           -----......
            00101.....
            00000.....
            -----.....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = 这个余数也就是所谓的CRC值,通常又被称为校验值。

希望进行到这里,你可以获取更多关于CRC的感性认识。而我们所要做的,也就是实现一个CRC的计算算法。
说白了,就是提供一个程序,给定一段数据,以及一个生成多项式(对于CRC32算法而言该值固定),然后
计算得出上面的1110余数。

The simplest algorithm.

最简单的实现算法,是一种模拟算法。我们模拟上面的除法过程,遵从网上一份比较全面的资料,我们设定
一个变量register。我们逐bit地将我们的数据放到register中。然后判断register最高位是否为1,如果是
则与生成多项式异或操作,否则继续处理。这个过程简单地模拟了上述除法过程:

 

/**////
/// The simplest CRC implement algorithm.
///

/**//*
   Load the register with zero bits.
   Augment the message by appending W zero bits to the end of it.
   While (more message bits)
      Begin
      Shift the register left by one bit, reading the next bit of the
         augmented message into register bit position 0.
      If (a 1 bit popped out of the register during step 3)
         Register = Register XOR Poly.
      End
   The register now contains the remainder.
*/


#include 
<stdio.h>

#define POLY 0x13

int main()
{
 
/**//// the data 
 unsigned short data = 0x035b;
 
/**//// load the register with zero bits
 unsigned short regi = 0x0000;
 
/**//// augment the data by appending W(4) zero bits to the end of it.
 data <<= 4;

 
/**//// we do it bit after bit
 forint cur_bit = 15; cur_bit >= 0-- cur_bit )
 
{
  
/**//// test the highest bit which will be poped later.
  
/// in fact, the 5th bit from right is the hightest bit here

  if( ( ( regi >> 4 ) & 0x0001 ) == 0x1 )
  
{
   regi 
= regi ^ POLY;
  }

  
/**//// shift the register
  regi <<= 1;
  
/**//// reading the next bit of the augmented data
  unsigned short tmp = ( data >> cur_bit ) & 0x0001;
  regi 
|= tmp;

 }


 
/**//// and now, register contains the remainder which is also called CRC value.

 
return 0;
}



better algorithm ?

很多时候这种让人容易理解的算法都不会被实际用到。这种逐bit操作的算法实在很慢。你可能知道
一般的CRC32算法都是一种基于表(table-driven)的算法。但是你可能不知道这个表是如何来的。

一种改善这种bit after bit的方法就是将这个bit扩大,例如典型的做法就是换成byte。这里我要详细地叙述下
上面那种算法的过程:

我们每次会先检查register的最高位是否为1,如果为1,则将生成多项式(所谓的Poly)与register进行异或操作。
然后,将register左移一位,也就舍弃了最高位。然后将我们的数据拿一bit出来放到register的最低位。

也就是说,register中的某一位的值会决定后面几位的值。如果将register最高字节每一bit编码为:
t7 t6 t5 t4 t3 t2 t1 t0。那么,t7会决定t6-t0的值(如果为1),t6会决定t5-t0的值,依次类推。但是,无论谁
决定谁的值,当上面那个算法迭代一个字节后(8bits),t7-t0都会被丢弃(whatever you do)。唯一留下来的东西,
就是对这个字节以后字节的影响。

那么,如果我们可以直接获取这个影响,我们就可以byte after byte地处理,而不是bit after bit。如何获取这个
影响呢?这个影响又是什么呢?这个影响就对应着我们的table-driven CRC算法中的表元素!

但是,为什么我们逐bit进行计算的过程为什么可以简化为一步操作?事实上,我们没有简化这个操作。一种用于教学
的算法,是实时地计算这个影响值:

 

/**////
/// The table-driven CRC implement algorithm part 1.
///

/**//*
  While (augmented message is not exhausted)
      Begin
      Examine the top byte of the register
      Calculate the control byte from the top byte of the register
      Sum all the Polys at various offsets that are to be XORed into
         the register in accordance with the control byte
      Shift the register left by one byte, reading a new message byte
         into the rightmost byte of the register
      XOR the summed polys to the register
      End
*/


#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<memory.h>

#define POLY 0x04C11DB7L

int main()
{
 
/**//// the data 
 unsigned long data = 0x1011035b;
 
/**//// load the register with the data
 unsigned long regi = 0;
 
/**//// allocate memory to contain the AUGMENTED data (added some zeros)
 unsigned char p[8];
 
/**//// copy data
 memset( p, 08 );
 memcpy( p, 
&data, 4 );
 
 
/**//// because data contains 4 bytes
 forint i = 0; i < 8++ i )
 
{
  
/**//// get the top byte of the register
  unsigned char top_byte = (unsigned char)( ( regi >> 24 ) & 0xff );
  
/**//// sum all the polys at various offsets 
  unsigned long sum_poly = top_byte << 24;
  
forint j = 0; j < 8++ j )
  
{
   
/**//// check the top bit
   if( ( sum_poly >> 31 ) != 0 )
   
{
    
/**//// TODO : understand why '<<' first
    sum_poly = ( sum_poly << 1 ) ^ POLY;
   }

   else
   
{
    sum_poly 
<<= 1;
   }

  }

  
/**//// shift the register left by on byte, reading a new 
  regi = ( ( regi << 8 ) | p[i] );
  
/**//// xor the summed polys to the register
  regi ^= sum_poly;
 }


 
/**//// and now, register contains the remainder which is also called CRC value.
 
 
return 0;
}



其中:

 

/**//// sum all the polys at various offsets 
  unsigned long sum_poly = top_byte << 24;
  
forint j = 0; j < 8++ j )
  
{
   
/**//// check the top bit
   if( ( sum_poly >> 31 ) != 0 )
   
{
    
/**//// TODO : understand why '<<' first
    sum_poly = ( sum_poly << 1 ) ^ POLY;
   }

   else
   
{
    sum_poly 
<<= 1;
   }

  }

  
就是用于计算这个影响值的。事实上,table-driven CRC算法中的那个表就是通过这段代码生成的(排除其他一些细节)。
你可能并不是很理解,这里我建议你忽略各种细节(更多的细节见参考资料)。你所需要知道的是,我们将8次逐bit的操
作合并到了一次byte操作中。而这个byte操作,就是8次bit操作的合操作(上面提到的影响值)。这个byte操作其实就是
一个数值,也就是table-driven CRC算法中那个表的一个元素。不同序列的bit操作其实对应着不同的unsigned char
值,因此那个table有256个元素。

 

show me where the table is :

如上所说,上面的算法很容易地就可以引进一个表:


进一步简化:

上述算法一个典型特征是会在我们的数据后面添加若干0。这样做其他做了很多没用的计算。一种简化做法就是将这些
没用的计算合并到其他计算中。其实这都是一些位操作的技巧:

/**////
/// The table-driven CRC implement algorithm part 2.
///

/**//*
  While (augmented message is not exhausted)
      Begin
      Examine the top byte of the register
      Calculate the control byte from the top byte of the register
      Sum all the Polys at various offsets that are to be XORed into
         the register in accordance with the control byte
      Shift the register left by one byte, reading a new message byte
         into the rightmost byte of the register
      XOR the summed polys to the register
      End
*/


#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<memory.h>

#define POLY 0x04C11DB7L

unsigned 
long get_sum_poly( unsigned char top_byte )
{
 
/**//// sum all the polys at various offsets 
 unsigned long sum_poly = top_byte << 24;
 
forint j = 0; j < 8++ j )
 
{
  
/**//// check the top bit
co
分享到:
评论

相关推荐

    探究CRC32算法实现原理-why table-driven implemention.txt

    ### 探究CRC32算法实现原理:为什么采用表驱动实现? #### 一、CRC算法简介 CRC(Cyclic Redundancy Check)是一种用于检测数据传输错误的校验方法,广泛应用于通信领域以及数据存储系统中。CRC的核心在于通过一个...

    crc算法 路由算法

    在这个计算机网络课程设计中,学生可能需要理解并实现CRC算法,这涉及到二进制操作、多项式表示和模2除法。对于CRC校验的实现,可以使用移位寄存器和异或操作。同时,他们还需要了解不同路由算法的基本原理,如距离...

    CRC检错探究

    通过对CRC算法原理的研究,我们可以更好地理解其工作机理,并在实际应用中合理选择不同的实现方法。无论是简单的按位计算还是高效的查表法,都能够根据具体需求灵活运用,以满足不同场景下的检错需求。未来随着通信...

    matlab译码学习毕业设计课题研究代码和文档

    针对极化码在AWGN信道下的性能瓶颈,探究码长、码率、保存路径数、CRC校验位数等因素对极化码性能的影响,分别进行性能优化和提高。 后续对比不同译码算法的性能和复杂度,分析其适用场景和优缺点,为极化码在实际...

    基于STM32的二维码生成与显示系统研究.pdf

    基于STM32的二维码生成与显示系统主要研究目标是利用STM32单片机完成二维码的生成、存储及显示。二维码作为一种二维条码,相比传统的条形码具有存储信息量大、编码字符集广泛的特点。在系统硬件设计方面,文章详细...

    应用编码与计算机密码学_程序

    1. 基本编码理论:了解并实现不同类型的纠错码,理解其工作原理。 2. 加密算法:学习对称加密和非对称加密的工作流程,以及如何在代码中实现这些算法。 3. 密钥管理:理解公钥基础设施(PKI)和密钥的生成、分发、...

    AMR-WB+源码

    学习AMR-WB+源码,可以帮助开发者深入理解音频编码的原理,掌握如何实现高效、高质量的语音通信。同时,这对于开发VoIP应用、优化移动通信系统或者进行相关研究都非常有价值。通过分析源码,我们可以探究算法的优化...

    科普特序列和格雷码序列.rar

    理解科普特序列的关键在于掌握CRC算法和多项式选择。 格雷码,又称为格雷二进制码,是一种二进制数字系统,其特点是相邻两个数字之间只有一个位不同。这种特性使得在数字系统中进行计数时,出现错误的可能性大大...

    PHP生成短网址的思路以及实现方法的详解

    PHP实现短网址生成的思路和方法涵盖的IT知识点较为丰富,首先需要了解什么是短网址,然后探究短网址的生成原理,接着深入到PHP编程语言的实现细节,并且涉及到URL重写、数据库操作等Web开发的基本知识。下面对这一...

    mmsstv-源码master_MMSSTV无线电图片传送_mmsstv-源码master_

    MMSSTV的核心是源码,源码是软件的心脏,揭示了软件的工作原理和实现方式。在这个开源项目中,我们可以深入探究MMSSTV如何处理图片数据,将其编码为适合无线电传输的信号,并在接收端解码还原出原始图像。源码分析有...

    Recommended Excercise 1

    3. **Firmware编程**:探究SSD固件的角色,包括错误校验(如CRC或ECC)、坏块管理、损耗均衡和TRIM命令的处理。 4. **控制器设计**:理解控制器如何协调数据传输,以及如何进行高速缓存管理和I/O调度。 5. **数据...

    信息论与编码课件 信息安全专业资料

    课程设计可能包括实践项目,如实现简单的编码算法,如哈夫曼编码器和解码器,或者模拟信道传输并分析不同编码方案下的误码率。这样的实践有助于学生深入理解理论知识,并锻炼其编程和问题解决能力。 总之,信息论与...

    TCP/IP协议源代码 ( xinu)

    源代码的提供为我们深入了解其工作原理提供了宝贵的机会。"TCP/IP协议源代码 (xinu)" 提供的是一个使用C++语言中的C库编写的实现,这样的代码通常更加底层且高效。 首先,TCP/IP协议栈由四层构成:应用层、传输层、...

    计算机网络自顶向下pdg版

    这样的学习路径符合人们认知事物的一般规律,即先理解如何使用,再探究其工作原理。书中涵盖了TCP/IP协议栈的各个层面,包括HTTP、FTP、DNS等常见应用协议,TCP和UDP传输协议,IP路由和寻址,以及局域网、广域网的...

    计算机网络考核大纲

    - **路由算法**:掌握链路状态(LS)和距离向量(DV)算法,理解它们在路由选择中的应用。 - **互联网路由协议**:了解RIP、OSPF、BGP等协议的基本原理。 #### CH5:链路层与局域网 - **链路层服务**:理解链路层...

    研究fdt.rar_FDT

    结果表明,随着频率偏移指数的增加,即使是最先进的错误校验算法也会面临更高的误码率,这无疑对通信系统的整体性能构成威胁。 此外,我们还讨论了如何优化FDT以适应不同的通信环境。例如,对于高速率、高数据量的...

    kiv_ti_sp:KIVTI主题的学期工作-理论信息学

    3. **数据压缩**:探究哈夫曼编码、算术编码等无损和有损压缩方法,实现信息的有效存储和传输。 4. **错误检测与纠正**:理解奇偶校验、CRC校验、纠错编码如Hamming码,学习如何保证信息传输的准确性。 5. **网络...

    Spring-2021-CSCI-270-Networks-and-Data-Comm

    - 错误检测与纠正:理解奇偶校验、CRC校验等错误检测机制,以及前向纠错和ARQ协议。 5. **网络安全**: - 加密技术:介绍对称加密和非对称加密算法,如AES、RSA。 - 密钥管理:探讨密钥的生成、分发和更新策略。...

Global site tag (gtag.js) - Google Analytics