循環冗餘碼

循環冗餘碼,又名多項式編碼(polynomial code),也稱CRC(Cyclic Redundancy Check).在傳送端產生一個循環冗餘碼,附加在信息位後面一起傳送到接收端,接收端收到的信息按傳送端形成循環冗餘碼同樣的算法進行校驗,若有錯,需重發。

循環冗餘編碼
循環冗餘編碼又名多項式編碼(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)可檢測出所有小於、等於校驗位長度的突發錯。

相關詞條

相關搜尋

熱門詞條

聯絡我們