計算機組成與體系結構第2章計算機系統中的

數據表示2.4檢錯與糾錯碼2數據出錯的原因：元器件故障；存儲介質；通信過程中的噪聲干擾。如何減少或避免數據錯誤：提高計算機系統硬件本身的可靠性。在電路、電源、布線等各方面采取必要的措施，提高計算機系統的抗干擾能力。改進生產工藝，提高器件的可靠性。采取數據檢錯和校正措施：在每個字中添加一些校驗位，用來確定字中出現錯誤的位置。經濟成本、設計目標32.4檢錯與糾錯碼奇偶校驗碼循環冗余校驗碼漢明碼4一、奇偶校驗碼定義：設X＝(xn-1xn-2…x2x1x0)是一個n位字，則

奇校驗位C定義為：

當X中包含有奇數個1時，C＝1，既C＝0。

偶校驗位C定義為：

當X中包含有偶數個1時，C＝0。5一、奇偶校驗碼校驗過程：

將一個字X從部件A傳送到部件B，采用偶校驗。發送端A：

計算出校驗位C，與要發送的數據合在一起，將（xn-1xn-2…x2x1x0C）發送到接收端B。接收端B：

接收到的是X’＝(x’n-1x’n-2…x’2x’1x’0C’)，

然后計算若F＝1，收到的信息有錯；若F＝0，字X傳送正確。6一、奇偶校驗碼缺點：只能檢測每個字中所產生的奇數個錯誤不具備糾錯能力優點：開銷小常用于校驗1字節長的數據：

通常1字節長的數據編碼發生錯誤時，1位出錯的概率較大，兩位以上同時出錯的概率極小。常用于存儲器讀寫校驗按字節傳輸過程中的數據校驗7一、奇偶校驗碼【例】假定最低一位為校驗位，其余高8位為數據位。數據偶校驗編碼奇校驗編碼0101010101010101x01010101x0010101000101010x00101010x0000000000000000x00000000x0111111101111111x01111111x1111111111111111x11111111x0101010100010101010000000000111111111111111100101010110010101000000000010111111101111111118一、奇偶校驗碼二維奇偶校驗：磁帶驅動器垂直冗余檢查VRC：

VerticalRedundancyCheck，

垂直方向(行)上的奇偶校驗檢查。縱向冗余檢查LRC：

LongitudinalRedundancyCheck，

縱長方向(列)上的奇偶檢查?！纠拷o定一個字符串：“Wearefriend．”，采用二維奇偶校驗檢查（偶校驗）。給出發送端的二維數據組織；人為引入錯誤，演示VRC和LRC的檢錯過程。9一、奇偶校驗碼【例】給定一個字符串：“Wearefriend．”，采用二維奇偶校驗檢查（偶校驗）。給出發送端的二維數據組織；人為引入錯誤，演示VRC和LRC的檢錯過程?！窘狻堪l送端：二維數據組織：Wearefriend．57652061726520667269656E642E—7位ASCIID765A0E17265A066726965EEE42E—偶校驗ASCII10VRC列號字符

87654321

行號111010111W

201100101e

310100000

411100001a

501110010r

601100101e

710100000

801100110f

901110010r

1001101001i

1101100101e

1211101110n

1311100100d

1400101110．

1501111000LRC57D7656520A061066667272696965656EEE64E42E2E一、奇偶校驗碼例：二維奇偶校驗(發送端)7位ASCII偶校驗ASCII11VRC列號字符

87654321

行號111110101W

201100101e

310100000

411000001a

501110010r

601100101e

710100000

801100010f

901110010r

1001101001i

1101100101e

1211101110n

1311100100d

1400101110．

1501111000LRC57D7656520A061066667272696965656EEE64E42E2E一、奇偶校驗碼例：二維奇偶校驗(接收端)7位ASCII偶校驗ASCII12二、循環冗余校驗碼循環冗余校驗：

