1、第一章 概述,計算機是一種能對數(shù)字化信息進行自動高速運算的通用處理裝置。,11 計算機的定義和特性,信息 運算 處理,1.1.1 什么是計算機,1.1.2 計算機的特性,計算機的特性可以歸納為高速、通用、準確、 智能四大特性。,12 計算機的發(fā)展歷程,1.2.1 電子計算機的誕生,第一臺電子計算機ENIAC（Electronic Numerical Integrator and Computer）于1946年在美國誕生。,每秒5000次加法運算； 每秒50次乘法運算； 平方和立方計算； Sin和Cos函數(shù)數(shù)值運算； 其它更復(fù)雜的計算。,1.2.2 第一代計算機 （20世紀40年代中到50年代末

2、）,第一代計算機為電子管計算機，其邏輯元件采用電子 管，存儲器件為聲延遲線或磁鼓，典型邏輯結(jié)構(gòu)為定 點運算。計算機“軟件”一詞尚未出現(xiàn)，編制程序所用 工具為低級語言。,1.2.3 第二代計算機（50年代中后期到60年代中）,第二代計算機為晶體管計算機。這一代計算機除了邏 輯元件采用晶體管以外，其內(nèi)存儲器由磁芯構(gòu)成，磁 鼓與磁帶成為外存儲器。,計算機典型邏輯結(jié)構(gòu)實現(xiàn)了浮點運算， 并提出了變址、中斷、I/O處理等新概念。 計算機軟件也得到了發(fā)展，出現(xiàn)了多種 高級語言及其編譯程序。,1.2.4 第三代計算機（60年代中到70年代中）,第三代計算機為集成電路計算機，其邏輯元件與存儲器 均由集成電路實現(xiàn)

3、，這是微電子與計算機技術(shù)相結(jié)合的 一大突破。微程序控制、高速緩存、虛擬存儲器、流水 線等先進計算機技術(shù)開始使用。另一大特點是大型/巨 型機與小型機同時發(fā)展。,1.2.5 第四代計算機（70年代中期開始）,大規(guī)模（LSI）和超大規(guī)模（VLSI）集成電路 及微處理器為這一代計算機的典型特征。,并行處理技術(shù)的研究與應(yīng)用以及眾多巨型機的產(chǎn)生也成 為這一時期計算機發(fā)展的特點。,四代機時期的一個重要特點是計算機網(wǎng)絡(luò)的發(fā)展與廣泛 應(yīng)用。,1.2.6 新一代計算機,新器件和非馮諾依曼結(jié)構(gòu)已成為新一代計算機的公認標志。,13 計算機的組成與結(jié)構(gòu),1.3.1 計算機系統(tǒng)的層次結(jié)構(gòu),1.3.2 計算機硬件,計算機硬

4、件是指構(gòu)成計算機的元器件、 部件、設(shè)備、以及它們的設(shè)計與實現(xiàn)技術(shù)。,馮諾依曼計算機的主要特點：,1）計算機由運算器、存儲器、控制器和輸入/輸出五個 部件組成。,本書討論的范圍涉及第0、1、2共3層， 主要內(nèi)容如下： 1. 高速的算術(shù)、邏輯運算方法及ALU的 邏輯設(shè)計； 2. 高速的指令執(zhí)行過程及指令部件的設(shè)計與實現(xiàn)， 是采用組合邏輯技術(shù)、或微程序設(shè)計技術(shù)，還是 PLA技術(shù)；是復(fù)雜指令集計算機（CISC），還是 精簡指令集計算機（RISC）； 3. 提高存儲器容量與速度的方法，以及如何解決 “CPU-Cache-MM-外存”之間的匹配問題； 4. 高效率的輸入/輸出方法、組織，以及它們之間的 互

5、聯(lián)技術(shù)； 5. 計算機五大部件（運算器、控制器、存儲器、輸入 和輸出）之間的相互作用、高效接口（總線）；,2）存儲器以二進制形式存儲指令和數(shù)據(jù)；,3）存儲程序工作方式；,4）五部件以運算器為中心進行組織；,1.3.3 計算機軟件,1. 軟件的作用,一般來說，計算機的工作總是由存儲程序來控制的。,軟件的具體作用為：,在計算機系統(tǒng)中起著指揮和管理的作用。,是計算機用戶和硬件的接口界面。,是計算機體系結(jié)構(gòu)設(shè)計的主要依據(jù)。,2. 軟件的發(fā)展過程,三個階段：,1)從第一臺計算機上的第一個程序出現(xiàn)到 實用的高級語言出現(xiàn)為第一階段（1946-1956年）。,2)從實用的高級程序設(shè)計語言出現(xiàn)到軟件工程出現(xiàn) 以

6、前為第二階段（1956-1968年）。,3)軟件工程出現(xiàn)以后迄今一直為第三階段（1965）。,3. 軟件的分類, 系統(tǒng)軟件：操作系統(tǒng)、編譯程序。, 支撐軟件：數(shù)據(jù)庫、各類接口軟件和工具組。, 應(yīng)用軟件：,14 計算機的分類與應(yīng)用,1.4.1 計算機的分類,按計算機所處理對象的表示形式不同可以 分成模擬計算機與數(shù)字計算機兩類。,計算機按其用途來分可以分成專用機和通用機兩類。其中，通用計算機按其規(guī)模、性能和價格來分，又可分為巨型機、大型機、小型機、工作站、微型機等多種類型。,1.4.2 計算機應(yīng)用,計算機信息處理技術(shù)包括了對各種信息媒體的獲取、 表示、加工與表現(xiàn)方法和技術(shù)，大致有以下幾個方 面內(nèi)容

7、：,1語言與文字的處理。,2計算機圖形學與數(shù)字圖象處理。,3多媒體技術(shù)。,4計算機輔助技術(shù)。,5計算機信息系統(tǒng)。,6計算機控制。,計算機應(yīng)用技術(shù)的發(fā)展方向為集成化、網(wǎng)絡(luò)化、智能化,第2章 數(shù)據(jù)的表示,本章討論在計算機內(nèi)部各類基本數(shù)據(jù) 的表示方法及其相互間的等值轉(zhuǎn)換。,21 數(shù)據(jù)、信息和媒體,數(shù)據(jù)是對事實、概念或指令的一種特殊表達形式，這種特殊的表達形式可以用人工的方式或者用自動化的裝置進行通信、翻譯轉(zhuǎn)換或者進行加工處理 。,在計算機系統(tǒng)中所指的數(shù)據(jù)均是以二進制編碼形式出現(xiàn)的。,計算機內(nèi)部由硬件實現(xiàn)的基本數(shù)據(jù)區(qū)分為數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)。,2.1.1 數(shù)據(jù),信息是對人有用的數(shù)據(jù)，這些數(shù)據(jù)可能影

