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

2、據約定規律被破壞后的某些特征對出錯位進行定位，從而可自動糾正錯誤。7/19/20223本質：加進一些冗余碼，使合法編碼出現某些錯誤時，就成為非法編碼。這樣，可通過檢測編碼的合法性來達到發現錯誤的目的。舉例：假設有效數據用3位二進制編碼，表示某個地區八個城市的代號。碼距：一個編碼系統中任意兩個合法編碼之間對應二進制位狀態不同的位數，稱為這兩個編碼的距離。任意兩個編碼的最小距離就是該編碼系統的碼距，通常用d表示。例子中的d=？二進制編碼 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為了使一個

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

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

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

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

7、的指錯字G3 G2 G1。7654321A4A3A2P3A1P2P1 Pi在海明碼中位序號為2i-1的位置上。7/19/2022147654321指錯字A4A3A2P3A1P2P1第3組G3第2組G2第1組G1 “”表示某位海明碼參加某組。 有效數據位Ai分別參加2組以上，且滿足如下關系：其位序號要等于所參與各組的校驗位的位序號之和。 每個校驗位Pi只參加本組。7/19/202215(3)編碼（以偶校驗為例）？第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、查錯與糾錯若G3G2G1000，若G3G2G1000，則無錯；則G3G2G1的值即指明出錯位，將該位取反即可糾正。7/19/2022167654321指錯字G3G2G1A4A3A2P3A1P2P1正確碼0101101000出錯碼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)邏輯實現(譯碼電路)7/19/202218 由于每一個有效數據位至少要參加兩個校驗組的奇偶檢測，因此當兩個有效數據只有一位不相同時，該位至少引起兩個校驗位的不同！故碼距d3。(6)

9、分析 d3的碼能夠檢測2位錯，或用來檢測并糾正 1位錯，但兩者只能擇一。 如要能檢測并糾正1位錯，同時能發現2位錯， 此時應增加一個校驗位，即應滿足： 2r-1k+r7/19/202219 校驗規則：讓校驗碼能被某一約定代碼除盡。 若能除盡，表明代碼無錯； 若除不盡，余數將指明出錯位置。 三、 循環冗余校驗碼（CRC碼） 實現原理：在k位信息位之后拼接r位校驗位。 問題1：如何從k位信息位簡便地得到r位校驗位？ 問題2：如何從k+r位信息碼判斷是否有錯？7/19/202220 模2運算：以按位模2相加為基礎， 運算時不考慮進位和借位。 模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運算來建立編譯碼規律的校驗碼，在計算機外存儲器校驗和通信等方面應用廣泛。7/19/202221 模2除（用模2減求余數） 每求1位商使部分余數減少1位。 上商原則：部分余數的首位為1，商取1； 部分余數的首位為0，商取0。 當部分余數位數小于除數位數時，該余數為最后余數。 例如： 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設：被除數M(x)：k位待編信息 除數G

11、(x)：r+1位？ 余數R(x)：r位校驗位 商Q(x) (1) CRC碼的編碼方法 具體實現a. 將待編碼的k位有效信息位組寫成表達式： M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+C0 (Ci=0或1)b. 將信息位組左移r位，變成多項式M(x) Xr；c. 用M(x) Xr除以G(x)，所得余數作為校驗位。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例如：對M(x)=1100，用G(x)=1011，求CRC碼。a. 將待編碼的k=4位有效信息位組寫成表達

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)，所得余數作為校驗位。d. 有效的CRC碼此處為(7,4)碼為： M(x) Xr+R(x)= 1100000 + 010 = 1100010。7/19/202224(2) CRC碼的譯碼與糾錯 譯碼：用收到的CRC碼除以G(x)。 若碼字無誤，則余數為0； 若有某1位錯，則余數不為0且不同位出錯時的余數不同。注意：余數與出錯位的對應關系不變， 它只與碼制和生成多項式G(x)有關， 而與待測碼字無關。7/19/202225 (7，4)循環碼的出錯模式(生成多項式G(x)=1011) A1A2A3A4A5A6A7余數出錯位正確11000100 0 0無錯誤11000110 0 1711000000 1 0611001101 0 0511010100 1 1411100101 1 0310000101 1 1201000101 0 117/19/202226 糾錯： 對于用G(x)作模2除得到的余數R(x)，若補0繼續除下去，發現各次的余數按上表的順序循環。 所以，可以采用一種節省硬件的糾錯辦法： 如只設置余數101的譯碼輸出，對應于第1位A1出錯。 在求出余數不為0后，對余數一邊補