crc演算法原理及實現

❶ 高手解釋下crc的具體演算法和用法

一、循環冗餘碼校驗英文名稱為Cyclical Rendancy
Check，簡稱CRC。它是利用除法及余數的原理來作錯誤偵測（Error
Detecting）的。實際應用時，發送裝置計算出CRC值並隨數據一同發送給接收裝置，接收裝置對收到的數據重新計算CRC並與收到的CRC相比較，若兩個CRC值不同，則說明數據通訊出現錯誤。
根據應用環境與習慣的不同，CRC又可分為以下幾種標准：
①CRC-12碼；
②CRC-16碼；
③CRC-CCITT碼；
④CRC-32碼。
CRC-12碼通常用來傳送6-bit字元串。CRC-16及CRC-CCITT碼則用是來傳送8-bit字元，其中CRC-16為美國採用，而CRC-CCITT為歐洲國家所採用。CRC-32碼大都被採用在一種稱為Point-to-Point的同步傳輸中。
下面以最常用的CRC-16為例來說明其生成過程。
CRC-16碼由兩個位元組構成，在開始時CRC寄存器的每一位都預置為1，然後把CRC寄存器與8-bit的數據進行異或，之後對CRC寄存器從高到低進行移位，在最高位（MSB）的位置補零，而最低位（LSB，移位後已經被移出CRC寄存器）如果為1，則把寄存器與預定義的多項式碼進行異或，否則如果LSB為零，則無需進行異或。重復上述的由高至低的移位8次，第一個8-bit數據處理完畢，用此時CRC寄存器的值與下一個8-bit數據異或並進行如前一個數據似的8次移位。所有的字元處理完成後CRC寄存器內的值即為最終的CRC值。
下面為CRC的計算過程：
1．設置CRC寄存器，並給其賦值FFFF(hex)。
2．將數據的第一個8-bit字元與16位CRC寄存器的低8位進行異或，並把結果存入CRC寄存器。
3．CRC寄存器向右移一位，MSB補零，移出並檢查LSB。
4．如果LSB為0，重復第三步；若LSB為1，CRC寄存器與多項式碼相異或。
5．重復第3與第4步直到8次移位全部完成。此時一個8-bit數據處理完畢。
6．重復第2至第5步直到所有數據全部處理完成。
7．最終CRC寄存器的內容即為CRC值。
常用的CRC循環冗餘校驗標准多項式如下：
CRC(16位) = X16+X15+X2+1
CRC(CCITT) = X16+X12 +X5+1
CRC(32位) = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1
以CRC(16位)多項式為例，其對應校驗二進制位列為1 1000 0000 0000 0101。
注意：這兒列出的標准校驗多項式都含有(X+1)的多項式因子；各多項式的系數均為二進制數，所涉及的四則運算仍遵循對二取模的運算規則。
(註：對二取模的四則運算指參與運算的兩個二進制數各位之間凡涉及加減運算時均進行XOR異或運算，即：1 XOR 1=0，0 XOR 0=0，1 XOR 0=1)

❷ 請問:CRC是什麼意思

CRC意思是循環冗餘碼校驗。

校驗原理：（M-R）/G=Q+0/G

說明：以接收到的校驗碼除以約定的除數，若余數為0，則可認為接收到的數據是正確的。

例：有效信息1101，生成多項式樣1011

循環校驗碼解：

有效信息1101（k=4），即M（x）=x3+x2+x0，生成多項式1011（r+1=4，即r=3）；

即G（x）=x3+x1+x0，M（x）·x3=x6+x5+x3，即1101000（對1101左移三位）；

M（x）·x3/G（x）=1101000/1011=1111+001/1011即1010的CRC是：1101001。

(2)crc演算法原理及實現擴展閱讀：

CRC碼集選擇的原則：

若設碼字長度為N，信息欄位為K位，校驗欄位為R位（N=K+R），則對於CRC碼集中的任一碼字，存在且僅存在一個R次多項式g（x），使得

V（x）=A（x）g（x）=xRm（x）+r（x）；

其中：m（x）為K次信息多項式，r（x）為R-1次校驗多項式，

g（x）稱為生成多項式：

g（x）=g0+g1x+g2x2+。。。+g（R-1）x（R-1）+gRxR

發送方通過指定的g（x）產生CRC碼字，接收方則通過該g（x）來驗證收到的CRC碼字。

❸ 關於計算機網路的crc計算