8、響到人們的行為和決策。,媒體又稱媒介、媒質(zhì)，是指承載信息的載體。,2.1.2 信息,計算機信息處理，實質(zhì)上就是由計算機進行數(shù)據(jù)處理的過程。,信息是對數(shù)據(jù)的解釋，數(shù)據(jù)是信息的載體。,2.1.3 媒體,與計算機信息處理有關(guān)的媒體有5種：,感覺媒體 表示媒體 存儲媒體 表現(xiàn)媒體 傳輸媒體,圖 2.1 計算機外部信息與內(nèi)部數(shù)據(jù)的轉(zhuǎn)換,22 數(shù)字化信息編碼,所謂編碼，就是用少量簡單的基本符號，對 大量復(fù)雜多樣的信息進行一定規(guī)律的組合。,在計算機系統(tǒng)中，凡是要進行處理（包括計算、查找、排序、分類、統(tǒng)計、合并等）、存儲和傳輸?shù)男畔?，都是用二進制進行編碼的。,計算機內(nèi)部采用二進制表示的原因： 1）二進制只有兩

9、種狀態(tài)，在數(shù)字電路中很容易實現(xiàn)。 2）二進制編碼、運算規(guī)則非常簡單。 3）二進制的“0”、“1”與二值邏輯一致，很容易實現(xiàn) 邏輯運算。,2.3 數(shù)值數(shù)據(jù)的編碼表示,數(shù)值數(shù)據(jù)是表示數(shù)量多少和數(shù)值大小的數(shù)據(jù)。,在計算機內(nèi)部，數(shù)值數(shù)據(jù)的表示方法有兩大類：第一 種是直接用二進制數(shù)表示；另一種是采用二進制編碼的 十進制數(shù)（Binary Coded Decimal Number，簡稱BCD） 表示。,表示一個數(shù)值數(shù)據(jù)要確定三個要素：進位計數(shù)制、 定浮點表示和數(shù)的編碼表示。,2.3.1 進位計數(shù)制及其各進位制數(shù)之間的轉(zhuǎn)換,在某個數(shù)字系統(tǒng)中，若采用R個基本符號（0，1， 2，R-1）表示各位上的數(shù)字，則稱其為

10、基R 數(shù)制，或稱R進制數(shù)字系統(tǒng)，R被稱為該數(shù)字系統(tǒng)的基， 采用“逢R進一”的運算規(guī)則，對于每一個數(shù)位i，其該 位上的權(quán)為R i。,在計算機系統(tǒng)中，常用的幾種進位計數(shù)制 有下列幾種： 二進制 R=2, 基本符號為 0和1 八進制 R=8, 基本符號為 0,1,2,3,4,5,6,7 十六進制 R=16, 基本符號為 0,1,2,3,4,5,6,7,8,9, A,B,C,D,E,F 十進制 R=10, 基本符號為 0,1,2,3,4,5,6,7,8,9,例：十進制數(shù)2585.62代表的實際值是 2x103+5x102+8x101+5x100+6x10-1+2x10-2,例：二進制數(shù)(100101.

11、01)2代表的實際值是： (100101.01)2 = 1x25 + 0 x24+ 0 x23 + 1x22 + 0 x21 + 1x20+ 0 x2-1 + 1x2-2=(37.25)10,1.R進制數(shù)轉(zhuǎn)換成十進制數(shù),任何一個R進制數(shù)轉(zhuǎn)換成十進制數(shù)時，只要 “按權(quán)展開”即可。,例1 二進制數(shù)轉(zhuǎn)換成十進制數(shù)。 (10101.01)2=(124+023+122+021+120+ 0 2-1+12-2)10=(21.25)10,例2 八進制數(shù)轉(zhuǎn)換成十進制數(shù)。 (307.6)8=(382+780+68-1) 10=(199.75) 10,例3 十六進制數(shù)轉(zhuǎn)換成十進制數(shù)。 (3A.C)=(3161+1

12、0160+1216-1) 10 =(58.75) 10,2. 十進制數(shù)轉(zhuǎn)換成R進制數(shù),任何一個十進制數(shù)轉(zhuǎn)換成R進制數(shù)時，要將 整數(shù)和小數(shù)部分分別進行轉(zhuǎn)換。,（1）整數(shù)部分的轉(zhuǎn)換 整數(shù)部分的轉(zhuǎn)換方法是“除基取余，上右下左”。,例1 將十進制整數(shù)835分別轉(zhuǎn)換成二、八進制數(shù)。,0,余數(shù) 低位,3,0,5,1,(835) 10=(1503) 8,高位,(835) 10=(1101000011) 2,（2）小數(shù)部分的轉(zhuǎn)換,小數(shù)部分的轉(zhuǎn)換方法是 “乘基取整，上左下右”。,例2 將十進制小數(shù)0.6875分別轉(zhuǎn)換成二、八進制數(shù)。,0.68752=1.375 1,整數(shù)部分,0.3752=0.75 0,0.75

