1、目錄...76.3.8定點(diǎn)數(shù)的運(yùn)算運(yùn)算部件的基本結(jié)構(gòu)定點(diǎn)加減運(yùn)算移位運(yùn)算定點(diǎn)乘法運(yùn)算定點(diǎn)除法運(yùn)算陣列乘除法器十進(jìn)制運(yùn)算基本的邏輯運(yùn)算Copyright 2012 Computer Organization Group. All rights reserved.6.3.4 定點(diǎn)乘法運(yùn)算以定點(diǎn)小數(shù)為例Y = - 0.1011Y = - 0.10001111例： X = 0.1101X ；。Copyright 2012 Computer Orga

2、nization Group. All rights reserved.機(jī)器實(shí)現(xiàn)問題： 1. 加法器只有兩個(gè)數(shù)據(jù)輸入端2. 加法器與運(yùn)算數(shù)據(jù)位數(shù)相同 解決方案： 1. 改n輸入數(shù)相加為兩兩相加； 2. 改2n位相加過程為n位相加。 0. 1 1 0 1 0. 1 01 10.00001 1 0 10.00011 0 10.00000 0+0.011010 . 1000 11 1 1筆算乘法過程 原碼一位乘法基本公式： 設(shè) 被乘數(shù) X原 = Xs . X1X2 Xn乘 數(shù) Y 原 = Ys . Y1Y2 Yn則積P原= XY原 = ( Xs Ys ).( X*Y* )=Ps.P1P2PnPn+1