我們知道，一台主機向另外一台主機發送報文的時候，需要一層層經過自己的協議棧進行數據封裝，到達最後一層（四層協議的網路介面層）時需要在幀尾部添加FCS校驗碼（通過CRC演算法得出）。當對端主機收到時，在接收端同樣通過CRC演算法進行驗證，確認傳輸過程中是否出現錯誤。它只能確認一個幀是否存在比特差錯，但沒有提供解決措施。

循環冗餘校驗的原理

• 在發送端，先把數據劃分為組（即：一幀）。假定每組 k 個比特。

• 在每組後面，添加供差錯檢測用的 n 位冗餘碼一起發送。即：實際發送長度為：k+n 比特。

• 發送前雙方協商n+1位的除數P，方便接收方收到後校驗。

• 給K比特的數據添加除數減一個0（P-1）作為被除數，與第三步確定的除數做「模2除法」。得出的余數即FCS校驗序列，它的位數也必須是（P-1）。

• 將FCS校驗序列添加至K個比特位的後面發送出去。

• 接收方對接收到的每一幀進行校驗，若得出的余數 R = 0，則判定這個幀沒有差錯，就接受(accept)。若余數 R ≠ 0，則判定這個幀有差錯，就丟棄。

對「模2除法」進行說明：

「模2除法」與「算術除法」類似，但它既不向上位借位，也不比較除數和被除數的相同位數值的大小，只要以相同位數進行相除即可。模2加法運算為：1+1=0，0+1=1，0+0=0，無進位，也無借位；模2減法運算為：1-1=0，0-1=1，1-0=1，0-0=0，也無進位，無借位。相當於二進制中的邏輯異或運算。

計算示例


那麼接收方拿到的就是：101001001。再以它為被除數，1101為除數進行「模2除法」。

❹ 循環冗餘檢驗 (CRC) 演算法原理

x只是一個標記，無任何意義。主要是看數字1,5,7,8,9,12,14。分別代表第二進制碼的第0位，第5位，第7位，第8位。。。為1，其餘則為0。

❺ CRC校驗的演算法