13、2=1.5 1,0.52=1.0 1,(0.6875) 10=(0.1011) 2,整數(shù)部分,0.68758=5.5 5,0.58=4.0 4,(0.6875) 10=(0.54) 8,例3 將十進制小數(shù)0.63轉(zhuǎn)換成二進制數(shù)。,整數(shù)部分,0.632=1.26 1,0.262=0.52 0,0.522=1.04 1,0.042=0.08 0,(0.63) 10=(0.1010) 2 (近似值),（3）含整數(shù)、小數(shù)部分的數(shù)的轉(zhuǎn)換,只要將整數(shù)、小數(shù)部分分別進行轉(zhuǎn)換，得 到轉(zhuǎn)換后的整數(shù)和小數(shù)部分，然后再這兩 部分組合起來得到一個完整的數(shù)。,例 4 將十進制數(shù)835.6875轉(zhuǎn)換成二、八進制數(shù)。 (8

14、35.6875) 10=(1101000011.1011) 2=(1503.54) 8,3. 二、八、十六進制數(shù)的相互轉(zhuǎn)換,（1）八進制數(shù)轉(zhuǎn)換成二進制數(shù),例1 將(13.724) 8轉(zhuǎn)換成二進制數(shù) (13.724) 8=( 001 011 . 111 010 100 )2 =(1011.1110101) 2,（2）十六進制數(shù)轉(zhuǎn)換成二進制數(shù),例2 將十六進制數(shù)2B.5E轉(zhuǎn)換成二進制數(shù) (2B.5E)16 = ( 0010 1011 . 0101 1110 ) 2 = (101011.0101111) 2,（3）二進制數(shù)轉(zhuǎn)換成八進制數(shù),(10011.01) 2 = ( 010 011 . 010

15、) 2 = (23.2) 8,（4）二進制數(shù)轉(zhuǎn)換成十六進制數(shù),(11001.11) 2 = ( 0001 1001 . 1100 ) 2 = ( 19.C ) 16,2.3.2 定點與浮點表示,1定點表示,所謂定點表示是約定計算機中所有數(shù)據(jù)的小數(shù)點 位置是固定不變的。該位置在計算機設(shè)計時已被隱含地 規(guī)定，因此勿需再用任何硬件設(shè)備狀態(tài)來明顯表示小數(shù)點。,利用定點表示進行計算，須將所有數(shù)據(jù)之 值按一定比例予以縮?。ɑ蚍糯螅┖笏腿?計算機，同時須將計算結(jié)果以同一比例增 大（或縮?。┖蟛拍艿谜_結(jié)果值。,由于采用定點數(shù)表示數(shù)的范圍較小，因此運算很容易 產(chǎn)生溢出，另外選擇適當?shù)谋壤蜃佑袝r也很困難。,2

16、浮點表示,在計算機中所表示的數(shù)，其小數(shù)點位置是可變的，這 種數(shù)稱為浮點數(shù)。,對于任意一個二進制數(shù)X，可以表示成 如下形式： X= MRE 其中：M為尾數(shù)，常用定點純小數(shù)表示；E為階，一般 用定點整數(shù)表示；R為基數(shù)，隱含為2，也可以為2q， q可取2，3，4等正整數(shù)。,浮點表示法的最大特點是它可以表示 很大的數(shù)據(jù)范圍以及較高的數(shù)據(jù)精度。,2.3.3 編碼系統(tǒng),確定一個數(shù)值數(shù)據(jù)的三要素是：進位計數(shù)制、 定點/浮點表示和編碼表示。它們分別用來解決數(shù)值 數(shù)據(jù)的基本表示符號、小數(shù)點位置和數(shù)的正負號表示。,符號數(shù)字化：0表示正號，1表示負號。,機器數(shù)：數(shù)值數(shù)據(jù)在計算機內(nèi)部編碼表示的數(shù)。 真值：機器數(shù)真正的

17、值（即：原來帶有正負號的數(shù)）。,機器數(shù)X的真值為： XT = X1Xn2X1X0 （當X為定點整數(shù)時） XT = 0 . X1X 2X(n 1)X n （當X為定點小數(shù)時） 數(shù)字化編碼后的機器數(shù)X表示為： X = Xn X n -1 X n -2 X 1 X 0,常用的編碼表示方式有三種：原碼、補碼和反碼。 對于這三種編碼：正數(shù)的所有編碼表示都是相同的。 其結(jié)果總是：符號位取值為0，數(shù)值部分保持不變。 負數(shù)的所有編碼表示，其符號位總是為1，而數(shù)值 部分對于不同的編碼則有不同的取值。,1原碼表示法,原碼表示的機器數(shù)由符號位后直接跟上 真值的數(shù)值構(gòu)成。,定點整數(shù)：,例： +1101原=01101

18、-1101原=11101,原碼表示的優(yōu)點是與真值的對應(yīng)關(guān)系直觀、方便， 因此與真值的轉(zhuǎn)換簡單，并且用原碼實現(xiàn)乘除運算 比較簡便，但其加/減法運算規(guī)則復(fù)雜。,2補碼表示法,(1) 模運算,“對一個多于n位的數(shù)丟棄高位而保留低n位數(shù)” 這樣一種處理，實際上等價于“將這個多于n位的數(shù)去 除以2n，然后丟去商保留其余數(shù)”的操作。這樣一種操 作運算就是“模運算”。,在模運算中，若A，B，M滿足下列關(guān)系：A=B+KM （K為整數(shù)）， 則記為： AB（mod M）。 即：A、B各除以M后的余數(shù)相同，故稱B和為模同 余。,假定現(xiàn)在鐘表時針指向10點，要將它撥向 點，則有兩種撥法：, 倒撥4格：10-4=6 順

19、撥8格：10+8186（mod 12）,所以在模12系統(tǒng)中：10-410+8(mod 12) 即： -48 (mod 12) 我們稱8是-4對模12的補碼。同樣有 -39（mod 12）；-57（mod 12）等等。,結(jié)論： “對于某一確定的模，某數(shù)減去小于模的另一 數(shù)，總可以用該數(shù)加上模與另一數(shù)絕對值之差來代替”。 因此，補碼可以用加法實現(xiàn)減法運算。,例1“鐘表”模運算系統(tǒng) 10-410+(12-4) 10+86 （mod 12）,例2“4位十進制數(shù)” 模運算系統(tǒng)（相當于只 有四檔的算盤） 9828-19289828+(104-1928) 9828+8072 7900 （mod 104 ）,

20、（2）補碼的定義,定點整數(shù)：,補碼0的表示是唯一的： +0補=0 0.0 -0補= 2 n -0=1 00.0=0 0.0 (mod 2 n),對于整數(shù)補碼有：-1補= 2 n 1=11.1 (n個1) 對于小數(shù)補碼有：-1補=2-1=1.00.0 (n-1個0),例設(shè)補碼的位數(shù)為6，求負數(shù)-0.10110 的補碼表示。 -0.10110補=2-0.10110 =10.00000-0.10110 =1.01010,求負數(shù)補碼的簡單方法：“符號位固定為1，其余各位 由真值中相應(yīng)各位取反后，末尾加1所得?！?由補碼求真值的簡便方法：“若符號位為1，則真值的符 號為負，其數(shù)值部分的各位由補碼中相應(yīng)各