3、P2n其中， X* 和Y*分別是X和Y的絕對(duì)值，Xs、Ys和Ps分別表示X原、Y原和P原的符號(hào)位。 1）算法推導(dǎo) 乘積絕對(duì)值通式： nP*=X*Y*= X*(0.Y1Y2Yn) = X*S Yi2-i展開得i=1= X*(Y12-1+Y22-2+Yn2-n)=2-1 (Y1X*+2-1 (Y2X*+2-1 (+2-1 (Yn-1X*+2-1 (YnX*+0)Copyright 2012 Computer Organization Group. All rights reserved.原碼一位乘法（續(xù)）p 令Zi表示第i次的部分積，上述迭代公式可寫成遞

4、推 公式的形式： Z= 00Z= 2（-1Y X* + Z ）1n0Z= 2（-1Y X* + Z）n -121Z= 2（-1 X* + ZY）n -i+1i-1iZ= 2（-1Y X* + Z）n -1n1Copyright 2012 Computer Organization Group. All rights reserved.p 由遞推公式可知， X*Y* 可轉(zhuǎn)化成n次加法和n次右移完成，其中 Zi表示第i次運(yùn)算的部分積； Z0表示部分積的初值 （Z0 =0）； Zn則為最后乘積的絕對(duì)值，即 P*= X*Y*= Zn原碼一位乘法運(yùn)算規(guī)則r 參

5、加運(yùn)算的兩個(gè)數(shù)均為原碼，兩數(shù)符號(hào)位不參加運(yùn)算， 取其絕對(duì)值做無符號(hào)數(shù)乘法； r 乘積的符號(hào)位單獨(dú)處理，由兩數(shù)符號(hào)“異或”產(chǎn)生； r 設(shè)部分積初值為0。為防止運(yùn)算過程中產(chǎn)生暫時(shí)性溢出 ，部分積采用單符號(hào)位參加運(yùn)算。n位數(shù)相乘，部分積連 同符號(hào)位應(yīng)取n+1位； r 運(yùn)算前先檢測(cè)0，只要兩數(shù)有任意一個(gè)為0，則乘積為0， 不再進(jìn)行運(yùn)算； r 部分積運(yùn)算：用乘數(shù)的最低位作為判斷位，若為1，加被 乘數(shù)；若為0，不加（相當(dāng)于加0）；運(yùn)算后部分積邏輯右移一位。 r 當(dāng)乘數(shù)數(shù)值部分為n位時(shí)，共作n次“加法”和“右移” ，最后得到2n位的乘積絕對(duì)值。 Copyright

6、 2012 Computer Organization Group. All rights reserved.原碼一位乘法運(yùn)算實(shí)例Y = - 0.1011Y原 = 1.1011例： X = 0.1101X原 = 0.1101則 X* = 0.1101Y* =0.1011XY原 = 1.1000 1111XY = -0.1000 1111計(jì)算機(jī)內(nèi)運(yùn)算的描述方法Copyright 2012 Computer Organization Group. All rights reserved.0. 1 1 0 1 0. 1 0 111 1 0 11 1 0 1

7、0 0 0 0+1 1 0 1手工運(yùn)算過程 0 . 1 0 0 0 1 1 1 1部分積乘數(shù) 0. 0 0 0 00.1 0 1 1+ 0. 1 1 0 10. 1 1 0 10. 0 1 1 01 0.1 0 1+ 0. 1 1 0 11. 0 0 1 10. 1 0 0 11 1 0.1 00. 0 1 0 01 1 1 0.1+ 0. 1 1 0 11. 0 0 0 10. 1 0 0 01 1 1 1 0.整數(shù)原碼一位乘法p 原碼一位乘算法規(guī)則同樣適用于整數(shù)，只要把例題中的小數(shù)點(diǎn)“.”改為逗號(hào)“,”即可。 p 注意整數(shù)小數(shù)點(diǎn)的隱含位置和定點(diǎn)小數(shù)不一樣，故乘積最終要向右對(duì)齊小數(shù)點(diǎn)，這是兩

8、種定點(diǎn)數(shù)據(jù)格式運(yùn)算時(shí)的主要差別。 r 例：X = 1101，Y = - 1011，用原碼一位乘法求XY=？r 解：X原= 0,1101，Y原=1,1011X*= 0,1101，Y*=1011Ps=XsYs=01=1；P*=0, 1000 1111P原= XY原=1, 1000 1111XY= - (0,11011011) = - 1000 1111Copyright 2012 Computer Organization Group. All rights reserved.整數(shù)原碼一位乘法運(yùn)算實(shí)例小數(shù)點(diǎn)位置

9、Copyright 2012 Computer Organization Group. All rights reserved.部分積 乘數(shù)Yn說明 0 , 0 0 0 0 + 0 , 1 1 0 1 1011 初始化 +X*0 , 1 1 0 1 1 0 , 0 1 1 0 + 0 , 1 1 0 1 第1步 +X*1 101 暫時(shí)性溢出 1 ,0 0 1 11 0 , 1 0 0 1 + 0 , 0 0 0 0 第2步 +0 11 10 0 , 1 0 0 1 1 0 , 0 1 0 0 + 0 , 1 1 0 1 第3步 +X*111 1 1 , 0 0 0 1 1 0 , 1 0 0

10、0 第4步 1111 原碼一位乘法運(yùn)算的硬件實(shí)現(xiàn)ys=1Psxsr 數(shù)值位為n位，運(yùn)算器的總位數(shù)應(yīng)達(dá)到n+1位； r 原碼乘法運(yùn)算器主要由一個(gè)加法器和三個(gè)寄存器組成；r A為累加器，用來存放部分積； r B為被乘數(shù)寄存器，其值保持不變； r Q為乘數(shù)/部分積寄存器，A、Q首尾相接實(shí)現(xiàn)聯(lián)合右移一位。Copyright 2012 Computer Organization Group. All rights reserved.CR(計(jì)數(shù)器)0Bn S0Qn 右移 + X *或+ 0&(控制門)n+1位(加法器)0An 原碼一位乘法運(yùn)算器框圖A+BAA、Q

11、同時(shí)邏輯右移一位CR1 CRE原碼一位乘法控制流程開始NQ =1?nYNCR=0?YE結(jié)束Copyright 2012 Computer Organization Group. All rights reserved.0 B0， 0 Q0B0Q0 SCR-1 CRA、Q同時(shí)邏輯右移一位 A+BA0 A被乘數(shù)原碼B 乘數(shù)原碼Qn CR補(bǔ)碼一位乘法（比較法）原碼乘法簡(jiǎn)單易實(shí)現(xiàn)，但有兩個(gè)問題:1.符號(hào)位與數(shù)值位分別處理，不方便； 若數(shù)據(jù)為補(bǔ)碼形式，可能需要多于兩次2.的補(bǔ)原碼轉(zhuǎn)換。 采用補(bǔ)碼表示的計(jì)算機(jī)中往往希望直接用補(bǔ)碼完成乘法運(yùn)算，即從補(bǔ)碼操作數(shù)開始運(yùn)

12、算，然后直接得到補(bǔ)碼的積。 下面看一看補(bǔ)碼乘運(yùn)算的實(shí)現(xiàn)算法。Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼一位乘法(比較法)的算法推導(dǎo)設(shè) 被乘數(shù) X補(bǔ) = X0. X1 X2 Xn乘數(shù) Y= Y0. Y1 Y2 Yn補(bǔ)先復(fù)習(xí)兩個(gè)概念: 已知 X補(bǔ) = X0. X1X2 Xn 時(shí)Xn-1X/2補(bǔ) = X0. X0X1X2 已知 Y補(bǔ) = Y0.Y1Y2 Yn 時(shí)nY = - Y S Y2-i0ii=1= Sn(Y-Y) 2-ii+1ii=0http:/corg.xjt

13、Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼一位乘法(比較法)的算法推導(dǎo)XY補(bǔ) ? 補(bǔ)補(bǔ)推導(dǎo)：nXY = X-Y0S Yi2-i i=1= X(0 .Y1Y2 Yn) - XY0 XY補(bǔ)=X (0.Y1Y2 Yn) - XY0補(bǔ)=X (0.Y1Y2 Yn)補(bǔ)- XY0補(bǔ)?=X補(bǔ) (0.Y1Y2 Yn) - Y0X補(bǔ)=X補(bǔ)YCopyright 2012 Computer Organization Group. All rights reserved.

14、補(bǔ)碼一位乘法(比較法)的算法推導(dǎo)求證：X(0.Y1Y2 Yn) 補(bǔ) = X補(bǔ)(0.Y1Y2 Yn)證明：(1)當(dāng)X 0 時(shí)，Yn)X(0.Y1Y2 Yn) = X(0.Y1Y2補(bǔ)=X補(bǔ)(0.Y1Y2 Yn)(2)當(dāng)X 0 時(shí)，X(0.Y1Y2 Yn)補(bǔ)= 2+X(0.Y1Y2 Yn)= 2n+1+X(0.Y1Y2 Yn)(mod 2)(mod 2)(mod 2)= 2n+1(0.Y1Y2 Yn)+X(0.Y1Y2 Yn)(mod 2)(mod 2)(mod 2)= (2n+1+X)(0.Y1Y2 Yn)= (2+X)(0.Y1Y2 Yn)= X補(bǔ)(0.Y1Y2 Yn)證畢http:/corg.

15、Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼一位乘法(比較法)的算法推導(dǎo)補(bǔ)碼乘法的基本公式： XY補(bǔ)補(bǔ)nY=（-Y0S Yi2-i )Y補(bǔ)展開多項(xiàng)式i=1令：Yi2-i= Yi2-(i-1)-Yi2-i0-1-2-n= -Y02+ Y12+ Y22+ + Yn2= -Y020 + (Y120-Y12-1) + (Y22-1 -Y22-2) + += (Y1-Y0) 20+ (Y2-Y1) 2-1 + + (Yn+1-Yn) 2-n最低位后再補(bǔ)1位令：Yn+1 = 0http:/corg

16、.Copyright 2012 Computer Organization Group. All rights reserved.寫成和式n=S( Yi+1 Yi ) 2-ii=0合并同次項(xiàng) 補(bǔ)碼一位乘法(比較法)的算法推導(dǎo)補(bǔ)碼一位乘比較法公式：nP補(bǔ)= XY補(bǔ) = 補(bǔ) Si=0(Yi+1 - Yi )2-i部分積遞推公式：Z0補(bǔ)= 0Z1補(bǔ)= 2-1 Z0補(bǔ)+ (Yn+1 - Yn)補(bǔ)Zi補(bǔ)= 2-1 Zi-1補(bǔ)+ (Yn-i+2 - Yn-i+1)補(bǔ)Zn補(bǔ)= 2-1 Zn-1補(bǔ)+ (Y2 - Y1)補(bǔ)(令：Yn+1= 0)Zn+1補(bǔ)= Zn補(bǔ)+ (Y1 - Y0)補(bǔ)

17、= XY補(bǔ) = P補(bǔ)Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼一位乘（比較法）算法規(guī)則Copyright 2012 Computer Organization Group. All rights reserved. 乘數(shù)最低位之后增加一位附加位Yn+1 ，且初始令Yn+1=0； 運(yùn)算前檢測(cè)0，只要X、Y有任意一個(gè)為0，則乘積為0，不再運(yùn)算； 用乘數(shù)的最低兩位YnYn+1作為判斷位，其比較值(Yn+1-Yn)始終決定了每

18、次應(yīng)執(zhí)行的操作。 r 部分積運(yùn)算規(guī)則如下： YnYn+1= 00 時(shí)， Zi補(bǔ)= Zi-1補(bǔ)+ 0， 算術(shù)右移1位； YnYn+1= 01 時(shí)， Zi補(bǔ)= Zi-1補(bǔ)+ X補(bǔ)， 算術(shù)右移1位； YnYn+1= 10 時(shí)， Zi補(bǔ)= Zi-1補(bǔ)+ -X補(bǔ)，算術(shù)右移1位； YnYn+1= 11 時(shí)， Zi補(bǔ)= Zi-1補(bǔ)+ 0， 算術(shù)右移1位； 重復(fù)n+1次比較和運(yùn)算，但只右移n次，最后一次只運(yùn)算不移位。 運(yùn)算完成后，為避免誤差，乘數(shù)的最低兩位YnYn+1清0。 X、Y均用補(bǔ)碼表示，且符號(hào)位都參加運(yùn)算，乘積的符號(hào)位由運(yùn)算過程自動(dòng)產(chǎn)生； 設(shè)部分積初值為0，部分積采用雙符號(hào)位運(yùn)算，但乘數(shù)只需要一位 符

19、號(hào)位參加運(yùn)算； 補(bǔ)碼一位乘（比較法）運(yùn)算實(shí)例已知：X = 0.1101Y = - 0.1011求：XY =？ 解：X補(bǔ) = 0.1101Y補(bǔ) = 1.0101-X= 1.0011補(bǔ) XY補(bǔ) = 11.0111000100XY = 0.100011111 1. 1 0 1 10 0 1 1.01Copyright 2012 Computer Organization Group. All rights reserved.部分積乘數(shù) ynyn+1 0 0. 0 0 0 01.0 1 0 10+1 1. 0 0 1 11 1. 0 0 1 11 1. 1

20、0 0 11 1.0 1 01+0 0. 1 1 0 10 0. 0 1 1 00 0. 0 0 1 10 1 1.0 10+1 1. 0 0 1 11 1. 0 1 1 0+0 0. 1 1 0 10 0. 1 0 0 00 0. 0 1 0 00 0 0 1 1.0+1 1. 0 0 1 11 1. 0 1 1 10 0 0 1 00清0整數(shù)補(bǔ)碼一位乘（比較法）算法r 補(bǔ)碼一位乘比較法規(guī)則同樣適用于整數(shù)，也需要把例題中的小數(shù)點(diǎn)“.”改為逗號(hào)“，”，關(guān)注的焦點(diǎn) 仍是小數(shù)點(diǎn)的隱含位置不同于小數(shù)。 r 為了硬件實(shí)現(xiàn)方便，可將小數(shù)點(diǎn)的位置約定在乘數(shù)的附加位之后，這意味著乘數(shù)在運(yùn)算前被乘了2。為 了

21、保證雙倍字長(zhǎng)整數(shù)乘積的小數(shù)點(diǎn)在其最低位（ LSB）的右邊對(duì)齊，最后一步運(yùn)算后，結(jié)果需要算術(shù)右移2位。 r 根據(jù)補(bǔ)碼的符號(hào)擴(kuò)展特性，整數(shù)補(bǔ)碼乘積高位與符 號(hào)位取值相同的部分，應(yīng)該全部看成擴(kuò)展的符號(hào)， 而不是有效的數(shù)值位。 Copyright 2012 Computer Organization Group. All rights reserved.整數(shù)補(bǔ)碼一位乘（比較法）舉例附加值yn+1部分積說明乘數(shù)yn00,00000,11010.初始化+00,1010+- X 補(bǔ)0000,10011001第1步00,1101.1+ X 補(bǔ)+11,01101101

22、10,111110001110第2步1+110,110.+ - X 補(bǔ)丟掉11+000000,000100110110第3步1101,11.+0001001,000001101110第4步1+11100,1.+ X 補(bǔ)111111,0111011101111111110100,1.0.0第5步1111111.符號(hào)延伸MSB小數(shù)點(diǎn)位置Copyright 2012 Computer Organization Group. All rights reserved.X =-1010Y =1101用補(bǔ)碼一位乘比較法求XY=？ 解： X補(bǔ)=11, 0110 Y補(bǔ)

23、=0,1101-X補(bǔ)=00, 1010P補(bǔ)=XY補(bǔ) =11,1101111 110XY=-10000010算法運(yùn)算步驟： 補(bǔ)碼一位乘法運(yùn)算的實(shí)現(xiàn)特點(diǎn)：與原碼一位乘法運(yùn)算器類似，主要區(qū)別為： p 運(yùn)算器的位數(shù)為n+2位（雙符號(hào)位運(yùn)算）； p 乘數(shù)單符號(hào)位參加運(yùn)算，Q寄存器最低位用作附加位Yn+1； p 核心部件為加/減法器， 由n+2個(gè)與或控制門電路控制輸入；p Q寄存器的最低兩位QnQn+1控制部分積作何種運(yùn)算； Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼一位乘

24、比較法運(yùn)算器補(bǔ)碼一位乘法運(yùn)算的實(shí)現(xiàn)開始0110QnQn+1=？0011YNCR=0?結(jié)束Copyright 2012 Computer Organization Group. All rights reserved.A、Q聯(lián)合算數(shù)右移一位 CR-1CRA+BAA-BA X 補(bǔ) B Y 補(bǔ) Q 0 A n+1 CR補(bǔ)碼一位乘比較法流程圖補(bǔ)碼兩位乘法（比較法）提高乘法運(yùn)算速度的方法r 基本乘法算法實(shí)質(zhì)：逐位循環(huán)迭代，一次乘轉(zhuǎn)換成n次累 加和移位，導(dǎo)致乘法運(yùn)算比加減慢得多。 r 兩條常見的提速思路 改進(jìn)算法，或研制更高效的算法 常用的改進(jìn)方法：合并乘法步驟

25、，通過提高算法本身的并行性、減少迭代次數(shù)來對(duì)乘法加速，如 兩位乘法一位乘兩步合并一步，速度可提高一倍左右； 三位乘法一位乘三步合并一步，速度可提高兩倍左右； 無法從根本上改變多次迭代的相乘過程 用硬件陣列直接實(shí)現(xiàn)乘法 通過多級(jí)加法器并行完成運(yùn)算，后面專門討論。 Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼兩位乘比較法p 算法推導(dǎo)設(shè) 被乘數(shù) X補(bǔ) = X0 .X1X2Xn乘Y數(shù) Y= Y0 .Y1Y2n補(bǔ)由一位乘算法得： Zi+1補(bǔ)= 2-1 Zi補(bǔ)+ (Yn-i+

26、1 - Yn-i)補(bǔ)Zi+2補(bǔ)= 2-12-1 Zi補(bǔ)+ (Yn-i+1 - Yn-i)補(bǔ)+ (Yn-i= 2-2 Zi補(bǔ)+ (Yn-i+1 + Yn-i 2Yn-i-1)補(bǔ)p 結(jié)論 - Yn-i-1)補(bǔ)補(bǔ)碼兩位乘比較法的部分積運(yùn)算由乘數(shù)相鄰的三位比較決定，運(yùn)算后每次右移兩位。 Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼兩位乘比較法算法規(guī)則 X、Y均用補(bǔ)碼表示，且符號(hào)位都參加運(yùn)算，乘積的符號(hào)位由運(yùn)算過程自動(dòng)產(chǎn)生； 部分積采用三位符號(hào)位運(yùn)算，初值為0 ； 乘數(shù)最低

27、位之后增加一位附加位Yn+1 ，初始令Yn+1=0； 運(yùn)算前檢測(cè)0：只要X、Y有任意一個(gè)為0，則乘積為0，不再進(jìn)行運(yùn)算； 設(shè)乘數(shù)數(shù)值部分為n位， 當(dāng)n為奇數(shù)時(shí)，乘數(shù)設(shè)1位符號(hào)位，做(n+1)/2次運(yùn)算和移位，最后一步右移1位； 當(dāng)n為偶數(shù)時(shí)，乘數(shù)設(shè)2位符號(hào)位，做(n/2)+1次運(yùn)算， n/2次移位，最后一步不移位。 運(yùn)算完成后，為避免誤差，乘數(shù)的最低三位Yn-1YnYn+1 清0。 Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼兩位乘比較法算法規(guī)則用乘數(shù)最低三位作判

28、斷位，每求一次部分積右移兩位，部 分積運(yùn)算規(guī)則如下： yn-1 yn yn+1= 000 時(shí)， Zi+2補(bǔ)= Zi補(bǔ)+ 0， yn-1 yn yn+1= 001 時(shí)， Zi +2補(bǔ)= Zi補(bǔ)+ X補(bǔ)，算術(shù)右移2位; 算術(shù)右移2位; 算術(shù)右移2位;yn-1 yn yn+1= 010 時(shí)， Zi +2補(bǔ)= Zi補(bǔ)+ X補(bǔ)，yn-1 yn yn+1= 011 時(shí)， Zi +2補(bǔ)= Zi補(bǔ)+ 2X補(bǔ)， 算術(shù)右移2位; yn-1 yn yn+1= 100 時(shí)， Zi +2補(bǔ)= Zi補(bǔ)+ 2-X補(bǔ)，算術(shù)右移2位; yn-1 yn yn+1= 101 時(shí)， Zi +2補(bǔ)= Zi補(bǔ)+ -X補(bǔ)， 算術(shù)右移2位;

29、 yn-1 yn yn+1= 110 時(shí)， Zi +2補(bǔ)= Zi補(bǔ)+ -X補(bǔ)， 算術(shù)右移2位;算術(shù)右移2位;yn-1 yn yn+1= 111 時(shí)， Zi +2補(bǔ)= Zi補(bǔ)+ 0，Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼兩位乘法運(yùn)算實(shí)例X補(bǔ) = 0.1101Y補(bǔ) = 1.0101則 -X補(bǔ) = 1.0011已知:XY=111.01110001000補(bǔ)Copyright 2012 Computer Organizati

30、on Group. All rights reserved.部分積乘 數(shù) yn yn+1 0 0 0. 0 0 0 01 1.0 1 0 10+ 0 0 0. 1 1 0 120 0 0. 1 1 0 10 0 0. 0 0 1 10 1 1 1.0 10+ 0 0 0. 1 1 0 120 0 1. 0 0 0 00 0 0. 0 1 0 00 0 0 1 1 1.0+ 1 1 1. 0 0 1 11 1 1. 0 1 1 10 0 0 1 0 00清0部分積乘數(shù) ynyn+1 0 0. 0 0 0 01.0 1 0 10+1 1. 0 0 1 111 1. 0 0 1 11 1. 1 0

31、0 11 1.0 1 01+0 0. 1 1 0 1110 0. 0 1 1 00 0. 0 0 1 10 1 1.0 10+1 1. 0 0 1 111 1. 0 1 1 01 1. 1 0 1 10 0 1 1.01+0 0. 1 1 0 1110 0. 1 0 0 00 0. 0 1 0 00 0 0 1 1.0+1 1. 0 0 1 11 1. 0 1 1 10 0 0 1 00清0比較乘法運(yùn)算總結(jié)注：n為乘數(shù)的數(shù)值部分的位數(shù)Copyright 2012 Computer Organization Group. All rights rese

32、rved.乘法類型 符號(hào)位 累加次數(shù) 移位 參加運(yùn)算 部分積 乘數(shù) 方向 次數(shù) 每次位數(shù) 補(bǔ)碼一位乘法 是 21n+1右 n1補(bǔ)碼兩位乘法 是 32(n為偶數(shù))n +1 2右 n221(n 為奇數(shù))n +1 2右 n +1 22(最后一次移1位)本章第二次作業(yè)（總第10次作業(yè)）r 6.25、6.28、6.33 、6.34r (1) 6.25可以僅做第三組，即X3、Y3、Z3(2) 6.34僅做原碼加減交替除法 r 本周作業(yè)下周五交Copyright 2012 Computer Organization Group. All rights reserv

33、ed.6.3.5 定點(diǎn)除法運(yùn)算定點(diǎn)小數(shù)為例例如：X = 0.1011Y = -0.1101筆算除法過程 ： 0.11010.11010.10110 -0.011010.010010-0.001101機(jī)器實(shí)現(xiàn)問題：1. 需單獨(dú)設(shè)計(jì)比較器線路； 2. 需2n位的減法器線路。 解決方案：1. 比較操作改由“試減”實(shí)現(xiàn)； 2. 將除數(shù)右移改為部分余數(shù)左移； 3. 減法由+-Y*補(bǔ)轉(zhuǎn)化為加法實(shí)現(xiàn)。 0.00010100-0.000011010.00000111Copyright 2012 Computer Organization Group. All rig

34、hts reserved.定點(diǎn)除法運(yùn)算定點(diǎn)小數(shù)為例基本公式：設(shè)被除數(shù) X 原 = Xs . X1 X2 XnY 原 = Ys . Y1 Y2 Yn除數(shù)0 X* Y*若則Q原 =XY原 = (XsYs). (X*Y*) =Qs.Q1Q2Qn其中，X*和Y*分別是X和Y的絕對(duì)值，Xs、Ys和Qs分別表示X原、Y原和Q原的符號(hào)位。Copyright 2012 Computer Organization Group. All rights reserved.原碼恢復(fù)余數(shù)除法例如： X = -0.1011Y = -0.1101求：XY=?解： X原= 1.10

35、11Y= 1.1101原X* = 0.1011Y* = 0.1101-Y*補(bǔ) = 1.0011X/Y 原 =0.1101 R*=0.01112-4Copyright 2012 Computer Organization Group. All rights reserved.被除數(shù)（余數(shù)）商說明 0. 1 0 1 10. 0 0 0 0+ 1. 0 0 1 1+ -Y*補(bǔ) （減除數(shù)） 1. 1 1 1 0余數(shù) 0, 商上11. 0 0 1 00. 0 0 0 1左移一位 + 1. 0 0 1 1+ -Y *補(bǔ) 0. 0 1 0 1余數(shù) 0, 商上10.

36、 1 0 1 00. 0 0 1 1左移一位 + 1. 0 0 1 1+ -Y *補(bǔ) 1. 1 1 0 1余數(shù) 0, 商上1原碼加減交替除法（不恢復(fù)余數(shù)法）算法推導(dǎo)：1. 若第 i 次求商，余數(shù)為 R i ， 若R i 0，則商上1，跳至2；若Ri 0 ，則商0，恢復(fù)余數(shù)為正且左移得 2(Ri + Y*)， 跳至3； 2.3.第 i + 1次求商，余數(shù)為 Ri+1 = 2Ri Y*第 i + 1次求商，余數(shù)為 Ri+1 = 2(Ri + Y*) Y*= 2Ri + Y*結(jié)論：當(dāng)某步試減操作不夠減時(shí)，并不需要立即恢復(fù)余 數(shù)，只要下一步試減直接做加法即可。 由于不需要恢復(fù)余數(shù)，且加減運(yùn)算交替進(jìn)行，

37、故稱 此算法為“原碼加減交替除法”或“不恢復(fù)余數(shù)除法”。 Copyright 2012 Computer Organization Group. All rights reserved.原碼加減交替除法算法規(guī)則r 參加運(yùn)算的數(shù)均為原碼，兩數(shù)符號(hào)位不參加運(yùn)算，取其絕 對(duì)值做無符號(hào)數(shù)除法； r 商的符號(hào)位單獨(dú)處理，由兩數(shù)符號(hào)“異或”產(chǎn)生； r 除法運(yùn)算前檢測(cè)0：只要X、Y有任意一個(gè)為0，不進(jìn)行實(shí) 際運(yùn)算； 若X*為0，則商為0；若Y*為0，按非法除數(shù)處理； r 運(yùn)算前應(yīng)滿足條件：X*Y*，否則按溢出處理； r 設(shè)商的初值為0（被除數(shù)單倍字長(zhǎng)）或?yàn)楸怀龜?shù)低

38、位部分 （被除數(shù)雙倍字長(zhǎng)）； 部分余數(shù)的初值為被除數(shù)（被除數(shù)單倍字長(zhǎng)）或?yàn)楸怀龜?shù) 高位部分（被除數(shù)雙倍字長(zhǎng)）。 r 部分余數(shù)采用單符號(hào)位，且符號(hào)位初值為0（取X*）； Copyright 2012 Computer Organization Group. All rights reserved.原碼加減交替除法算法規(guī)則 部分余數(shù)運(yùn)算：余數(shù)為正，商上1，余數(shù)和商左移一位，減除數(shù)；試減 X*+-Y*補(bǔ)重復(fù)n步 第n+1步：若余數(shù)為正，商上1，商左移一位，余數(shù)不移位，運(yùn)算結(jié)束； 若余數(shù)為負(fù)，商上0，商左移一位，但當(dāng)結(jié)果需要余數(shù)時(shí)， 需恢復(fù)余數(shù)（余數(shù)不移位直

