標題: 循環冗余校驗碼 [打印本頁]
作者: liuyy 時間: 2015-1-12 02:11
標題: 循環冗余校驗碼
在串行傳送（磁盤、通訊）中，廣泛采用循環冗余校驗碼（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所示：
N | K | 碼距d | G(x)多項式 | G(x) |
7 | 4 | 3 | | 1011 |
7 | 4 | 3 | | 1101 |
7 | 3 | 4 | | 11101 |
7 | 3 | 4 | | 10111 |
15 | 11 | 3 | | 10011 |
15 | 7 | 5 | | 111010001 |
31 | 26 | 3 | | 100101 |
31 | 21 | 5 | | |
63 | 57 | 3 | | |
63 | 51 | 5 | | |
1041 | 1024 | | | |
圖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)（碼字），只會改變表中碼字內容，不改變余數與出錯位的對應關系。
| | 余數 | 出錯位 |
碼位 | |
正確 | | 000 | 無 |
錯 誤
| | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| | |
圖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://www.zg4o1577.cn/bbs/) |
Powered by Discuz! X3.1 |
主站蜘蛛池模板：
www.日日夜夜
|
日韩av福利在线观看
|
日韩欧美在线观看
|
欧美日韩大片
|
午夜视频一区二区三区
|
久久精品这里
|
成人一区精品
|
中文字幕在线观
|
国产精品av久久久久久毛片
|
亚洲欧美国产精品一区二区
|
国产精品久久在线观看
|
天天躁日日躁狠狠躁白人
|
国产高清在线精品一区二区三区
|
精品视频在线观看
|
一区二区三区播放
|
亚洲一区二区在线
|
欧美日韩精品免费观看
|
欧美一级大黄
|
国产黄色免费网站
|
国产精品二区三区
|
国产99热
|
亚洲一区二区av
|
一级黄色绿像片
|
成人永久免费视频
|
青青草精品|
中国人pornoxxx麻豆
|
一区二区在线不卡
|
亚洲免费视频在线观看
|
日本一区二区三区在线观看
|
欧美一区二区三区
|
aa级毛片毛片免费观看久
|
亚洲精品乱码久久久久久黑人
|
亚洲成年影院
|
日本亚洲欧美
|
久久久网|
国产免费一区
|
日皮视频免费
|
网络毛片
|
伊人久久大香线
|
在线看黄免费
|
国产精品看片
|