1、08:11:06,1,第 3.6節(jié),數(shù)據(jù)校驗碼,08:11:06,2,奇偶校驗碼的校驗方法，應(yīng)用場合。 循環(huán)冗余校驗碼(CRC)的編碼、譯碼方法、應(yīng)用場合。,奇偶校驗碼；循環(huán)冗余校驗碼。（）,教學(xué)內(nèi)容,掌握重點,08:11:06,3,數(shù)據(jù)校驗碼：是一種常用的帶有發(fā)現(xiàn)某些錯誤或自動改錯能力的數(shù)據(jù)編碼方法。 編碼系統(tǒng)的碼距：一個編碼系統(tǒng)中任意兩個合法編碼（碼字）之間最少變化的二進(jìn)制位數(shù)（bit）,稱為這個編碼系統(tǒng)的碼字的碼距。 即:整個編碼系統(tǒng)中任意兩個碼字的的最小距離。,一、基本理論,3.6 數(shù)據(jù)校驗碼,08:11:06,4,兩個碼字最小值為1，故這個系統(tǒng)的碼距為1。 如果任何碼字中一位或多位被

2、顛倒了，結(jié)果這個碼字就不能與其它有效信息區(qū)分開。,例如 如果傳送信息為001，誤接收的信息為011. 會被認(rèn)為是合法的碼字?,如圖所示的編碼系統(tǒng),3.6 數(shù)據(jù)校驗碼,08:11:06,5,碼字間的最小距離可以增加到2。在這個系統(tǒng)中， 偶數(shù)個（2或4）差錯無法發(fā)現(xiàn)。,為使一個系統(tǒng)能檢查和糾正一個差錯,碼間最小距離必須至少是“3”.,例如 如果傳送信息是1001，誤收為1011,接收機發(fā)生了一個差錯，但無法糾正。假定只有一個數(shù)位是錯的, 可能的正確碼字有哪些?,如圖所示的編碼系統(tǒng),正確碼字可以是: 1001，1111，0011或1010。,3.6 數(shù)據(jù)校驗碼,08:11:06,6,碼距2的數(shù)據(jù)校驗

3、碼，開始具有檢錯能力；為了使一個系統(tǒng)能檢查和糾正一個差錯,碼間最小距離必須至少是3。碼距越大，檢錯糾錯能力就越強，但數(shù)據(jù)冗余也越大，編碼效率低。碼距的選擇要取決于特定系統(tǒng)的參數(shù)。,3.6 數(shù)據(jù)校驗碼,08:11:06,7,通過函數(shù)f 對數(shù)據(jù)進(jìn)行計算，以產(chǎn)生一種代碼， 代碼和數(shù)據(jù)都被存儲，如果原數(shù)據(jù)字長為M位， 校驗碼長為K位，則實際存儲的字長應(yīng)為M+K位。 加進(jìn)冗余碼，當(dāng)合法數(shù)據(jù)編碼出現(xiàn)某些錯誤時， 就成為非法編碼。這樣，就可以通過檢測編碼 的合法性來達(dá)到發(fā)現(xiàn)錯誤的目的。,二、實現(xiàn)原理,3.6 數(shù)據(jù)校驗碼,08:11:06,8,當(dāng)原先存儲的字讀出時，這個代碼用于檢錯和糾 錯，在M位數(shù)據(jù)中產(chǎn)生一

4、組新的K位代碼，與取出 的代碼進(jìn)行比較： 結(jié)果一致，無差錯，取出的數(shù)據(jù)位傳送出去； 檢測到差錯，并可以糾正，數(shù)據(jù)位和糾錯位一 起送入糾正器，然后產(chǎn)生一組正確的M位數(shù)據(jù)位； 檢測到差錯，但無法糾正，報告出錯。,二、實現(xiàn)原理,3.6 數(shù)據(jù)校驗碼,08:11:06,9,3.6.1 奇偶校驗碼,一、奇偶校驗碼的特點 開銷最?。辉黾佣M(jìn)制傳輸系統(tǒng)最小距離的簡單和廣泛采用的方法； 適用于并行數(shù)據(jù)傳送； 碼距為2，可以檢測1位錯誤（或奇數(shù)位錯誤）。但不能確定是哪一位錯,也不能發(fā)現(xiàn)偶數(shù)個位錯。 常用于存儲器讀寫檢查，或ASCII字符傳送過程中的檢查。,08:11:06,10,二、奇偶校驗碼的編碼方法,不管數(shù)據(jù)

