第6章計(jì)算機(jī)中的數(shù)據(jù)表示方法

1、本章的主要內(nèi)容本章的主要內(nèi)容 數(shù)據(jù)表示：定點(diǎn)和浮點(diǎn)數(shù)據(jù)表示格式數(shù)據(jù)表示：定點(diǎn)和浮點(diǎn)數(shù)據(jù)表示格式(含浮點(diǎn)規(guī)格化含浮點(diǎn)規(guī)格化) 補(bǔ)碼中模的概念及應(yīng)用、補(bǔ)碼與真值之間的關(guān)系補(bǔ)碼中模的概念及應(yīng)用、補(bǔ)碼與真值之間的關(guān)系 校驗(yàn)及其原理、作用、實(shí)現(xiàn)方法校驗(yàn)及其原理、作用、實(shí)現(xiàn)方法 數(shù)據(jù)信息的校驗(yàn)數(shù)據(jù)信息的校驗(yàn) 第第6章章 計(jì)算機(jī)中的數(shù)據(jù)表示方法計(jì)算機(jī)中的數(shù)據(jù)表示方法 1、數(shù)據(jù)格式、數(shù)據(jù)格式 選擇數(shù)據(jù)格式要考慮的因素：選擇數(shù)據(jù)格式要考慮的因素： 數(shù)的類型數(shù)的類型 數(shù)的范圍數(shù)的范圍 數(shù)的精度數(shù)的精度 存儲和處理的代價存儲和處理的代價 是否有利于軟件的移植是否有利于軟件的移植 一、數(shù)值數(shù)據(jù)與非數(shù)值數(shù)據(jù)的表示方法一

2、、數(shù)值數(shù)據(jù)與非數(shù)值數(shù)據(jù)的表示方法 1)定點(diǎn)數(shù)定點(diǎn)數(shù) 可表示定點(diǎn)小數(shù)和整數(shù)可表示定點(diǎn)小數(shù)和整數(shù) 表現(xiàn)形式：表現(xiàn)形式：X0.X1X2X3X4.Xn 定點(diǎn)小數(shù)定點(diǎn)整數(shù) 定點(diǎn)小數(shù)的表示數(shù)的范圍：定點(diǎn)小數(shù)的表示數(shù)的范圍：1-2n |x| 2-n 定點(diǎn)整數(shù)的表示數(shù)的范圍：定點(diǎn)整數(shù)的表示數(shù)的范圍：2n-1 |x| 1 2、計(jì)算機(jī)中常用的兩種數(shù)值數(shù)據(jù)格式及其表示范圍、計(jì)算機(jī)中常用的兩種數(shù)值數(shù)據(jù)格式及其表示范圍 浮點(diǎn)數(shù)的使用場合浮點(diǎn)數(shù)的使用場合 當(dāng)數(shù)的表示范圍超出了定點(diǎn)數(shù)能表示的范圍時使用。當(dāng)數(shù)的表示范圍超出了定點(diǎn)數(shù)能表示的范圍時使用。 (1)格式格式(一般格式一般格式) ESE1E2E3EnMSM1M2M3M

3、4.Mk 階碼：決定數(shù)據(jù)的范圍階碼：決定數(shù)據(jù)的范圍 尾數(shù)：決定數(shù)的精度尾數(shù)：決定數(shù)的精度 2)浮點(diǎn)數(shù)：把數(shù)的范圍和精度分別表示的一種數(shù)據(jù)表示方法。浮點(diǎn)數(shù)：把數(shù)的范圍和精度分別表示的一種數(shù)據(jù)表示方法。 N=Rem 基基 (2)IEEE 754格式格式 S 8位偏指數(shù)位偏指數(shù)E23位有效尾數(shù)位有效尾數(shù)M單精度單精度 11位偏指數(shù)位偏指數(shù)E52位有效尾數(shù)位有效尾數(shù)M S 雙精度雙精度 指數(shù)采用偏移值指數(shù)采用偏移值,其中單精度為其中單精度為127,雙精度為雙精度為1023.這樣非負(fù)浮點(diǎn)數(shù)這樣非負(fù)浮點(diǎn)數(shù) 能作為整數(shù)對待進(jìn)行比較運(yùn)算能作為整數(shù)對待進(jìn)行比較運(yùn)算,便于浮點(diǎn)數(shù)的比較和排序便于浮點(diǎn)數(shù)的比較和排序.