39、接加除數(shù)）。 R* = R n 2-n 。 Copyright 2012 Computer Organization Group. All rights reserved.余數(shù)為負(fù)，商上0，余數(shù)和商左移一位，加除數(shù)； 原碼加減交替除法舉例X = -0.1011 Y = - 0.1101求： XY=?解：X= 1.1011原Y原= 1.1101X* = 0.1011Y* = 0.1101-Y*補(bǔ) = 1.0011XY原= 0.1101XY= 0.1101R*=0.01112-4 Copyright 2012

40、Computer Organization Group. All rights reserved.被除數(shù)（余數(shù)）商說明 0. 1 0 1 10. 0 0 0 0+ 1. 0 0 1 1+ -Y*補(bǔ) (減除數(shù))1. 1 1 1 0余數(shù) 0, 商上11. 0 0 1 00. 0 0 0 1左移一位 + 1. 0 0 1 1+ -Y*補(bǔ) 0. 0 1 0 1余數(shù) 0, 商上10. 1 0 1 00. 0 0 1 1左移一位 + 1. 0 0 1 1+ -Y*補(bǔ) 1. 1 1 0 1余數(shù) 0, 商上10. 1 1 0 1商左移一位 原碼加減交替除法的實(shí)現(xiàn)Co

41、pyright 2012 Computer Organization Group. All rights reserved.p 原碼加減交替除法同樣適用于整數(shù)，但被除數(shù)應(yīng)采用雙倍字長(zhǎng)運(yùn)算，否則當(dāng)單字長(zhǎng)被除數(shù)的絕對(duì)值小于除數(shù)時(shí)，得不到整數(shù)商。 原碼加減交替除法運(yùn)算器原碼加減交替除法控制流程ED開始YAYA 0?NCRYA 0?NYDE結(jié)束Copyright 2012 Computer Organization Group. All rights reserved.1 Qn0 Qn A+B AA+B AA-BACR-1CR0 B0， 0 A0A、Q同時(shí)左