5、位長度多少，校驗位只有一位。 奇校驗:數(shù)據(jù)位和校驗位一起所含“1”的 個數(shù)為奇數(shù)。 偶校驗:數(shù)據(jù)位和校驗位一起所含“1”的 個數(shù)為偶數(shù)。 校驗:對奇校驗，如接收端收到是偶碼， 表示傳送有誤，因此可發(fā)現(xiàn)一位錯(奇位錯)。,08:11:06,11,例 數(shù)據(jù) 奇校驗的編碼 偶校驗的編碼 00000000 100000000 000000000 01010100 001010100 101010100 01111111 001111111 101111111,08:11:06,12,三、實現(xiàn)原理 使碼距由1增加到2。通常是為一個字節(jié)補充一個二進(jìn)制位（稱為校驗位）； 設(shè)置校驗位的值為0或1，使字節(jié)的8位

6、和該校驗位含有1值的個數(shù)為奇數(shù)或偶數(shù)。 進(jìn)行校驗時用奇校驗或偶校驗。依據(jù)8位的數(shù)據(jù)位中1值的個數(shù)確定校驗位的值；,08:11:06,13,四、實現(xiàn)方式,D7 D6 D5 D4 D3 D2 D1 D0 D校,偶校驗位形成 =D0D1D2D7 奇校驗位形成 =NOT（D0D1D2D7） 偶校驗出錯 =D0D1D2D7 D校 奇校驗出錯=NOT（D0D1D2D7D校,奇性檢測等效于所有碼字的模二加， 并能夠由所有碼字的異或運算來確定。 奇偶校驗位可由硬件電路（異或門）產(chǎn)生：,08:11:06,14,五、分組奇偶校驗碼,實際中經(jīng)常采用縱橫都加校驗的奇偶校驗位的編碼系統(tǒng)-分組奇偶校驗碼(交叉奇偶校驗)。

7、 某一個系統(tǒng)，它傳輸若干個長度為m位的信息。如果把這些信息都編成每組n個信息的分組，則在這些不同的信息間，也如對單個信息一樣，能夠作奇偶校驗。 n個信息分組排列成矩形式樣，以橫向奇偶（HP）及縱向奇偶（VP）的形式編出奇偶校驗位。,08:11:06,15,縱橫奇偶校驗的分組奇偶校驗碼,結(jié)論：分組奇偶校驗碼不僅能檢測許多形式的錯誤。并且在給定的行或列中產(chǎn)生孤立的錯誤時，還可對該錯誤進(jìn)行糾正。,例由 6 個字符的 7 位 ASCII 編碼排列，再加上水平垂直奇偶校驗位構(gòu)成下列矩陣,求:1）X1 X2 X3 X4 ; X5 X6 X7 X8; X9 X10 X11 X12的比特分別為 _ 2）Y1

