第四講 數(shù)據(jù)信息表示2 第2章

第2章數(shù)據(jù)信息表示 1 1 數(shù)據(jù)格式 定點數(shù)和浮點數(shù)浮點數(shù)的規(guī)格化 IEEE7542 非數(shù)值數(shù)據(jù)的編碼字符 漢字3 檢驗碼奇偶校驗 海明碼 CRC 第二講安排 3 定點數(shù) 小數(shù)點固定在某一位置的數(shù)據(jù) 純小數(shù) 表示形式有符號數(shù)x xSx 1x 2 x n0 x 1 2 n xs為符號位無符號數(shù)x x0 x 1x 2 x n0 x 1 2 n xs為符號位數(shù)據(jù)表示范圍0 0 0 0 x 1 2 n 0 1 1純整數(shù) 表示形式有符號數(shù)x xsxn 1 x1x0 x 2n 1 xs為符號位無符號數(shù)x xnxn 1 x1x00 x 2n 1 1 xn為數(shù)值位注意 小數(shù)點的位置是機器約定好的 并沒有實際的保存 x0 x 1x 2x 3 x n xnxn 1xn 2 x1x0 數(shù)據(jù)格式 定點數(shù) 設(shè)采用n 1位數(shù)據(jù) 3 4 4 定點機的特點 所能表示的數(shù)據(jù)范圍小使用不方便 運算精度較低存儲單元利用率低 5 數(shù)據(jù)格式 浮點數(shù) 浮點數(shù) 小數(shù)點位置可變 形如科學(xué)計數(shù)法中的數(shù)據(jù)表示 浮點數(shù)格式定義 N Re MM 尾數(shù) mantissa 是一個純小數(shù) 表示數(shù)據(jù)的全部有效數(shù)位 決定著數(shù)值的精度 R 基數(shù) radix 可以取2 8 10 16 表示當(dāng)前的數(shù)制 微機中 一般默認(rèn)為2 隱含表示 e 階碼 exponent 是一個整數(shù) 用于指出小數(shù)點在該數(shù)中的位置 決定著數(shù)據(jù)數(shù)值的大小 機器數(shù)的一般表示形式 6 6 科學(xué)計數(shù)法的表示 一個十進制數(shù)可以表示成不同的形式 同理 一個二進制數(shù)也可以有多種表示 7 浮點數(shù)規(guī)格化 浮點數(shù)的表示1 11 20 0 111 21 11 1 2 1機器數(shù)的表示不同 不利于運算規(guī)格化的目的保證浮點數(shù)表示的唯一性 保留更多地有效數(shù)字 提高運算的精度 規(guī)格化要求1 R 尾數(shù) 1 規(guī)格化處理 尾數(shù)向左移n位 小數(shù)點右移 同時階碼減n 尾數(shù)向右移n位 小數(shù)點左移 同時階碼加n 規(guī)格化 右規(guī) 左規(guī) 8 8 浮點數(shù)的規(guī)格化 尾數(shù)用原碼表示時尾數(shù)最高數(shù)值位為1 尾數(shù)形如0 1 正 或1 1 負(fù) 例如 0 011 25要規(guī)格化則變?yōu)? 11 24 0 011 25要規(guī)格化則變?yōu)? 11 24 尾數(shù)用補碼表示時尾數(shù)最高數(shù)值位和尾數(shù)符號位相反 尾數(shù)形如0 1 正 或1 0 負(fù) 例如 0 011 25要規(guī)格化 則變?yōu)? 11 24 0 011 25要規(guī)格化 則變?yōu)? 01 24 9 浮點數(shù)的數(shù)據(jù)表示范圍 0 最大負(fù)數(shù) 最小正數(shù) 最小負(fù)數(shù) 最大正數(shù) 下溢區(qū) 上溢區(qū) 上溢區(qū) 負(fù)數(shù)區(qū) 正數(shù)區(qū) 浮點數(shù)的溢出 階碼溢出上溢 階碼大于所能表示的最大值 下溢 階碼小于所能表示的最小值 機器零 尾數(shù)為0 或階碼小于所能表示的最小值 10 浮點數(shù)的最值 設(shè)浮點數(shù)格式為 移碼表示 2m 2m 1 補碼表示 1 1 2 n 1 2 2m 1 2 n 2 2m 2 n 2 2m 1 2 n 2 2m 1 11 11 100 00 00 00 111 11 00 00 000 01 11 11 011 11 同左 同左 00 00 101 11 2 1 2 n 2 2m 2 1 2 2m 同左 同左 00 00 010 00 11 例1 設(shè)浮點數(shù)的階碼6位 含符號位 尾數(shù)為10位 含符號位 階碼采用補碼表示 尾數(shù)采用原碼表示 分析其浮點數(shù)表示范圍 最大正數(shù)最大正數(shù)為0 11 1 2011 1即 1 2 9 231該浮點數(shù)即為規(guī)格化數(shù)形式 12 例1 設(shè)浮點數(shù)的階碼6位 含符號位 尾數(shù)為10位 含符號位 階碼采用補碼表示 尾數(shù)采用原碼表示 分析其浮點數(shù)表示范圍 最小正數(shù)非規(guī)格化數(shù)形式最小正數(shù)為0 0 01 210 0即2 9 2 25 2 9 2 32規(guī)格化數(shù)形式最小正數(shù)為0 1 210 02 1 2 25 2 33 13 例1 設(shè)浮點數(shù)的階碼6位 含符號位 尾數(shù)為10位 含符號位 階碼采用補碼表示 尾數(shù)采用原碼表示 分析其浮點數(shù)表示范圍 最小負(fù)數(shù)最小負(fù)數(shù)為 0 1 1 201 1即 1 2 9 2 25 1 1 2 9 231該浮點數(shù)即為規(guī)格化數(shù)形式 14 例1 設(shè)浮點數(shù)的階碼6位 含符號位 尾數(shù)為10位 含符號位 階碼采用補碼表示 尾數(shù)采用原碼表示 分析其浮點數(shù)表示范圍 最大負(fù)數(shù)非規(guī)格化數(shù)形式最大負(fù)數(shù)為 0 0 01 210 0即 2 9 2 25 2 9 2 32規(guī)格化數(shù)形式最大負(fù)數(shù)為 0 1 210 0即 2 1 2 25 2 1 2 32 例2 設(shè)浮點數(shù)的階碼6位 含符號位 尾數(shù)為10位 含符號位 階碼和尾數(shù)均采用補碼表示 分析其規(guī)格化浮點數(shù)表示范圍 最大正數(shù)階碼最大 尾數(shù)最大最大正數(shù)為0 11 1 211 1 1 2 9 231最小正數(shù)最小正數(shù)為0 10 00 2 32即2 32 2 1 2 33注意 不是因為0 0 1 2 32不是規(guī)格化數(shù) 15 例2 設(shè)浮點數(shù)的階碼6位 含符號位 尾數(shù)為10位 含符號位 階碼和尾數(shù)均采用補碼表示 分析其規(guī)格化浮點數(shù)表示范圍 最小的負(fù)數(shù)最小負(fù)數(shù)為 1 00 0 231即231 1 231最大的負(fù)數(shù)最大負(fù)數(shù)為 0 10 01 2 32即 2 9 2 1 2 32注意 因有規(guī)格化要求 不是 16 17 浮點數(shù)的IEEE754標(biāo)準(zhǔn)表示 IEEE InstituteofElectricalandElectronicsEngineers 美國電氣及電子工程師學(xué)會IEEE是一家總部在美國的工程技術(shù)和電子專家的組織 IEEE致力于電氣 電子 計算機工程和與科學(xué)有關(guān)的領(lǐng)域的開發(fā)和研究 也是計算機網(wǎng)絡(luò)標(biāo)準(zhǔn)的主要制定者 為便于軟件移植 按照IEEE754標(biāo)準(zhǔn) 實際機器內(nèi)32位浮點數(shù)和64位浮點數(shù)的標(biāo)準(zhǔn)格式如下 0 22 23 30 31 23位尾數(shù) 僅為數(shù)值部分 8位階碼 包括階符 1位數(shù)符 32位浮點數(shù) 0 51 52 62 63 64位浮點數(shù) 32位浮點數(shù)的IEEE754標(biāo)準(zhǔn)表示 數(shù)符S 表示浮點數(shù)的符號 占1位 0 正數(shù) 1 負(fù)數(shù) 尾數(shù)M 23位 原碼純小數(shù)表示 小數(shù)點在尾數(shù)域的最前面 由于原碼表示的規(guī)格化浮點數(shù)要求 最高數(shù)值位始終為1 因此該標(biāo)準(zhǔn)中隱藏最高數(shù)值位 1 尾數(shù)的實際值為1 M 階碼E 8位 采用有偏移值的移碼表示 移127碼 即E e 127 E的8位二進制數(shù)即為移127碼的編碼 浮點數(shù)的真值 N 1 S 1 M 2E 127 19 IEEE754標(biāo)準(zhǔn)格式 64位格式 其真值表示為 x 1 S 1 M 2E 1023e E 1023 20 IEEE754標(biāo)準(zhǔn)的數(shù)據(jù)表示 32位格式 IEEE754標(biāo)準(zhǔn)中的階碼E正零 負(fù)零E與M均為零 正負(fù)之分由數(shù)據(jù)符號確定 正無窮 負(fù)無窮E為全1 M為全零 正負(fù)之分由數(shù)據(jù)符號確定 階碼E的其余值 00000001 11111110 為規(guī)格化數(shù)據(jù) 真正的指數(shù)e的范圍為 126 127 E 00000000 M 0000 0000 E 11111111 M 0000 0000 00000000 11111111 21 IEEE754標(biāo)準(zhǔn)對特殊數(shù)據(jù)的表示 32位格式 22 23 例2 將 20 59375 10轉(zhuǎn)換成754標(biāo)準(zhǔn)的32位浮點數(shù)的二進制存儲格式 解 20 59375 10 10100 10011 2將尾數(shù)規(guī)范為1 M的形式 10100 10011 1 010010011 24e 4可得 M 010010011S 0E 4 127 131 10000011故 32位浮點數(shù)的754標(biāo)準(zhǔn)格式為 01000001101001001100000000000000 41A4C000 16 24 單精度浮點數(shù)與雙精度浮點數(shù) 高級語言的float double使用的即是IEEE754規(guī)定的格式 float 32位浮點值 也叫單精度浮點數(shù) 4字節(jié)保存 double 64位浮點值 也叫雙精度浮點數(shù) 8字節(jié)保存 單精度浮點數(shù)的例子 1位8位7位8位8位 1100 0 01 25 單精度浮點數(shù)與雙精度浮點數(shù) 除0之外 IEEE754標(biāo)準(zhǔn)中單精度浮點數(shù)所能表示的絕對值最小的規(guī)格化浮點數(shù)的格式為 S0000000100000000000000000000000V 1 S 2 126 1 M 1 S 2 126 1 0 00 0 除 之外 IEEE754標(biāo)準(zhǔn)中單精度浮點數(shù)所能表示的絕對值最大的規(guī)格化浮點數(shù)的格式為 S1111111011111111111111111111111V 1 S 2 127 1 M 1 S 2 126 1 1 11 1 26 求解技巧 例如 將下列十進制數(shù)表示成IEEE754格式的32位浮點數(shù)二進制存儲形式 27 3211 512求解 27 32 27 1 32 00011011 2 2 5尾數(shù) 1 1011 階碼 e 5 4 1 E e 127 126IEEE754數(shù)據(jù) 0011111101011000000000000000000011 512 00001011 2 2 9尾數(shù) 1 011 階碼 e 9 3 6 E e 127 121IEEE754數(shù)據(jù) 0011110010110000000000000000000 27 例 將十進制數(shù) 54表示成二進制定點數(shù) 16位 和浮點數(shù) 16位 其中數(shù)值部分10位 階碼部分4位 階符和數(shù)符各取1位 并寫出它在定點機和浮點機中的機器數(shù)形式 28 浙江大學(xué)考研試題 計算機儲存程序的特點之一是把數(shù)據(jù)和指令都作為二進制信號看待 今有一計算機字長32bit 數(shù)符位是第31bit 單精度浮點數(shù)格式如圖所示 對于二進制數(shù)10001111111011111100000000000000 表示一個補碼整數(shù) 其十進制值是多少 表示一個無符號整數(shù) 其十進制值是多少 表示一個IEEE754標(biāo)準(zhǔn)的單精度浮點數(shù) 其值是多少 29 二進制數(shù)10001111111011111100000000000000 表示一個補碼整數(shù) 其十進制值是多少 作為補碼整數(shù) 其對應(yīng)的原碼是11110000000100000100000000000000十進制值是 230 229 228 220 214 表示一個無符號整數(shù) 其十進制值是多少 作為無符號整數(shù) 其十進制值是231 227 226 225 224 223 222 221 219 218 217 216 215 214 30 二進制數(shù)10001111111011111100000000000000 作為IEEE754標(biāo)準(zhǔn)的單精度浮點數(shù)階碼E是00011111指數(shù)e 階碼E 127 00011111 01111111 1100000B 96D尾數(shù)M 11011111100000000000000則1 M 1 11011111100000000000000 1 110111111 單精度浮點數(shù)值為 X 1 s 1 M 2e 1 110111111 2 96 0 1110111111 2 95 14 16 1 15 16 2 12 16 3 2 95 0 3115 2 95 31 2009考研真題 12 一個C語言程序在一臺32位機器上運行 程序中定義了三個變量x y和z 其中x和z是int型 y為short型 當(dāng)x 127 y 9時 執(zhí)行賦值語句z x y后 x y和z的值分別是 x 0000007FH y FFF9H z 00000076Hx 0000007FH y FFF9H z FFFF0076Hx 0000007FH y FFF7H z FFFF0076Hx 0000007FH y FFF7H z 00000076H 在32位機上int型變量占4個字節(jié) short占2個字節(jié) 32 2010考研真題 14 假定變量i f d數(shù)據(jù)類型分別為int float double int用補碼表示 float和double用IEEE754單精度和雙精度浮點數(shù)據(jù)格式表示 已知i 785 f 1 5678e3 d 1 5e100 若在32位機器中執(zhí)行下列關(guān)系表達式 則結(jié)果為真的是 I i int float i II f float int f III f float double f IV d f d fA 僅I和IIB 僅I和IIIC 僅II和IIID 僅III和IV 關(guān)鍵是 兩端的數(shù)據(jù)類型是否一致 33 數(shù)據(jù)格式 十進制數(shù)串的表示方法 BCD碼 8421碼 每個十進制數(shù)位用4個二進制數(shù)表示 使用二進制數(shù)表示十進制數(shù) 主要用于非數(shù)值計算的應(yīng)用領(lǐng)域 采用BCD碼表示 一個字節(jié)可存放兩個十進制數(shù)位 節(jié)省存儲空間 便于直接完成十進制數(shù)的算術(shù)運算 34 字符與字符串的表示方法 ASCII碼 美國國家信息交換標(biāo)準(zhǔn)字符碼 包括128個字符 共需7位編碼 ASCII碼規(guī)定 最高位為0 余下7位作為128個字符的編碼 最高位的作用 奇偶校驗 擴展編碼 字符串指連續(xù)的一串字符 每個字節(jié)存一個字符 當(dāng)存儲字長為2 或4個字節(jié)時 在同一個存儲單元中 可按從低位字節(jié)向高位字節(jié)的順序存放字符串的內(nèi)容 或按從高位字節(jié)向低位字節(jié)的次序順序存放字符串的內(nèi)容 35 漢字的表示方法 漢字的輸入編碼目的 直接使用西文標(biāo)準(zhǔn)鍵盤把漢字輸入到計算機 分類 主要有數(shù)字編碼 拼音碼 字形編碼三類 區(qū)位碼漢字庫中區(qū)號 位號 2020H國標(biāo)碼目的 不同的漢字信息系統(tǒng)之間進行漢字交換 8080H漢字內(nèi)碼 區(qū)分與ASCII碼 用于漢字信息的存儲 交換 檢索等操作的機內(nèi)代碼漢字字模碼用點陣表示的漢字字形代碼 用于漢字的輸出 36 中文編碼 37 漢字字模碼 38 校驗碼 數(shù)據(jù)校驗 數(shù)據(jù)校驗原因為減少和避免數(shù)據(jù)在計算機系統(tǒng)運行或傳送過程中發(fā)生錯誤 在數(shù)據(jù)的編碼上提供了檢錯和糾錯的支持 數(shù)據(jù)校驗碼的定義能夠發(fā)現(xiàn)某些錯誤或具有自動糾錯能力的數(shù)據(jù)編碼 也稱檢錯碼 數(shù)據(jù)校驗的基本原理是擴大碼距 碼距 任意兩個合法碼之間不同的二進制位的最少位數(shù) 僅有一位不同時 稱其碼距為1 39 碼距及作用 設(shè)用四位二進制表示16種狀態(tài)16種編碼都用到了 此時碼距為1 任何一種狀態(tài)的四位碼中的一位或幾位出錯 就變成另一個合法碼 無查錯能力 若用四位二進制表示8個狀態(tài)只用其中的8種編碼 而把另8種編碼作為非法編碼 可使碼距擴大為2 注意 并不是任選8種編碼都可擴大碼距 40 校驗碼的類型 奇偶校驗碼判斷數(shù)據(jù)中1的個數(shù)設(shè)置1位校驗位 分奇校驗和偶校驗兩種 只能檢錯 無糾錯能力 海明校驗碼在奇偶校驗的基礎(chǔ)上增加校驗位而得 具有檢錯和糾錯的能力 循環(huán)冗余校驗碼 CRC 通過模2的除法運算建立數(shù)據(jù)信息和校驗位之間的約定關(guān)系 具有很強的檢錯糾錯能力 41 奇偶校驗碼 概念 奇偶校驗原理在數(shù)據(jù)中增加1個冗余位 使碼距由1增加到2 如果合法編碼中有奇數(shù)個位發(fā)生了錯誤 就將成為非法代碼 增加的冗余位稱為奇偶校驗位 校驗的類型偶校驗 每個碼字 包括校驗位 中1的數(shù)目為偶數(shù) 奇校驗 每個碼字 包括校驗位 中1的數(shù)目為奇數(shù) 校驗過程發(fā)送端 按照校驗類型 在發(fā)送數(shù)據(jù)后添加校驗位P 接收端 對接收到的數(shù)據(jù) 包括校驗位 進行同樣類型的校驗 決定數(shù)據(jù)傳輸中是否存在錯誤 42 奇偶校驗碼 校驗原理 偶校驗 在接收端求校驗位P D7 D6 D5 D4 D3 D2 D1 D0 P若P 0 則無錯 若P 1 則有錯 奇校驗 在接收端求校驗位P D7 D6 D5 D4 D3 D2 D1 D0 P若P 1 則無錯 若P 0 則有錯 電路實現(xiàn) 一般采用異或電路得到校驗位 10101011 求校驗碼 偶校驗碼101010111 奇校驗碼101010110 43 奇偶校驗碼 例題 1 2 44 奇偶校驗碼 例題 1 2 45 海明碼 海明碼是1950年提出的 只要增加少數(shù)的幾位校驗碼 即可檢測出多位出錯 并能自動恢復(fù)一或幾位出錯信息 實現(xiàn)原理 在一個數(shù)據(jù)中加入幾個校驗位 每個校驗位和某幾個特定的信息位構(gòu)成偶校驗的關(guān)系 接收端對每個偶關(guān)系進行校驗 產(chǎn)生校驗因子 通過校正因子區(qū)分無錯和碼字中的n個不同位置的錯誤 不同代碼位上的錯誤會得出不同的校驗結(jié)果 46 海明碼 確定校驗位的位數(shù) 47 海明碼 確定校驗位的位置 數(shù)據(jù)表示數(shù)據(jù)位D DiDi 1 D1D0 校驗位P PjPj 1 P2P1 海明碼H 包括數(shù)據(jù)位和校驗位 HmHm 1 H2H1 分組原則每個校驗位Pi從低到高被分在海明碼中位號2i 1的位置 例如 數(shù)據(jù)D3D2D1D0 1001 校驗位P3P2P1海明碼共7位H7H6 H2H1 各位分配如下 P1 P2 P3 D0 D1 D2 D3 48 海明碼 校驗分組 校驗原則海明碼的每一位Hi有多個校驗位校驗 其關(guān)系是被校驗的每一位位號等于校驗它的各校驗位的位號之和 每個信息位的位置寫成用2的冪次之和的形式 例如H7 D3 參與H1 H2 H4的校驗 H6 D2 參與H2 H4的校驗 H5 D1 參與H1 H4的校驗 H3 D0 參與H1 H2的校驗 分組情況 P1 P2 P3 D0 D1 D2 D3 第一組P1 第二組P2 第三組P3 第一組 P1 D3 D1 D0 第二組 P2 D3 D2 D0 第三組 P3 D3 D2 D1 49 海明碼 校驗位的形成 50 海明碼 接收端校驗 1 2 接收端接收到數(shù)據(jù)后 分別求S1 S2 S3 SjS1 第一組中所有位 包括P1 求異或 Sj 第j組中所有位 包括Pj 求異或Sj 1 Pj 1 所有位 包括P1 P2 Pj 求異或當(dāng)Sj 1 1時 有一位出錯 由Sj S3S2S1的編碼指出出錯位號 將其取反 即可糾錯 當(dāng)Sj 1 0時 無錯或有偶數(shù)個錯 兩個錯的可能性比較大 當(dāng)Sj S3S2S1 0 000時 接收的數(shù)無錯 否則有兩個錯 51 同上例 接收端接收的數(shù)據(jù)為接收端求SS1 0 1 0 1 0S2 0 1 0 1 0S3 1 1 0 0 0S4 1 1 0 0 1 1 0 0 0若接收端接收到錯誤的數(shù)據(jù)S1 0 1 0 1 0S2 0 1 1 1 1S3 1 1 1 0 1S4 1 1 1 0 1 1 0 0 1 海明碼 接收端校驗 2 2 第一組 P1 D3 D1 D0 第二組 P2 D3 D2 D0 第三組 P3 D3 D2 D1 無錯誤 1 S4 1 有錯誤 S3S2S1 110 H6位有錯 應(yīng)取反 52 練習(xí) 設(shè)待校驗的數(shù)據(jù)為D7 D0 10101011 寫出其海明校驗碼 解 確定海明校驗位的位數(shù)因為K 8 由N K r 2r 1 得9 r 2r 校驗位的位數(shù)為r 4 確定校驗位的位置i 121110987654321D7D6D5D4P4D3D2D1P3D0P2P1 分組 N位分r組 53 練習(xí) 設(shè)待校驗的數(shù)據(jù)為D7 D0 10101011 寫出其海明校驗碼 校驗位的形成P1 D6 D4 D3 D1 D0 1 P2 D6 D5 D3 D2 D0 1P3 D7 D3 D2 D1 1 P4 D7 D6 D5 D4 0所以 信息碼10101011的海明校驗碼為 101001011111 54 海明碼的糾錯與檢錯能力 一個系統(tǒng)能糾正一位差錯時 碼距最小是3 碼距為3時 或能糾正一位錯 或能檢測二位錯 但不能同時糾正一位錯并檢測二位錯 碼距為1至7時 海明碼的糾錯和檢