各種校驗(yàn)碼校驗(yàn)算法分析

1、各種校驗(yàn)碼校驗(yàn)算法分析 二進(jìn)制數(shù)據(jù)經(jīng)過(guò)傳送、存取等環(huán) 節(jié)會(huì)發(fā)生誤碼 1變成 0或 0變成 1這就有如何發(fā)現(xiàn)及糾正誤 碼的問(wèn)題。所有解決此類(lèi)問(wèn)題的方法就是在原始數(shù)據(jù)數(shù)碼位 基礎(chǔ)上增加幾位校驗(yàn)冗余位。一、碼距 一個(gè)編碼系統(tǒng)中任意兩個(gè)合法編碼碼字之間不同 的二進(jìn)數(shù)位 bit 數(shù)叫這兩個(gè)碼字的碼距而整個(gè)編碼系統(tǒng)中任 意兩個(gè)碼字的的最小距離就是該編碼系統(tǒng)的碼距。 如圖 1所示的一個(gè)編碼系統(tǒng)用三個(gè) bit 來(lái)表示八個(gè)不同信息中。在 這個(gè)系統(tǒng)中兩個(gè)碼字之間不同的 bit 數(shù)從 1到 3不等但最小 值為 1故這個(gè)系統(tǒng)的碼距為 1。如果任何碼字中一位或多位 被顛倒了結(jié)果這個(gè)碼字就不能與其它有效信息區(qū)分開(kāi)。例如

2、如果傳送信息 001而被誤收為 011因 011仍是表中的合法碼 字接收機(jī)仍將認(rèn)為 011是正確的信息。 然而如果用四個(gè)二 進(jìn)數(shù)字來(lái)編 8個(gè)碼字那么在碼字間的最小距離可以增加到 2如圖 2的表中所示。 信息序號(hào) 二進(jìn)碼字 a2 a1 a0 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 圖 1 信息序號(hào) 二進(jìn)碼字 a3 a2 a1 a0 0 0 0 0 0 1 1 0 0 1 2 1 0 1 0 3 0 0 1 1 4 1 1 0 0 5 0 1 0 1 6 0 1 1 0 7 1 1 1 1 圖 2 注意圖 8-

3、2的 8個(gè)碼字相互間最少有兩 bit 的差異。因此如果任何信息的一個(gè)數(shù)位被顛倒就成為一個(gè)不 用的碼字接收機(jī)能檢查出來(lái)。例如信息是 1001誤收為 1011接收機(jī)知道發(fā)生了一個(gè)差錯(cuò)因?yàn)?1011不是一個(gè)碼字表中沒(méi)有。然而差錯(cuò)不能被糾正。假定只有一個(gè)數(shù)位是錯(cuò)的正確碼 字可以是 100111110011或 1010。接收者不能確定原來(lái)到底 是這 4個(gè)碼字中的那一個(gè)。 也可看到 在這個(gè)系統(tǒng)中偶數(shù)個(gè) 2或 4差錯(cuò)也無(wú)法發(fā)現(xiàn)。 為了使一個(gè)系統(tǒng)能檢查和糾正一個(gè) 差錯(cuò)碼間最小距離必須至少是“3”。最小距離為 3時(shí)或能 糾正一個(gè)錯(cuò)或能檢二個(gè)錯(cuò)但不能同時(shí)糾一個(gè)錯(cuò)和檢二個(gè)錯(cuò)。 編碼信息糾錯(cuò)和檢錯(cuò)能力的進(jìn)一步提高需要