4、 (A) 754尾數(shù)形式為尾數(shù)形式為1.XXXXXX, 其中其中M部分保存的是部分保存的是XXXXXX.這樣這樣 可以保留更多的有效數(shù)字位可以保留更多的有效數(shù)字位,進(jìn)一步提高數(shù)據(jù)表示的精確度進(jìn)一步提高數(shù)據(jù)表示的精確度 754的的0特殊處理特殊處理,只要指數(shù)為只要指數(shù)為0,不論尾數(shù)為多少均作為零對待不論尾數(shù)為多少均作為零對待 (A)計(jì)算機(jī)組成和設(shè)計(jì)計(jì)算機(jī)組成和設(shè)計(jì) 硬件硬件/軟件接口軟件接口 第第2版版 .P211-213.鄭緯民譯鄭緯民譯 IEEE754 32位浮點(diǎn)數(shù)與對應(yīng)真值之間的變換流程位浮點(diǎn)數(shù)與對應(yīng)真值之間的變換流程 例例1：將十進(jìn)制數(shù)：將十進(jìn)制數(shù)20.59375轉(zhuǎn)換成轉(zhuǎn)換成32位位IE

5、EE754格式浮點(diǎn)數(shù)的格式浮點(diǎn)數(shù)的 二進(jìn)制格式來存儲二進(jìn)制格式來存儲 。 解解:首先分別將整數(shù)和分?jǐn)?shù)部分轉(zhuǎn)換成二進(jìn)制數(shù)：首先分別將整數(shù)和分?jǐn)?shù)部分轉(zhuǎn)換成二進(jìn)制數(shù)： 20.59375=10100.10011(0.5+0.25+0.125+0.0625+0.03125) 移動小數(shù)點(diǎn)，使其變成移動小數(shù)點(diǎn)，使其變成1.M的形式的形式 10100.10011=1.01001001124 得到：得到： S=0, e = 4，E= 100+01111111 =10000011，M = 010010011 最后得到最后得到32位浮點(diǎn)數(shù)的二進(jìn)制存儲格式為：位浮點(diǎn)數(shù)的二進(jìn)制存儲格式為： 0100 0001 1010

6、 0100 1100 0000 0000 0000 = (41A4C000)16 例例2： 若某浮點(diǎn)數(shù)若某浮點(diǎn)數(shù)x的二進(jìn)制存儲格式為的二進(jìn)制存儲格式為(41360000)16 ,求與其求與其 對應(yīng)的對應(yīng)的32位浮點(diǎn)表示的十進(jìn)的值。位浮點(diǎn)表示的十進(jìn)的值。 解：解： 將將(41360000)16 = (0 100,0001,0 011,0 110,0 000,0 000,0 000,0 000)2 s=0 e=10000010-01111111=00000011=(3)10 1.M=1.011011 則上述浮點(diǎn)數(shù)對應(yīng)的真值為則上述浮點(diǎn)數(shù)對應(yīng)的真值為 X=(-1)0 (1.011011)2 23 =