21、位取反后， 末尾加1所得?！?求一個補碼“取負”后的補碼表示方法： “只要對該已知補碼各位取反，末尾加1即可?！?由x求 x的方法：將xn的符號位和數(shù)值位 一起向右移動一位，符號位移走后還保持原來的值不變。,例1已知：XT =-0.1011010，求XT補 。 XT補=1. 0100101+0. 0000001 =1. 0100110,例2已知：XT補 = 1 011010，求XT 。 XT = -100101+1= -100110,例3已知：XT補=1 011010，求-XT補 -XT補=0 100101+1=0 100110,例4.設(shè)x補=1.0101000，則,補=1.1010100,補

22、=1.1110101,補=1.1101010,第3章 運算器與運算方法, 運算器部件是計算機中的執(zhí)行部件，它可以對二進制數(shù)據(jù)進行各種算術(shù)和邏輯運算； 運算器也是計算機內(nèi)部數(shù)據(jù)信息的重要通路。, 本章重點介紹運算器的核心部件算術(shù)邏輯運算單元ALU的組成與工作原理，以及數(shù)據(jù)在運算器的基本運算方法。,3.1 基本組成,1. 算術(shù)邏輯運算單元ALU, 運算器實現(xiàn)了對計算機中數(shù)據(jù)的加工處理；包括數(shù)值數(shù)據(jù)的算術(shù)運算和邏輯數(shù)據(jù)的邏輯操作。, 運算器中完成數(shù)據(jù)算術(shù)與邏輯運算的部件稱之為算術(shù)與邏輯運算單元（Arithmetic and Logic Unit，簡稱ALU）。ALU是運算器的核心。, ALU通常表示

23、為兩個輸入端口，一個輸出端口和多個功能控制信號端的這樣的一個邏輯符號。,圖3.1 ALU的邏輯符號表示與多路開關(guān),2. 通用寄存器組, 運算器內(nèi)設(shè)有若干通用寄存器，構(gòu)成通用寄存器組；用于暫時存放參加運算的數(shù)據(jù)和某些中間結(jié)果。, 在運算器中用來提供一個操作數(shù)并存放運算結(jié)果的通用寄存器稱作為累加器。, 通用寄存器的數(shù)量越多，對提高運算器性能和程序執(zhí)行速度越有利。, 通用寄存器組是對用戶開放的，用戶可以通過指令去使用這些寄存器。, 如：ADD A, Rj,3.專用寄存器, 運算器需要記錄下指令執(zhí)行過程中的重要狀態(tài)標記，以及提供運算前后數(shù)據(jù)的暫存緩沖等，這通過在運算器中設(shè)置若干專用寄存器來實現(xiàn)。, 循

24、環(huán)計數(shù)器對程序員是透明的。, 程序狀態(tài)字PSW(Program Status Word)，它存放著指令執(zhí)行結(jié)果的某些狀態(tài)；如是否溢出、是否為零、是否有進位/借位、是否為負等。它對程序員是開放的。, 堆棧指針SP(Stack Pointer)，它指示了堆棧的使用情況。,4. 附加的控制線路, 在運算器中附加一些控制線路；以達到運算速度快，運算精度高的目的，。, 如：運算器中的乘除運算和某些邏輯運算是通過移位操作來實現(xiàn)的。在ALU的輸出端設(shè)置移位線路來實現(xiàn)左移、右移和直送。, 移位線路是一個多路選擇器。, 圖3.2 實現(xiàn)移位功能的多路選擇器,3.2 算術(shù)與邏輯單元 3.2.1 半加器與全加器, 運

25、算器中各種運算都是分解成加法運算進行的，因此加法器是計算機中最基本的運算單元。,1.半加器, 兩個一位二進制數(shù)相加(不考慮低位的進位)，稱為半加。實現(xiàn)半加操作的電路，稱為半加器。,Xi Yi Hi Ci,0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1,表3.1 半加運算的真值表, 表3.1 是兩個一位二進制數(shù)Xi、Yi相加的真值表， Hi和Ci的邏輯表達式如下：,2. 全加器, 考慮低位進位的加法運算就是全加運算，實現(xiàn)全加運算的電路稱為全加器。, 根據(jù)真值表表3.2可寫出Fi和Ci的邏輯表達式：,表 3.2 全加運算的真值表,圖 3.4 全加器的邏輯圖和符號表示, 實現(xiàn)邏輯表達

26、式的全加器邏輯圖和全加器的符號表示,3.2.2 串行進位與并行進位, n個全加器相連可得n位的加法器；圖 3.5是串行進位或行波進位加法器。,圖3.5 n位加法器, 先行進位或并行進位加法器, 預(yù)先形成各位進位，將進位信號同時送到各位全加器的進位輸入端。, 就4位加法器，討論一下其進位C1、C2、C3和C4的產(chǎn)生條件：, 下述條件中任一條滿足就可生成C1=1： 1) X1、Y1均為“1”; 2) X1、Y1任一個為“1”，且進位C0為“1”。, 可得C1的表達式為： C1=X1Y1+（X1+Y1）C0, 下述條件中任一條滿足，就可生成C2=1。 1) X2、Y2均為“1”； 2) X2、Y2任