8、和 Y2 處的字符分別為 _ 和 _。,1）X1X2X3X4 = 1110;X5X6X7X8 = 1000;X9X10X11X12 = 1011 2）字符Y1的ASCII碼49H,Y1即是“I”(“D”的ASCII碼是44H); 字符Y2的ASCII碼37H, Y2即是“7”(“3”的ASCII碼是33H）,“A”的ASCII碼是41H “0”的ASCII碼是30H,08:11:06,17,3.6.3 循環(huán)冗余校驗(CRC)碼,一、循環(huán)冗余校驗(CRC)碼的特點： CRC碼可以發(fā)現(xiàn)并糾正信息串行讀寫、存儲或傳送過程中出現(xiàn)的一位、多位錯誤；檢錯能力極強; 適用于串行數(shù)據(jù)傳送（磁盤、通訊） ； 在

9、磁介質(zhì)存儲器讀寫和計算機之間通信方面得到廣泛應(yīng)用。 開銷小，易于用編碼器及檢測電路實現(xiàn)。,08:11:06,18,在K位信息碼后再拼接R位的校驗碼，整個編碼長度 為N位，因此，這種編碼又叫（N，K）碼。 校驗碼的基本原理： 發(fā)送信息用信息多項式C(X)表示， 將C(x)左移R位，則可表示成C(x)*XR，這樣C(x)的右邊就會空出R位，這就是校驗碼的位置。 通過C(x)*XR除以生成多項式G(x)得到的余數(shù)就是校驗碼。,編碼組成:,二、循環(huán)冗余校驗碼基本原理,3.6.3 循環(huán)冗余校驗(CRC)碼,08:11:06,19,三、多項式與二進(jìn)制數(shù)碼的關(guān)系,多項式包括：G(x)和C(x)。 它們與二進(jìn)

10、制數(shù)碼的直接對應(yīng)關(guān)系為： x的最高冪次對應(yīng)二進(jìn)制數(shù)的最高位， 以下各位對應(yīng)多項式的各冪次； 有此冪次項對應(yīng)1，無此冪次項對應(yīng)0。 x的最高冪次為R,轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)有R+1位。,3.6.3 循環(huán)冗余校驗(CRC)碼,例 生成多項式為G(x)=x4+x3+x+1， 可轉(zhuǎn)換為二進(jìn)制數(shù)碼為11011。 發(fā)送信息位 1111轉(zhuǎn)換為數(shù)據(jù)多項式為： C(x)=x3+x2+x+1。,08:11:06,20,常用的對應(yīng)于不同碼制的生成多項式,08:11:06,21,四、生成多項式,生成多項式是接受方和發(fā)送方的一個約定，也是一個二進(jìn)制數(shù)，在整個傳輸過程中，這個數(shù)始終保持不變。 發(fā)送方：利用生成多項式對信息多

11、項式做 模2除生成校驗碼。 在接受方：利用生成多項式對收到的編碼 多項式做模2除檢測和確定錯誤位置。,3.6.3 循環(huán)冗余校驗(CRC)碼,08:11:06,22,3.6.3 循環(huán)冗余校驗(CRC)碼,生成多項式： 對于一個給定的（N，K）碼，生成多項式G(x) 最高次冪為R= N-K ； 根據(jù)G(x)可以生成K位信息的校驗碼，而G(x) 叫做這個CRC碼的生成多項式。,08:11:06,23,五、CRC碼的編碼方法,模：計量器的容量（M表示） 例4位二進(jìn)制數(shù),從0-15,再加1,記數(shù)值又為0， 故：M=24=16 模2運算：指以按位模2相加為基礎(chǔ)的四則運算， 運算時不考慮進(jìn)位和借位。 (1)

12、模2加減（按位加，可用異或邏輯實現(xiàn)） 0土0=0，0土11，1土01，1土10。 兩個相同的數(shù)據(jù)的模2和為0。,3.6.3 循環(huán)冗余校驗(CRC)碼,08:11:06,24,0.1010 101,1010 0000 1010,100010,(2)模2乘 按模2加求部分積之和。,3.6.3 循環(huán)冗余校驗(CRC)碼,08:11:06,25,例 11110001101,1111000,010,1,0,1101,1101,0,1,0000,100,0,1,1101,1010,111,(3)模2除,1101,商=1011；余數(shù)=111,按模2減求部分余數(shù)。 每求一位商應(yīng)使部分 余數(shù)減少一位。,08:1