7、(11.375)10 例例3 假設(shè)由假設(shè)由E、M二個域組成一個二個域組成一個32位二進(jìn)制所表示的非位二進(jìn)制所表示的非 零規(guī)格化浮點(diǎn)數(shù)零規(guī)格化浮點(diǎn)數(shù)X。若其階碼為。若其階碼為8位，尾數(shù)為位，尾數(shù)為24位。位。 求所求所 能表示的規(guī)格化的最大正數(shù)、最小正數(shù)、最大負(fù)數(shù)和最小能表示的規(guī)格化的最大正數(shù)、最小正數(shù)、最大負(fù)數(shù)和最小 負(fù)數(shù)分別是多少負(fù)數(shù)分別是多少？ 解：對于浮點(diǎn)數(shù)而言，其表示的真值由兩部分構(gòu)成：解：對于浮點(diǎn)數(shù)而言，其表示的真值由兩部分構(gòu)成： X= 2階碼的值 階碼的值 尾數(shù)值 尾數(shù)值 (假設(shè)均為補(bǔ)碼表示假設(shè)均為補(bǔ)碼表示) 最大正數(shù)：最大正數(shù)： 階碼正最大階碼正最大 而而0011與與0000兩組

8、兩組 編碼的距離為編碼的距離為2。 若用四位二進(jìn)制編碼只表示若用四位二進(jìn)制編碼只表示0000、0011、0101、0110、1001、 1010、1100、1111等八種編碼等八種編碼,則碼距為則碼距為2。此時，這。此時，這8種編碼種編碼 中的任何一位發(fā)生改變，如中的任何一位發(fā)生改變，如0000變成變成1000就從有效編碼變成就從有效編碼變成 了無效編碼，容易檢測到這種錯誤。了無效編碼，容易檢測到這種錯誤。 如果用四位二進(jìn)制編十六種狀態(tài)，情況又如何？如果用四位二進(jìn)制編十六種狀態(tài)，情況又如何？ 數(shù)據(jù)校驗(yàn)可數(shù)據(jù)校驗(yàn)可在正常編碼的基礎(chǔ)上，通過增加一些附加的校驗(yàn)位得在正常編碼的基礎(chǔ)上，通過增加一些附加

9、的校驗(yàn)位得 到。增加校驗(yàn)的同時也增加了碼距，當(dāng)碼距增加到一定程度時，到。增加校驗(yàn)的同時也增加了碼距，當(dāng)碼距增加到一定程度時， 校驗(yàn)碼不僅具有檢錯功能，而且還可具有糾正錯誤的能力。校驗(yàn)碼不僅具有檢錯功能，而且還可具有糾正錯誤的能力。 5) 5)碼距與數(shù)據(jù)校驗(yàn)之間的關(guān)系碼距與數(shù)據(jù)校驗(yàn)之間的關(guān)系 碼距碼距d與校驗(yàn)碼的與校驗(yàn)碼的檢錯檢錯和和糾錯糾錯能力的關(guān)系如下：能力的關(guān)系如下： (1)d e+1 :可檢測可檢測e個錯誤。個錯誤。 (2)d 2t+1 :可糾正可糾正t個錯誤。個錯誤。 (3)d e+t+1 :可檢測可檢測e個錯誤并糾正個錯誤并糾正t個錯誤個錯誤(e t) 。 如如 X=1001101

10、，則，則C=1 被傳送的數(shù)據(jù)為：被傳送的數(shù)據(jù)為：10011011 接收方對接收到的數(shù)字序列進(jìn)行下列運(yùn)算接收方對接收到的數(shù)字序列進(jìn)行下列運(yùn)算 F= X0 X1 X2 X n-1 C 若若F=1則正確、則正確、 反之則錯。反之則錯。 即當(dāng)收到的數(shù)字為即當(dāng)收到的數(shù)字為10011011時時 F=1 當(dāng)收到的數(shù)字為當(dāng)收到的數(shù)字為11011011時時 F=0 ，出錯，要求重發(fā)，出錯，要求重發(fā) 1)奇校驗(yàn)奇校驗(yàn) C= X0 X1 X2 X n-1 。 發(fā)送方，通過設(shè)置校驗(yàn)位的值，使待傳數(shù)據(jù)中發(fā)送方，通過設(shè)置校驗(yàn)位的值，使待傳數(shù)據(jù)中(含一位校驗(yàn)含一位校驗(yàn) 位位)1的個數(shù)的個數(shù) 為奇數(shù)。設(shè)校驗(yàn)位為為奇數(shù)。設(shè)校驗(yàn)

