【正文】 部分 計算機(jī)組成原理 72 （ 3）規(guī)格化處理。本例尾數(shù)已規(guī)格化，不需要再處理。如未規(guī)格化，需左規(guī)。 （ 4）舍入。尾數(shù) (乘積 )低位部分的最高為 1，需要舍入，在乘積高位部分的最低位加 1因此 [X Y]補(bǔ)＝ 1． 0011010 (尾數(shù)部分 ) （ 5）判溢出。階碼未溢出，故結(jié)果為正確。 X Y： 0110 10011010 階碼 (移碼 ) 尾數(shù) (補(bǔ)碼 ) X Y=22（－ ） 說明：浮點(diǎn)數(shù)除法運(yùn)算步驟與乘法運(yùn)算類似，也分求商的階碼、尾數(shù)相除、規(guī)格化、舍入判溢出 5個步驟，不再詳細(xì)討論。 3．浮點(diǎn)運(yùn)算部件 通常由階碼運(yùn)算部件和尾數(shù)運(yùn)算部件組成，其各自的結(jié)構(gòu)與定點(diǎn)運(yùn)算部件相似。但階碼部分僅執(zhí)行加減法運(yùn)算。其尾數(shù)部分則執(zhí)行加減乘除運(yùn)算，左規(guī)時有時需要左移多位。為加速移位過程，有的機(jī)器設(shè)置了可移動多位的電路。 計算機(jī)組成原理 73 計算機(jī)系統(tǒng)中的數(shù)據(jù)，在讀寫、存取和傳送的過程中可能產(chǎn)生錯誤。為減少和避免這類錯誤，一方面是精心設(shè)計各種電路，提高計算機(jī)硬件的可靠性；另一方面是在數(shù)據(jù)編碼上找出路，即采用某種編碼法，通過少量的附加電路，使之能發(fā)現(xiàn)某些錯誤，甚至能確定出錯位置，進(jìn)而實(shí)現(xiàn)自動改錯的能力。 數(shù)據(jù)校驗(yàn)碼是一種常用的帶有發(fā)現(xiàn)某些錯誤或自動改錯能力的數(shù)據(jù)編碼方法。它的實(shí)現(xiàn)原理，是加進(jìn)一些冗余碼，使合法數(shù)據(jù)編碼出現(xiàn)某些錯誤時，就成為非法編碼。這樣，就可以通過檢測編碼的合法性來達(dá)到發(fā)現(xiàn)錯誤的目的。 碼距是根據(jù)任意兩個合法碼之間至少有幾個二進(jìn)制位不相同而確定的，僅有一位不同，稱其碼距為 1。 常用的數(shù)據(jù)校驗(yàn)碼主要有奇偶校驗(yàn)碼、海明校驗(yàn)碼和循環(huán)冗余校驗(yàn)碼 計算機(jī)組成原理 74 奇偶校驗(yàn)碼 奇偶校驗(yàn)碼是一種開銷最小，能發(fā)現(xiàn)數(shù)據(jù)代碼中一位錯情況的編碼，常用于存儲器讀寫檢查，或 ASCII字符傳送過程中的檢查。奇偶校驗(yàn)法的基本思想是通過在原數(shù)據(jù)信息中增加一位奇校驗(yàn)位（或偶校驗(yàn)位），然后將原數(shù)據(jù)和得到的奇（偶）校驗(yàn)位一起進(jìn)行存取或傳送，對存取后或在傳送的目標(biāo)部件得到的相應(yīng)數(shù)據(jù)和奇（偶）校驗(yàn)位，再進(jìn)行一次編碼，求出新的奇校驗(yàn)位（或偶校驗(yàn)位），最后根據(jù)得到的這個新的校驗(yàn)位的值，確定是否發(fā)生了錯誤。 奇偶校驗(yàn)碼的實(shí)現(xiàn)原理如下：假設(shè)將數(shù)據(jù) B=bn1bn2...b1b0從源部件傳送至目標(biāo)部件。在終部件接收到的數(shù)據(jù)為 B39。=bn139。bn239。...b139。b039。為了判斷數(shù)據(jù) B在傳送中是否發(fā)生了錯誤，可以按照如下步驟，通過最終得到的奇（偶）校驗(yàn)位 P*來判斷是否發(fā)生了數(shù)據(jù)傳送錯誤。 計算機(jī)組成原理 75 第 1步：在源部件求出奇（偶）校驗(yàn)位 P。 若采用奇校驗(yàn)位，則 P=bn1⊕ bn2 ⊕ ...⊕ b1⊕ b0⊕ 1。 即：若 B有奇數(shù)個 1，則 P取 0，否則， P取 1。 若采用偶校驗(yàn)位，則 P=bn1⊕ bn2 ⊕ ...⊕ b1⊕ b0。 例如，若傳送的字符碼是： 1000001，則增加奇校驗(yàn)位后的編碼為：11000001，而加上偶校驗(yàn)位后的編碼為： 01000001。 第 2步：在目標(biāo)部件求出奇（偶）校驗(yàn)位 P39。 若采用奇校驗(yàn)位，則 P39。= bn139。⊕ bn239。⊕ ...⊕ b139。⊕ b039。⊕ 1。 若采用偶校驗(yàn)位，則 P39。=bn139。⊕ bn2 39。⊕ ...⊕ b139。⊕ b039。 第 3步：計算最終的校驗(yàn)位 P*，并根據(jù)其值判斷有無奇偶錯。 P與 B是一起從源部件傳到目標(biāo)部件的，假定 P在目標(biāo)部件接受到的值為 P，則采用異或操作 P*=P39。⊕ P，對 P39。和 P進(jìn)行下列比較，確定有無奇偶錯： (1)若 P*=1，則表示目標(biāo)部件接受的數(shù)據(jù)有奇數(shù)位錯。 (2)若 P*=0，則表示目標(biāo)部件接受的數(shù)據(jù)正確或有偶數(shù)個錯。 計算機(jī)組成原理 76 在奇偶校驗(yàn)碼中，若兩個數(shù)據(jù)中有奇數(shù)位不同，則它們相應(yīng)的校驗(yàn)位就不同；若有偶數(shù)位不同，則雖校驗(yàn)位相同，但至少有兩位數(shù)據(jù)位不同。因而任意兩個碼字之間至少有兩位不同，所以碼距 d=2。因而只能發(fā)現(xiàn)奇數(shù)位出錯，不能發(fā)現(xiàn)偶數(shù)位出錯，而且也不能確定發(fā)生錯誤的位置，因而不具有糾錯能力。圖 38 奇偶校驗(yàn)位的形成及校驗(yàn) 計算機(jī)組成原理 77 海明校驗(yàn)碼 海明校驗(yàn)碼是由 Richard Hamming于 1950年提出的目前還被廣泛使用的一種數(shù)據(jù)校驗(yàn)碼。它主要用于存儲器中數(shù)據(jù)存取校驗(yàn)。前面所述的奇偶校驗(yàn)碼對整個數(shù)據(jù)編碼生成一位校驗(yàn)位。因此這種校驗(yàn)碼檢錯能力差，并且沒有糾錯能力。如果將整個數(shù)據(jù)按某種規(guī)律分成若干組，對每組進(jìn)行相應(yīng)的奇偶檢測，就能提供多位檢錯信息，從而對錯誤位置進(jìn)行定位，并將其糾正。海明校驗(yàn)碼實(shí)質(zhì)上就是一種多重奇偶校驗(yàn)碼。 海明校驗(yàn)碼的處理過程與上面給出的一般過程一樣。最終進(jìn)行比較時，按位進(jìn)行異或操作，根據(jù)異或操作的結(jié)果，確定是否發(fā)生了差錯。這種異或操作所得到的結(jié)果稱為故障字（ syndrome word）。顯然，校驗(yàn)位和故障字的位數(shù)是相同的 計算機(jī)組成原理 78 1. 校驗(yàn)位位數(shù)的確定 假設(shè)校驗(yàn)位的個數(shù)為 r。則它能表示 2r個信息，用其中的一個信息指出“沒有錯誤”，其余的 2r1個信息指出錯誤發(fā)生在哪一位。然而錯誤也可能發(fā)生在校驗(yàn)位，因此只有 k＝ 2r1r個信息能用于糾正被傳送數(shù)據(jù)的位數(shù)，也就是說要滿足關(guān)系： 2r≥k+r+1 (公式 1) 如要能檢測與自動校正一位錯，并發(fā)現(xiàn)兩位錯，此時校驗(yàn)位的位數(shù) r和數(shù)據(jù)位的位數(shù) k是應(yīng)滿足下述關(guān)系： 2r1≥k+r (公式 2) 計算機(jī)組成原理 79 2．分組方式的確定 數(shù)據(jù)位和校驗(yàn)位是一起被存儲的，通過將它們中的各位按某種方式排列為一個 n+k的碼字，將該字中每一位的出錯位置與故障字的數(shù)值建立關(guān)系，這樣就可通過故障字的值很快確定是該碼字中的哪一位發(fā)生了錯誤，并能很容易地將其取反來糾正。 根據(jù)上述基本思想，我們按以下規(guī)則來解釋各故障字的值。 （ 1）如果故障字各位全部是 0，則表示沒有發(fā)生錯誤。 （ 2）如果故障字中有且僅有一位為 1，則表示校驗(yàn)位中有一位出錯，不需要糾正。 （ 3）如果故障字中多位為 1，則表示有一個數(shù)據(jù)位出錯，其在碼字中的出錯位置由故障字的數(shù)值來確定。糾正時只要將出錯位取反即可。 為了介紹海明校驗(yàn)碼的原理，以 8位數(shù)據(jù)進(jìn)行檢測與自動校正一位錯的代碼為例說明。假定一個 8位數(shù)據(jù) M= D8D7D6D5D4D3D2D1， K=8,根據(jù)公式 1可以計算出 r＝ 4， 8位數(shù)據(jù)需要 4位校驗(yàn)位，其相應(yīng)的 4位校驗(yàn)位為 P=P4P3P2P1，所以可知海明碼共 12位（ k+r）。 計算機(jī)組成原理 80 假若海明碼表示為 M＝ HmHm1…H2H1 ，其最高位號為 m，最低位號為 1，則此海明碼的編碼規(guī)律通常是： (1)校驗(yàn)位與數(shù)據(jù)位之和為 m，每個校驗(yàn)位 Pi在海明碼中被分在位號 2i1位置，其余各位為數(shù)據(jù)位，并按從低向高逐位依次排列的關(guān)系分配各數(shù)據(jù)位 — 。 (2)海明碼的每一位碼 Hi(包括數(shù)據(jù)位和校驗(yàn)位本身 )由多個校驗(yàn)位校驗(yàn)，其關(guān)系是被校驗(yàn)的每一位位號要等于校驗(yàn)它的各校驗(yàn)位的位號之和。這樣安排的目的，是希望校驗(yàn)的結(jié)果能正確反映出出錯位的位號。 按上述規(guī)律 8個二進(jìn)制數(shù)據(jù)位的海明碼可表示為： H12 H11 … H3 H2 H1 4個校驗(yàn)位 P4～ P1對應(yīng)的海明碼位號應(yīng)分別為 H8， H4，H2和 H1，滿足 Pi的位號等于 2i1的關(guān)系。其余為數(shù)據(jù)位 Di，則 H12～ H1有如下排列關(guān)系： D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1 計算機(jī)組成原理 81 按照前面敘述的規(guī)則解釋上述編碼，將數(shù)據(jù) D和校驗(yàn)位P按照一定的規(guī)律排到一個 12位的碼字中。根據(jù)上述第一個規(guī)則，故障字為 0000時，表示無錯，因此沒有和位置號0000對應(yīng)的出錯情況，所以位置號從 0001開始。根據(jù)第二個規(guī)則，故障字中有且僅有一位為 1時，表示校驗(yàn)位中有一位出錯，此時，故障字只可能是 000 00 0100、 1000四種情況，將這四種狀態(tài)分別代表校驗(yàn)位中第 P P PP4位發(fā)生錯誤的情況，因此，校驗(yàn)位 P P P P4應(yīng)分別位于碼字的第 000 00 0100、 1000位。根據(jù)最后一個規(guī)則，將其他多位為 1的故障字依次表示數(shù)據(jù)位 D1～ D8發(fā)生錯誤的情況。因此，數(shù)據(jù)位 D1～ D88應(yīng)分別位于碼字的第001 010 01 011 100 10 101 1100位。 計算機(jī)組成原理 82 3．校驗(yàn)位的生成和檢錯、糾錯 分組完成后，就可對每組采用相應(yīng)的奇（偶）校驗(yàn)，以得到相應(yīng)的一個校驗(yàn)位。如 P1參與對數(shù)據(jù)位 Dl， D2， D4， D5和 D7的校驗(yàn)， P4參與對 D5 D6 D7 和 D8 的校驗(yàn)等等。假定采用偶校驗(yàn)（即取校驗(yàn)位 Pi，使對應(yīng)組中有偶數(shù)個 1），則得到校驗(yàn)位與數(shù)據(jù)位之間存在如下關(guān)系： P1 =Dl⊕ D2⊕ D4⊕ D5⊕ D7 () P2=Dl⊕ D3⊕ D4⊕ D6⊕ D7 () P3=D2⊕ D3⊕ D4⊕ D8 () P4 =D5⊕ D6⊕ D7⊕ D8 () 注意：如果要分清是兩位出錯還是一位出錯，還要補(bǔ)充一個 P5總校驗(yàn)位，使 P5＝ D8⊕ D7⊕ D6⊕ D5⊕ D4⊕ D3⊕ D2⊕ D1⊕ P5⊕ P4⊕ P3⊕ P2⊕ P1 在上面式子中，每一位數(shù)據(jù)位都至少出現(xiàn)在 3個 Pi值的形成關(guān)系中。當(dāng)任一位數(shù)據(jù)碼發(fā)生變化時，必將引起 3個或 4個 Pi值跟著變化。 計算機(jī)組成原理 83 假如故障字 S=S4S3S2S1，根據(jù) S的值可以確定是沒有發(fā)生錯誤，還是僅校驗(yàn)位發(fā)生錯誤，還是哪一個數(shù)據(jù)位發(fā)生了錯誤。結(jié)合式子()～ ()可得到故障字和海明碼偶校驗(yàn)關(guān)系如下： S1= P1 ⊕ D1⊕ D2⊕ D4⊕ D5⊕ D7 () S2= P2 ⊕ D1⊕ D3⊕ D4⊕ D6⊕ D7 () S3= P3 ⊕ D2⊕ D3⊕ D4⊕ D8 () S4= P4 ⊕ D5⊕ D6⊕ D7⊕ D8 () S5= P5⊕ P4⊕ P3⊕ P2⊕ P1⊕ D8⊕ D7⊕ D6⊕ D5⊕ D4⊕ D3⊕ D2⊕ D1 () 則校驗(yàn)得到的結(jié)果值 S4～ S1能反映 12位海明碼的出錯情況。 注意：如果要發(fā)現(xiàn)兩位出錯必須使用 S5= P5⊕ P4⊕ P3⊕ P2⊕ P1⊕ D8⊕ D7⊕ D6⊕ D5⊕ D4⊕ D3⊕ D2⊕ D1公式計算出 S5，任何偶數(shù)個數(shù)出錯， S5一定為 0，因此可區(qū)分兩位出錯或一位出錯。 計算機(jī)組成原理 84 圖 39是 H＝ 12，數(shù)據(jù)位 k＝ 8，校驗(yàn)位 r=4的海明校驗(yàn)線路，記作 (12， 8)分組碼。 圖 39 (12， 8)分組碼海明校驗(yàn)框圖 計算機(jī)組成原理 85 (CRC)碼 循環(huán)冗余校驗(yàn)碼（ Cyclic Redundancy Check），簡稱 CRC碼，是一種具有很強(qiáng)檢錯、糾錯能力的校驗(yàn)碼。循環(huán)冗余校驗(yàn)碼常用于外存儲器的數(shù)據(jù)校驗(yàn)，在計算機(jī)通信中，也被廣泛采用。在數(shù)據(jù)傳輸中奇偶校驗(yàn)碼是在每個字符信息后增加一位奇偶校驗(yàn)位來進(jìn)行數(shù)據(jù)校驗(yàn)的，這樣對大批量傳輸數(shù)據(jù)進(jìn)行校驗(yàn)時，會增加大量的額外開銷，尤其是在網(wǎng)絡(luò)通信中，傳輸?shù)臄?shù)據(jù)信息都是二進(jìn)制比特流，因而沒有必要將數(shù)據(jù)再分解成一個個字符，這樣也就無法采用奇偶校驗(yàn)碼，因此，通常采用 CRC碼進(jìn)行校驗(yàn)。 CRC碼可以發(fā)現(xiàn)并糾正信息存儲或傳送過程中連續(xù)出現(xiàn)的多位錯誤，其實(shí)現(xiàn)方法主要是 在 k位信息碼之后拼接 r位校驗(yàn)碼。應(yīng)用 CRC碼的關(guān)鍵是如何從 k位信息位簡便地得到 r位校驗(yàn)位 (編碼 )，以及如何從 k+r位信息碼判斷是否出錯。 因?yàn)?CRC碼的編碼原理復(fù)雜，它是通過某種數(shù)學(xué)運(yùn)算來建立數(shù)據(jù)和校驗(yàn)位之間的約定關(guān)系，這里僅對其編碼方式和實(shí)現(xiàn)過程作簡單介紹，而不詳細(xì)進(jìn)行數(shù)學(xué)推導(dǎo)。 計算機(jī)組成原理 86 1．模 2運(yùn)算 先介紹 CRC碼編碼用到的模 2運(yùn)算。 模 2運(yùn)算是指以按位模 2相加為基礎(chǔ)的四則運(yùn)算，運(yùn)算時不考慮進(jìn)位和借位。 (1)模 2加減：即按位加，可用異或邏輯實(shí)現(xiàn)。模 2加與模 2減的結(jié)果相同， 即 0177。 0=0， 0177。 1=1， 1177。 0=1， 1177。 1=0。兩個相同的數(shù)據(jù)的模 2和為 0。 (2)模 2乘 ―― 按模 2加求部分積之和 . 例如： 1 1 1 0 ) 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0