數(shù)據(jù)校驗(yàn)碼-PPT課件

1、第4章 存儲(chǔ)器 補(bǔ)充內(nèi)容： 數(shù)據(jù)校驗(yàn)碼7/19/20221數(shù)據(jù)校驗(yàn)碼是什么？數(shù)據(jù)在傳輸或存儲(chǔ)過(guò)程中常因受到某種隨機(jī)干擾而發(fā)生錯(cuò)誤（即誤碼）：1 0 或 01為了保證數(shù)據(jù)的正確性，必須及時(shí)發(fā)現(xiàn)并糾正數(shù)據(jù)中的錯(cuò)誤。數(shù)據(jù)校驗(yàn)碼：一種具有檢錯(cuò)能力或自動(dòng)改錯(cuò)能力的數(shù)據(jù)編碼方法。7/19/20222“冗余校驗(yàn)”思想：（以數(shù)據(jù)傳輸為例）（1）編碼：在原始數(shù)據(jù)（即有效數(shù)據(jù)位）的基礎(chǔ)上增加冗余數(shù)據(jù)（即校驗(yàn)位），按照某種規(guī)律將有效數(shù)據(jù)位和校驗(yàn)位一起編碼，得到數(shù)據(jù)校驗(yàn)碼；（2）譯碼：按同一約定規(guī)律對(duì)收到的數(shù)據(jù)校驗(yàn)碼進(jìn)行分析，并判斷約定規(guī)律是否被破壞。 若未被破壞，則正確，從中取出有效數(shù)據(jù)即可； 若被破壞，則有錯(cuò)，根

2、據(jù)約定規(guī)律被破壞后的某些特征對(duì)出錯(cuò)位進(jìn)行定位，從而可自動(dòng)糾正錯(cuò)誤。7/19/20223本質(zhì)：加進(jìn)一些冗余碼，使合法編碼出現(xiàn)某些錯(cuò)誤時(shí)，就成為非法編碼。這樣，可通過(guò)檢測(cè)編碼的合法性來(lái)達(dá)到發(fā)現(xiàn)錯(cuò)誤的目的。舉例：假設(shè)有效數(shù)據(jù)用3位二進(jìn)制編碼，表示某個(gè)地區(qū)八個(gè)城市的代號(hào)。碼距：一個(gè)編碼系統(tǒng)中任意兩個(gè)合法編碼之間對(duì)應(yīng)二進(jìn)制位狀態(tài)不同的位數(shù)，稱為這兩個(gè)編碼的距離。任意兩個(gè)編碼的最小距離就是該編碼系統(tǒng)的碼距，通常用d表示。例子中的d=？二進(jìn)制編碼 D2 D1 D0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 101101001 P7/19/20224為了使一個(gè)

3、編碼系統(tǒng)能發(fā)現(xiàn)并糾正一位錯(cuò)，其碼距至少應(yīng)為3。此時(shí)，或能糾正一位錯(cuò)，或能發(fā)現(xiàn)二位錯(cuò)。但不能同時(shí)兼有這兩種能力。為了進(jìn)一步提高編碼系統(tǒng)的檢錯(cuò)和糾錯(cuò)能力，必須進(jìn)一步增加碼距。碼距d=碼距編碼系統(tǒng)能力查錯(cuò) 糾錯(cuò)10 021 032 或 142 與 15 2 與 26 3 與 273 與 37/19/20225 結(jié)論：增加的校驗(yàn)位越多，碼距越大，糾錯(cuò)能力越強(qiáng)；但數(shù)據(jù)冗余也越大，代價(jià)越高。數(shù)據(jù)校驗(yàn)碼設(shè)計(jì)原則：在不過(guò)多增加硬件開銷的情況下，盡可能多地發(fā)現(xiàn)和糾正錯(cuò)誤。設(shè)計(jì)者要綜合考慮信息發(fā)生差錯(cuò)的概率以及具體應(yīng)用系統(tǒng)所能容許的最小差錯(cuò)率等因素來(lái)選擇合適的碼距。7/19/20226一、奇偶校驗(yàn)碼最簡(jiǎn)單、開銷最

4、小，廣泛應(yīng)用于存儲(chǔ)器讀寫校驗(yàn)。編碼規(guī)律：偶校驗(yàn)：配一個(gè)校驗(yàn)位，使整個(gè)校驗(yàn)碼（包括有效數(shù)據(jù)位和校驗(yàn)位）中“1”的個(gè)數(shù)為偶數(shù)；奇校驗(yàn)：配一個(gè)校驗(yàn)位，使整個(gè)校驗(yàn)碼（包括有效數(shù)據(jù)位和校驗(yàn)位）中“1”的個(gè)數(shù)為奇數(shù)；采用奇校驗(yàn)還是偶校驗(yàn)，應(yīng)事先約定好。7/19/20227以偶校驗(yàn)為例介紹其編、譯碼方法編碼：統(tǒng)計(jì)有效數(shù)據(jù)中“1”的個(gè)數(shù)，若為奇數(shù)（偶數(shù)），則令增加的校驗(yàn)位為“1”（“0”），由有效數(shù)據(jù)和校驗(yàn)位構(gòu)成整個(gè)校驗(yàn)碼。（寫入存儲(chǔ)器）形如 D8D7D6D5D4D3D2D1D校其中 D校=D8D7D6D5D4D3D2D1例如：有效數(shù)據(jù)偶校驗(yàn)碼101100101011001001011001110110011