27、一個為“1”， 且進位C1為“1”。, 可得C2的表達式為： C2=X2Y2+(X2+Y2)C1 =X2Y2+(X2+Y2)X1Y1+(X2+Y2)(X1+Y1)C0, 同理，可得C3的表達式為： C3=X3Y3+(X3+Y3)C2 =X3Y3+(X3+Y3)X2Y2+(X2+Y2)X1Y1+ (X2+Y2)(X1+Y1)C0,= X3Y3+(X3+Y3)X2Y2+(X3+Y3) (X2+Y2)X1Y1+ (X3+Y3) (X2+Y2)(X1+Y1)C0, 同理,可得C4的表達式為： C4=X4Y4+(X4+Y4)C3,=X4Y4+(X4+Y4)X3Y3+(X3+Y3)X2Y2+ (X3+Y3

28、)(X2+Y2)X1Y1+(X3+Y3) (X2+Y2)(X1+Y1)C0,=X4Y4+(X4+Y4)X3Y3+(X4+Y4)(X3+Y3)X2Y2+ (X4+Y4)(X3+Y3)(X2+Y2)X1Y1+ (X4+Y4) (X3+Y3) (X2+Y2)(X1+Y1)C0, 定義兩個輔助函數(shù)： Pi= Xi+Yi Gi= XiYi, Pi表示進位傳遞函數(shù)，當Xi、Yi中有一個為“1”時，若有低位進位輸入，則本位向高位傳送進位。, Gi表示進位產(chǎn)生函數(shù)，當Xi、Yi均為“1”時，不管有無低位進位輸入，本位一定向高位產(chǎn)生進位輸出。, 將Pi、Gi代入前面的C1C4式，可得： C1=G1+P1C0 C

29、2=G2+P2 G1+ P2P1C0 C3=G3+P3 G2+ P3 P2 G1+ P3 P2P1C0 C4=G4+P4 G3+ P4P3 G2+ P4P3 P2 G1 +P4P3 P2P1C0, “先行進位產(chǎn)生電路” （圖 3.6 (a)）及“4位先行進位加法器”的邏輯圖（圖 3.6 (b)）,圖3.6 (a) 先行進位產(chǎn)生電路,圖3.6 (b) 4位先行進位加法器, 四個4位先行進位加法器串接起來構(gòu)成16位加法器, 在各加法單元之間，進位信號是串行傳送的，而在加法單元內(nèi)，進位信號是并行傳送的。,圖3.7 組間為串行進位構(gòu)成的16位加法器, 并行進位的概念可用于16位加法器；進一步提高16位

30、加法器的運算速度。, Cm表示4位加法器的進位輸出，Pm表示4位加法器的進位傳遞輸出，Gm表示4位加法器的進位產(chǎn)生輸出。, Cm=Gm+PmC0, Pm 和Gm分別為： Pm= P4P3P2P1 Gm= G4 +P4 G3 + P4P3G2 +P4P3P2G1, 應(yīng)用于四個4位先行進位加法器，則有： Cm1=Gm1+Pm1C0,Cm2=Gm2+Pm2Cm1 = Gm2+ Pm2Gm1 + Pm2 Pm1C0,Cm3=Gm3+Pm3Cm2 = Gm3+ Pm3Gm2 + Pm3Pm2Gm1+ Pm3 Pm2 Pm1C0,Cm4=Gm4+Pm4Cm3 = Gm4+ Pm4Gm3 + Pm4Pm3G

31、m2+ Pm4Pm3Pm2 Gm1+ Pm4Pm3Pm2P m1C0,圖3.8 組間由先行進位鏈構(gòu)成的16位加法器, 可將并行進位的概念用于更大位數(shù)的加法器上，隨著加法器位數(shù)的增加，加法電路變得越來越復(fù)雜。,33 定點加、減法運算, 計算機的一個重要特點是它只能用有限的 數(shù)碼位數(shù)來表示操作數(shù)和操作結(jié)果。, 制定用來表示正、負數(shù)的各種碼制；通過數(shù)據(jù)編碼來簡化數(shù)據(jù)的運算，特別是補碼，把加法和減法巧妙地結(jié)合起來。, 定點加、減法運算只有在遵守模運算規(guī)則的限制條件下其結(jié)果才是正確的，否則就會出現(xiàn)結(jié)果“溢出”。,3.3.1 補碼定點加、減法, 補碼制的加、減法運算公式： X+Y補= (X補+Y 補) M

32、OD 2n X-Y補= (X補+-Y 補) MOD 2n, 在補碼制方法下，無論X、Y是正數(shù)還是負數(shù)，加、減法運算統(tǒng)一采用加法來處理；, X補和Y補的符號位和數(shù)值位一起參與求和運算，加、減運算結(jié)果的符號位也在求和運算中直接得出。, 例1：已知X補=01001，Y補=11100 ； 求X+Y補， X-Y補。, 則-Y補=00100, X+Y補= (X補+Y補) MOD 2 5 =(01001+11100) MOD 2 5 =00101, X-Y補= (X補+-Y補) MOD 2 5 =(01001+00100) MOD 2 5 =01101, 若結(jié)果超過了允許表示的最小負數(shù)時，產(chǎn)生的溢出稱為下溢

33、。, 當算術(shù)運算的結(jié)果超出了數(shù)碼位數(shù)允許的數(shù)據(jù)范圍時，就產(chǎn)生溢出。, 對于n位的二進制碼表示的補碼整數(shù)（符號位占一位），它可表示的數(shù)據(jù)范圍為-2n-12n-1-1。, 若結(jié)果超過了允許表示的最大正數(shù)時，產(chǎn)生的溢出稱為上溢；, 在運算器中應(yīng)設(shè)有溢出判別線路和溢出標志位。, 例2：已知X補=01010，Y補=01010 X+Y補=(01010+01010) MOD 2 5 = 10100 溢出, 例3：已知X補=10010，Y補=00100 X-Y補=(10010+11100) MOD 2 5 = 01110 溢出, 1010 + 1010= 201015 產(chǎn)生上溢, -1410 - 410= -

34、1810-16 產(chǎn)生下溢, 溢出常用的判別方法：, 兩個補碼數(shù)實現(xiàn)加、減運算時，若最高數(shù)值位向符號位的進位值Cn-1與符號位產(chǎn)生的進位輸出值Cn不相同，表明加減運算產(chǎn)生了溢出OVR；, 可以表示為： OVR= Cn-1Cn OVR=1表示結(jié)果有溢出，OVR=0表示結(jié)果正確。,在例1中，求X+Y補時：OVR= Cn-1Cn =11=0，結(jié)果正確。,在例2中，求X+Y補時：OVR= Cn-1Cn =10=1，結(jié)果溢出。,在例3中，求X -Y補時：OVR= Cn-1Cn =01=1，結(jié)果溢出。, 常用雙符號位方法來判別加、減法運算是否有溢出，正數(shù)的雙符號位是00，負數(shù)的雙符號位是11。, 兩個正數(shù)雙