4、進(jìn)一步增加碼 字間的最小距離。 圖 8-3的表概括了最小距離為 1至 7的 碼的糾錯(cuò)和檢錯(cuò)能力。 碼距 碼 能 力 檢錯(cuò) 糾錯(cuò) 1 2 3 4 5 6 7 0 0 1 0 2 或 1 2 加 1 2 加 2 3 加 2 3 加 3 圖 3 碼距越大糾錯(cuò)能力越強(qiáng)但數(shù)據(jù)冗余也越大即編碼效率低了。 所以選擇碼距要取決于特定系統(tǒng)的參數(shù)。數(shù)字系統(tǒng)的設(shè)計(jì)者 必須考慮信息發(fā)生差錯(cuò)的概率和該系統(tǒng)能容許的最小差錯(cuò) 率等因素。要有專(zhuān)門(mén)的研究來(lái)解決這些問(wèn)題。二、奇偶校驗(yàn) 奇偶校驗(yàn)碼是一種增加二進(jìn)制傳輸系統(tǒng)最小 距離的簡(jiǎn)單和廣泛采用的方法。例如單個(gè)的奇偶校驗(yàn)將使碼 的最小距離由一增加到二。 一個(gè)二進(jìn)制碼字如果它的碼元

5、 有奇數(shù)個(gè) 1就稱(chēng)為具有奇性。例如碼字“10110101”有五個(gè) 1因此這個(gè)碼字具有奇性。同樣偶性碼字具有偶數(shù)個(gè) 1。注 意奇性檢測(cè)等效于所有碼元的模二加并能夠由所有碼元的 異或運(yùn)算來(lái)確定。對(duì)于一個(gè) n 位字奇性由下式給出 奇性 a0 a1 a2 an 奇偶校驗(yàn)可描述為給每一個(gè)碼字加一個(gè)校驗(yàn)位用它來(lái)構(gòu)成奇性或偶性校驗(yàn)。例如在圖 8-2中就是這 樣做的?？梢钥闯龈郊哟a元 d2是簡(jiǎn)單地用來(lái)使每個(gè)字成為 偶性的。因此若有一個(gè)碼元是錯(cuò)的就可以分辨得出因?yàn)槠媾?校驗(yàn)將成為奇性。奇偶校驗(yàn)編碼通過(guò)增加一位校驗(yàn)位來(lái)使編 碼中 1個(gè)個(gè)數(shù)為奇數(shù)奇校驗(yàn)或者為偶數(shù)偶校驗(yàn)從而使碼距變 為 2。因?yàn)槠淅玫氖蔷幋a中 1的

6、個(gè)數(shù)的奇偶性作為依據(jù)所 以不能發(fā)現(xiàn)偶數(shù)位錯(cuò)誤。 再以數(shù)字 0的七位 ASCII 碼 0110000為例如果傳送后右邊第一位出錯(cuò) 0變成 1。接收端 還認(rèn)為是一個(gè)合法的代碼 0110001數(shù)字 1的 ASCII 碼。若在 最左邊加一位奇校驗(yàn)位編碼變?yōu)?10110000如果傳送后右邊 第一位出錯(cuò)則變成 101100011的個(gè)數(shù)變成偶數(shù)就不是合法的 奇校驗(yàn)碼了。但若有兩位假設(shè)是第 1、 2位出錯(cuò)就變成 101100111的個(gè)數(shù)為 5還是奇數(shù)。接收端還認(rèn)為是一個(gè)合法 的代碼數(shù)字 3的 ASCII 碼。所以奇偶校驗(yàn)不能發(fā)現(xiàn)。 奇偶 校驗(yàn)位可由硬件電路異或門(mén)或軟件產(chǎn)生 偶校驗(yàn)位 an a0 a1 a2 a

7、n-1 奇校驗(yàn)位 an NOTa0 a1 a2 an-1。 在一個(gè)典型系統(tǒng)里在傳輸以前由奇偶發(fā)生器把奇偶校驗(yàn)位 加到每個(gè)字中。原有信息中的數(shù)字在接收機(jī)中被檢測(cè) 如果 沒(méi)有出現(xiàn)正確的奇、偶性這個(gè)信息標(biāo)定為錯(cuò)誤的這個(gè)系統(tǒng)將 把錯(cuò)誤的字拋掉或者請(qǐng)求重發(fā)。 在實(shí)際工作中還經(jīng)常采用 縱橫都加校驗(yàn)奇偶校驗(yàn)位的編碼系統(tǒng) -分組奇偶校驗(yàn)碼。 現(xiàn)在考慮一個(gè)系統(tǒng) 它傳輸若干個(gè)長(zhǎng)度為 m 位的信息。如果把這些信息都編成每組 n 個(gè)信息的分組則在這些不同的信息 間也如對(duì)單個(gè)信息一樣能夠作奇偶校驗(yàn)。圖 4中 n 個(gè)信息的 一個(gè)分組排列成矩形式樣并以橫向奇偶 HP 及縱向奇偶 VP 的 形式編出奇偶校驗(yàn)位。 m位數(shù)字 橫