在代數編碼理論中，將一個碼組表示為一個多項式，碼組中各碼元當作多項式的系數。例如 1100101 表示為1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即 x6+x5+x2+1。
設編碼前的原始信息多項式為P(x)，P(x)的最高冪次加1等於k；生成多項式為G(x)，G(x)的最高冪次等於r；CRC多項式為R(x)；編碼後的帶CRC的信息多項式為T(x)。
發送方編碼方法：將P(x)乘以xr(即對應的二進制碼序列左移r位)，再除以G(x)，所得余式即為R(x)。用公式表示為T(x)=xrP(x)+R(x)
接收方解碼方法：將T(x)除以G(x)，得到一個數，如果這個余數為0，則說明傳輸中無錯誤發生，否則說明傳輸有誤。
舉例來說，設信息編碼為1100，生成多項式為1011，即P(x)=x3+x2，G(x)=x3+x+1，計算CRC的過程為
xrP(x) =x3(x3+x2) = x6+x5 G(x)= x3+x+1 即 R(x)=x。注意到G(x)最高冪次r=3，得出CRC為010。
如果用豎式除法(計算機的模二，計算過程為
1110 ------- 1011 /1100000 (1100左移3位) 1011 ---- 1110 1011 ----- 1010 1011 ----- 0010 0000 ---- 010 因此，T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010
如果傳輸無誤，
T(x)= （x6+x5+x）/G(x) = , G(x)= 無余式。回頭看一下上面的豎式除法，如果被除數是1100010，顯然在商第三個1時，就能除盡。
上述推算過程，有助於我們理解CRC的概念。但直接編程來實現上面的演算法，不僅繁瑣，效率也不高。實際上在工程中不會直接這樣去計算和驗證CRC。
下表中列出了一些見於標準的CRC資料：
名稱 生成多項式 簡記式* 應用舉例
CRC-4 x4+x+1 3 ITU G.704
CRC-8 x8+x5+x4+1 31 DS18B20
CRC-12 x12+x11+x3+x2+x+1 80F
CRC-16 x16+x15+x2+1 8005 IBM SDLC
CRC-ITU** x16+x12+x5+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS,ZigBee
CRC-32 x32+x26+x23+...+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI,IEEE 1394,PPP-FCS
CRC-32c x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP
* 生成多項式的最高冪次項系數是固定的1，故在簡記式中，將最高的1統一去掉了，如04C11DB7實際上是104C11DB7。 ** 前稱CRC-CCITT。ITU的前身是CCITT。
備註：
（1）生成多項式是標准規定的
（2）CRC校驗碼是基於將位串看作是系數為0或1的多項式，一個k位的數據流可以看作是關於x的從k-1階到0階的k-1次多項式的系數序列。採用此編碼，發送方和接收方必須事先商定一個生成多項式G(x)，其高位和低位必須是1。要計算m位的幀M(x)的校驗和，基本思想是將校驗和加在幀的末尾，使這個帶校驗和的幀的多項式能被G(x)除盡。當接收方收到加有校驗和的幀時，用G(x)去除它，如果有餘數，則CRC校驗錯誤，只有沒有餘數的校驗才是正確的。

❻ 關於CRC效驗

為保證傳輸過程的正確性，需要對通信過程進行差錯控制。差錯控制最常用的方法是自動請求重發方式（ARQ）、向前糾錯方式（FEC）和混合糾錯（HEC）。在傳輸過程誤碼率比較低時，用FEC方式比較理想。在傳輸過程誤碼率較高時，採用FEC容易出現「亂糾」現象。HEC方式則是ARQ和FEC的結合。在許多數字通信中，廣泛採用ARQ方式，此時的差錯控制只需要檢錯功能。實現檢錯功能的差錯控制方法很多，傳統的有：奇偶校驗、校驗和檢測、重復碼校驗、恆比碼校驗、行列冗餘碼校驗等，這些方法都是增加數據的冗餘量，將校驗碼和數據一起發送到接受端。接受端對接受到的數據進行相同校驗，再將得到的校驗碼和接受到的校驗碼比較，如果二者一致則認為傳輸正確。但這些方法都有各自的缺點，誤判的概率比較高。
循環冗餘校驗CRC（Cyclic Rendancy Check）是由分組線性碼的分支而來，其主要應用是二元碼組。編碼簡單且誤判概率很低，在通信系統中得到了廣泛的應用。下面重點介紹了CRC校驗的原理及其演算法實現。

CRC校驗可以100％地檢測出所有奇數個隨機錯誤和長度小於等於k（k為g（x）的階數）的突發錯誤。所以CRC的生成多項式的階數越高，那麼誤判的概率就越小。

CRC代碼的一些基本概念和運算：

CRC多項式：

例：

代碼：1010111 對應的多項式為：X6+X4+X2+X+1

多項式X5+X3+X2+X1+1對應的代碼為101111

CRC生成多項式:

首位和最後一位必須是1。CRC生成多項式是給定的，在傳輸過程中不變，即發送和接收端生成碼相同。

一些常用的校驗碼為：

CRC8=X8+X5+X4+1

CRC-CCITT=X16+X12+X5+1

CRC16=X16+X15+X5+1

CRC12=X12+X11+X3+X2+1

CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

CRC的運算本質是異或運算（模2除法）

例：原信息碼為1011001

生成碼為11001

校驗碼計算過程

① 將信息碼左移4位（生成碼長-1）；得到10110010000

② 異或運算

10110010000

11001

01111010000（前面的數進行異或運算，後面的直接抄下來）

11001

0011110000（和生成碼異或運算的必須從1開始）

11001

00111000

11001

001010

這樣得到的結果為1010，即為所需要的校驗碼，添加到信息碼後，得到發送的代碼為:

10110011010

我把上面的手算過程用c#寫了一段程序，如下：

using System;

namespace mainClass
{
public class mainProgress
{
public static void Main()
{
byte[] msg={1,0,1,1,0,0,1};//信息碼
byte[] gmsg=new byte[msg.Length+4];
crc c = new crc();
gmsg=c.code(msg);
Console.Write("編碼後字元串為：");
for (int i = 0; i < gmsg.Length; i++)
{
Console.Write("{0}", gmsg[i].ToString());
}
Console.Write("\n");
byte[] gmsg1={ 1, 0, 1, 1, 0, 1, 1 };//接收到的代碼
bool r = c.det(gmsg1);
if (r)
{
Console.WriteLine("傳輸正確");
}
else
{ Console.WriteLine("傳輸錯誤"); }
}
}

public class crc//CRC編碼類
{
private byte[] g = { 1,1,0,0,1};//生成碼
public byte[] code(byte[] msg)//編碼
{
byte[] gmsg=new byte[g.Length+msg.Length-1];
msg.CopyTo(gmsg, 0);//
for (int i = 0; i < msg.Length; i++)//完成異或運算，即模2除法
{
if (gmsg[i] == 1)
{
for (int j = 0; j < g.Length; j++)
{
if (gmsg[i + j] == g[j])
gmsg[i + j] = 0;
else
gmsg[i + j] = 1;
}
}
}
msg.CopyTo(gmsg, 0);
return gmsg;
}
private bool f=true;

//接收端檢測
public bool det(byte[] gmsg)
{
for (int i = 0; i < gmsg.Length - g.Length+1; i++)
{
if(gmsg[i]==0)
continue;
for (int j = 0; j < g.Length; j++)
{
if (gmsg[i + j] == g[j])
gmsg[i + j] = 0;
else
gmsg[i + j] = 1;
}
}
for (int i = 0; i < gmsg.Length; i++)
{
if (gmsg[i] == 1)
f = false;
}
return f;
}

}
}

❼ 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)得到的余數就是校驗碼。
任意一個由二進制位串組成的代碼都可以和一個系數僅為『0』和『1』取值的多項式一一對應。例如：代碼1010111對應的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應的代碼101111。