35、符號位的運算為00+00=00時，結(jié)果不溢出；, 兩個正數(shù)雙符號位的運算為00+00+1=01時，結(jié)果上溢。, 兩個負數(shù)的雙符號位運算為（11+11+1）MOD 4 =11時，結(jié)果不溢出；, 兩個負數(shù)的雙符號位的運算為（11+11）MOD 4=10時，結(jié)果下溢。, 采用模4補碼運算，其運算結(jié)果的兩個符號位不一致時，產(chǎn)生溢出。, 實現(xiàn)補碼加、減法運算的邏輯電路(圖3.15),圖3.15 實現(xiàn)補碼加減法運算的邏輯電路, 它的核心部件是二進制并行加法器F，它接收來自寄存器X和寄存器Y的兩個操作數(shù)。, 用圖3.15 來實現(xiàn)加法X+Y補的邏輯操作步驟如下：, X補寄存器X，Y補寄存器Y。, 給出控制信號

36、：X F=1，YF=1，且1F =0 。X補和Y補送入加法器F的兩個輸入端。, 并行加法器F接收X補和Y 補，完成X補+Y 補的加法過程，輸出X+Y補，并置溢出、進位等信號到標志寄存器。, 給出控制信號：FX=1，加法器F的輸出結(jié)果送入寄存器X。加法運算結(jié)束。, 用圖3.15 來實現(xiàn)減法X-Y補的邏輯操作步驟如下： X補寄存器X，Y補寄存器Y。, 給出控制信號：XF=1，YF=1。X補和Y補=yn-1yn-2y0送入加法器F的兩個輸入端。, 給出控制信號：1F=1，并行加法器F接收X補 、Y 補和進位信號1，完成X補+ yn-1yn-2 y0+1= X補+-Y 補的加法過程，輸出X-Y補，并置

37、溢出、進位等信號到標志寄存器。, 給出控制信號：FX=1，加法器F的輸出結(jié)果 X-Y補送入寄存器X。減法運算結(jié)束。, 當寄存器X或寄存器Y的內(nèi)容送到加法器F時，將符號位等值擴充一位，形成雙符號位；雙符號位只在加法器中執(zhí)行加法運算時是必要的。, 寄存器X、寄存器Y和加法器F的二進制位數(shù)對運算數(shù)據(jù)和運算結(jié)果的大小有限制作用，當超過了這些運算結(jié)構(gòu)所能表示的數(shù)據(jù)范圍時，就產(chǎn)生溢出。, 以加法器和通用寄存器的二進制位數(shù)定義為計算機的字長。計算機的字長通常是8的整數(shù)倍。,3.4 定點乘法運算, 常規(guī)的乘法運算方法（定點小數(shù)）, 筆-紙乘法方法，, 原碼乘法，, 帶符號位運算的補碼乘法，, 用組合邏輯線路構(gòu)

38、成的陣列乘法器。,3.4.1 原碼一位乘法, 用原碼實現(xiàn)乘法運算時，符號位與數(shù)值位是分開計算的；, 原碼乘法運算分為二步；, 第二步是計算乘積的數(shù)值位；乘積的數(shù)值部分為兩數(shù)的絕對值之積。, 第一步是計算乘積的符號位；乘積的符號為相乘二數(shù)符號的異或值。, 用數(shù)學表達式描述原碼乘法運算, 設(shè)：X原=x0 x1xn，Y原= y0y1yn (其中x0 、y0分別為它們的符號位), 若 X*Y原=z0z1z2n (其中z0 為結(jié)果之符號位) 則 z0= x0 y0, z1z2n= (x1xn ) *(y1yn), 筆-紙乘法方法, 例1. X=0.1011,Y=0.1101，X*Y的筆-紙乘法過程：,0

39、.1011 被乘數(shù)X=0.x1x2x3x4=0.1011 * 0.1101 乘數(shù)Y=0.y1y2y3y4=0.1101,1011 X* y4*2 4,0000 X* y3*2 3,1011 X* y2*2 2,1011 X* y1*2 1,0.10001111, 因此 X*Y=0.10001111, X*Y的筆-紙乘法過程中，計算兩個正數(shù)的乘法特點：, 用乘數(shù)Y的每一位依次去乘以被乘數(shù)，得X*yi，i=4、3、2、1。若yi=0，得0。若yi=1，得X。, 把中求得的各項結(jié)果X*yi在空間上向左錯位排列，即逐次左移，可以表示為X* yi*2-i 。, 對中求得的結(jié)果求和， ，這也就是兩個正數(shù)的

40、乘積。, 就筆-紙乘法方法，為提高效率而采取的改進措施, 每將乘數(shù)Y 的一位乘以被乘數(shù)得X*yi后，就將該結(jié)果與前面所得的結(jié)果累加，而得到P i，稱之為部分積；這減少了保存每次相乘結(jié)果X*yi的開銷。, 將部分積P i右移一位與X*yi相加。加法運算始終對部分積中的高n位進行；因此，只需用 n位的加法器就可實現(xiàn)二個n位數(shù)的相乘。, 對乘數(shù)中“1”的位執(zhí)行加法和右移運算，對“0”的位只執(zhí)行右移運算，而不執(zhí)行加法運算?？梢怨?jié)省部分積的生成時間。, 已知兩正小數(shù)X和Y，Y=0.y1y2yn，則： X*Y=X*(0.y1y2yn),= X* y1*2-1 +X* y2*2-2 +X* y3*2-3 +

41、- +X* yn*2-n, 部分積迭代法,=2-1 2-1 2-1-2-1 (2-1 (0 + X* yn)+ X* yn-1)+ -+ X* y2+ X* y1 n個2-1, 設(shè)P0=0 P1= 2-1 (P0+ X* yn) P2= 2-1 (P1+ X* yn-1) Pi+1= 2-1 (Pi+ X* yn-i) ( i=0,1,2,3, n-1 ) Pn= 2-1 (Pn-1+ X* y1), 上述乘法運算可以歸結(jié)為循環(huán)地計算下列算式：, 顯然，X*Y= Pn, 迭代過程可以歸結(jié)為：, 若Yn-i的值為“1”，將上一步迭代的部分積Pi 與X相加。, 若Yn-i的值為“0”，什么也不做。