8、向奇偶位 n 個(gè) 碼 字 a1 a2 am-1 am HP1 b1 b2 bm-1 bm HP2 c1 c2 cm-1 c m HP3 n1 n2 nm -1 nm HPn VP1 VP2 VPm-1 VPm HPn1 縱向奇偶位 圖 4 用綜橫奇偶校驗(yàn)的分組 奇偶校驗(yàn)碼 研究圖 4可知分組奇偶校驗(yàn)碼不僅能檢測(cè)許多 形式的錯(cuò)誤。并且在給定的行或列中產(chǎn)生孤立的錯(cuò)誤時(shí)還可 對(duì)該錯(cuò)誤進(jìn)行糾正。 在初級(jí)程序員試題中早期也出現(xiàn)在程 序員試題中經(jīng)常有綜橫奇偶校驗(yàn)的題目。一般解法應(yīng)該是這 樣先找一行或一列已知數(shù)據(jù)完整的確定出該行或列是奇校 驗(yàn)還是偶校驗(yàn)。并假設(shè)行與列都采用同一種校驗(yàn)這個(gè)假設(shè)是 否正確在全部做

9、完后可以得到驗(yàn)證。然后找只有一個(gè)未知數(shù) 的行或列根據(jù)校驗(yàn)性質(zhì)確定該未知數(shù)這樣不斷做下去就能 求出所有未知數(shù)。 【例】 2001年初級(jí)程序員試題 由 6 個(gè) 字符的 7 位 ASCII 編碼排列再加上水平垂直奇偶校驗(yàn)位 構(gòu)成下列矩陣最后一列為水平奇偶校驗(yàn)位最后一行為垂直 奇偶校驗(yàn)位 : 字符 7 位 ASCII 碼 HP 3 0 X1 X2 0 0 1 1 0 Y1 1 0 0 1 0 0 X3 1 X4 1 0 1 0 1 1 0 Y2 0 1 X5 X6 1 1 1 1 D 1 0 0 X7 1 0 X8 0 0 X9 1 1 1 X10 1 1 VP 0 0 1 1 1 X11 1 X12

10、 則 X1 X2 X3 X4 處的比特分別為 _36_ X5 X6X7 X8 處的比特分別為 _ X9 X10 XI1 X12 處的比特分 別為 _38_ Y1 和 Y2 處的字符分別為 _39_ 和_40_ 。 解 從 ASCII 碼左起第 5列可知垂直為偶校驗(yàn)。 則 從第 1列可知 X40從第 3行可知水平也是偶校驗(yàn)。 從第 2行可知 X31從第 7列可知 X80從第 8列可知 X121 從第 7行可知 X111從第 6列可知 X100從第 6行可知 X91從第 2列 可知 X11 從第 1行可知 X21從第 3列可知 X51從第 4行可知 X60 從第 4列或第 5行可知 X70整理一下

11、 36 X1X2X3X4 1110 37 X5X6X7X8 1000 38 X9X10X11X12 1011 39 由字符 Y1的 ASCII 碼 100100149H 知道 Y1即是“I”由“D”的 ASCII 碼 是 100010044H 推得 40 由字符 Y2的 ASCII 碼 011011137H 知道 Y2即是“7”由“3”的 ASCII 碼是 011001133H 推得 假 如你能記住“0”的 ASCII 碼是 011000030H“A”的 ASCII 碼 是 100000141H 則解起來(lái)就更方便了。三、海明校驗(yàn) 我們?cè)谇懊嬷赋鲞^(guò)要能糾正信息字中的單個(gè) 錯(cuò)誤所需的最小距離為 3