42、移一位 CR-1B0A0 S0 QnA+B A溢出，1V0 Qn A、Q10 Q被除數(shù)原碼A 除數(shù)原碼Bn CRN0?A-B ACR=0?N1 Qn A、Q1補(bǔ)碼加減交替除法（不恢復(fù)余數(shù)法）pp算法基本思想同原碼加減交替除法。 主要區(qū)別：被除數(shù)和除數(shù)都用補(bǔ)碼參加運(yùn)算，直接補(bǔ)碼相除； 求出反碼商，再修正為近似的補(bǔ)碼商； 余數(shù)也是補(bǔ)碼形式，商符通過運(yùn)算自動(dòng)產(chǎn)生。 p需要解決的問題：商值的確定； 求商符； 獲得新余數(shù)； 商的校正。 Copyright 2012 Computer Organization Group. All rights reserved

43、.補(bǔ)碼加減交替除法算法分析(1)商和新余數(shù)的確定上商的過程實(shí)際上是比較被除數(shù)（余數(shù)）和除數(shù)所對(duì) 應(yīng)絕對(duì)值大小的過程。 若X與Y同號(hào)：做減法，即 R0補(bǔ) =X補(bǔ) +-Y補(bǔ) 夠減： R0 與Y 同號(hào)，商上1，左移一位，減除數(shù)； 即 R1補(bǔ) =2R0補(bǔ) +-Y補(bǔ) 不夠減：R0 與Y 異號(hào)，商上0，左移一位，加除數(shù)。即 R1補(bǔ) =2R0補(bǔ) +Y補(bǔ) Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼加減交替除法算法分析p 若X與Y異號(hào)：做加法，即 R0補(bǔ) =X補(bǔ) +Y補(bǔ) 夠減：