❽ crc32演算法原理

一、循環冗餘碼校驗英文名稱為Cyclical Rendancy Check,簡稱CRC.
它是利用除法及余數的原理來作錯誤偵測（Error Detecting）的.實際應用時,發送裝置計算出CRC值並隨數據一同發送給接收裝置,接收裝置對收到的數據重新計算CRC並與收到的CRC相比較,若兩個CRC值不同,則說明數據通訊出現錯誤.
根據應用環境與習慣的不同,CRC又可分為以下幾種標准：
①CRC-12碼；
②CRC-16碼；
③CRC-CCITT碼；
④CRC-32碼.
CRC-12碼通常用來傳送6-bit字元串.
CRC-16及CRC-CCITT碼則用是來傳送8-bit字元,其中CRC-16為美國採用,而CRC-CCITT為歐洲國家所採用.
CRC-32碼大都被採用在一種稱為Point-to-Point的同步傳輸中.
下面以最常用的CRC-16為例來說明其生成過程.
CRC-16碼由兩個位元組構成,在開始時CRC寄存器的每一位都預置為1,然後把CRC寄存器與8-bit的數據進行異或(異或：二進制運算 相同為0,不同為1；0^0=0;0^1=1;1^0=1;1^1=0),
之後對CRC寄存器從高到低進行移位,在最高位（MSB）的位置補零,而最低位（LSB,移位後已經被移出CRC寄存器）如果為1,則把寄存器與預定義的多項式碼進行異或,否則如果LSB為零,則無需進行異或.重復上述的由高至低的移位8次,第一個8-bit數據處理完畢,用此時CRC寄存器的值與下一個8-bit數據異或並進行如前一個數據似的8次移位.所有的字元處理完成後CRC寄存器內的值即為最終的CRC值.
下面為CRC的計算過程：
1．設置CRC寄存器,並給其賦值FFFF(hex).
2．將數據的第一個8-bit字元與16位CRC寄存器的低8位進行異或,並把結果存入CRC寄存器.
3．CRC寄存器向右移一位,MSB補零,移出並檢查LSB.
4．如果LSB為0,重復第三步；若LSB為1,CRC寄存器與多項式碼相異或.
5．重復第3與第4步直到8次移位全部完成.此時一個8-bit數據處理完畢.
6．重復第2至第5步直到所有數據全部處理完成.
7．最終CRC寄存器的內容即為CRC值.
常用的CRC循環冗餘校驗標准多項式如下：
CRC(16位) = X16+X15+X2+1
CRC(CCITT) = X16+X12 +X5+1
CRC(32位) = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1
以CRC(16位)多項式為例,其對應校驗二進制位列為1 1000 0000 0000 0101.
注意：這兒列出的標准校驗多項式都含有(X+1)的多項式因子；各多項式的系數均為二進制數,所涉及的四則運算仍遵循對二取模的運算規則.
(註：對二取模的四則運算指參與運算的兩個二進制數各位之間凡涉及加減運算時均進行XOR異或運算,即：1 XOR 1=0,0 XOR 0=0,1 XOR 0=1,0 XOR 1=1,即相同為0,不同為1)