12、。實(shí)現(xiàn)這種糾正的方法之一是海明 碼。 海明碼是一種多重復(fù)式奇偶檢錯(cuò)系統(tǒng)。它將信息用邏 輯形式編碼以便能夠檢錯(cuò)和糾錯(cuò)。用在海明碼中的全部傳輸 碼字是由原來(lái)的信息和附加的奇偶校驗(yàn)位組成的。每一個(gè)這 種奇偶位被編在傳輸碼字的特定位置上。實(shí)現(xiàn)得合適時(shí)這個(gè) 系統(tǒng)對(duì)于錯(cuò)誤的數(shù)位無(wú)論是原有信息位中的還是附加校驗(yàn) 位中的都能把它分離出來(lái)。 推導(dǎo)并使用長(zhǎng)度為 m 位的碼字的海明碼所需步驟如下 1、確定最小的校驗(yàn)位數(shù) k 將它們記 成 D1、 D2、 、 Dk 每個(gè)校驗(yàn)位符合不同的奇偶測(cè)試規(guī)定。 2、 原有信息和 k 個(gè)校驗(yàn)位一起編成長(zhǎng)為 mk 位的新碼字。 選擇 k 校驗(yàn)位 0或 1以滿(mǎn)足必要的奇偶條件。 3、

13、對(duì)所接收的信息 作所需的 k 個(gè)奇偶檢查。 4、如果所有的奇偶檢查結(jié)果均為 正確的則認(rèn)為信息無(wú)錯(cuò)誤。 如果發(fā)現(xiàn)有一個(gè)或多個(gè)錯(cuò)了則 錯(cuò)誤的位由這些檢查的結(jié)果來(lái)唯一地確定。 校驗(yàn)位數(shù)的位 數(shù) 推求海明碼時(shí)的一項(xiàng)基本考慮是確定所需最少的校驗(yàn)位 數(shù) k ?？紤]長(zhǎng)度為 m 位的信息若附加了 k 個(gè)校驗(yàn)位則所發(fā)送 的總長(zhǎng)度為 mk 。 在接收器中要進(jìn)行 k 個(gè)奇偶檢查每個(gè)檢查結(jié) 果或是真或是偽。這個(gè)奇偶檢查的結(jié)果可以表示成一個(gè) k 位 的二進(jìn)字它可以確定最多 2k 種不同狀態(tài)。 這些狀態(tài)中必有 一個(gè)其所有奇偶測(cè)試試都是真的它便是判定信息正確的條 件。于是剩下的 2k-1種狀態(tài)可以用來(lái)判定誤碼的位置。于 是

14、導(dǎo)出下一關(guān)系 2k-1mk 碼字格式 從理論上講校驗(yàn)位可 放在任何位置但習(xí)慣上校驗(yàn)位被安排在 1、 2、 4、 8、的位 置上。 圖 5列出了 m4k3時(shí)信息位和校驗(yàn)位的分布情況。 碼 字位置 B1 B2 B3 B4 B5 B6 B7 校驗(yàn)位 x x x 信息位 x x x x 復(fù)合碼字 P1 P2 D1 P3 D2 D3 D4 圖 5 海明碼中校驗(yàn)位和 信息位的定位 校驗(yàn)位的確定 k個(gè)校驗(yàn)位是通過(guò)對(duì) mk 位復(fù)合 碼字進(jìn)行奇偶校驗(yàn)而確定的。 其中 P1位負(fù)責(zé)校驗(yàn)海明碼的 第 1、 3、 5、 7、P1、 D1、 D2、 D4、位包括 P1自己 P2負(fù)責(zé)校驗(yàn)海明碼的第 2、 3、 6、 7、P