44、R0 與Y異號(hào)，商上0，左移一位，加除數(shù)；即 R1補(bǔ) = 2R0補(bǔ) +Y補(bǔ) 不夠減：R0 與Y同號(hào)，商上1，左移一位，減除數(shù)。即 R1補(bǔ) = 2R0補(bǔ) +-Y補(bǔ) p分析得出的結(jié)論：Ri 與Y同號(hào)，商上1， Ri+1補(bǔ) = 2Ri補(bǔ) +-Y補(bǔ)Ri 與Y異號(hào)，商上0， Ri+1補(bǔ) = 2Ri補(bǔ) +Y補(bǔ) 注：不能再用Ri0 （夠減）作為上商的依據(jù)； 改用判斷Ri 與Y同/異號(hào)來決定上商和下一步加/減。pCopyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼加減交替除法算法分析(2

45、) 求商符由于運(yùn)算前，滿足 0 XY所以第一次試減后的上商結(jié)果為： X與Y同號(hào)時(shí)：若不夠減，R0 與Y異號(hào)，商上0 ；X與Y異號(hào)時(shí)：若不夠減，R0 與Y同號(hào)，商上1 。故商符由第一次試減后自動(dòng)形成，且與商的數(shù)值位上商規(guī)律相同。 Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼加減交替除法算法分析(3) 商的校正從前面的分析知：當(dāng)商為負(fù)時(shí)，算法以反碼形式上商， 而按補(bǔ)碼運(yùn)算要求，應(yīng)得商的補(bǔ)碼，兩者之間相差2-n。 為了最終得到補(bǔ)碼商，通常采用商末位“恒置1”的舍入方法進(jìn)