❾ crc電路原理

CRC(Cyclic Rendancy Check)被廣泛用於數據通信過程中的差錯檢測，具有很強的
檢錯能力。本文詳細介紹了CRC的基本原理，並且按照解釋通行的查表演算法的由來的思路介紹
了各種具體的實現方法。
1.差錯檢測
數據通信中，接收端需要檢測在傳輸過程中是否發生差錯，常用的技術有奇偶校驗(Parity
Check)，校驗和(Checksum)和CRC(Cyclic Rendancy Check)。它們都是發送端對消息按照
某種演算法計算出校驗碼，然後將校驗碼和消息一起發送到接收端。接收端對接收到的消息按
照相同演算法得出校驗碼，再與接收到的校驗碼比較，以判斷接收到消息是否正確。
奇偶校驗只需要1位校驗碼，其計算方法也很簡單。以奇檢驗為例，發送端只需要對所有消息
位進行異或運算，得出的值如果是0，則校驗碼為1，否則為0。接收端可以對消息進行相同計
算，然後比較校驗碼。也可以對消息連同校驗碼一起計算，若值是0則有差錯，否則校驗通過。
通常說奇偶校驗可以檢測出1位差錯，實際上它可以檢測出任何奇數位差錯。
校驗和的思想也很簡單，將傳輸的消息當成8位(或16/32位)整數的序列，將這些整數加起來
而得出校驗碼，該校驗碼也叫校驗和。校驗和被用在IP協議中，按照16位整數運算，而且其
MSB(Most Significant Bit)的進位被加到結果中。
顯然，奇偶校驗和校驗和都有明顯的不足。奇偶校驗不能檢測出偶數位差錯。對於校驗和，
如果整數序列中有兩個整數出錯，一個增加了一定的值，另一個減小了相同的值，這種差錯
就檢測不出來。
2.CRC演算法的基本原理
-------------------
CRC演算法的是以GF(2)(2元素伽羅瓦域)多項式算術為數學基礎的，聽起來很恐怖，但實際上它
的主要特點和運算規則是很好理解的。
GF(2)多項式中只有一個變數x，其系數也只有0和1，如：
1*x^7 + 0*x^6 + 1*x^5 + 0*x^4 + 0*x^3 + 1*x^2 +1*x^1 + 1*x^0
即：
x^7 + x^5 + x^2 + x + 1
(x^n表示x的n次冪)
GF(2)多項式中的加減用模2算術執行對應項上系數的加減，模2就是加減時不考慮進位和借位，
即：
0 + 0 = 0 0 - 0 = 0
0 + 1 = 1 0 - 1 = 1
1 + 0 = 1 1 - 0 = 1
1 + 1 = 0 1 - 1 = 0
顯然，加和減是一樣的效果(故在GF(2)多項式中一般不出現"-"號)，都等同於異或運算。例
如P1 = x^3 + x^2 + 1，P2 = x^3 + x^1 + 1，P1 + P2為：
x^3 + x^2 + 1
+x^3 + x + 1
------------------------------
x^2 + x
GF(2)多項式乘法和一般多項式乘法基本一樣，只是在各項相加的時候按模2算術進行，例如
P1 * P2為：
(x^3 + x^2 + 1)(x^3 + x^1 + 1)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x + 1)
= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
GF(2)多項式除法也和一般多項式除法基本一樣，只是在各項相減的時候按模2算術進行，例
如P3 = x^7 + x^6 + x^5 + x^2 + x，P3 / P2為：
x^4 + x^3 + 1
--------------------------------------------------------------
x^3 + x + 1 )x^7 + x^6 + x^5 + x^2 + x
x^7 + x^5 + x^4
-----------------------------------

❿ 請教查表法計算CRC的原理

1）將上次計算出的CRC校驗碼右移一個位元組；
（2）將移出的這個位元組與新的要校驗的位元組進行XOR 運算；
（3）用運算出的值在預先生成碼表中進行索引，獲取對應的值（稱為余式）；
（4）用獲取的值與第（1）步右移後的值進行XOR 運算；
（5）如果要校驗的數據已經處理完，則第（4）步的結果就是最終的CRC校驗碼。如果還有數據 要進行處理，則再轉到第（1）步運行。
CRC32=CRC_32_Tbl[(CRC32^((unsigned__int8*)p)[i])&0xff]^(CRC32>>8);
怎麼樣？簡單吧。