11、位為C，則：，則： 8、奇、奇/偶校驗(yàn)偶校驗(yàn) 發(fā)送方發(fā)送方通過設(shè)置校驗(yàn)位的值，使待傳數(shù)據(jù)通過設(shè)置校驗(yàn)位的值，使待傳數(shù)據(jù) 中中(含一位校驗(yàn)位含一位校驗(yàn)位)1的個數(shù)的個數(shù) 為偶數(shù)。設(shè)校驗(yàn)位為為偶數(shù)。設(shè)校驗(yàn)位為C，則，則 C= X0 X1 X2 X n-1 如如 X=1001101 則則C=0 被傳送的數(shù)據(jù)為：被傳送的數(shù)據(jù)為：10011010 接收方對接收到的數(shù)字序列進(jìn)行下列運(yùn)算接收方對接收到的數(shù)字序列進(jìn)行下列運(yùn)算 F= X0 X1 X2 X n-1 C 若若F=0則正確、則正確、 反之則錯。反之則錯。 即當(dāng)收到的數(shù)字為即當(dāng)收到的數(shù)字為10011010時時 F=0 當(dāng)收到的數(shù)字為當(dāng)收到的數(shù)字為110

12、11011時時 F=1，錯，要求重發(fā)，錯，要求重發(fā) 2)偶校驗(yàn)偶校驗(yàn) 簡單簡單 碼距為碼距為2(?),不能檢測出同時出現(xiàn)偶數(shù)個位錯誤的錯誤！不能檢測出同時出現(xiàn)偶數(shù)個位錯誤的錯誤！ 如上例中如上例中 偶校驗(yàn)時發(fā)送偶校驗(yàn)時發(fā)送10011010 ，當(dāng)接收為當(dāng)接收為10010000 時仍然不能檢測出傳輸錯誤！時仍然不能檢測出傳輸錯誤！ 3)奇偶校驗(yàn)的特點(diǎn)奇偶校驗(yàn)的特點(diǎn) 4)奇偶校驗(yàn)的應(yīng)用場合分析奇偶校驗(yàn)的應(yīng)用場合分析 本身穩(wěn)定性不高，本身穩(wěn)定性不高， 近距離近距離 RAID 5)交叉奇交叉奇/偶校驗(yàn)偶校驗(yàn) 9、海明校驗(yàn)、海明校驗(yàn)(Richard Hamming（理查德（理查德海明海明）1950年提出年

13、提出) 1) 奇偶校驗(yàn)的不足奇偶校驗(yàn)的不足: 只能檢測奇數(shù)個位錯誤只能檢測奇數(shù)個位錯誤,且不能糾錯，且不能糾錯， 檢測得出的無錯誤結(jié)果不一定可信。檢測得出的無錯誤結(jié)果不一定可信。 2) 海明校驗(yàn)海明校驗(yàn): 具有檢測和糾正錯誤的一種編碼具有檢測和糾正錯誤的一種編碼 ( 多重奇偶校驗(yàn)多重奇偶校驗(yàn)) 基本思想基本思想: 將待傳送的信息將待傳送的信息 , 按照某種規(guī)律分成若干組按照某種規(guī)律分成若干組, 每每 組安排一個校驗(yàn)位組安排一個校驗(yàn)位 , 用于奇偶測試用于奇偶測試, 這樣就提供了多位檢這樣就提供了多位檢 錯信息錯信息, 以指出最大可能是哪一位出錯以指出最大可能是哪一位出錯, 從而糾正從而糾正.