CyclicRedundancyCheck，簡稱CRC。13二、循環冗余校驗碼1.CRC算法原理通過某種數學運算建立數據和校驗位之間的約定關系。編碼及譯碼：發送端：被校驗數據除以生成多項式；被校驗數據減去余數，結果作為發送數據。接收端：接收數據除以生成多項式?？梢猿M，編碼正確；除不盡，余數指明出錯位所在的位置。14二、循環冗余校驗碼1.CRC算法原理采用模2算術運算：通過模2減法實現模2除法；以模2加法將所得余數拼接在被校驗數據的后面，形成能除盡的被校驗數據。生成多項式應滿足的要求：任何一位發生錯誤都應使余數不為0；不同位發生錯誤應當使余數不同；應滿足余數循環規律。生成多項式的表示：

如，生成多項式G＝10112，表示生成多項式為

G(X)＝X3＋X＋115二、循環冗余校驗碼2.CRC編碼及譯碼符號及約定：被校驗數據(被除數)為F(X)；約定的生成多項式(除數)為G(X)；發送方和接收方使用同一個生成多項式G(X)G(X)的首位和最后一位的系數必須為1所產生的余數為R(X)。16二、循環冗余校驗碼2.CRC編碼及譯碼發送端，CRC的編碼方法：將被校驗數據(共k位)的有效信息F(X)左移r

位，得到

F(X)×Xr。選取一個r＋1

位的生成多項式G(X)，對F(X)×Xr作模2除法：

F(X)×Xr/G(X)＝Q(X)＋R(X)/G(X)將F(X)與R(X)相拼接。

F(X)×Xr＋R(X)＝F(X)×Xr－R(X)＝Q(X)×G(X)

拼接了校驗碼的數據必定能被約定的G(X)所除盡。17二、循環冗余校驗碼2.CRC編碼及譯碼接收端，CRC的譯碼方法：將接收到的編碼字除以約定的生成多項式G(X)：余數為0，則傳輸沒有錯誤。余數不為0，則某一位出錯。余數代碼與出錯位序號之間有唯一的對應關系：根據余數找到出錯位；將出錯位取反即可糾錯。18二、循環冗余校驗碼2.CRC編碼及譯碼【例】假設信息字節為

F＝10010102

；選取G＝10112；將F左移l－1位，

形成F'

＝10010100002

；用F'

做被除數、G做除數，

進行模2除法。

忽略商，余數為R＝1112。把余數加到F'中，組成要發送的信息M：10010100002＋1112＝10010101112。接收器采用相反的過程對接收的信息M進行解碼和校驗。M應該可以被G嚴格整除。100101000010111010101101110011000101111001011111101119二、循環冗余校驗碼2.CRC編碼及譯碼【例】接收器：解碼校驗（正確的情況）接收器：解碼校驗（1位出錯的情況）20二、循環冗余校驗碼2.CRC編碼及譯碼【例】接收器：解碼校驗（正確的情況）接收器：解碼校驗（1位出錯的情況）21二、循環冗余校驗碼3.CRC碼的糾錯(7，4)循環碼編碼、余數與出錯位置的關系G(X)＝10112編碼舉例1編碼舉例2余數出錯

位置數據位6543校驗位210數據位6543校驗位210正確10011101100010000無錯誤10011111100011001010011001100000010110010101100110100210001101101010011310111101110010110411011101000010111500011100100010101622二、循環冗余校驗碼CRC的生成多項式的階數越高，誤判的概率就越小。常用的4個標準多項式：CRC-12：

G(X)＝X12＋X11＋X3＋X2＋X＋1CRC-16(ANSI)：

G(X)＝X16＋X15＋X2＋1CRC-CCITT(ITU-T)：

G(X)＝X16＋X12＋X5＋1CRC-32：

G(X)＝X32＋X26＋X23＋X22＋X16＋X12＋X11

＋X10＋X8＋X7＋X5＋X4＋X2＋X＋123三、漢明碼某些系統需要具備糾正合理數量錯誤的能力。漢明碼(Hammingcode)：由RichardHamming于1950年提出。主要用于存儲器數據的校驗與糾正。采用奇偶校驗的原理，錯誤檢測和校正能力隨著信息字中加入奇偶校驗位的數目線性增加。適用于最有可能發生隨機錯誤的系統。每一位的出錯概率相同；每一位與其它位是否出錯沒有任何關聯。24三、漢明碼1.最小漢明距離兩個編碼字之間對應位置數值不同的位置數目稱為兩個編碼字的漢明距離。【例】假定某編碼方案有下列8個合法編碼：000000、001011、010101、011110、

