❶ 关于CRC算法，高手赐教
循环冗余校验（CRC）是一种根据网络数据封包或电脑档案等数据产生少数固定位数的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者储存之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。一般来说，循环冗余校验的值都是32位的整数。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。它是由W. Wesley Peterson在他1961年发表的论文中披露[1]。
{{noteTA
|T=zh-hans:循环冗余校验;zh-hant:循环冗余校验;
|1=zh-hans:循环冗余校验;zh-hant:循环冗余校验;
}}
'''循环冗余校验'''（CRC）是一种根据网路数据封包或[[电脑档案]]等数据产生少数固定位数的一种[[散列函数]]，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者储存之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。一般来说，循环冗余校验的值都是32位的整数。由于本函数易于用二进制的[[电脑硬件]]使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。它是由[[W. Wesley Peterson]]在他1961年发表的论文中披露<ref name="PetersonBrown1961">
{{cite journal
| author = Peterson, W. W. and Brown, D. T.
| year = 1961
| month = January
| title = Cyclic Codes for Error Detection
| journal = Proceedings of the IRE
| doi = 10.1109/JRPROC.1961.287814
| issn = 0096-8390
| volume = 49
| pages = 228
}}</ref>。
==简介==
CRC“校验和”是两个位元数据流采用二进制除法（没有进位，使用XOR异或来代替减法）相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示；除数是一个长度为<math>n+1</math>的预定义（短）的二进制数，通常用多项式的系数来表示。在做除法之前，要在信息数据之后先加上<math>n</math>个0.
CRCa 是基于[[有限域]]GF(2)([[同余|关于2同余]])的[[多项式环]]。简单的来说，就是所有系数都为0或1（又叫做二进制）的多项式系数的集合，并且集合对于所有的代数操作都是封闭的。例如：
:<math>(x^3 + x) + (x + 1) = x^3 + 2x + 1 \equiv x^3 + 1</math>
2会变成0，因为对系数的加法都会模2. 乘法也是类似的：
:<math>(x^2 + x)(x + 1) = x^3 + 2x^2 + x \equiv x^3 + x</math>
我们同样可以对多项式作除法并且得到商和余数。例如， 如果我们用''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x''除以''x'' + 1。我们会得到：
:<math>\frac{(x^3 + x^2 + x)}{(x+1)} = (x^2 + 1) - \frac{1}{(x+1)}</math>
<!--注：在说“除以”的时候, 读者将会看到等式中的除号。这里看不到除号常使我感到有点混乱。-->
也就是说，
:<math>(x^3 + x^2 + x) = (x^2 + 1)(x + 1) - 1</math>
这里除法得到了商''x''<sup>2</sup> + 1和余数-1，因为是奇数所以最后一位是1。
字符串中的每一位其实就对应了这样类型的多项式的系数。为了得到CRC, 我们首先将其乘以<math>x^{n}</math>，这里<math>n</math>是一个固定多项式的[[多项式的阶|阶]]数, 然后再将其除以这个固定的多项式，余数的系数就是CRC。
在上面的等式中，<math>x^2+x+1</math>表示了本来的信息位是<code>111</code>, <math>x+1</math>是所谓的'''钥匙''', 而余数<math>1</math>（也就是<math>x^0</math>）就是CRC. key的最高次为1, 所以我们将原来的信息乘上<math>x^1</math>来得到<math>x^3 + x^2 + x</math>，也可视为原来的信息位补1个零成为<code>1110</code>。
一般来说，其形式为：
:<math>M(x) \cdot x^{n} = Q(x) \cdot K(x) + R (x) </math>
这里 M(x) 是原始的信息多项式。K(x)是<math>n</math>阶的“钥匙”多项式。<math>M(x) \cdot x^{n}</math>表示了将原始信息后面加上<math>n</math>个0。R(x)是余数多项式，既是CRC“校验和”。在通讯中，发送者在原始的信息数据M后加上<math>n</math>位的R（替换本来附加的0）再发送。接收者收到M和R后，检查<math>M(x) \cdot x^{n} - R(x)</math>是否能被<math>K(x)</math>整除。如果是，那么接收者认为该信息是正确的。值得注意的是<math>M(x) \cdot x^{n} - R(x)</math>就是发送者所想要发送的数据。这个串又叫做''codeword''.
CRCs 经常被叫做“[[校验和]]”, 但是这样的说法严格来说并不是准确的，因为技术上来说，校验“和”是通过加法来计算的，而不是CRC这里的除法。
“[[错误纠正编码]]”常常和CRCs紧密相关，其语序纠正在传输过程中所产生的错误。这些编码方式常常和数学原理紧密相关。
==实现==
==变体==
CRC 有几种不同的变体
* <code>shiftRegister</code> 可以逆向使用，这样就需要检测最低位的值，每次向右移动一位。这就要求 <code>polynomial</code> 生成逆向的数据位结果。''实际上这是最常用的一个变体。''
* 可以先将数据最高位读到移位寄存器，也可以先读最低位。在通讯协议中，为了保留 CRC 的[[突发错误]]检测特性，通常按照[[物理层]]发送数据位的方式计算 CRC。
* 为了检查 CRC，需要在全部的码字上进行 CRC 计算，而不是仅仅计算消息的 CRC 并把它与 CRC 比较。如果结果是 0，那么就通过这项检查。这是因为码字 <math>M(x) \cdot x^{n} - R(x) = Q(x) \cdot K(x)</math> 可以被 <math>K(x)</math> 整除。
* 移位寄存器可以初始化成 1 而不是 0。同样，在用算法处理之前，消息的最初 <math>n</math> 个数据位要取反。这是因为未经修改的 CRC 无法区分只有起始 0 的个数不同的两条消息。而经过这样的取反过程，CRC 就可以正确地分辨这些消息了。
* CRC 在附加到消息数据流的时候可以进行取反。这样，CRC 的检查可以用直接的方法计算消息的 CRC、取反、然后与消息数据流中的 CRC 比较这个过程来完成，也可以通过计算全部的消息来完成。在后一种方法中，正确消息的结果不再是 0，而是 <math>\sum_{i=n}^{2n-1} x^{i}</math> 除以 <math>K(x)</math> 得到的结果。这个结果叫作核验多项式 <math>C(x)</math>，它的十六进制表示也叫作[[幻数]]。
按照惯例，使用 CRC-32 多项式以及 CRC-16-CCITT 多项式时通常都要取反。CRC-32 的核验多项式是
<math>C(x) = x^{31} + x^{30} + x^{26} + x^{25} + x^{24} + x^{18} + x^{15} + x^{14} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^4 + x^3 + x + 1</math>。
==错误检测能力==
CRC 的错误检测能力依赖于关键多项式的阶次以及所使用的特定关键多项式。''误码多项式'' <math>E(x)</math> 是接收到的消息码字与正确消息码字的''异或''结果。当且仅当误码多项式能够被 CRC 多项式整除的时候 CRC 算法无法检查到错误。
* 由于 CRC 的计算基于除法，任何多项式都无法检测出一组全为零的数据出现的错误或者前面丢失的零。但是，可以根据 CRC 的[[#变体|变体]]来解决这个问题。
* 所有只有一个数据位的错误都可以被至少有两个非零系数的任意多项式检测到。误码多项式是 <math>x^k</math>，并且 <math>x^k</math> 只能被 <math>i \le k</math> 的多项式 <math>x^i</math> 整除。
* CRC 可以检测出所有间隔距离小于[[多项式阶次]]的双位错误，在这种情况下的误码多项式是
<math>E(x) = x^i + x^k = x^k \cdot (x^{i-k} + 1), \; i > k</math>。
如上所述，<math>x^k</math> 不能被 CRC 多项式整除，它得到一个 <math>x^{i-k} + 1</math> 项。根据定义，满足多项式整除 <math>x^{i-k} + 1</math> 的 <math>{i-k}</math> 最小值就是多项是的阶次。最高阶次的多项式是[[本原多项式]]，带有二进制系数的 <math>n</math> 阶多项式
==CRC 多项式规范==
下面的表格略去了“初始值”、“反射值”以及“最终异或值”。
* 对于一些复杂的校验和来说这些十六进制数值是很重要的，如 CRC-32 以及 CRC-64。通常小于 CRC-16 的 CRC 不需要使用这些值。
* 通常可以通过改变这些值来得到各自不同的校验和，但是校验和算法机制并没有变化。
CRC 标准化问题
* 由于 CRC-12 有三种常用的形式，所以 CRC-12 的定义会有歧义
* 在应用的 CRC-8 的两种形式都有数学上的缺陷。
* 据称 CRC-16 与 CRC-32 至少有 10 种形式，但没有一种在数学上是最优的。
* 同样大小的 CCITT CRC 与 ITU CRC 不同，这个机构在不同时期定义了不同的校验和。
==常用 CRC（按照 ITU-IEEE 规范）==
{|class="wikitable"
! 名称|| 多项式 || 表示法：正常或者翻转
|-
|CRC-1 || <math>x + 1</math><br>(用途：硬件，也称为[[奇偶校验位]]) || 0x1 or 0x1 (0x1)
|-
|CRC-5-CCITT || <math>x^{5} + x^{3} + x + 1</math> ([[ITU]] G.704 标准) || 0x15 (0x??)
|-
|CRC-5-USB || <math>x^{5} + x^{2} + 1</math> (用途：[[USB]] 信令包) || 0x05 or 0x14 (0x9)
|-
|CRC-7 || <math>x^{7} + x^{3} + 1</math> (用途：通信系统) || 0x09 or 0x48 (0x11)
|-
|CRC-8-ATM || <math>x^8 + x^2 + x + 1</math> (用途：ATM HEC) || 0x07 or 0xE0 (0xC1)
|-
|CRC-8-[[CCITT]] || <math>x^8 + x^7 + x^3 + x^2 + 1</math> (用途：[[1-Wire]] [[总线]]) ||
|-
|CRC-8-[[Dallas_Semiconctor|Dallas]]/[[Maxim_IC|Maxim]] || <math>x^8 + x^5 + x^4 + 1</math> (用途：[[1-Wire]] [[bus]]) || 0x31 or 0x8C
|-
|CRC-8 || <math>x^8 + x^7 + x^6 + x^4 + x^2 +1</math> || 0xEA(0x??)
|-
|CRC-10 || x<sup>10</sup> + x<sup>9</sup> + x<sup>5</sup> + x<sup>4</sup> + x + 1 || 0x233 (0x????)
|-
|CRC-12 || <math>x^{12} + x^{11} + x^3 + x^2 + x + 1</math><br>(用途：通信系统) || 0x80F or 0xF01 (0xE03)
|-
|CRC-16-Fletcher || 参见 [[Fletcher's checksum]] || 用于 [[Adler-32]] A & B CRC
|-
|CRC-16-CCITT || ''x''<sup>16</sup> + ''x''<sup>12</sup> + ''x''<sup>5</sup> + 1 ([[X25]], [[V.41]], [[Bluetooth]], [[PPP]], [[IrDA]]) || 0x1021 or 0x8408 (0x0811)
|-
|CRC-16-[[IBM]] || ''x''<sup>16</sup> +''x''<sup>15</sup> + ''x''<sup>2</sup> + 1 || 0x8005 or 0xA001 (0x4003)
|-
|CRC-16-[[BBS]] || x<sup>16</sup> + x<sup>15</sup> + x<sup>10</sup> + x<sup>3</sup> (用途：[[XMODEM]] 协议) || 0x8408 (0x????)
|-
|CRC-32-Adler || See [[Adler-32]] || 参见 [[Adler-32]]
|-
|CRC-32-MPEG2 || See [[IEEE 802.3]] || 参见 [[IEEE 802.3]]
|-
|CRC-32-[[IEEE 802.3]] || <math>x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</math> || 0x04C11DB7 or 0xEDB88320 (0xDB710641)
|-
|CRC-32C (Castagnoli)<ref name="cast93"/>|| <math>x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1</math> || 0x1EDC6F41 or 0x82F63B78 (0x05EC76F1)
|-
|CRC-64-ISO || <math>x^{64} + x^4 + x^3 + x + 1</math><br>(use: ISO 3309) || 0x000000000000001B or 0xD800000000000000 (0xB000000000000001)
|-
|CRC-64-[[Ecma International|ECMA]]-182 || <math>x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} + x^{32} </math><br><!--Too long to display in one table--><math>+ x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1</math><br>(as described in [http://www.ecma-international.org/publications/standards/Ecma-182.htm ECMA-182] p.63) || 0x42F0E1EBA9EA3693 or 0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
|-
|CRC-128 || IEEE-ITU 标准。被 [[MD5]] & [[SHA-1]] 取代||
|-
|CRC-160 || IEEE-ITU 标准。被 [[MD5]] & [[SHA-1]] 取代||
|-
|}
==CRC 与数据完整性==
尽管在[[错误检测]]中非常有用，CRC 并不能可靠地验证[[数据完整性]]（即数据没有发生任何变化），这是因为 CRC 多项式是线性结构，可以非常容易地''故意''改变数据而维持 CRC 不变，参见[http://www.woodmann.com/fravia/crctut1.htm CRC and how to Reverse it]中的证明。我们可以用 [[Message authentication code]] 验证数据完整性。
===CRC发生碰撞的情况===
与所有其它的[[散列函数]]一样，在一定次数的碰撞测试之后 CRC 也会接近 100% 出现碰撞。CRC 中每增加一个数据位，就会将碰撞数目减少接近 50%，如 CRC-20 与 CRC-21 相比。
* 理论上来讲，CRC64 的碰撞概率大约是每 18{{e|18}} 个 CRC 码出现一次。
* 由于 CRC 的不分解多项式特性，所以经过合理设计的较少位数的 CRC 可能会与使用较多数据位但是设计很差的 CRC 的效率相媲美。在这种情况下 CRC-32 几乎同 CRC-40 一样优秀。
===设计 CRC 多项式===
生成多项式的选择是 CRC 算法实现中最重要的部分，所选择的多项式必须有最大的错误检测能力，同时保证总体的碰撞概率最小。多项式最重要的属性是它的长度，也就是最高非零系数的数值，因为它直接影响着计算的校验和的长度。
最常用的多项式长度有
* 9 位 (CRC-8)
* 17 位 (CRC-16)
* 33 位 (CRC-32)
* 65 位 (CRC-64)
在构建一个新的 CRC 多项式或者改进现有的 CRC 时，一个通用的数学原则是使用满足所有模运算不可分解多项式约束条件的多项式。
* 这种情况下的不可分解是指多项式除了 1 与它自身之外不能被任何其它的多项式整除。
生成多项式的特性可以从算法的定义中推导出来：
* 如果 CRC 有多于一个的非零系数，那么 CRC 能够检查出输入消息中的所有单数据位错误。
* CRC 可以用于检测短于 2k 的输入消息中的所有双位错误，其中 k 是多项式的最长的不可分解部分的长度。
* 如果多项式可以被 x+1 整除，那么不存在可以被它整除的有奇数个非零系数的多项式。因此，它可以用来检测输入消息中的奇数个错误，就象奇偶校验函数那样。
==参见==
总的分类
* [[纠错码]]
* [[校验和算法列表]]
* [[奇偶校验位]]
特殊技术参考
* [[Adler-32]]
* [[Fletcher's checksum]]
==参考文献 ==
<references/>
==外部链接==
* [http://www.relisoft.com/science/CrcMath.html Tutorial and C++ implementation] of CRC
* Cyclic rendancy check - a simple guide to what it means for your data, CD and DVD discs. http://www.softwarepatch.com/tips/cyclic-rendancy.html
* [http://www.ross.net/crc/ ''The CRC Pitstop'']
* Williams, R. (1993-09) [http://www.repairfaq.org/filipg/LINK/F_crc_v3.html ''A Painless Guide to CRC Error Detection Algorithms'']
* [http://www.4d.com/docs/CMU/CMU79909.HTM ''Understanding Cyclic Rendancy Check'']
* Black, R. (1994-02) [http://www.cl.cam.ac.uk/Research/SRG/bluebook/21/crc/crc.html ''Fast CRC32 in Software''] — Algorithm 4 is used in Linux and info-zip's zip and unzip.
* Barr, M. ([http://www.netrino.com/Connecting/1999-11/ ''1999-11''], [http://www.netrino.com/Connecting/1999-12/ ''1999-12''], [http://www.netrino.com/Connecting/2000-01/ ''2000-01'']) checksums, CRCs, and their source code. Embedded Systems Programming
* [http://www.codeproject.com/cpp/crc32.asp CRC32: Generating a checksum for a file], C++ implementation by Brian Friesen
* Online [http://serversniff.net/hash.php Tool to compute common CRCs (8/16/32/64) from strings]
* Online [http://www.zorc.breitbandkatze.de/crc.html CRC calculator]
* Online [http://www.easics.com/webtools/crctool CRC Tool: Generator of synthesizable CRC functions]
* [http://www.paulschou.com/tools/xlate/ Online Char (ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms]
* [http://apollo.backplane.com/matt/crc64.html CRC16 to CRC64 collision research]
* [http://sar.informatik.hu-berlin.de/research/publications/index.htm#SAR-PR-2006-05 Reversing CRC – Theory and Practice.]
{{math-stub}}
[[Category:校验和算法]]
[[bg:CRC]]
[[ca:Control de rendància cíclica]]
[[cs:Cyklický rendantní součet]]
[[de:Zyklische Rendanzprüfung]]
[[en:Cyclic rendancy check]]
[[es:Control de rendancia cíclica]]
[[eu:CRC]]
[[fi:CRC]]
[[fr:Contrôle de redondance cyclique]]
[[he:בדיקת יתירות מחזורית]]
[[id:CRC]]
[[it:Cyclic rendancy check]]
[[ja:巡回冗长検査]]
[[ko:순환 중복 검사]]
[[nl:Cyclic Rendancy Check]]
[[pl:CRC]]
[[pt:CRC]]
[[ru:Циклический избыточный код]]
[[simple:Cyclic rendancy check]]
[[sk:Kontrola cyklickým kódom]]
[[sv:Cyclic Rendancy Check]]
[[vi:CRC]]
❷ CRC8校验算法的作用是什么
不了解不好意思！
❸ CRC8算法疑问
信息大，会分段传输，每段都有自己的crc校验，然后在接收方组合。crc相同的情况叫做crc碰撞，由于crc只有8位，所以发生碰撞的概率比较高，所以一般需要安全性比较高的地方都是用md5或sha1校验的。
❹ 关于DS18B20的CRC-8校验计算的问题
我没有仔细看你一步一步的计算，我是按照程序中的速算法来推算的（参照美信官网的Application Note 27中提供的速算程序，链接：https://www.maximintegrated.com/en/app-notes/index.mvp/id/27），计算步骤如下：
待验证序列为：28 FF 15 8A 74 16 04 72
00 xor 28 = 28, TABLE[28] = E1
E1 xor FF = 1E, TABLE[1E] = 82
82 xor 15 = 97, TABLE[97] = 92
92 xor 8A = 18, TABLE[18] = 5F
5F xor 74 = 2B, TABLE[2B] = 03
03 xor 16 = 15, TABLE[15] = A2
A2 xor 04 = A6, TABLE[A6] = 72
72 xor 72 = 00
因此18B20中的数据是没有问题的。
❺ 如何用java实现CRC8验证算法
/*http://www.koders.com/java/.aspx?s=Address#L34
*---------------------------------------------------------------------------
* Copyright (C) 1999,2000 Dallas Semiconctor Corporation, All Rights Reserved.
*
* Permission is hereby granted, free of charge, to any person obtaining a
* of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, , modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above right notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
* IN NO EVENT SHALL DALLAS SEMICONDUCTOR BE LIABLE FOR ANY CLAIM, DAMAGES
* OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*
* Except as contained in this notice, the name of Dallas Semiconctor
* shall not be used except as stated in the Dallas Semiconctor
* Branding Policy.
*---------------------------------------------------------------------------
*/
package com.dalsemi.onewire.utils;
/**
* CRC8 is a class to contain an implementation of the
* Cyclic-Rendency-Check CRC8 for the iButton. The CRC8 is used
* in the 1-Wire Network address of all iButtons and 1-Wire
* devices.
* <p>
* CRC8 is based on the polynomial = X^8 + X^5 + X^4 + 1.
*
* @version 0.00, 28 Aug 2000
* @author DS
*
*/
public class CRC8
{
//--------
//-------- Variables
//--------
/**
* CRC 8 lookup table
*/
private static byte dscrc_table [];
/*
* Create the lookup table
*/
static
{
//Translated from the assembly code in iButton Standards, page 129.
dscrc_table = new byte [256];
int acc;
int crc;
for (int i = 0; i < 256; i++)
{
acc = i;
crc = 0;
for (int j = 0; j < 8; j++)
{
if (((acc ^ crc) & 0x01) == 0x01)
{
crc = ((crc ^ 0x18) >> 1) | 0x80;
}
else
crc = crc >> 1;
acc = acc >> 1;
}
dscrc_table [i] = ( byte ) crc;
}
}
//--------
//-------- Constructor
//--------
/**
* Private constructor to prevent instantiation.
*/
private CRC8 ()
{
}
//--------
//-------- Methods
//--------
/**
* Perform the CRC8 on the data element based on the provided seed.
* <p>
* CRC8 is based on the polynomial = X^8 + X^5 + X^4 + 1.
*
* @param dataToCrc data element on which to perform the CRC8
* @param seed seed the CRC8 with this value
* @return CRC8 value
*/
public static int compute (int dataToCRC, int seed)
{
return (dscrc_table [(seed ^ dataToCRC) & 0x0FF] & 0x0FF);
}
/**
* Perform the CRC8 on the data element based on a zero seed.
* <p>
* CRC8 is based on the polynomial = X^8 + X^5 + X^4 + 1.
*
* @param dataToCrc data element on which to perform the CRC8
* @return CRC8 value
*/
public static int compute (int dataToCRC)
{
return (dscrc_table [dataToCRC & 0x0FF] & 0x0FF);
}
/**
* Perform the CRC8 on an array of data elements based on a
* zero seed.
* <p>
* CRC8 is based on the polynomial = X^8 + X^5 + X^4 + 1.
*
* @param dataToCrc array of data elements on which to perform the CRC8
* @return CRC8 value
*/
public static int compute (byte dataToCrc [])
{
return compute(dataToCrc, 0, dataToCrc.length);
}
/**
* Perform the CRC8 on an array of data elements based on a
* zero seed.
* <p>
* CRC8 is based on the polynomial = X^8 + X^5 + X^4 + 1.
*
* @param dataToCrc array of data elements on which to perform the CRC8
* @param off offset into array
* @param len length of data to crc
* @return CRC8 value
*/
public static int compute (byte dataToCrc [], int off, int len)
{
return compute(dataToCrc, off, len, 0);
}
/**
* Perform the CRC8 on an array of data elements based on the
* provided seed.
* <p>
* CRC8 is based on the polynomial = X^8 + X^5 + X^4 + 1.
*
* @param dataToCrc array of data elements on which to perform the CRC8
* @param off offset into array
* @param len length of data to crc
* @param seed seed to use for CRC8
* @return CRC8 value
*/
public static int compute (byte dataToCrc [], int off, int len, int seed)
{
// loop to do the crc on each data element
int CRC8 = seed;
for (int i = 0; i < len; i++)
CRC8 = dscrc_table [(CRC8 ^ dataToCrc [i + off]) & 0x0FF];
return (CRC8 & 0x0FF);
}
/**
* Perform the CRC8 on an array of data elements based on the
* provided seed.
* <p>
* CRC8 is based on the polynomial = X^8 + X^5 + X^4 + 1.
*
* @param dataToCrc array of data elements on which to perform the CRC8
* @param seed seed to use for CRC8
* @return CRC8 value
*/
public static int compute (byte dataToCrc [], int seed)
{
return compute(dataToCrc, 0, dataToCrc.length, seed);
}
}
❻ CRC余数表怎么计算出来的
循环冗余检验 (CRC) 算法原理
转载：http://www.cnblogs.com/esestt/archive/2007/08/09/848856.html
Cyclic Rendancy Check循环冗余检验，是基于数据计算一组效验码，用于核对数据传输过程中是否被更改或传输错误。
算法原理
假设数据传输过程中需要发送15位的二进制信息 g=101001110100001，这串二进制码可表示为代数多项式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1，其中g中第k位的值，对应g(x)中x^k的系数。将g(x)乘以x^m，既将g后加m个0，然后除以m阶多项式h(x)，得到的(m-1)阶余项 r(x)对应的二进制码r就是CRC编码。
h(x)可以自由选择或者使用国际通行标准，一般按照h(x)的阶数m，将CRC算法称为CRC-m，比如CRC-32、CRC-64等。国际通行标准可以参看http://en.wikipedia.org/wiki/Cyclic_rendancy_check
g(x)和h(x)的除运算，可以通过g和h做xor（异或）运算。比如将11001与10101做xor运算：
明白了xor运算法则后，举一个例子使用CRC-8算法求101001110100001的效验码。CRC-8标准的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1，既h是9位的二进制串111010101。
经过迭代运算后，最终得到的r是10001100，这就是CRC效验码。
通过示例，可以发现一些规律，依据这些规律调整算法：
1. 每次迭代，根据gk的首位决定b，b是与gk进行运算的二进制码。若gk的首位是1，则b=h；若gk的首位是0，则b=0，或者跳过此次迭代，上面的例子中就是碰到0后直接跳到后面的非零位。
2. 每次迭代，gk的首位将会被移出，所以只需考虑第2位后计算即可。这样就可以舍弃h的首位，将b取h的后m位。比如CRC-8的h是111010101，b只需是11010101。
3. 每次迭代，受到影响的是gk的前m位，所以构建一个m位的寄存器S，此寄存器储存gk的前m位。每次迭代计算前先将S的首位抛弃，将寄存器左移一位，同时将g的后一位加入寄存器。若使用此种方法，计算步骤如下：
※蓝色表示寄存器S的首位，是需要移出的，b根据S的首位选择0或者h。黄色是需要移入寄存器的位。S'是经过位移后的S。
查表法
同样是上面的那个例子，将数据按每4位组成1个block，这样g就被分成6个block。
下面的表展示了4次迭代计算步骤，灰色背景的位是保存在寄存器中的。
经4次迭代，B1被移出寄存器。被移出的部分，不我们关心的，我们关心的是这4次迭代对B2和B3产生了什么影响。注意表中红色的部分，先作如下定义：
B23 = 00111010
b1 = 00000000
b2 = 01010100
b3 = 10101010
b4 = 11010101
b' = b1 xor b2 xor b3 xor b4
4次迭代对B2和B3来说,实际上就是让它们与b1,b2,b3,b4做了xor计算，既：
B23 xor b1 xor b2 xor b3 xor b4
可以证明xor运算满足交换律和结合律，于是：
B23 xor b1 xor b2 xor b3 xor b4 = B23 xor (b1 xor b2 xor b3 xor b4) = B23 xor b'
b1是由B1的第1位决定的，b2是由B1迭代1次后的第2位决定（既是由B1的第1和第2位决定），同理,b3和b4都是由B1决定。通过B1就 可以计算出b'。另外，B1由4位组成，其一共2^4有种可能值。于是我们就可以想到一种更快捷的算法，事先将b'所有可能的值，16个值可以看成一个 表；这样就可以不必进行那4次迭代，而是用B1查表得到b'值，将B1移出，B3移入，与b'计算，然后是下一次迭代。
可看到每次迭代，寄存器中的数据以4位为单位移入和移出，关键是通过寄存器前4位查表获得
，这样的算法可以大大提高运算速度。
上面的方法是半字节查表法，另外还有单字节和双字节查表法，原理都是一样的——事先计算出2^8或2^16个b'的可能值，迭代中使用寄存器前8位或16位查表获得b'。
PS:补充重要知识点：
http://hi..com/ivan_liumh/blog/item/0fd28dd3c63062d9562c8479.html
循环冗余校验码
在串行传送（磁盘、通讯）中，广泛采用循环冗余校验码（CRC）。CRC也是给信息码加上几位校验码，以增加整个编码系统的码距和查错纠错能力。
CRC的理论很复杂，一般书上只介绍已有生成多项式后计算校验码的方法。检错能力与生成多项式有关，只能根据书上的结论死记。
循 环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的 （N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项 式。
校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2R，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。
几个基本概念
1、多项式与二进制数码
多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。
多项式包括生成多项式G(x)和信息多项式C(x)。
如生成多项式为G(x)=x4+x3+x+1， 可转换为二进制数码11011。
而发送信息位 1111，可转换为数据多项式为C(x)=x3+x2+x+1。
2、生成多项式
是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。
在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。
应满足以下条件：
a、生成多项式的最高位和最低位必须为1。
b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。
c、不同位发生错误时，应该使余数不同。
d、对余数继续做模2除，应使余数循环。
将这些要求反映为数学关系是比较复杂的。但可以从有关资料查到常用的对应于不同码制的生成多项式如图9所示：
图9 常用的生成多项式
3、模2除（按位除）
模2除做法与算术除法类似，但每一位除（减）的结果不影响其它位，即不向上一位借位。所以实际上就是异或。然后再移位移位做下一位的模2减。步骤如下：
a、用除数对被除数最高几位做模2减，没有借位。
b、除数右移一位，若余数最高位为1，商为1，并对余数做模2减。若余数最高位为0，商为0，除数继续右移一位。
c、一直做到余数的位数小于除数时，该余数就是最终余数。
【例】1111000除以1101：
1011———商
————
1111000-----被除数
1101———— 除数
————
010000
1101
————
01010
1101
————
111————余数
CRC码的生成步骤
1、将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。
2、将信息码左移R位，相当与对应的信息多项式C(x)*2R
3、用生成多项式（二进制数）对信息码做模2除，得到R位的余数。
4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。
【例】假设使用的生成多项式是G(x)=x3+x+1。4位的原始报文为1010，求编码后的报文。
解：
1、将生成多项式G(x)=x3+x+1转换成对应的二进制除数1011。
2、此题生成多项式有4位（R+1），要把原始报文C(x)左移3（R）位变成1010000
3、用生成多项式对应的二进制数对左移4位后的原始报文进行模2除：
1001-------商
------------------------
1010000
1011----------除数
------------
1000
1011
------------
011-------余数（校验位）
5、编码后的报文（CRC码）：
1010000
+ 011
------------------
1010011
CRC的和纠错
在 接收端收到了CRC码后用生成多项式为G(x)去做模2除，若得到余数为0,则码字无误。若如果有一位出错，则余数不为0，而且不同位出错，其余数也不 同。可以证明，余数与出错位的对应关系只与码制及生成多项式有关，而与待测码字（信息位）无关。图10给出了G(x)＝1011，C(x)＝1010的出 错模式，改变C(x)（码字），只会改变表中码字内容，不改变余数与出错位的对应关系。
图10 （7，4）CRC码的出错模式（G(x)＝1011）
如 果循环码有一位出错，用G(x)作模2除将得到一个不为0的余数。如果对余数补0继续除下去，我们将发现一个有趣的结果；各次余数将按图10顺序循环。例 如第一位出错，余数将为001，补0后再除（补0后若最高位为1，则用除数做模2减取余；若最高位为0，则其最低3位就是余数），得到第二次余数为 010。以后继续补0作模2除，依次得到余数为100，0ll…，反复循环，这就是“循环码”名称的由来。这是一个有价值的特点。如果我们在求出余数不为 0后，一边对余数补0继续做模2除，同时让被检测的校验码字循环左移。图10说明，当出现余数(101)时，出错位也移到A7位置。可通过异或门将它纠正后在下一次移位时送回A1。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时，循环码校验能有效地降低硬件代价，这是它得以广泛应用的主要原因。
【例】 对图10的CRC码（G(x)＝1011，C(x)＝1010），若接收端收到的码字为1010111，用G(x)＝1011做模2除得到一个不为0的余 数100，说明传输有错。将此余数继续补0用G(x)＝1011作模2除，同时让码字循环左移1010111。做了4次后，得到余数为101，这时码字也 循环左移4位，变成1111010。说明出错位已移到最高位A7，将最高位1取反后变成0111010。再将它循环左移3位，补足7次，出错位回到A3位，就成为一个正确的码字1010011。
引用：http://hi..com/tudou888/blog/item/36df6017172a6e4020a4e95c.html
CRC-32 的程序实现
为了提高编码效率，在实际运用中大多采用查表法来完成CRC-32 校验，下面是产生CRC-32
校验吗的子程序。
unsigned long crc_32_tab[256]={
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535,
0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d
};//事先计算出的参数表，共有256 项，未全部列出。
unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long len)
{
unsigned long oldcrc32;
unsigned long crc32;
unsigned long oldcrc;
unsigned int charcnt;
char c,t;
oldcrc32 = 0x00000000; //初值为0
charcnt=0;
while (len--) {
t= (oldcrc32 >> 24) & 0xFF; //要移出的字节的值
oldcrc=crc_32_tab[t]; //根据移出的字节的值查表
c=DataBuf[charcnt]; //新移进来的字节值
oldcrc32= (oldcrc32 << 8) | c; //将新移进来的字节值添在寄存器末字节中
oldcrc32=oldcrc32^oldcrc; //将寄存器与查出的值进行xor 运算
charcnt++;
}
crc32=oldcrc32;
return crc32;
}
参数表可以先在PC 机上算出来，也可在程序初始化时完成。下面是用于计算参数表的c 语言
子程序，在Visual C++ 6.0 下编译通过。
#include <stdio.h>
unsigned long int crc32_table[256];
unsigned long int ulPolynomial = 0x04c11db7;
unsigned long int Reflect(unsigned long int ref, char ch)
{ unsigned long int value(0);
// 交换bit0 和bit7，bit1 和bit6，类推
for(int i = 1; i < (ch + 1); i++)
{ if(ref & 1)
value |= 1 << (ch - i);
ref >>= 1; }
return value;
}
init_crc32_table()
{ unsigned long int crc,temp;
// 256 个值
for(int i = 0; i <= 0xFF; i++)
{ temp=Reflect(i, 8);
crc32_table[i]= temp<< 24;
for (int j = 0; j < 8; j++){
unsigned long int t1,t2;
unsigned long int flag=crc32_table[i]&0x80000000;
t1=(crc32_table[i] << 1);
if(flag==0)
t2=0;
else
t2=ulPolynomial;
crc32_table[i] =t1^t2 ; }
crc=crc32_table[i];
crc32_table[i] = Reflect(crc32_table[i], 32);
}
}
❼ 求一个C# CRC8 的算法代码 生成多项式可以随意选 能够得到CRC码 然后调用函数
public static byte CRC8(byte[] buffer,byte poly)
{
byte crc = 0;
byte CRCPoly = poly;
for (int j = 0; j < buffer.Length; j++)
{
crc ^= buffer[j];
for (int i = 0; i < 8; i++)
{
if ((crc & 0x80) != 0)
{
crc <<= 1;
crc ^= CRCPoly;
}
else
{
crc <<= 1;
}
}
}
crc = Convert.ToByte(crc ^ 0x00);
return crc;
}
❽ CRC校验是怎么算的
你这个是CRC16要实现校验的话，你首先需要知道对方采用的是何种CRC公式不同的CRC公式 得到的校验码是不一样的在知道公式的情况下做crc表，然后按照crc算法，计算这8个字节的整体crc如果传输没有错误的话，最终的crc值是0也可以计算前六个的crc，然后和最后两个字节比较，效果是相同的。