14、3)具有指出并糾正一位錯誤的海明校驗(yàn)需要的位數(shù)具有指出并糾正一位錯誤的海明校驗(yàn)需要的位數(shù) 設(shè)有設(shè)有r r位校驗(yàn)位，共能表示位校驗(yàn)位，共能表示2 2r r種不同的狀態(tài)，用一種狀態(tài)表種不同的狀態(tài)，用一種狀態(tài)表 示無差錯，剩余的可以表示示無差錯，剩余的可以表示2 2r r -1 -1種錯誤，由于差錯可能出種錯誤，由于差錯可能出 現(xiàn)在數(shù)據(jù)位和校驗(yàn)位，因此必須滿足：現(xiàn)在數(shù)據(jù)位和校驗(yàn)位，因此必須滿足： 2 2r r - 1 = k + r - 1 = k + r (k (k數(shù)據(jù)位的位數(shù)數(shù)據(jù)位的位數(shù) r r校驗(yàn)位的位數(shù)校驗(yàn)位的位數(shù) ) ) 校驗(yàn)位在海明碼中的分布規(guī)則：校驗(yàn)位在海明碼中的分布規(guī)則： k+r位海

15、明碼中，校驗(yàn)位位海明碼中，校驗(yàn)位Pi分布在海明碼分布在海明碼的的H H2 2i i-1-1 位上位上,i=1.r,i=1.r 4)海明碼的形成方法海明碼的形成方法 海明碼位號海明碼位號 Hj1 2 3 4 5 6 7 8 9 10 11 P和和b的分布的分布 P1 P2 b1 P3 b2 b3 b4 P4 b5 b6 b7 a)分組原則：分組原則： 確定海明碼每位數(shù)據(jù)位所用的校驗(yàn)位確定海明碼每位數(shù)據(jù)位所用的校驗(yàn)位 Hi1234567891011 Pi121,241,42,41,2,481,82,81,2,8 根據(jù)每個校驗(yàn)位校驗(yàn)的位分組：根據(jù)每個校驗(yàn)位校驗(yàn)的位分組： P1: 3,5,7,9,11

16、 P2: 3,6,7,10,11 P3: 5,6,7 P4: 9,10,11 b)校驗(yàn)位的取值校驗(yàn)位的取值(偶校驗(yàn)為例偶校驗(yàn)為例)- Hi1234567891011 Pi121,2 /b1 41,4 /b2 2,4 /b3 1,2,4 /b4 81,8 /b5 2,8 /b6 1,2,8 /b7 P1=b1 b2 b4 b5 b7 P2=b1 b3 b4 b6 b7 P3=b2 b3 b4 P4=b5 b6 b7 假設(shè)假設(shè)b1b2b3b4b5b6b7 = 1011000 則：則：P1= 1 0 1 0 0 = 0 P2 = 1 1 1 0 0=1 P3=0 1 1 = 0 P4=0 0 0 =

17、 0 則則H = 0 1 1 0 0 1 1 0 0 0 0 c)指錯、糾錯原理指錯、糾錯原理 指錯字指錯字 P1= b1 b2 b4 b5 b7 P2= b1 b3 b4 b6 b7 P3=b2 b3 b4 P4=b5 b6 b7 則指錯字由則指錯字由G4G3G2G1組成，其中：組成，其中： G4= P4 b5 b6 b7 G3 = P3 b2 b3 b4 G2= P2 b1 b3 b4 b6 b7 G1= P1 b1 b2 b4 b5 b7 上例中上例中 發(fā)送方發(fā)送方H = 0 1 1 0 0 1 1 0 0 0 0 如果接收到如果接收到 H = 0 1 1 0 0 1 1 0 0 0 1