5、17/19/20228譯碼： （從存儲(chǔ)器讀出）統(tǒng)計(jì)整個(gè)校驗(yàn)碼中“1”的個(gè)數(shù)，若仍為偶數(shù)，則表明約定規(guī)律未被破壞，讀出的數(shù)據(jù)是正確的，從中取出有效數(shù)據(jù)即可；否則，表明出錯(cuò)。出錯(cuò)條件可表示為： 偶校驗(yàn)錯(cuò)= D8D7D6D5D4D3D2D1D校檢錯(cuò)糾錯(cuò)能力分析：碼距 d=2；只能發(fā)現(xiàn)1位錯(cuò)，而不能糾正錯(cuò)誤；不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。因一位出錯(cuò)的幾率大，故有實(shí)用價(jià)值。7/19/20229邏輯實(shí)現(xiàn)：編碼譯碼7/19/202210二、 海明校驗(yàn)碼 1950年，Richard Hamming提出。目前仍應(yīng)用廣泛。實(shí)質(zhì)：是一種多重奇偶校驗(yàn)碼。實(shí)現(xiàn)原理：按一定規(guī)律將有效數(shù)據(jù)位劃分為若干組，分組進(jìn)行奇偶校驗(yàn)。各組的檢錯(cuò)

6、信息構(gòu)成一個(gè)指錯(cuò)字，不但可以發(fā)現(xiàn)出錯(cuò)，還能指出是哪一位出錯(cuò)，為自動(dòng)糾錯(cuò)提供依據(jù)。7/19/202211(1)分成幾組？增加多少校驗(yàn)位？ 設(shè)待編信息k位，分為r組，每組增加一個(gè)校驗(yàn)位，則r位校驗(yàn)位構(gòu)成一個(gè)r位的指錯(cuò)字。 r位校驗(yàn)位能表示2r種狀態(tài)： 用全0表示“沒(méi)有錯(cuò)誤”； 用其余2r-1種狀態(tài)指出錯(cuò)誤發(fā)生在哪一位。 具體實(shí)現(xiàn)7/19/202212需要滿足： 2r 1 k + r若設(shè)k=4，則r3，組成7位海明碼。k1245111226275758120r2345677/19/202213(2)分組方法？ 設(shè)有效數(shù)據(jù)4位：A4 A3 A2 A1， 增加3位校驗(yàn)位：P3 P2 P1， 構(gòu)成一個(gè)3位

7、的指錯(cuò)字G3 G2 G1。7654321A4A3A2P3A1P2P1 Pi在海明碼中位序號(hào)為2i-1的位置上。7/19/2022147654321指錯(cuò)字A4A3A2P3A1P2P1第3組G3第2組G2第1組G1 “”表示某位海明碼參加某組。 有效數(shù)據(jù)位Ai分別參加2組以上，且滿足如下關(guān)系：其位序號(hào)要等于所參與各組的校驗(yàn)位的位序號(hào)之和。 每個(gè)校驗(yàn)位Pi只參加本組。7/19/202215(3)編碼（以偶校驗(yàn)為例）？第1組：P1=A1 A2 A4 G1=P1 A1 A2 A4第2組：P2=A1 A3 A4 G2=P2 A1 A3 A4第3組：P3=A2 A3 A4 G3=P3 A2 A3 A4(4)

8、查錯(cuò)與糾錯(cuò)若G3G2G1000，若G3G2G1000，則無(wú)錯(cuò)；則G3G2G1的值即指明出錯(cuò)位，將該位取反即可糾正。7/19/2022167654321指錯(cuò)字G3G2G1A4A3A2P3A1P2P1正確碼0101101000出錯(cuò)碼0111101G1=P1 A1 A2 A4=1 1 1 0=1G2=P2 A1 A3 A4=0 1 1 0=0G3=P3 A2 A3 A4=1 1 1 0=11017/19/202217(5)邏輯實(shí)現(xiàn)(譯碼電路)7/19/202218 由于每一個(gè)有效數(shù)據(jù)位至少要參加兩個(gè)校驗(yàn)組的奇偶檢測(cè)，因此當(dāng)兩個(gè)有效數(shù)據(jù)只有一位不相同時(shí)，該位至少引起兩個(gè)校驗(yàn)位的不同！故碼距d3。(6)

