【文章內(nèi)容簡(jiǎn)介】 0”的 ASCII碼是 0110000=30H； “A”的 ASCII碼是1000001=41H，則解起來(lái)就更方便了* 41計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼這是由 RichardHamming于 1950年提出的、目前還被廣泛采用在網(wǎng)絡(luò)傳輸?shù)阮I(lǐng)域。實(shí)現(xiàn)原理 ：在有效信息位中加入幾個(gè)校驗(yàn)位形成海明碼，使碼距比較均勻的拉大，并把數(shù)據(jù)的每一個(gè)二進(jìn)制位分配在幾個(gè)奇偶校驗(yàn)組中。當(dāng)某一位出錯(cuò)后，就會(huì)引起有關(guān)的幾個(gè)校驗(yàn)組的值發(fā)生變化，這不但可以發(fā)現(xiàn)出錯(cuò)，還能指出是哪一位出錯(cuò)，為自動(dòng)糾錯(cuò)提供了依據(jù)。* 42計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼假設(shè)校驗(yàn)位的個(gè)數(shù)為 r，則它能表示 2r個(gè)信息，用其中的一個(gè)信息指出 “沒(méi)有錯(cuò)誤 ”，其余的 2r1個(gè)信息指出錯(cuò)誤發(fā)生在哪一位。然而錯(cuò)誤也可能發(fā)生在校驗(yàn)位，因此只有 k=2r1r個(gè)信息能用于糾正被傳送數(shù)據(jù)的位數(shù)，也就是說(shuō)要滿(mǎn)足關(guān)系 。2r≥k+r+1 ()如要能 檢測(cè)與自動(dòng)校正一位錯(cuò) ，并 發(fā)現(xiàn)兩位錯(cuò) ，則應(yīng)在前一條件下 再增加 1位總校驗(yàn)位 ，此時(shí)校驗(yàn)位的位數(shù) r和數(shù)據(jù)位的位數(shù) k應(yīng)滿(mǎn)足下述關(guān)系：2r1≥k+r ()* 43計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼可計(jì)算出數(shù)據(jù)位 k與校驗(yàn)位 r的對(duì)應(yīng)關(guān)系，如表。表 k與 r之 間 的關(guān)系表r值 k值 r值 k值23412～ 45～ 1156712～ 2627～ 5758～ 120* 44計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼海明碼的編碼規(guī)律： 數(shù)據(jù)位 k位，校驗(yàn)位 r位，假設(shè)海明碼的最高位號(hào)為 m，最低位號(hào)為 1，即 HmHm1…H 2H1(1)校驗(yàn)位與數(shù)據(jù)位之和為 m， 每個(gè)校驗(yàn)位 Pi在海明碼中被分在位號(hào) 2i1的位置 ，其余各位為數(shù)據(jù)位，并按從低向高逐位依次排列的關(guān)系分配各數(shù)據(jù)位。(2)海明碼的每一位碼 Hi(包括數(shù)據(jù)位和校驗(yàn)位本身 )由多個(gè)校驗(yàn)位校驗(yàn)，其關(guān)系是 被校驗(yàn)的每一位位號(hào)要等于校驗(yàn)它的各校驗(yàn)位的位號(hào)之和 。以便校驗(yàn)的結(jié)果能正確反映出出錯(cuò)位的位號(hào)。* 45計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼例如 :校驗(yàn)位 r=5，用 P1P5表示，數(shù)據(jù)位 k=8，用D1D8表示， 5個(gè)校驗(yàn)位 P5~P1對(duì)應(yīng)的海明碼位號(hào)應(yīng)分別為 H13， H8， H4， H2和 H1。 P5只能放在H13一位上，它已經(jīng)是海明碼的最高位了 ， 其他 4位滿(mǎn)足 Pi的位號(hào)等于 2i1的關(guān)系 。其余為數(shù)據(jù)位 Di，則有如下排列關(guān)系：P5D8D7D6D5P4D4D3D2P3D1P2P1按照海明碼的編碼規(guī)律， 每個(gè)海明碼的位號(hào)要等于參與檢驗(yàn)它的幾個(gè)檢驗(yàn)位的位號(hào)之和的關(guān)系 ，可以給出如表 * 46計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算海明碼位號(hào) 數(shù) 據(jù)位 /校驗(yàn)位 參與校驗(yàn)的校驗(yàn)位位號(hào)被校驗(yàn)位的海明碼位號(hào) =校驗(yàn)位位號(hào)之和H1 P1 1 1=1H2 P2 2 2=2H3 D1 1， 2 3=1+2H4 P3 4 4=4H5 D2 1， 4 5=1+4H6 D3 2， 4 6=2+4H7 D4 1， 2， 4 7=1+2+4H8 P4 8 8=8H9 D5 1， 8 9=1+8H10 D6 2， 8 10=2+8H11 D7 1， 2， 8 11=1+2+8H12 D8 4， 8 12=4+8H13 P5 13 13=13表 出錯(cuò)的海明碼位號(hào)和校驗(yàn)位位號(hào)的關(guān)系 * 47計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼由有關(guān)數(shù)據(jù)位形成 Pi值的 偶 校驗(yàn) 的結(jié)果 :P1=D1D2D4D5D7P2=D1D3D4D6D7P3=D2D3D4D8P4=D5D6D7D8若要分清是兩位出錯(cuò)還是一位出錯(cuò)，還要 補(bǔ)充一位 P5總校驗(yàn)位P5=D1D2D3D4D5D6D7D8P4P3P2P1每一位數(shù)據(jù)位，都至少出現(xiàn)在 3個(gè) Pi值 的形成關(guān)系中。當(dāng)任一位數(shù)據(jù)碼發(fā)生變化時(shí)，必將引起 3個(gè)或 4個(gè) Pi值跟著變化，該海明碼的 碼距為 4。* 48計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼按如下關(guān)系對(duì)所得到的海明碼實(shí)現(xiàn) 偶校驗(yàn) :S1=P1D1D2D4D5D7S2=P2D1D3D4D6D7S3=P3D2D3D4D8S4=P4D5D6D7D8S5=P5P4P3P2P1D1D2D3D4D5D6D7D8校驗(yàn)得到的結(jié)果值 S5~S1能反應(yīng) 13位海明碼的出錯(cuò)情況任何奇數(shù)個(gè)數(shù)出錯(cuò)， S5一定為 1任何偶數(shù)個(gè)數(shù)出錯(cuò)， S5一定為 0圖 H=12，數(shù)據(jù)位 k=8，校驗(yàn)位 r=4的海明校驗(yàn)線路，記作(12， 8)分組碼。* 49計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼圖 H=12，數(shù)據(jù)位 k=8，校驗(yàn)位 r=4的海明校驗(yàn)線路，記作 (12， 8)分組碼。圖中， H12,H11,…,H 1是被校驗(yàn)碼， D8,D7,…,D1是糾正后的數(shù)據(jù)， S4,S3,S2,S1是用奇偶形成線路得到的。若 S4~S1全 0，說(shuō)明代碼無(wú)錯(cuò)；若為 1100或 1011，則分別表示 H12或 H11有錯(cuò)，通過(guò)相關(guān)譯碼線經(jīng)異或電路糾正該位 。* 50計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼圖 (12， 8)分組碼海明校驗(yàn)線路* 51計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 海明校驗(yàn)碼假如要進(jìn)一步判別是 1位錯(cuò)還是 2位錯(cuò)，則再增加一個(gè)校驗(yàn)位 。并用圖 ，此時(shí)增加了一個(gè)奇偶形成線路 S5。 如為 一位錯(cuò)，仍按圖 ；如為 兩位錯(cuò)，則無(wú)法糾正錯(cuò)誤 。圖 判 1位 /2位錯(cuò)的附加線路* 52計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 循環(huán)冗余校驗(yàn)碼CRC(cyclicredundancycheck)碼可以發(fā)現(xiàn)并糾正信息存儲(chǔ)或傳送過(guò)程中連續(xù)出現(xiàn)的多位錯(cuò)誤，在磁介質(zhì)存儲(chǔ)和計(jì)算機(jī)之間通信方面得到廣泛應(yīng)用 。在數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)通訊領(lǐng)域， CRC應(yīng)用廣泛 :著名通訊協(xié)議 FCS(幀檢錯(cuò)序列 )采用 CRC.CCITT， ARJ、 LHA等壓縮工具軟件采用的是CRC32，磁盤(pán)驅(qū)動(dòng)器的讀寫(xiě)采用了 CRC16，通用的圖像存儲(chǔ)格式 GIF、 TIFF等也都用 CRC作為檢錯(cuò)手段。歐洲交換機(jī)都使用 CRC4。* 53計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 循環(huán)冗余校驗(yàn)碼CRC碼是基于 模 2運(yùn)算 而建立編碼規(guī)律的校驗(yàn)碼 。模 2運(yùn)算特點(diǎn)： 運(yùn)算不考慮進(jìn)位和借位 ， 規(guī)則 如下：① 模 2加和模 2減規(guī)則相同，按位異或，相同得 0，不同得 1。即： 0177。0=0， 0177。1=1， 1177。0=1， 1177。1=0。② 模 2乘時(shí)按模 2加求部分積之和。③ 模 2除是按模 2減求部分余數(shù)。每求一位商應(yīng)使部分余數(shù)減少一位。 上商規(guī)則 是：當(dāng)部分余數(shù)的首位為 1時(shí)，商取 1，當(dāng)部分余數(shù)的首位為 0時(shí)，商取 0；當(dāng)部分余數(shù)的位數(shù)小于除數(shù)位數(shù)時(shí)，該余數(shù)即為最后余數(shù)。* 54計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 循環(huán)冗余校驗(yàn)碼模 2乘例子： 模 2除例子：1010?)10110100000?1010100010101?10110000101010?00010010101商R余數(shù)* 55計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 循環(huán)冗余校驗(yàn)碼CRC碼基本原理 是：在 K位信息碼后再拼接 R位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為 N位，因此，這種編碼又叫 （ N， K）碼 。對(duì)于一個(gè)給定的（ N， K）碼，可以證明存在一個(gè)最高次冪為 NK=R的多項(xiàng)式 G(x)。根據(jù) G(x)可以生成 K位信息的校驗(yàn)碼，而 G(x)叫做這個(gè) CRC碼的 生成多項(xiàng)式 。CRC碼的 關(guān)鍵 是如何從 K位信息位簡(jiǎn)便地得到 r位校驗(yàn)位 (編碼 )，及如何從 K+R位信息碼判斷是否出錯(cuò)。* 56計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 循環(huán)冗余校驗(yàn)碼CRC碼的編碼方法：將待編碼的 k位有效信息位組表達(dá)為 多項(xiàng)式 M(x)：M(x)=Ck1xk1+Ck2xk2+…+ Cixi+…+C 1x+C0將信息位組 左移 r位 ，則可表示為多項(xiàng)式 M(x)xr?？煽粘?r位，以便拼接 r位校驗(yàn)位 CRC碼用多項(xiàng)式 M(x)xr除以 G(x)(生成多項(xiàng)式 )所得余數(shù)作為校驗(yàn)位。為了得到 r位余數(shù) (校驗(yàn)位 )， G(x)必須是 r+1位。設(shè)所得余數(shù)表達(dá)為 R(x)，商為 Q(x)。將余數(shù)拼接在信息位組左移空出的 r位上，構(gòu)成有效信息的 CRC碼。多項(xiàng)式表達(dá)為： M(x)xr+R(x)=［ Q(x)G(x)+R(x)］ +R(x) =［ Q(x)G(x)］ +［ R(x)+R(x)］ =Q(x)G(x)* 57計(jì)算機(jī)組成與結(jié)構(gòu)計(jì)算機(jī)組成與結(jié)構(gòu) 第第 2章章 數(shù)據(jù)的表示和運(yùn)算數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼 數(shù)據(jù)校驗(yàn)碼 循環(huán)冗余校驗(yàn)碼CRC碼的編碼方法：因此所得 CRC碼可被 G(x)表示的數(shù)碼除盡。如果 CRC碼在傳輸過(guò)程中不出錯(cuò)，其余數(shù)必為 0；