循環冗餘編碼

循環冗餘編碼又名多項式編碼（polynomial code）,也稱CRC(Cyclic Redundancy Check).

CRC的工作方法

在發送端產生一個循環冗餘碼，附加在信息位後面一起發送到接收端，接收端收到的信息按發送端形成循環冗餘碼同樣的算法進行校驗，

若有錯，需重發。

2.循環冗餘碼的產生與碼字正確性檢驗例子。

CRC校驗碼的算法分析

CRC校驗碼的編碼方法是用待發送的二進制數據t（x）除以生成多項式g（x），將最後的餘數作為CRC校驗碼。

其實現步驟如下：

（1） 設待發送的數據塊是m位的二進制多項式t（x），（2） 生成多項式為r階的g（x）。在數據塊的末尾添加r個0，（3） 數據塊的長度增加到m+r位，（4） 對應的二進制多項式為 。

（5） 用生成多項式g（x）去除 ，（6） 求得餘數為階數為r-1的二進制多項式y（x）。此二進制多項式y（x）就是t（x）經過生成多項式g（x）編碼的CRC校驗碼。

（7） 用 以模2的方式減去y（x），（8） 得到二進制多項式 。 就是包含了CRC校驗碼的待發送字符串。

從CRC的編碼規則可以看出，CRC編碼實際上是將代發送的m位二進制多項式t（x）轉換成了可以被g（x）除盡的m+r位二進制多項式 ，所以解碼時可以用接受到的數據去除g（x），如果餘數位零，則表示傳輸過程沒有錯誤；如果餘數不為零，則在傳輸過程中肯定存在錯誤。許多CRC的硬件解碼電路就是按這種方式進行檢錯的。同時 可以看做是由t（x）和CRC校驗碼的組合，所以解碼時將接收到的二進制數據去掉尾部的r位數據，得到的就是原始數據。

為了更清楚的瞭解CRC校驗碼的編碼過程，下面用一個簡單的例子來説明CRC校驗碼的編碼過程。由於CRC-32、CRC-16、CCITT和CRC-4的編碼過程基本一致，只有位數和生成多項式不一樣。

3.循環冗餘碼的工作原理

循環冗餘碼CRC在發送端編碼和接收端校驗時，都可以利用事先約定的生成多項式G(X)來得到，K位要發送的信息位可對應於一個(k-1)

次多項式K(X),r位冗餘位則對應於一個(r-1)次多項式R(X)，由r位冗餘位組成的n=k+r位碼字則對應於一

個(n-1)次多項式T(X)=Xr*K(X)+R(X)。

4.循環冗餘校驗碼的特點

（1）可檢測出所有奇數位錯；

（2）可檢測出所有雙比特的錯；

（3）可檢測出所有小於、等於校驗位長度的突發錯。