計(jì)算機(jī)是一種能對(duì)數(shù)字化信息進(jìn)行自動(dòng)高速運(yùn)算的通用處....ppt

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

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

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

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

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

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

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

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

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

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

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

12、0160+1216-1) 10 =(58.75) 10,2. 十進(jìn)制數(shù)轉(zhuǎn)換成R進(jìn)制數(shù),任何一個(gè)十進(jìn)制數(shù)轉(zhuǎn)換成R進(jìn)制數(shù)時(shí)，要將 整數(shù)和小數(shù)部分分別進(jìn)行轉(zhuǎn)換。,（1）整數(shù)部分的轉(zhuǎn)換 整數(shù)部分的轉(zhuǎn)換方法是“除基取余，上右下左”。,例1 將十進(jìn)制整數(shù)835分別轉(zhuǎn)換成二、八進(jìn)制數(shù)。,0,余數(shù) 低位,3,0,5,1,(835) 10=(1503) 8,高位,(835) 10=(1101000011) 2,（2）小數(shù)部分的轉(zhuǎn)換,小數(shù)部分的轉(zhuǎn)換方法是 “乘基取整，上左下右”。,例2 將十進(jìn)制小數(shù)0.6875分別轉(zhuǎn)換成二、八進(jì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 將十進(jìn)制小數(shù)0.63轉(zhuǎn)換成二進(jì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ù)部分分別進(jìn)行轉(zhuǎn)換，得 到轉(zhuǎn)換后的整數(shù)和小數(shù)部分，然后再這兩 部分組合起來(lái)得到一個(gè)完整的數(shù)。,例 4 將十進(jìn)制數(shù)835.6875轉(zhuǎn)換成二、八進(jìn)制數(shù)。 (8

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

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

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

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

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

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

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

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

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

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

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

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

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

27、一個(gè)為“1”， 且進(jìn)位C1為“1”。, 可得C2的表達(dá)式為： C2=X2Y2+(X2+Y2)C1 =X2Y2+(X2+Y2)X1Y1+(X2+Y2)(X1+Y1)C0, 同理，可得C3的表達(dá)式為： 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的表達(dá)式為： 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, 定義兩個(gè)輔助函數(shù)： Pi= Xi+Yi Gi= XiYi, Pi表示進(jìn)位傳遞函數(shù)，當(dāng)Xi、Yi中有一個(gè)為“1”時(shí)，若有低位進(jìn)位輸入，則本位向高位傳送進(jìn)位。, Gi表示進(jìn)位產(chǎn)生函數(shù)，當(dāng)Xi、Yi均為“1”時(shí)，不管有無(wú)低位進(jìn)位輸入，本位一定向高位產(chǎn)生進(jì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, “先行進(jìn)位產(chǎn)生電路” （圖 3.6 (a)）及“4位先行進(jìn)位加法器”的邏輯圖（圖 3.6 (b)）,圖3.6 (a) 先行進(jìn)位產(chǎn)生電路,圖3.6 (b) 4位先行進(jìn)位加法器, 四個(gè)4位先行進(jìn)位加法器串接起來(lái)構(gòu)成16位加法器, 在各加法單元之間，進(jìn)位信號(hào)是串行傳送的，而在加法單元內(nèi)，進(jìn)位信號(hào)是并行傳送的。,圖3.7 組間為串行進(jìn)位構(gòu)成的16位加法器, 并行進(jìn)位的概念可用于16位加法器；進(jìn)一步提高16位

30、加法器的運(yùn)算速度。, Cm表示4位加法器的進(jìn)位輸出，Pm表示4位加法器的進(jìn)位傳遞輸出，Gm表示4位加法器的進(jìn)位產(chǎn)生輸出。, Cm=Gm+PmC0, Pm 和Gm分別為： Pm= P4P3P2P1 Gm= G4 +P4 G3 + P4P3G2 +P4P3P2G1, 應(yīng)用于四個(gè)4位先行進(jìn)位加法器，則有： 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 組間由先行進(jìn)位鏈構(gòu)成的16位加法器, 可將并行進(jìn)位的概念用于更大位數(shù)的加法器上，隨著加法器位數(shù)的增加，加法電路變得越來(lái)越復(fù)雜。,33 定點(diǎn)加、減法運(yùn)算, 計(jì)算機(jī)的一個(gè)重要特點(diǎn)是它只能用有限的 數(shù)碼位數(shù)來(lái)表示操作數(shù)和操作結(jié)果。, 制定用來(lái)表示正、負(fù)數(shù)的各種碼制；通過(guò)數(shù)據(jù)編碼來(lái)簡(jiǎn)化數(shù)據(jù)的運(yùn)算，特別是補(bǔ)碼，把加法和減法巧妙地結(jié)合起來(lái)。, 定點(diǎn)加、減法運(yùn)算只有在遵守模運(yùn)算規(guī)則的限制條件下其結(jié)果才是正確的，否則就會(huì)出現(xiàn)結(jié)果“溢出”。,3.3.1 補(bǔ)碼定點(diǎn)加、減法, 補(bǔ)碼制的加、減法運(yùn)算公式： X+Y補(bǔ)= (X補(bǔ)+Y 補(bǔ)) M

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

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

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

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

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

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

38、成的陣列乘法器。,3.4.1 原碼一位乘法, 用原碼實(shí)現(xiàn)乘法運(yùn)算時(shí)，符號(hào)位與數(shù)值位是分開(kāi)計(jì)算的；, 原碼乘法運(yùn)算分為二步；, 第二步是計(jì)算乘積的數(shù)值位；乘積的數(shù)值部分為兩數(shù)的絕對(duì)值之積。, 第一步是計(jì)算乘積的符號(hào)位；乘積的符號(hào)為相乘二數(shù)符號(hào)的異或值。, 用數(shù)學(xué)表達(dá)式描述原碼乘法運(yùn)算, 設(shè)：X原=x0 x1xn，Y原= y0y1yn (其中x0 、y0分別為它們的符號(hào)位), 若 X*Y原=z0z1z2n (其中z0 為結(jié)果之符號(hào)位) 則 z0= x0 y0, z1z2n= (x1xn ) *(y1yn), 筆-紙乘法方法, 例1. X=0.1011,Y=0.1101，X*Y的筆-紙乘法過(guò)程：,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的筆-紙乘法過(guò)程中，計(jì)算兩個(gè)正數(shù)的乘法特點(diǎn)：, 用乘數(shù)Y的每一位依次去乘以被乘數(shù)，得X*yi，i=4、3、2、1。若yi=0，得0。若yi=1，得X。, 把中求得的各項(xiàng)結(jié)果X*yi在空間上向左錯(cuò)位排列，即逐次左移，可以表示為X* yi*2-i 。, 對(duì)中求得的結(jié)果求和， ，這也就是兩個(gè)正數(shù)的

40、乘積。, 就筆-紙乘法方法，為提高效率而采取的改進(jìn)措施, 每將乘數(shù)Y 的一位乘以被乘數(shù)得X*yi后，就將該結(jié)果與前面所得的結(jié)果累加，而得到P i，稱之為部分積；這減少了保存每次相乘結(jié)果X*yi的開(kāi)銷。, 將部分積P i右移一位與X*yi相加。加法運(yùn)算始終對(duì)部分積中的高n位進(jìn)行；因此，只需用 n位的加法器就可實(shí)現(xiàn)二個(gè)n位數(shù)的相乘。, 對(duì)乘數(shù)中“1”的位執(zhí)行加法和右移運(yùn)算，對(duì)“0”的位只執(zhí)行右移運(yùn)算，而不執(zhí)行加法運(yùn)算?？梢怨?jié)省部分積的生成時(shí)間。, 已知兩正小數(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個(gè)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), 上述乘法運(yùn)算可以歸結(jié)為循環(huán)地計(jì)算下列算式：, 顯然，X*Y= Pn, 迭代過(guò)程可以歸結(jié)為：, 若Yn-i的值為“1”，將上一步迭代的部分積Pi 與X相加。, 若Yn-i的值為“0”，什么也不做。

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

43、位,0 0110 1 101 得P1,+1101 y3=1，+X,1 0011 C,P 和Y同時(shí)右移一位,0 1001 11 10 得P2,y2=0，不作加法 C,P 和Y同時(shí)右移一位 0 0100 111 1 得P3,+1101 y1=1，+X,1 0001 C,P 和Y同時(shí)右移一位,0 1000 1111 得P4, z1z8=10001111, X*Y原=z0z1z8=010001111,0 0110 1 101 得P1,3.4.2 原碼二位乘法, 為提高乘法的速度，可以對(duì)乘數(shù)的每?jī)晌蝗≈登闆r進(jìn)行判斷，一步求出對(duì)應(yīng)于該兩位的部分積。, 在乘法中，乘數(shù)的每?jī)晌挥兴姆N可能的組合，每種組合對(duì)應(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), 實(shí)現(xiàn)+3X有兩種方法：, 分+X再+2X來(lái)進(jìn)行，次法速度較低。, 以4X-X來(lái)代替3X運(yùn)算，在本次運(yùn)算中只執(zhí)行-X，而+4X則歸并到下一拍執(zhí)行。 Pi+1=2-2(Pi +3X)= 2-2(Pi -X+4X)= 2-2(Pi -X) +X。, 用yi-1、yi和T三位來(lái)控制乘法操作, 觸發(fā)器T用來(lái)記錄是否欠下+X，若是，則1T, 原碼兩位乘法

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

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

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

48、1,i=1,n,n,i=1, Booth（布斯）乘法, 相乘二數(shù)用補(bǔ)碼表示，它們的符號(hào)位與數(shù)值位一起參與乘法運(yùn)算過(guò)程，直接得出用補(bǔ)碼表示的乘法結(jié)果，且正數(shù)和負(fù)數(shù)同等對(duì)待。, A.D.Booth算法思想：, Booth算法推導(dǎo)：, 已知X補(bǔ)=x0 x1 xn , Y補(bǔ)= y0y1 yn ；根據(jù)補(bǔ)碼定義，可得出:, 根據(jù)補(bǔ)碼定義，可得出其真值: 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補(bǔ)=X* (yi+1-yi)2-i補(bǔ),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) ) ) 補(bǔ), 得到如下遞推公式： Pi+1補(bǔ)= 2-1(Pi + (yn-i+1-yn-i)X)補(bǔ) ( i= 0，1，2 n), 上式中Pi為上次部分積，Pi1為本次部分積。 令P0補(bǔ)0

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

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

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

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

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

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

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