42、再右移一位，產(chǎn)生本次的迭代部分積Pi+1。, 整個迭代過程以乘數(shù)最低位yn和P0=0開始，經(jīng)過n次“判斷加法右移”循環(huán)直到求出Pn為止。, Pn就為乘法結(jié)果。, 實現(xiàn)這種方法的二個定點小數(shù)乘法的邏輯電路框圖,圖3.16 實現(xiàn)定點乘法運算的邏輯電路,圖3.17 兩個定點小數(shù)的乘法操作流程, 例1 已知 X原=01101 , Y原= 01011 , z1z8=1101*1011的計算采用上述乘法流程，實現(xiàn)的具體過程如下：, 若 X*Y原=z0z1z8 則 z0= 0 0=0,C P Y 說明 0 0000 1011 開始，設(shè)P0=0,+1101 y4=1，+X,0 1101 C,P 和Y同時右移一

43、位,0 0110 1 101 得P1,+1101 y3=1，+X,1 0011 C,P 和Y同時右移一位,0 1001 11 10 得P2,y2=0，不作加法 C,P 和Y同時右移一位 0 0100 111 1 得P3,+1101 y1=1，+X,1 0001 C,P 和Y同時右移一位,0 1000 1111 得P4, z1z8=10001111, X*Y原=z0z1z8=010001111,0 0110 1 101 得P1,3.4.2 原碼二位乘法, 為提高乘法的速度，可以對乘數(shù)的每兩位取值情況進行判斷，一步求出對應(yīng)于該兩位的部分積。, 在乘法中，乘數(shù)的每兩位有四種可能的組合，每種組合對應(yīng)于

44、以下操作：, 原碼二位乘法的思想, 采用原碼二位乘法，只需增加少量的邏輯線路，就可以將乘法的速度提高一倍。,00 Pi+1=2-2Pi,01 Pi+1=2-2(Pi +X),10 Pi+1=2-2(Pi +2X),11 Pi+1=2-2(Pi +3X), 實現(xiàn)+3X有兩種方法：, 分+X再+2X來進行，次法速度較低。, 以4X-X來代替3X運算，在本次運算中只執(zhí)行-X，而+4X則歸并到下一拍執(zhí)行。 Pi+1=2-2(Pi +3X)= 2-2(Pi -X+4X)= 2-2(Pi -X) +X。, 用yi-1、yi和T三位來控制乘法操作, 觸發(fā)器T用來記錄是否欠下+X，若是，則1T, 原碼兩位乘法

45、運算規(guī)則,表3.3 原碼兩位乘法運算規(guī)則, 原碼兩位乘法運算過程舉例,例1： 已知 X原=0111001 , Y原= 0100111 , |X|補=0111001 ，-|X|補=1000111 ；, 若 X*Y原=z0z1z12 則 z0= 0 0=0, z1z12=111001*100111 具體過程：,P Y T 說明 000 000000 100111 0 開始，P0=0，T=0,+111 000111 y5y6T=110 ，-X ,T=1,111 000111 P和Y同時右移2位,111 000111 P和Y同時右移2位,111 110001 11 1001 1 得P1,+001 11

46、0010 y3y4T=011 ，+2X ,T=0,001 100011 P和Y同時右移2位,000 011000 1111 10 0 得P2,+001 110010 y1y2T=100 ，+2X ,T=0,010 001010 P和Y同時右移2位,000 100010 101111 0 得P3, z1z12=100010101111, 因此X*Y原=0100010101111,3.4.3 補碼一位乘法, 考查兩個補碼乘法運算的例子,例1： 已知 X=0.1011，Y=0.0001,X補=01011 , Y補= 00001,X*Y補=000001011,X補*Y補=000001011, 顯然，X

47、*Y補=X補*Y補,例2： 已知 X=0.1011，Y= - 0.0001,X補=01011 , Y補= 11111,X*Y補=111110101,X補*Y補=101010101, 顯然，X*Y補X補*Y補, 對兩個正數(shù)來說，它們補碼的乘積等于它們乘積的補碼。若乘數(shù)是負數(shù)時，這種情況就不成立了。, 若X補=x0 x1 xn , Y補= y0y1 yn 。, 考查兩個補碼乘法運算的一般情況, 根據(jù)補碼定義，可得出其真值: Y= - y0+ yi2-i,i=1,n, X*Y補= X*(-y0+ yi2-i) 補,= X *yi2-i-X*y0 補,= X *yi2-i 補 +-X*y0補,n,i=

48、1,i=1,n,n,i=1, Booth（布斯）乘法, 相乘二數(shù)用補碼表示，它們的符號位與數(shù)值位一起參與乘法運算過程，直接得出用補碼表示的乘法結(jié)果，且正數(shù)和負數(shù)同等對待。, A.D.Booth算法思想：, Booth算法推導(dǎo)：, 已知X補=x0 x1 xn , Y補= y0y1 yn ；根據(jù)補碼定義，可得出:, 根據(jù)補碼定義，可得出其真值: Y= - y0+ yi2-i,i=1,n,= - y0+y12-1+y22-2+y32-3+ +yn2-n,= - y0+(y1-y12-1)+ (y22-1-y22-2)+ + (yn2-(n-1)-yn2-n),= (y1-y0)+ (y2-y1)2-

49、1+ (y3-y2)2-2+ + (yn-yn-1 )2-(n-1) +(0-yn )2-n,= (yi+1-yi)2-i,n,i=1, 設(shè)yn+1=0（稱為輔助位）；有： X*Y補=X* (yi+1-yi)2-i補,n,i=1,=(y1-y0)X+ 2-1( y2-y1)X + 2-1( y3-y2)X + +2-1(yn-i+1-yn-i)X+ +2-1(yn-yn-1)X+2-1(yn+1-yn) X) ) ) 補, 得到如下遞推公式： Pi+1補= 2-1(Pi + (yn-i+1-yn-i)X)補 ( i= 0，1，2 n), 上式中Pi為上次部分積，Pi1為本次部分積。 令P0補0