15、2、 D1、 D3、 D4、位 包括 P2自己 P3負(fù)責(zé)校驗(yàn)海明碼的第 4、 5、 6、 7、P3、 D2、 D3、 D4、位包括 P3自己 對(duì) m4k3偶校驗(yàn)的例子只要 進(jìn)行式次偶性測(cè)試。這些測(cè)試以 A 、 B 、 C 表示在圖 6所示各 位的位置上進(jìn)行。 奇偶條件 碼 字 位 置 1 2 3 4 5 6 7 A B C x x x x x x x x x x x x 圖 6 奇偶校驗(yàn)位置 因此可 得到三個(gè)校驗(yàn)方程及確定校驗(yàn)位的三個(gè)公式 AB1 B3 B5 B70 得 P1D1 D2 D4 BB2 B3 B6 B70 得 P2D1 D3 D4 CB4 B5 B6 B70 得 P3D2 D3

16、D4 若四位信息碼 為 1001利用這三個(gè)公式可求得三個(gè)校驗(yàn)位 P1、 P2、 P3值。 和海明碼如圖 7則表示了信息碼為 1001時(shí)的海明碼編碼的 全部情況。而圖 8中則列出了全部 16種信息 D1D2D3D400001111的海明碼。 碼字位置 B1 B2 B3 B4 B5 B6 B7 碼位類(lèi)型 P1 P2 D1 P3 D2 D3 D4 信息碼 - - 1 - 0 0 1 校驗(yàn)位 0 0 - 1 - - - 編碼后的海明碼 0 0 1 1 0 0 1 圖 7 四位信息碼的海明編碼 P1 P2 D1 P3 D2 D3 D4 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0

17、1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 圖 8 未編碼信息的海明碼 上面是發(fā)送方的處理 在接收方也 可根據(jù)這三個(gè)校驗(yàn)方程對(duì)接收到的信息進(jìn)行同樣的奇偶測(cè)試 AB1 B3 B5 B70 BB2 B3 B6 B70 CB4 B5 B5 B70。 若三個(gè)校驗(yàn)方程都成立

18、即方程式右邊都等于 0則說(shuō) 明沒(méi)有錯(cuò)。若不成立即方程式右邊不等于 0說(shuō)明有錯(cuò)。從三 個(gè)方程式右邊的值可以判斷那一位出錯(cuò)。例如如果第 3位數(shù) 字反了則 C0此方程沒(méi)有 B3AB1這兩個(gè)方程有 B3?？蓸?gòu)成二 進(jìn)數(shù) CBA 以 A 為最低有效位則錯(cuò)誤位置就可簡(jiǎn)單地用二進(jìn)數(shù) CBA011指出。 同樣若三個(gè)方程式右邊的值為 001說(shuō)明第 1位出錯(cuò)。 若三個(gè)方程式右邊的值為 100說(shuō)明第 4位出錯(cuò)。 海 明碼的碼距應(yīng)該是 3所以能糾正 1位出錯(cuò)。而奇偶校驗(yàn)碼的 碼距才是 2只能發(fā)現(xiàn) 1位出錯(cuò)但不能糾正不知道那一位錯(cuò)。 無(wú)校驗(yàn)的碼距是 1它出任何一位出錯(cuò)后還是合法代碼所以也 就無(wú)法發(fā)現(xiàn)出錯(cuò)。 這是關(guān)于海明

19、碼的經(jīng)典說(shuō)法即碼距為 3可以發(fā)現(xiàn) 2位或者糾正 1位錯(cuò)。應(yīng)滿(mǎn)足 2k-1mk。 但在清 華的王愛(ài)英主編的計(jì)算機(jī)組成與結(jié)構(gòu)該書(shū)已成為國(guó)內(nèi)的 權(quán)威中還提出了一種碼距為 4的海明碼可以發(fā)現(xiàn) 2位并且糾 正 1位錯(cuò)。應(yīng)滿(mǎn)足 2k-1mk。 由于王愛(ài)英書(shū)上對(duì)這兩種概 念沒(méi)有很仔細(xì)解釋特別對(duì)碼距為 3的海明碼過(guò)渡很突然。有 些書(shū)簡(jiǎn)單抄襲時(shí)沒(méi)有仔細(xì)消化所以出現(xiàn)一些概念錯(cuò)。對(duì)于一 般碼距為 3的海明碼應(yīng)該是“可以發(fā)現(xiàn) 2位或者糾正 1位 錯(cuò)”而不是“可以發(fā)現(xiàn) 2位并且糾正 1位錯(cuò)”。在試題中出 現(xiàn)過(guò)類(lèi)似的錯(cuò)誤。 四、循環(huán)冗余校驗(yàn)碼 在串行傳送磁盤(pán)、 通訊中廣泛采用循環(huán)冗余校驗(yàn)碼 CRC 。 CRC 也是給信息

