❶ 關於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，然後和最後兩個位元組比較，效果是相同的。