100110、101101、110011、111000。找出任意編碼字之間的海明距離，可以發現最小漢明距離為：Dmin＝3。假設讀到的編碼字為001000，與上述8種合法編碼字都不相同，因此至少存在1位錯誤。差額向量：（1，2，4，3，4，3，5，2）校正結果：00000010110111001125三、漢明碼1.最小漢明距離任意編碼字X如果被當作另外一個合法的編碼字Y被接收的話，則在X中至少發生了Dmin個錯誤。要檢測出k個(或少于k個)單位錯誤，所有合法編碼之間就至少具有Dmin＝k＋1的漢明距離。漢明編碼通?？梢詸z測出Dmin-1個碼位錯誤；漢明編碼可以校正個碼位錯誤。要能校正k個錯誤，編碼方案的最小漢明距離必須大于2k＋1。最小漢明距離Dmin決定了該編碼校驗和糾正錯誤的能力。26三、漢明碼

2.檢錯與糾錯方法(n＋1)×2m≤2n信息碼校驗碼m位r位編碼字：n位在只發生1位錯誤的情況下，每個數據可能對應的編碼字的個數(1個合法的編碼字＋n個非法的編碼字)2r－1≥n＝m＋r(m＋r＋1)≤2rr位校驗碼可以區分出：“1個合法的編碼字＋n個非法的編碼字”27三、漢明碼

2.檢錯與糾錯方法數據位的

位數m校驗位的

位數r增加的

百分比4375.00％8450.00％16531.25％32618.75％64710.94％12886.25％25693.52％數據位與校驗位之間位數的關系(m＋r＋1)≤2r信息碼校驗碼m位r位編碼字：n位假設數據位長度m＝3，則：r≥3(r＋4)≤2r28三、漢明碼3.漢明校驗先確定編碼所需的校驗位數目r，然后算出編碼字的長度n，其中n＝m＋r。將編碼字的各位從右向左排列，從1開始進行位置編號。編號是2的整數次冪的位置為奇偶校驗位，其它位為數據位，按順序填寫。用如下方法確定某數據位應被哪些奇偶校驗位所檢測：第b位數據應被第b1、b2、…、bj位奇偶校驗位所檢測。其中，b1、b2、…、bj必為2的整數次冪，且b1＋b2＋…＋bj＝b。

比如，位置編號為7（即b＝7）的數據，由于b＝1＋2＋4，則此數據位應被位置編號為1、2、4的奇偶校驗位所檢測。29三、漢明碼3.漢明校驗【例2.21】利用上述構造海明碼的步驟，采用偶校驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤?！窘狻孔址癕”的ASCII編碼為01001101。①

確定所需校驗位的數目。 數據位的位數m＝8，設校驗位的位數為r， 則根據不等式(m＋r＋1)≤2r， 即(r＋9)≤2r，有r≥4。 選擇r＝4，則編碼字共m＋r＝12位。

②

編碼字：1211109876543210100110130三、漢明碼3.漢明校驗【例2.21】利用上述構造海明碼的步驟，采用偶校驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤?！窘狻孔址癕”的ASCII編碼為01001101。③

確定奇偶校驗位的值：121110987654321010011011＝12＝23＝1＋24＝45＝1＋46＝2＋47＝1＋2＋48＝89＝1＋810＝2＋811＝1＋2＋812＝4＋831三、漢明碼3.漢明校驗【例2.21】利用上述構造海明碼的步驟，采用偶校驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤?！窘狻孔址癕”的ASCII編碼為01001101。③

確定奇偶校驗位的值：121110987654321010011011＝12＝23＝1＋24＝45＝1＋46＝2＋4

7＝1＋2＋48＝8

9＝1＋810＝2＋811＝1＋2＋812＝4＋8132三、漢明碼3.漢明校驗【例2.21】利用上述構造海明碼的步驟，采用偶校驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤?！窘狻孔址癕”的ASCII編碼為01001101。③

確定奇偶校驗位的值：121110987654321010011011＝12＝23＝1＋24＝45＝1＋46＝2＋4

7＝1＋2＋48＝89＝1＋810＝2＋811＝1＋2＋812＝4＋81033三、漢明碼3.漢明校驗【例2.21】利用上述構造海明碼的步驟，采用偶校驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤。【解】字符“M”的ASCII編碼為01001101。③