20、碼加上幾位校驗(yàn)碼以增加整個(gè)編碼系統(tǒng)的碼距和查錯(cuò)糾錯(cuò)能力。 CRC 的理論很復(fù)雜一般書(shū)上只介紹已有生成多項(xiàng)式后計(jì)算校 驗(yàn)碼的方法。檢錯(cuò)能力與生成多項(xiàng)式有關(guān)只能根據(jù)書(shū)上的結(jié) 論死記。 循環(huán)冗余校驗(yàn)碼 CRC 的基本原理是在 K 位信息碼 后再拼接 R 位的校驗(yàn)碼整個(gè)編碼長(zhǎng)度為 N 位因此這種編碼又 叫 NK 碼。對(duì)于一個(gè)給定的 NK 碼可以證明存在一個(gè)最高次冪 為 N-KR 的多項(xiàng)式 Gx 。 根據(jù) Gx 可以生成 K 位信息的校驗(yàn)碼而 Gx 叫做這個(gè) CRC 碼的生成多項(xiàng)式。 校驗(yàn)碼的具體生成過(guò)程 為假設(shè)發(fā)送信息用信息多項(xiàng)式 CX 表示將 Cx 左移 R 位則可表 示成 Cx2R 這樣 Cx 的

21、右邊就會(huì)空出 R 位這就是校驗(yàn)碼的位置。 通過(guò) Cx2R 除以生成多項(xiàng)式 Gx 得到的余數(shù)就是校驗(yàn)碼。 幾 個(gè)基本概念 1、多項(xiàng)式與二進(jìn)制數(shù)碼 多項(xiàng)式和二進(jìn)制數(shù)有 直接對(duì)應(yīng)關(guān)系 x 的最高冪次對(duì)應(yīng)二進(jìn)制數(shù)的最高位以下各位 對(duì)應(yīng)多項(xiàng)式的各冪次有此冪次項(xiàng)對(duì)應(yīng) 1無(wú)此冪次項(xiàng)對(duì)應(yīng) 0。 可以看出 x 的最高冪次為 R 轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制數(shù)有 R1位。 多項(xiàng)式包括生成多項(xiàng)式 Gx 和信息多項(xiàng)式 Cx 。 如生成多項(xiàng)式 為 Gxx4x3x1 可轉(zhuǎn)換為二進(jìn)制數(shù)碼 11011。 而發(fā)送信息位 1111可轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式為 Cxx3x2x1。 2、生成多項(xiàng)式 是 接受方和發(fā)送方的一個(gè)約定也就是一個(gè)二進(jìn)制數(shù)在整個(gè)

22、傳 輸過(guò)程中這個(gè)數(shù)始終保持不變。 在發(fā)送方利用生成多項(xiàng)式 對(duì)信息多項(xiàng)式做模 2除生成校驗(yàn)碼。在接受方利用生成多項(xiàng) 式對(duì)收到的編碼多項(xiàng)式做模 2除檢測(cè)和確定錯(cuò)誤位置。 應(yīng)滿(mǎn)足以下條件 a、生成多項(xiàng)式的最高位和最低位必須為 1。 b 、當(dāng)被傳送信息 CRC 碼任何一位發(fā)生錯(cuò)誤時(shí)被生成多項(xiàng)式 做模 2除后應(yīng)該使余數(shù)不為 0。 c、不同位發(fā)生錯(cuò)誤時(shí)應(yīng)該 使余數(shù)不同。 d、對(duì)余數(shù)繼續(xù)做模 2除應(yīng)使余數(shù)循環(huán)。 將 這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的。但可以從有關(guān)資料 查到常用的對(duì)應(yīng)于不同碼制的生成多項(xiàng)式如圖 9所示 N K 碼距 d Gx多項(xiàng)式 Gx 7 4 3 x3x1 1011 7 4 3 x3x21