50、，有：,P1補=2-1(yn+1-yn)*X補 (i= 0) P2補=2-1(P1 + (yn-yn-1)*X)補 (i= 1) Pn補=2-1(Pn-1 + (y2-y1)*X)補 (i= n-1) Pn+1補=Pn + (y1-y0)*X補, 經(jīng)過比較可得 X*Y補=Pn+1補= Pn + (y1-y0)*X補,= Pn 補+ (y1-y0)*X補, 對乘數(shù)的連續(xù)兩位yn-i和yn-i+1進行判斷,若yn-i yn-i+1=01， 則Pi+1補=2-1(Pi + X)補 若yn-i yn-i+1=10， 則Pi+1補=2-1(Pi - X)補 若yn-i yn-i+1=00或11，則Pi+

51、1補=2-1Pi 補, 一個補碼數(shù)據(jù)的右移是連同符號位右移，且最高位補充符號位的值。, 補碼乘法運算規(guī)則：, 乘數(shù)最低位增加一輔助位yn+1= 0；, 判斷yn-i yn-i+1的值，決定是“+X”或“-X”，或僅右移一位，得部分積；, 重復(fù)第步，直到最高位參加操作(y1-y0)*X，但不作移位，結(jié)果得X*Y補。, 圖3.18 是實現(xiàn)布斯乘法的算法流程圖,是,是,是,否,否,否,圖3.18 布斯乘法運算流程圖,開始,yn+1，P0 X補碼制的被乘數(shù) Y補碼制的乘數(shù) Cnn,yn yn+1,P P+X,Cn=0,P和Y同時右移一位 Cn Cn-1,yn yn+1,P P-X,結(jié)束, 例3： 已知

52、 X補=01101, Y補= 10110，-X補=10011。, 用布斯乘法計算X*Y補的過程如下,P Y yn+1 說明 00 0000 10110 0 開始，設(shè)y5=0，P0補=0,y4 y5 =00，P、Y同時右移一位 00 0000 0 1011 0 得P1補,+11 0011 y3 y4 =10，+-X補,11 0011 P、Y同時右移一位,11 1001 10 101 1 得P2補,y2 y3 =11，P、Y同時右移一位,11 1100 110 10 1 得P3補,11 1100 110 10 1 得P3補,+00 1101 y1y2 =01，+X補,00 1001 P、Y同時右移

53、一位,00 0100 1110 1 0 得P4補,+11 0011 y0 y1 =10，+-X補,11 0111 1110 1 最后一次不右移, 因此，X * Y補=101111110, 布斯乘法的算法過程為n+1次的“判斷加減右移”的循環(huán)，判斷的次數(shù)為n+1次，右移的次數(shù)為n次。, 在布斯乘法中，遇到連續(xù)的“1”或連續(xù)的“0”時，是跳過加法運算，直接實現(xiàn)右移操作的，運算效率高。,3.4.4 補碼二位乘法, 補碼二位一乘的方法可以用布斯乘法過程來推導(dǎo), Pi+1補=2-1Pi補 + (yn-i+1-yn-i)* X 補, Pi+2補=2-1Pi+1補+ (yn-i-yn-i-1)* X 補,

54、Pi+2 補=2-2Pi 補+ (yn-i+1 +yn-i -2yn-i-1)* X 補, 根據(jù)乘數(shù)的兩位代碼yn-i-1和yn-i以及右鄰位yn-i+1的值的組合作為判斷依據(jù)，跳過Pi+1補步，即從Pi補直接求得Pi+2補。,乘數(shù)代碼對 右鄰位 加減判斷規(guī)則 Pi+2補 yn-i-1 yn-i yn-i+1,表3.4 乘數(shù)3位代碼組合構(gòu)成的判斷規(guī)則,0 0 0 0 2-2Pi補,0 0 1 +X補 2-2Pi補+X補,0 1 0 +X補 2-2Pi補+X補,0 1 1 +2X補 2-2Pi補+2X補,1 0 0 +2-X補 2-2Pi補+2-X補,1 0 1 +-X補 2-2Pi補+-X補,

55、1 1 0 +-X補 2-2Pi補+-X補,1 1 1 0 2-2Pi補, 設(shè)乘數(shù)Y補= y0y1 yn ，導(dǎo)出補碼二位乘法中的計算量。,(1) 當n為偶數(shù)時，乘法運算過程中的總循環(huán)次數(shù)為n/2+1。,(2) 當n為奇數(shù)時，乘法運算過程中的總循環(huán)次數(shù)為（n+1）/2。, 例4：已知X補=00011 , Y補= 11010 ；-X補=11101 。用補碼二位乘法計算X * Y補的過程。,P Y yn+1 說明,000 0000 11010 0 開始，設(shè)y5=0，P0補=0,+111 1010 y3 y4 y5 =100，+2-X補,111 1010 P和Y同時右移二位,111 1110 10 1

56、10 1 得P1補,+111 1101 y1 y2 y3 =101，+-X補,111 1011 P和Y同時右移二位,111 1110 1110 1 1 得P2補,y0 y0 y1 =111，不做加法 最后一次不右移, X * Y補=111101110,3.4.5 陣列乘法器, 實現(xiàn)上述執(zhí)行過程的陣列結(jié)構(gòu)的乘法器，稱為陣列乘法器(Array Multiplier), 圖3.19中實現(xiàn)了X*Y的乘法運算，其中X=x1x2 x3 x4 , Y= y1y2y3y4 。X和Y都是無符號的小數(shù)部分。, 上式中一位乘積xi*yj用一個兩輸入端的“與”門實現(xiàn)；, 每一次加法操作用一個全加器實現(xiàn)；, 2-i和2-j 的因子所蘊含的移位是由全加器的空間錯位來實現(xiàn)。,圖3.19 直接實現(xiàn)定點數(shù)絕對值相乘的陣列乘法器, Booth算法的乘法運算也可以用陣列乘法器的方法實現(xiàn)，但要求的單元更復(fù)雜。, 陣列乘法器的組織結(jié)構(gòu)規(guī)則性強，標準化程度高。適合用超大規(guī)模集成電路實現(xiàn)，且能獲得很高的運算速度。, 集成電路的價格不斷下降，陣列乘法器在某些數(shù)字系統(tǒng)中，例如在信號及數(shù)據(jù)處理系統(tǒng)中受到重視，它不需要時鐘脈沖，而其乘法速度僅決定于門和加法器的傳輸延遲