確定奇偶校驗位的值：121110987654321010011011＝12＝23＝1＋24＝45＝1＋46＝2＋4

7＝1＋2＋48＝89＝1＋810＝2＋811＝1＋2＋812＝4＋810034三、漢明碼3.漢明校驗【例2.21】利用上述構造海明碼的步驟，采用偶校驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤。【解】字符“M”的ASCII編碼為01001101。③

確定奇偶校驗位的值：121110987654321010011011＝12＝23＝1＋24＝45＝1＋46＝2＋47＝1＋2＋4

8＝8

9＝1＋810＝2＋811＝1＋2＋812＝4＋81001因此，“M”的編碼字為：。35三、漢明碼3.漢明校驗【例2.21】利用上述構造海明碼的步驟，采用偶校驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤?！窘狻俊癕”的編碼字為：。④在第6位引入一個錯誤：1211109876543210100100110011＝12＝23＝1＋24＝45＝1＋46＝2＋47＝1＋2＋48＝89＝1＋810＝2＋811＝1＋2＋812＝4＋836三、漢明碼4.總結假設16位數據D＝D15D14D13D12D11D10D9D8D7D6D5D4D3D2D1D0，對應的校驗位H＝H4H3H2H1H0，則海明碼及其校驗方程：編碼

內容D15D14D13D12D11H4D10D9D8D7D6D5D4H3D3D2D1H2D0H1H0編碼

位置212019181716151413121110987654321校驗方程PP0＝D15⊕D13⊕D11⊕D10⊕D8⊕D6⊕D4⊕D3⊕D1⊕D0⊕H0P1＝D13⊕D12⊕D10⊕D9⊕D6⊕D5⊕D3⊕D2⊕D0⊕H1P2＝D15⊕D14⊕D10⊕D9⊕D8⊕D7⊕D3⊕D2⊕D1⊕H2P3＝D10⊕D9⊕D8⊕D7⊕D6⊕D5⊕D4⊕H3P4＝D15⊕D14⊕D13⊕D12⊕D11⊕H437三、漢明碼4.總結發送端如何產生8位或16位數據的漢明碼？假定所有的校驗位Hi均為0，計算出校驗方程Pi(i＝0～4)；將計算出來的Pi看成相應的Hi，填入對應的編碼位置。接收端如何校驗及糾錯？將接收到的編碼字的各位帶入校驗方程：若各校驗方程的計算結果均為0，則數據正確；若計算結果不為0，則它們的編碼值P（P＝P4P3P2P1P0）就表示出錯位的位置編號；根據出錯的位置編號，將編碼字中的對應位取反即可實現糾錯。38三、漢明碼4.總結【例2.21】利用上述構造海明碼的步驟，采用偶校

驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤?！窘狻孔址癕”的ASCII編碼為01001101。假定H0～H3均為0，計算Pi：P0＝D6⊕D4⊕D3⊕D1⊕D0⊕H0＝1⊕0⊕1⊕0⊕1⊕0＝1＝H0P1＝D6⊕D5⊕D3⊕D2⊕D0⊕H1＝1⊕0⊕1⊕1⊕1⊕0＝0＝H1P2＝D7⊕D3⊕D2⊕D1⊕H2＝0⊕1⊕1⊕0⊕0＝0＝H2P3＝D7⊕D6⊕D5⊕D4⊕H3＝0⊕1⊕0⊕0⊕0＝1＝H3∴ASCII字符“M”對應的海明碼編碼字為：C＝D7D6D5D4H3D3D2D1H2D0H1H0＝39三、漢明碼4.總結【例2.21】利用上述構造海明碼的步驟，采用偶校

驗，對8位ASCII字符“M”進行編碼（最高位為0）。人為地引入一個1位錯誤，說明如何找出這個錯誤。【解】在接收端，根據接收到的編碼字求得校驗方程Pi（i＝0～4），校驗方程的編碼值P(P＝P4P3P2P1P0)可作如下解釋：(1)如果P各位全是0，則表示接收到的編碼字中沒有錯誤。(2)如果P中多位為1，則表示有一個數據位出錯，且P的值即出錯位在編