WEB开发网
开发学院WEB开发Jsp CRC32算法学习笔记以及如何用java实现 阅读

CRC32算法学习笔记以及如何用java实现

 2008-01-05 19:27:08 来源:WEB开发网   
核心提示:一:说明论坛上关于CRC32校验算法的具体介绍不多,前几天偶然看到Ross N. Williams的文章,CRC32算法学习笔记以及如何用java实现,总算把CRC32算法的来龙去脉搞清楚了,本来想把原文翻译出来,3 2 1 0 Bits+---+---+---+---+Pop <-- <- Au

  一:说明
  论坛上关于CRC32校验算法的具体介绍不多。前几天偶然看到Ross N. Williams的文章,总算把CRC32算法的来龙去脉搞清楚了。本来想把原文翻译出来,但是时间参促,只好把自己的一些学习心得写出。这样大家可以更快的了解CRC32的主要思想。由于水平有限,还恳请大家指正。原文可以访问:http://www.repairfaq.org/filipg/LINK/F_crc_v31.Html 。
  
  二:基本概念及相关介绍
  2.1 什么是CRC
  
  在远距离数据通信中,为确保高效而无差错地传送数据,必须对数据进行校验即差错控制。循环冗余校验CRC(Cyclic Redundancy Check/Code)是对一个传送数据块进行校验,是一种高效的差错控制方法。
  
  CRC校验采用多项式编码方法。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,如同逻辑异或运算。
  
  2.2 CRC的运算规则
  
  CRC加法运算规则:0+0=0
  
  0+1=1
  
  1+0=1
  
  1+1=0 (注重:没有进位)
  
  CRC减法运算规则:
  
  0-0=0
  
  0-1=1
  
  1-0=1
  
  1-1=0
  
  CRC乘法运算规则:
  
  0*0=0
  
  0*1=0
  
  1*0=0
  
  1*1=1
  
  CRC除法运算规则:
  
  1100001010 (注重:我们并不关心商是多少。)
  _______________
  
  10011 ) 11010110110000
  
  10011,,.,,....
  
  -----,,.,,....
  
  10011,.,,....
  
  10011,.,,....
  
  -----,.,,....
  
  00001.,,....
  
  00000.,,....
  
  -----.,,....
  
  00010,,....
  
  00000,,....
  
  -----,,....
  
  00101,....
  
  00000,....
  
  -----,....
  
  01011....
  
  00000....
  
  -----....
  
  10110...
  
  10011...
  
  -----...
  
  01010..
  
  00000..
  
  -----..
  
  10100.
  
  10011.
  
  -----.
  
  01110
  
  00000
  
  -----
  
  1110 = 余数
  
  2.3 如何生成CRC校验码
  
  (1) 设G(X)为W阶,在数据块末尾添加W个0,使数据块为M+ W位,则相应的多项式为XrM(X);
  
    (2) 以2为模,用对应于G(X)的位串去除对应于XrM(X)的位串,求得余数位串;
  
    (3) 以2为模,从对应于XrM(X)的位串中减去余数位串,结果就是为数据块生成的带足够校验信息的CRC校验码位串。
  
  2.4 可能我们会问那如何选择G(x)
  
  可以说选择G(x)不是一件很轻易的事。一般我们都使用已经被大量的数据,时间检验过的,正确的,高效的,生成多项式。一般有以下这些:
  
  16 bits: (16,12,5,0) [X25 standard]
  
  (16,15,2,0) ["CRC-16"]
  
  32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]
  
  三: 如何用软件实现CRC算法
  现在我们主要问题就是如何实现CRC校验,编码和解码。用硬件实现目前是不可能的,我们主要考虑用软件实现的方法。
  
  以下是对作者的原文的翻译:
  
  我们假设有一个4 bits的寄存器,通过反复的移位和进行CRC的除法,最终该寄存器中的值就是我们所要求的余数。
  
  3 2 1 0 Bits
  
  +---+---+---+---+
  
  Pop <-- <----- Augmented message(已加0扩张的原始数据)
  
  +---+---+---+---+
  
  1 0 1 1 1 = The Poly
  
  (注重: The augmented message is the message followed by W zero bits.)
  
  依据这个模型,我们得到了一个最最简单的算法:
  
  把register中的值置0.
  
  把原始的数据后添加r个0.
  
  While (还有剩余没有处理的数据)
  
  Begin
  
  把register中的值左移一位,读入一个新的数据并置于register的0 bit的位置。

Tags:CRC 算法 学习

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接