46、行處理。采用這種方法產(chǎn)生的誤差為： 2-n。 此方法簡(jiǎn)單、便于實(shí)現(xiàn)，運(yùn)算后不需對(duì)商專門校正。 Copyright 2012 Computer Organization Group. All rights reserved.補(bǔ)碼加減交替除法算法規(guī)則r 操作數(shù)均為補(bǔ)碼表示，兩數(shù)的符號(hào)位參加運(yùn)算； 商符由運(yùn)算自動(dòng)產(chǎn)生； r 除法運(yùn)算前先檢測(cè)0： 只要X、Y有任意一個(gè)為0，不進(jìn)行實(shí)際運(yùn)算； 若X為0，則商為0； 若Y為0，按非法除數(shù)處理； r 運(yùn)算前應(yīng)滿足條件：X*Y*，否則按溢出處理； r 設(shè)商的初值為0（被除數(shù)單倍字長(zhǎng)）或?yàn)楸怀龜?shù)低位部分（被除數(shù)雙倍字長(zhǎng)）； 部分余數(shù)的初值為被除數(shù)（被除數(shù)單倍字長(zhǎng)）或?yàn)?被除數(shù)的高位部分（被除數(shù)雙倍字長(zhǎng)）； r 為防止運(yùn)算過程中產(chǎn)生暫時(shí)性的溢出，部分余數(shù)可采用單符號(hào)位或