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

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