9、分析 d3的碼能夠檢測(cè)2位錯(cuò)，或用來(lái)檢測(cè)并糾正 1位錯(cuò)，但兩者只能擇一。 如要能檢測(cè)并糾正1位錯(cuò)，同時(shí)能發(fā)現(xiàn)2位錯(cuò)， 此時(shí)應(yīng)增加一個(gè)校驗(yàn)位，即應(yīng)滿足： 2r-1k+r7/19/202219 校驗(yàn)規(guī)則：讓校驗(yàn)碼能被某一約定代碼除盡。 若能除盡，表明代碼無(wú)錯(cuò)； 若除不盡，余數(shù)將指明出錯(cuò)位置。 三、 循環(huán)冗余校驗(yàn)碼（CRC碼） 實(shí)現(xiàn)原理：在k位信息位之后拼接r位校驗(yàn)位。 問(wèn)題1：如何從k位信息位簡(jiǎn)便地得到r位校驗(yàn)位？ 問(wèn)題2：如何從k+r位信息碼判斷是否有錯(cuò)？7/19/202220 模2運(yùn)算：以按位模2相加為基礎(chǔ)， 運(yùn)算時(shí)不考慮進(jìn)位和借位。 模2加減（異或） 000 011 101 110 模2乘（

10、用模2加求和） 例如： 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 CRC碼是基于模2運(yùn)算來(lái)建立編譯碼規(guī)律的校驗(yàn)碼，在計(jì)算機(jī)外存儲(chǔ)器校驗(yàn)和通信等方面應(yīng)用廣泛。7/19/202221 模2除（用模2減求余數(shù)） 每求1位商使部分余數(shù)減少1位。 上商原則：部分余數(shù)的首位為1，商取1； 部分余數(shù)的首位為0，商取0。 當(dāng)部分余數(shù)位數(shù)小于除數(shù)位數(shù)時(shí)，該余數(shù)為最后余數(shù)。 例如： 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 17/19/202222設(shè)：被除數(shù)M(x)：k位待編信息 除數(shù)G

11、(x)：r+1位？ 余數(shù)R(x)：r位校驗(yàn)位 商Q(x) (1) CRC碼的編碼方法 具體實(shí)現(xiàn)a. 將待編碼的k位有效信息位組寫成表達(dá)式： M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+C0 (Ci=0或1)b. 將信息位組左移r位，變成多項(xiàng)式M(x) Xr；c. 用M(x) Xr除以G(x)，所得余數(shù)作為校驗(yàn)位。d. 有效的CRC碼為： M(x) Xr+R(x)=Q(x) G(x)+R(x)+R(x)= Q(x) G(x)。所以：CRC碼能夠被G(x)除盡。7/19/202223例如：對(duì)M(x)=1100，用G(x)=1011，求CRC碼。a. 將待編碼的k=4位有效信息位組寫成表達(dá)

12、式： M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+C0=X3+X2=1100b. 將信息位組左移r=3位,M(x) Xr=M(X) X3=1100000c. 用M(x) Xr除以G(x)，所得余數(shù)作為校驗(yàn)位。d. 有效的CRC碼此處為(7,4)碼為： M(x) Xr+R(x)= 1100000 + 010 = 1100010。7/19/202224(2) CRC碼的譯碼與糾錯(cuò) 譯碼：用收到的CRC碼除以G(x)。 若碼字無(wú)誤，則余數(shù)為0； 若有某1位錯(cuò)，則余數(shù)不為0且不同位出錯(cuò)時(shí)的余數(shù)不同。注意：余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系不變， 它只與碼制和生成多項(xiàng)式G(x)有關(guān)， 而與待測(cè)碼字無(wú)關(guān)。7/19/202225 (7，4)循環(huán)碼的出錯(cuò)模式(生成多項(xiàng)式G(x)=1011) A1A2A3A4A5A6A7余數(shù)出錯(cuò)位正確11000100 0 0無(wú)錯(cuò)誤11000110 0 1711000000 1 0611001101 0 0511010100 1 1411100101 1 0310000101 1 1201000101 0 117/19/202226 糾錯(cuò)： 對(duì)于用G(x)作模2除得到的余數(shù)R(x)，若補(bǔ)0繼續(xù)除下去，發(fā)現(xiàn)各次的余數(shù)按上表的順序循環(huán)。 所以，可以采用一種節(jié)省硬件的糾錯(cuò)辦法： 如只設(shè)置余數(shù)101的譯碼輸出，對(duì)應(yīng)于第1位A1出錯(cuò)。 在求出余數(shù)不為0后，對(duì)余數(shù)一邊補(bǔ)