13、1:06,26,六、CRC碼的生成步驟,1、將x的最高冪次為R的生成多項式G(x) 轉(zhuǎn)換成對應(yīng)的R+1位二進(jìn)制數(shù)。 2、將信息碼左移R位，相當(dāng)與對應(yīng)的信息 多項式C(x)*2R 。 3、C(x)*2R/G(X)的二進(jìn)制數(shù)（做模2除）， 得到R位的余數(shù)。 4、將余數(shù)拼到信息碼左移后空出的位置， 得到完整的CRC碼。,3.6.3 循環(huán)冗余校驗(CRC)碼,08:11:06,27,【例】假設(shè)使用的生成多項式是G(x)=x3+x+1。 4位的原始報文為1010，求編碼后的報文。,3.6.3 循環(huán)冗余校驗(CRC)碼,解： 1、將生成多項式G(x)轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)1011。,2、生成多項式有4位（R

14、+1），要把原始報文C(x) 左移3位（R）變成1010000,3、C(X)*24G(X) = 10100001011 1001-商 011-余數(shù)（校驗位）,08:11:06,28,出錯模式改變了C(x)（碼字），只會改變表中碼字內(nèi)容，不改變余數(shù)與出錯位的對應(yīng)關(guān)系。,例已知G(x)=1011， C(x)=1010,08:11:06,29,七.糾錯方法,例第一位出錯，余數(shù)為001，依次補0作模2除得到余數(shù)為：010，100，0ll，反復(fù)循環(huán)。 如果循環(huán)碼有1位出錯，如果對余數(shù)補0用G(x)作模2除，將得到一個不為0的余數(shù)。 一個有趣的結(jié)果：各次余數(shù)將按上頁圖順序循環(huán) 根據(jù)不同的余數(shù)來糾正不同的出

15、錯位,當(dāng)最高位變成101時（出錯位移到A6),則最高位取反糾錯。,3.6.3 循環(huán)冗余校驗(CRC)碼,08:11:06,30,結(jié)論 生成多項式應(yīng)滿足的條件,生成多項式的最高位和最低位必須為1。 當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯誤時， 被生成多項式做模2除后應(yīng)該使余數(shù)不為0。 不同位發(fā)生錯誤時，應(yīng)該使余數(shù)不同。 對余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。,3.6.3 循環(huán)冗余校驗(CRC)碼,08:11:06,31,在國際標(biāo)準(zhǔn)中，根據(jù)生成多項式G(x)的不同，CRC又可分為以下幾種標(biāo)準(zhǔn)： CRC-12碼: G(x)=X12+X11+X3+X2+X+1 CRC-16碼: G(x)=X16+X15+

16、X2+1 CRC-CCITT碼: G(x)=X16+X12+X5+1 CRC-32碼: G(x)=X32+X26+X23+X22+X16+X12+X11 +X10+ X8+X7+X5+X4+X2+X+1,八、通信與網(wǎng)絡(luò)中常用的CRC,3.6.3 循環(huán)冗余校驗(CRC)碼,08:11:06,32,八、通信與網(wǎng)絡(luò)中常用的CRC,突發(fā)錯誤：幾乎是連續(xù)發(fā)生的一串錯，突發(fā)長度 就是指從出錯的第一位到出錯的最后一位的長度。,3.6.3 循環(huán)冗余校驗(CRC)碼,標(biāo)準(zhǔn)的16位生成多項式CRC-16x16+x15+x2+1 一般情況下，對r=16的情況，就能檢測出所有突發(fā)長度小于等于16的突發(fā)錯以及99997%的突發(fā)長度為17的突發(fā)錯和99998%的突發(fā)長度大于17的突發(fā)錯。,【思考題】某CRC碼的生成多項式 G(x)x3+x2+1,用此生成多項式產(chǎn)生的冗余位，加在信息位后形成 CRC 碼。若發(fā)送信息位 1111 和 1100 則它的 CRC 碼分別為A和B。由于某種原因，使接收端收到了按某種規(guī)律可判斷為出錯的 CRC 碼，例如碼字C、D、和E,解： A：G(x)1101，C(x)1111 C(x)*23G(x)111100011011011余111 得到的CRC碼為1111111 B：G(x)1101，C(x)1100 C(x)*23G(x)11000001