18、 G4 = 0 0 0 1 = 1 G3 = 0 0 1 1 = 0 G2 = 1 1 1 1 0 1 = 1 G1 = 0 1 0 1 0 1 = 1 G4G3G2G1= 1011 表明表明H11出錯，改正該位的錯誤即可。出錯，改正該位的錯誤即可。 則錯誤字為：則錯誤字為： 5)海明校驗(yàn)的缺點(diǎn)海明校驗(yàn)的缺點(diǎn) 計(jì)算復(fù)雜計(jì)算復(fù)雜 6)關(guān)于擴(kuò)展的海明校驗(yàn)編碼，請查閱相關(guān)資料。關(guān)于擴(kuò)展的海明校驗(yàn)編碼，請查閱相關(guān)資料。 1)CRC 是一種基于模是一種基于模2運(yùn)算建立編碼規(guī)則的校驗(yàn)碼運(yùn)算建立編碼規(guī)則的校驗(yàn)碼 ; 2)模模2運(yùn)算規(guī)則運(yùn)算規(guī)則: a)加加/減運(yùn)算減運(yùn)算 (異或運(yùn)算，或不帶進(jìn)位的加法，不帶借位

19、的減法異或運(yùn)算，或不帶進(jìn)位的加法，不帶借位的減法) 000，011，101，110 b)乘法運(yùn)算：按模乘法運(yùn)算：按模2加求部分積之和加求部分積之和 ，不進(jìn)位，不進(jìn)位 c)模模2除法除法 按模按模2減求部分余數(shù)，不借位。減求部分余數(shù)，不借位。 上商原則是：上商原則是： (1)部分余數(shù)首位為部分余數(shù)首位為1時，商為時，商為1，減除數(shù)；，減除數(shù)； (2)部分余數(shù)首位為部分余數(shù)首位為0時，商為時，商為0，減，減0； (3)當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該余數(shù)為最后余數(shù)。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該余數(shù)為最后余數(shù)。 10、循環(huán)冗余校驗(yàn)、循環(huán)冗余校驗(yàn)(Cyclic Redundancy Che

20、ck) (1)部分余數(shù)首位為部分余數(shù)首位為1時，商為時，商為1，減除數(shù)；，減除數(shù)； (2)部分余數(shù)首位為部分余數(shù)首位為0時，商為時，商為0，減，減0； (3)當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該余數(shù)為最后余數(shù)。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該余數(shù)為最后余數(shù)。 3) CRC編碼方法編碼方法 (1)選擇合適的生成多項(xiàng)式選擇合適的生成多項(xiàng)式G(x),其最高位的權(quán)值其最高位的權(quán)值r log2k,其中其中 K為被校驗(yàn)信息的位數(shù)；為被校驗(yàn)信息的位數(shù)； 如如K=4位時，位時，r=3. (2)將待校驗(yàn)的二進(jìn)制信息將待校驗(yàn)的二進(jìn)制信息Q(X)邏輯左移邏輯左移r位位,得到得到Q(X) (3)用用Q(X) 按模

21、按模2運(yùn)算法則除運(yùn)算法則除G(x)，將得到的，將得到的r位余數(shù)替換位余數(shù)替換 Q(X)最后的最后的r位，就得到位，就得到Q(X)的的CRC。 解：解： M(x)1100， r3 M(x)231100000 1100000 / 1011 按模按模2除法，得商除法，得商Q(x)1110，余數(shù)，余數(shù)R(x)010。 該信息的該信息的CRC碼碼 ：1100010 該該CRC碼稱為碼稱為(7,4）碼）碼 例例 求有效信息求有效信息1100的的CRC碼，多項(xiàng)式碼，多項(xiàng)式G(x)1011。 3) CRC糾錯糾錯 (1)檢錯檢錯 接收部件收到接收部件收到CRC碼后，仍用約定的生成多項(xiàng)式碼后，仍用約定的生成多項(xiàng)式G(x)去除，若余去除，若余 數(shù)為數(shù)為0，表示傳送正確；若余數(shù)不為，表示傳送正確；若余數(shù)不為0，表示出錯，再由余數(shù)的值，表示出錯，再由余數(shù)的值 來確定哪一位出錯，從而加以糾正。來確定哪一位出錯，從而加以糾正。 (2)糾錯糾錯 不論錯誤出現(xiàn)在哪一位不論錯誤出現(xiàn)在哪一位,均要通過將出錯位循環(huán)左移到最左邊的一均要通過將出錯位循環(huán)左移到最左邊的一 位上時被糾