第2章 計算機(jī)系統(tǒng)中的數(shù)據(jù)表示方法

第2章計算機(jī)系統(tǒng)中的數(shù)據(jù)表示方法程利新哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.1概述計算機(jī)的組成在很大程度上取決于數(shù)字、字符和控制信息的表示方法。計算機(jī)系統(tǒng)基本信息單元：位（bit），表示了電子開關(guān)的狀態(tài)或電位的高低。字節(jié)（byte）：8位組成的計算機(jī)存儲器編址的基本單位。字（word）：由兩個或者多個相鄰的字節(jié)構(gòu)成。字的大小表示特定計算機(jī)體系結(jié)構(gòu)能夠處理的數(shù)據(jù)大小。8位計算機(jī)、16位計算機(jī)、32位計算機(jī)、64位計算機(jī)、……。半字節(jié)（nibble）：字節(jié)的一半（高4位或者低4位）2.2位置編碼系統(tǒng)十進(jìn)制表示法位置編碼系統(tǒng)（positionalnumberingsystem）基本思想：任意數(shù)字的值可以通過表示成某個基數(shù)（或稱為底，radix）的乘冪形式，也稱為權(quán)重編碼系統(tǒng)（weightednumberingsystem）。在位置編碼系統(tǒng)中，數(shù)中每一個位置都是基數(shù)的冪次方，故稱位置編碼系統(tǒng)。位置編碼系統(tǒng)中所使用的有效數(shù)字的數(shù)目等于系統(tǒng)基數(shù)的大小。任何一種計數(shù)系統(tǒng)（數(shù)制）的最大合法數(shù)字均為基數(shù)減1.采用下標(biāo)表示基數(shù)，缺省的表示十進(jìn)制數(shù)2.2位置編碼系統(tǒng)計算機(jī)科學(xué)中，最重要的數(shù)制是二進(jìn)制（基數(shù)是2）和十六進(jìn)制（基數(shù)為16）。另外一個比較重要的數(shù)制是八進(jìn)制（基數(shù)為8）。2.3十進(jìn)制數(shù)和二進(jìn)制數(shù)之間的轉(zhuǎn)換二進(jìn)制計數(shù)系統(tǒng)實質(zhì)上已經(jīng)成為所有依賴于數(shù)字控制的電子設(shè)備的核心基礎(chǔ)。二進(jìn)制計數(shù)法簡單，可以較為方便的轉(zhuǎn)換為對應(yīng)電子線路。2.3.1無符號整數(shù)的轉(zhuǎn)換轉(zhuǎn)換方法分為兩種：重復(fù)減法除法余數(shù)法重復(fù)減法比較麻煩，要求對所使用基數(shù)的冪指數(shù)形式比較熟悉除法余數(shù)法簡單并快速N為無符號二進(jìn)制數(shù)表示范圍：0到2N-1無符號十進(jìn)制數(shù)。對二進(jìn)制數(shù)進(jìn)行算術(shù)運(yùn)算時，給定位數(shù)二進(jìn)制數(shù)所能表示的數(shù)值范圍是非常重要的。溢出（overflow）現(xiàn)象：運(yùn)算結(jié)果超出二進(jìn)制位數(shù)所能表示范圍。2.3.2分?jǐn)?shù)轉(zhuǎn)換在任意數(shù)制中，分?jǐn)?shù)都可以采用其他數(shù)制中基數(shù)的負(fù)指數(shù)冪來近似表示。小數(shù)點分開整數(shù)部分和分?jǐn)?shù)部分，十進(jìn)制小數(shù)點，二進(jìn)制小數(shù)點。對于分?jǐn)?shù)轉(zhuǎn)換，同樣可以采用重復(fù)減法和余數(shù)法。其中余數(shù)法由除法余數(shù)法變?yōu)槌朔ㄓ鄶?shù)法，同時由取余數(shù)，變?yōu)槿〗Y(jié)果的整數(shù)部分，結(jié)果的順序從由下而上變?yōu)橛缮隙?。對于循環(huán)分?jǐn)?shù)，執(zhí)行某些取舍近似算法，保證有限字長條件下的轉(zhuǎn)換精度。重復(fù)減法和余數(shù)法可以用于任意基數(shù)數(shù)字間的轉(zhuǎn)換，若通過十進(jìn)制數(shù)中轉(zhuǎn)，可比直接轉(zhuǎn)換快捷和精確。2.3.3以2的指數(shù)冪為基數(shù)的數(shù)制之間的轉(zhuǎn)換將二進(jìn)制轉(zhuǎn)換為十六進(jìn)制或者八進(jìn)制增加可讀性16=24，8=23，因而可以對二進(jìn)制數(shù)進(jìn)行分組，從而快速進(jìn)行十六進(jìn)制或者八進(jìn)制轉(zhuǎn)換。倍乘轉(zhuǎn)換法一種將二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的最快方法基本思想：從最左邊的位開始，每個后面位（高位）的2的乘冪總是前面位（低位）的2的乘冪的2倍。從最左邊的位開始進(jìn)行計算，將第一位乘以2加到第二位上去，得到結(jié)果再乘以2加到第三位上，以此類推，直到最右邊的位。2.4帶符號整數(shù)的表示方法將存儲單元的最高位作為符號位，最高位為‘0’表示正整數(shù)，最高位為‘1’表示負(fù)整數(shù)。帶符號整數(shù)表示法符號幅值法（原碼）：利用符號位后的剩余位數(shù)表示數(shù)字的幅值（大?。┓创a補(bǔ)碼2.4.1符號幅值表示法（原碼）符號幅值表示法中，數(shù)字的最左邊的位（也稱為最高位，或者最高有效位）是一個符號，而余下的位用來表示數(shù)值的幅值（或稱為絕對值）。N位二進(jìn)制數(shù)，采用符號幅值表示法能夠表示的整數(shù)范圍是：-2(N-1)+1到2(N-1)-1。符號幅值表示法盡管方法簡單，但是對其進(jìn)行運(yùn)算則較為復(fù)雜。對于符號幅值表示法表示的數(shù)據(jù)，運(yùn)算過程中產(chǎn)生的對最高位的進(jìn)位必須舍棄。符號位需要進(jìn)行單獨處理。原碼加減法與十進(jìn)制算術(shù)的紙筆運(yùn)算方法類似。2.4.1符號幅值表示法（原碼）原碼的缺點：計算復(fù)雜存在正0和負(fù)0的區(qū)別2.4.2補(bǔ)碼體系十進(jìn)制減法可以通過加上減數(shù)與全9組成的數(shù)字的差，再加回一個進(jìn)位的方法來實現(xiàn)。這種方法稱為取減數(shù)的9的補(bǔ)碼，或者稱為求減數(shù)的十進(jìn)制反碼。這種表示法的好處是不需要單獨處理符號位。2.4.2補(bǔ)碼體系反碼：如果已知基數(shù)為r，有d位數(shù)字表示，那么數(shù)字N的反碼定義為（rd-1）-N構(gòu)成一個二進(jìn)制數(shù)的反碼很簡單，將二進(jìn)制數(shù)按位取反即可。正數(shù)的反碼就是其本身，負(fù)數(shù)才有反碼。二進(jìn)制減法可轉(zhuǎn)化為反碼加法：將減數(shù)表示成反碼形式，與被減數(shù)相加，最高位的進(jìn)位加到結(jié)果的最低位從而得到最終結(jié)果。由反碼求原碼的方法與由原碼求反碼的方法一致。N位二進(jìn)制數(shù)，采用反碼表示法能夠表示的整數(shù)范圍是：-2(N-1)+1到2(N-1)-1。反碼的缺點：存在正‘0’：00000000和負(fù)‘0’：11111111。2.4.2補(bǔ)碼體系補(bǔ)碼：如果已知基數(shù)為r，有d位數(shù)字表示，若數(shù)字N不等于0，則N的反碼定義為rd–N，如果N等于0，則N的補(bǔ)碼定義為0.求補(bǔ)碼方法：對于正數(shù)，其補(bǔ)碼就是其本身，對于負(fù)數(shù)，其補(bǔ)碼通過將其原碼按位取反后加1得到。補(bǔ)碼運(yùn)算中，必須舍棄所有與最高位有關(guān)的進(jìn)位。由補(bǔ)碼求原碼方法：將補(bǔ)碼按位取反后加1得到。N位二進(jìn)制數(shù)，采用補(bǔ)碼表示法能夠表示的整數(shù)范圍是：-2(N-1)到2(N-1)-1。補(bǔ)碼運(yùn)算溢出判斷法則：如果進(jìn)入符號位和移出符號位的進(jìn)位相同，那么沒有溢出發(fā)生，否則，就有溢出發(fā)生，也就是出現(xiàn)一個錯誤。補(bǔ)碼是目前最通用的帶符號數(shù)字表示方法。2.5浮點表示法早期計算機(jī)的設(shè)計初衷是面向整數(shù)計算的，在處理浮點數(shù)計算的問題中，采用一些編程技巧來使得浮點運(yùn)算得以實現(xiàn)。浮點運(yùn)算的處理方法：科學(xué)計數(shù)法。即在一個整數(shù)機(jī)的系統(tǒng)中實現(xiàn)浮點仿真，將小數(shù)部分（尾數(shù)）和指數(shù)部分分別表示?？茖W(xué)計數(shù)法是現(xiàn)代數(shù)字計算機(jī)中浮點計算法的基礎(chǔ)。2.5.1一個簡單的模型數(shù)字計算機(jī)系統(tǒng)中，浮點數(shù)由三部分組成：符號位、指數(shù)部分（以2的冪指數(shù)形式表示）和小數(shù)部分，其中小數(shù)部分稱為有效數(shù)。表示范圍和精度表示范圍越大，使用的指數(shù)位數(shù)越多精度越高，需要的有效數(shù)的位數(shù)越多2.5.1一個簡單的模型為了解決負(fù)指數(shù)如何表示的問題，采用偏移指數(shù)的方法。偏移指數(shù)方法的思想：在允許的范圍內(nèi)將每一個整數(shù)指數(shù)轉(zhuǎn)化成一個非負(fù)整數(shù)指數(shù)，這樣就可以把每個整數(shù)都作為一個二進(jìn)制數(shù)來存儲。偏移指數(shù)方法：在指數(shù)允許的表示范圍之內(nèi)，在每個指數(shù)上加一個固定偏移值來對整數(shù)指數(shù)進(jìn)行調(diào)整。一般取偏移值為可表示范圍的中間值。規(guī)格化：將有效數(shù)的最左邊的位設(shè)置為1。2.5.2浮點算法浮點數(shù)加減法：先將兩個數(shù)表示成具有同一基數(shù)的相同指數(shù)形式，然后將小數(shù)部分相加減。浮點數(shù)乘除法：與十進(jìn)制指數(shù)運(yùn)算法則相同2.5.3浮點誤差誤差產(chǎn)生的原因：計算機(jī)的有限整數(shù)系統(tǒng)對無限的實數(shù)系統(tǒng)進(jìn)行建模，只能是實數(shù)系統(tǒng)的的一個近似。所使用的位數(shù)越多，近似就越好。但誤差總是存在的。不管把系統(tǒng)設(shè)計得有多么大，只要是利用有限的系統(tǒng)表示實數(shù)，或多或少都會引入不同程度的浮點誤差，即使是最小的誤差，有時也會導(dǎo)致嚴(yán)重的后果。2.5.4IEEE-754浮點標(biāo)準(zhǔn)前面引入的浮點模型可以推廣至任意位數(shù)浮點數(shù)的表示。由于標(biāo)準(zhǔn)的不統(tǒng)一，各類系統(tǒng)難以兼容。1985年，IEEE發(fā)表單精度和雙精度浮點表示標(biāo)準(zhǔn)IEEE-754。IEEE-754單精度浮點數(shù)字長32位，其中8位指數(shù)，以127為偏移值，23位有效數(shù)，1位符號位。IEEE-754雙精度浮點數(shù)字長64位，其中11位指數(shù)，52位有效數(shù)，1位符號位，偏移值為1023。2.6字符編碼數(shù)字計算機(jī)除了使用二進(jìn)制體系表示和處理數(shù)字值，還要考慮將計算機(jī)內(nèi)部數(shù)值轉(zhuǎn)換成人所能理解的形式。這種轉(zhuǎn)換方式既取決于計算機(jī)使用的編碼系統(tǒng)，也和這些數(shù)值的存取方式有關(guān)。2.6.1二進(jìn)制編碼的十進(jìn)制數(shù)二進(jìn)制編碼的十進(jìn)制數(shù)（Binary-CodedDecimal,BCD)：將每個十進(jìn)制數(shù)字編碼成一個4位二進(jìn)制數(shù)形式。在按照8位進(jìn)行存儲時，BCD碼的高4位稱為區(qū)位，而低4位稱為數(shù)字。區(qū)位表示了符號，1111為無符號數(shù)，1100為正數(shù)，1101為負(fù)數(shù)。壓縮的BCD碼：將多個相連的數(shù)字放入相鄰的半字節(jié)中，只留下一個半字節(jié)表示符號。這樣可以簡化計算，并且可以節(jié)省空間。2.6.2EBCDICEBCDIC（ExtendedBinaryCodedDecimalInterchangeCode）：為了提高計算機(jī)系統(tǒng)的信息處理能力以及同時存儲數(shù)字和數(shù)據(jù)的統(tǒng)一方法。2.6.3ASCIIASCII（AmericanStandardCodeforInformationInterchange）美國信息交換標(biāo)準(zhǔn)碼ASCII碼來自5位的摩爾編碼，并被擴(kuò)充至7位編碼，被稱為第5種國際字母。ASCII碼定義了32個控制字符，10個數(shù)字，52個英文字母，32個特殊字符以及空格符號。最高位預(yù)留用于奇偶校驗位。ASCII碼的應(yīng)用十分廣泛，20世紀(jì)80年代，計算機(jī)設(shè)備制造商利用奇偶校驗位來為128和255之間的數(shù)值提供一個“擴(kuò)展的”字符集。2.6.4統(tǒng)一字符編碼無論是EBCDIC，還是ASCII碼，均面向拉丁語系字母的編碼。對于非拉丁語系字符的編碼難以處理。統(tǒng)一字符編碼（Unicode）被發(fā)明用于都全世界每一種語言的大多數(shù)字符進(jìn)行統(tǒng)一編碼。2.7用于數(shù)據(jù)記錄和傳遞的編碼方式ASCII碼、EBCDIC碼和Unicode用于存儲器中的字符編碼，但不適合磁介質(zhì)存儲和遠(yuǎn)距離傳輸。數(shù)據(jù)編碼：用于磁介質(zhì)存儲和遠(yuǎn)距離傳輸?shù)淖址幋a2.7.1不歸零編碼采用電平的高低或者磁通量的極性表示編碼容易出錯。2.7.2反轉(zhuǎn)不歸零編碼采用信號的轉(zhuǎn)變表示編碼，電平的變化表示1，沒有變化表示02.7.3相位調(diào)制編碼也稱為曼徹斯特編碼（ManchesterCoding）：通過為編碼的每一位提供一個信號跳變，二進(jìn)制數(shù)1由上升跳變給出，0則對應(yīng)一個下降跳變，從而解決同步問題。2.7.4頻率調(diào)制編碼在每個位單元中至少提供一個信號躍變，這些同步躍變發(fā)生在每個位單元的開始處。同時對于二進(jìn)制數(shù)1還要在位單元的中間再多提供一個額外信號躍變2.7.5運(yùn)行長度限制編碼一種對有字符編碼組成的字進(jìn)行分塊的編碼方式。2.8錯誤檢測與校正錯誤檢測與校正的必要性既不可能不產(chǎn)生錯誤，也不可能百分百檢測出錯誤的發(fā)生，或者校正錯誤。在計算機(jī)系統(tǒng)的設(shè)計中，錯誤檢測和校正十分重要。2.8.1循環(huán)冗余碼校驗循環(huán)冗余碼校驗（CyclicRedundancyCheck，CRC）：一種求校驗和的錯誤檢測方法。CRC可在一大塊或者是一長串?dāng)?shù)據(jù)中判斷是否出現(xiàn)錯誤。CRC將生成的錯誤校驗位加在原始信息數(shù)據(jù)位的后面，組成錯誤校驗位的位組合，進(jìn)行傳輸或者存儲。利用位組合中的錯誤校驗位檢驗數(shù)據(jù)位的正確性。2.8.1循環(huán)冗余碼校驗?zāi)?算術(shù)：無進(jìn)位和借位的二進(jìn)制算術(shù)0+0=00+1=11+0=11+1=0CRC計算和使用方法確定CRC多項式P將待編碼數(shù)據(jù)字I左移P的位數(shù)減1位將I作為被除數(shù)，將P作為除數(shù)，進(jìn)行模2除法，略去商只留下余數(shù)把余數(shù)加到I上，組成編碼字M校驗時，將P作為除數(shù)，將M做為被除數(shù)，若能整除，則沒有出錯，否則，傳輸或存儲過程中一定發(fā)生了錯誤。2.8.1循環(huán)冗余碼校驗CRC多項式采用大指數(shù)冪的互質(zhì)多項式時，檢測效果最好標(biāo)準(zhǔn)多項式CRC-CCITT(ITU-T):X16+X12+X5+1CRC-12:X12+X11+X3+X2+X+1CRC-16(ANSI):X16+X15+X2+1CRC-32:X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X+1CRC硬件加速將各種可能輸入的位組合模式產(chǎn)生的余數(shù)“燒錄”到存儲設(shè)備中2.8.2海明編碼（HammingCode）較為適用于存儲設(shè)備的錯誤檢測和恢復(fù)機(jī)制數(shù)據(jù)通信數(shù)據(jù)檢測出錯誤后，可進(jìn)行數(shù)據(jù)重傳存儲數(shù)據(jù)再生較難海明編碼基于奇偶校驗的概念，檢測和校正能力隨著所加入奇偶校驗位的數(shù)目成正比。常用于隨機(jī)錯誤的檢測和校正應(yīng)用前提：數(shù)據(jù)位中每一位的出錯概率相同，與其他位的出錯沒有關(guān)聯(lián)2.8.2海明編碼（HammingCode）海明編碼術(shù)語校驗位：海明編碼中所使用的奇偶校驗位，也稱冗余位編碼字：由所存儲信息字（數(shù)據(jù)字）加上冗余位形成的二進(jìn)制編碼。每個數(shù)據(jù)字有且僅有一個編碼字與其對應(yīng)。海明距離（Hammingdistance）：兩個編碼字之間不同位的位置數(shù)目最小海明距離：對于任意一種計算海明校驗位的算法，都可以構(gòu)造出全部合法編碼字的完整列表。各對編碼字之間的最小海明距離稱為該編碼的最小海明距離，記為D(min)。最小海明距離決定了編碼校驗錯誤的能力。2.8.2海明編碼（HammingCode）海明碼錯誤檢測原理：若兩個編碼字的海明距離為d，那么把一個編碼字轉(zhuǎn)換為另一個編碼字需要翻轉(zhuǎn)d個單一位，因此不同單一位位置數(shù)目小于d的編碼字，為出錯編碼字。最小海明距離決定了編碼校驗錯誤的能力。任意編碼字X若要被當(dāng)做另一個合法編碼字Y來接收的話，那么X中至少需要發(fā)生D(min)個錯誤。因此要檢驗k（或者少于k個）單位錯誤，編碼就必須具有D(min)=k+1的海