23、 1101 7 3 4 x4x3x21 11101 7 3 4 x4x2x1 10111 15 11 3 x4x1 10011 15 7 5 x8x7x6x41 111010001 31 26 3 x5x21 100101 31 21 5 x10x9x8x6x5x31 11101101001 63 57 3 x6x1 1000011 63 51 5 x12x10x5x4x21 1010000110101 1041 1024 x16x15x21 11000000000000101 圖 9 常用的生成多項(xiàng)式 3、 模 2除按位 除 模 2除做法與算術(shù)除法類(lèi)似但每一位除減的結(jié)果不影響 其它位即不向上

24、一位借位。所以實(shí)際上就是異或。然后再移 位移位做下一位的模 2減。步驟如下 a、用除數(shù)對(duì)被除數(shù)最 高幾位做模 2減沒(méi)有借位。 b、除數(shù)右移一位若余數(shù)最高位 為 1商為 1并對(duì)余數(shù)做模 2減。若余數(shù)最高位為 0商為 0除 數(shù)繼續(xù)右移一位。 c、一直做到余數(shù)的位數(shù)小于除數(shù)時(shí)該余 數(shù)就是最終余數(shù)。 【例】 1111000除以 1101 1011商 1111000-被除數(shù) 1101 除數(shù) 010000 1101 01010 1101 111余數(shù) CRC碼的生成步驟 1、將 x 的最高冪次為R 的生成多項(xiàng)式 Gx 轉(zhuǎn)換成對(duì)應(yīng)的 R1 位二進(jìn)制數(shù)。 2、將信 息碼左移 R 位相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式 Cx2

25、R 3、用生成多項(xiàng) 式二進(jìn)制數(shù)對(duì)信息碼做模 2 除得到 R 位的余數(shù)。 4、將余數(shù) 拼到信息碼左移后空出的位置得到完整的 CRC 碼。 【例】 假設(shè)使用的生成多項(xiàng)式是 Gxx3x1。4 位的原始報(bào)文為 1010 求編碼后的報(bào)文。 解 1、將生成多項(xiàng)式 Gxx3x1 轉(zhuǎn)換成對(duì)應(yīng) 的二進(jìn)制除數(shù) 1011。 2、此題生成多項(xiàng)式有 4 位 R1 要把原 始報(bào)文 Cx 左移 3R 位變成 1010000 3、用生成多項(xiàng)式對(duì)應(yīng)的 二進(jìn)制數(shù)對(duì)左移 4 位后的原始報(bào)文進(jìn)行模 2 除 1001-商 - 1010000 1011-除 數(shù) - 1000 1011 - 011-余 數(shù)校驗(yàn)位 5、編碼后的報(bào)文 CRC

26、碼 1010000 011 - 1010011 CRC 的和糾錯(cuò) 在接收端收到 了 CRC 碼后用生成多項(xiàng)式為 Gx 去做模 2 除若得到余數(shù)為 0 則碼字無(wú)誤。若如果有一位出錯(cuò)則余數(shù)不為 0 而且不同位出 錯(cuò)其余數(shù)也不同?？梢宰C明余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系只與碼 制及生成多項(xiàng)式有關(guān)而與待測(cè)碼字信息位無(wú)關(guān)。圖 10 給出 了 Gx1011Cx1010 的出錯(cuò)模式改變 Cx 碼字只會(huì)改變表中碼字 內(nèi)容不改變余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系。 收到的 CRC 碼字 余 數(shù) 出錯(cuò)位 碼位 A7 A6 A5 A4 A3 A2 A1 正確 1 0 1 0 0 1 1 000 無(wú) 錯(cuò) 誤 1 0 1 0 0 1 0 1

27、 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 001 010 100 011 110 111 101 1 2 3 4 5 6 7 圖 10 74CRC 碼的出錯(cuò)模式 Gx1011 如果循環(huán)碼有一位出錯(cuò)用 Gx 作 模 2 除將得到一個(gè)不為 0 的余數(shù)。如果對(duì)余數(shù)補(bǔ) 0 繼續(xù)除下 去我們將發(fā)現(xiàn)一個(gè)有趣的結(jié)果各次余數(shù)將按圖 10 順序循環(huán)。 例如第一位出錯(cuò)余數(shù)將為 001 補(bǔ) 0 后再除補(bǔ) 0 后若最高位為 1 則用除數(shù)做模 2 減取余若最高位為 0 則其最低 3 位就是余 數(shù)得

28、到第二次余數(shù)為 010。以后繼續(xù)補(bǔ) 0 作模 2 除依次得到 余數(shù)為 1000ll反復(fù)循環(huán)這就是“循環(huán)碼”名稱(chēng)的由來(lái)。 這 是一個(gè)有價(jià)值的特點(diǎn)。如果我們?cè)谇蟪鲇鄶?shù)不為 0 后一邊對(duì) 余數(shù)補(bǔ) 0 繼續(xù)做模 2 除同時(shí)讓被檢測(cè)的校驗(yàn)碼字循環(huán)左移。 圖 10 說(shuō)明當(dāng)出現(xiàn)余數(shù) 101 時(shí)出錯(cuò)位也移到 A7 位置?？赏ㄟ^(guò) 異或門(mén)將它糾正后在下一次移位時(shí)送回 A1。 這樣我們就不必 像海明校驗(yàn)?zāi)菢佑米g碼電路對(duì)每一位提供糾正條件。當(dāng)位數(shù) 增多時(shí)循環(huán)碼校驗(yàn)?zāi)苡行У亟档陀布鷥r(jià)這是它得以廣泛 應(yīng)用的主要原因。 【例】對(duì)圖 10 的 CRC 碼 Gx1011Cx1010 若接收端收到的碼字為 1010111 用

29、Gx1011 做模 2 除得到一 個(gè)不為 0 的余數(shù) 100 說(shuō)明傳輸有錯(cuò)。將此余數(shù)繼續(xù)補(bǔ) 0 用 Gx1011 作模 2 除同時(shí)讓碼字循環(huán)左移 1010111。做了 4 次后 得到余數(shù)為 101 這時(shí)碼字也循環(huán)左移 4 位變成 1111010。說(shuō) 明出錯(cuò)位已移到最高位 A7 將最高位 1 取反后變成 0111010。 再將它循環(huán)左移 3 位補(bǔ)足 7 次出錯(cuò)位回到 A3 位就成為一個(gè) 正確的碼字 1010011。 通信與網(wǎng)絡(luò)中常用的 CRC 在數(shù)據(jù)通 信與網(wǎng)絡(luò)中通常 k 相當(dāng)大由一千甚至數(shù)千數(shù)據(jù)位構(gòu)成一幀而 后采用 CRC 碼產(chǎn)生 r 位的校驗(yàn)位。它只能檢測(cè)出錯(cuò)誤而不能 糾正錯(cuò)誤。一般取 r16 標(biāo)準(zhǔn)的 16 位生成多項(xiàng)式有 CRC-16x16x15x21 和 CRC-CCITTx16x15x21。 一般情況下 r 位生成多項(xiàng)式產(chǎn)生的 CRC 碼可檢測(cè)出所有的雙錯(cuò)、奇數(shù)位錯(cuò) 和突發(fā)長(zhǎng)度小于等于 r 的突發(fā)錯(cuò)以及 1-2-r-1 的突發(fā)長(zhǎng)度為 r1 的突發(fā)錯(cuò)和 1-2-r 的突發(fā)長(zhǎng)度大于 r1 的突發(fā)錯(cuò)。例如對(duì) 上述 r16 的情況就能檢測(cè)出所有突發(fā)長(zhǎng)度小于等于 16 的突 發(fā)錯(cuò)以及 99997 的突