原碼補(bǔ)碼乘除法

1、原碼一位乘運(yùn)算原碼一位乘運(yùn)算以定點(diǎn)小數(shù)為例以定點(diǎn)小數(shù)為例 0. 1 1 0 1 0. 1 0 1 1 0. 0 0 0 0 1 1 0 1 0. 0 0 0 1 1 0 1 0. 0 0 0 0 0 0 +0. 0 1 1 0 1 0 . 1 0 0 0 1 1 1 1 返回返回例如：例如： X = 0.1101 Y = - 0.1011筆算乘法過(guò)程筆算乘法過(guò)程 機(jī)器實(shí)現(xiàn)問題：機(jī)器實(shí)現(xiàn)問題：1. 加法器只有兩個(gè)數(shù)據(jù)輸入端；加法器只有兩個(gè)數(shù)據(jù)輸入端；2. 加法器與運(yùn)算數(shù)據(jù)位數(shù)相同。加法器與運(yùn)算數(shù)據(jù)位數(shù)相同。解決方案：解決方案：1. 改改n輸入數(shù)相加過(guò)程為兩兩輸入數(shù)相加過(guò)程為兩兩相加；相加；2.

2、改改2n位相加過(guò)程為位相加過(guò)程為n位相加。位相加。 X Y = - 0.10001111原碼一位乘運(yùn)算原碼一位乘運(yùn)算返回返回基本公式：基本公式： 設(shè)設(shè) 被乘數(shù)被乘數(shù) X原原 = xf . x1 x2 x n 乘乘 數(shù)數(shù) Y原原 = yf . y1 y2 y n 則則 X Y原原 =( xf yf ). ( X* Y* ) 其中，其中， X X* * 和和Y Y* *分別是分別是X X和和Y Y的絕對(duì)值的絕對(duì)值例如：例如： X = 0.1101 Y = - 0.1011 X原原= 0.1101 Y原原 = 1.1011 X* = 0.1101 Y* = 0.1011 0. 1 1 0 1 . 累

3、加器初值取零值累加器初值取零值 0. 1 0 1 1 + . 1 1 0 1 . 初值加被乘數(shù)初值加被乘數(shù) 1 1 0 1 . 部分積右移，部分積右移， 0 0 0 0 將移出的一位保存起來(lái)將移出的一位保存起來(lái) + 1 1 0 1 求第一次部分積求第一次部分積 0 . 1 0 0 0 1 1 1 1 手工運(yùn)算過(guò)程手工運(yùn)算過(guò)程 原碼一位乘運(yùn)算原碼一位乘運(yùn)算原碼一位乘運(yùn)算原碼一位乘運(yùn)算 X* = 0.1101 Y* = 0.1011 0. 1 1 0 1 . 1 0. 1 0 1 1 + . 1 1 0 1 . 前次部分積加被乘數(shù)前次部分積加被乘數(shù) 1 1 0 1 . 部分積右移部分積右移 0 0

4、 0 0將移出的一位保存起來(lái)將移出的一位保存起來(lái) + 1 1 0 1 求第二次部分積求第二次部分積 0 . 1 0 0 0 1 1 1 1 手工運(yùn)算過(guò)程手工運(yùn)算過(guò)程 返回返回原碼一位乘運(yùn)算原碼一位乘運(yùn)算 X* = 0.1101 Y* = 0.1011 0. 1 1 0 1 . 1 1 0. 1 0 1 1 + . 1 1 0 1 . 前次部分積加前次部分積加 1 1 0 1 .部分積右移部分積右移 0 0 0 0將移出的一位保存起來(lái)將移出的一位保存起來(lái) + 1 1 0 1 求第三次部分積求第三次部分積 0 . 1 0 0 0 1 1 1 1 手工運(yùn)算過(guò)程手工運(yùn)算過(guò)程 返回返回原碼一位乘運(yùn)算原碼

5、一位乘運(yùn)算 X* = 0.1101 Y* = 0.1011 0. 1 1 0 1 . * 0. 1 0 1 1 + . 1 1 0 1 .前次部分積加被乘數(shù)前次部分積加被乘數(shù) 1 1 0 1 .部分積右移部分積右移 0 0 0 0將移出的一位保存起來(lái)將移出的一位保存起來(lái) + 1 1 0 1 求第四次部分積求第四次部分積 0 . 1 0 0 0 1 1 1 1 手工運(yùn)算過(guò)程手工運(yùn)算過(guò)程 再用一步完成兩數(shù)符號(hào)異或求再用一步完成兩數(shù)符號(hào)異或求積的符號(hào)積的符號(hào), 結(jié)果為結(jié)果為 -0.10001111返回返回原碼一位乘運(yùn)算規(guī)則原碼一位乘運(yùn)算規(guī)則原碼一位乘運(yùn)算規(guī)則：原碼一位乘運(yùn)算規(guī)則： 1. 1. 乘積的

6、符號(hào)位由兩數(shù)符號(hào)位乘積的符號(hào)位由兩數(shù)符號(hào)位“異或異或”產(chǎn)生，符產(chǎn)生，符號(hào)號(hào)位不參與運(yùn)算；位不參與運(yùn)算； 2. 2. 部分積可采用一位或兩位符號(hào)位；部分積可采用一位或兩位符號(hào)位； 3. 3. 乘積的數(shù)值部分由兩數(shù)絕對(duì)值相乘產(chǎn)生，通過(guò)乘積的數(shù)值部分由兩數(shù)絕對(duì)值相乘產(chǎn)生，通過(guò)n n次次“加法加法”和和“右移右移”操作實(shí)現(xiàn)。操作實(shí)現(xiàn)。(n(n為乘數(shù)整數(shù)部分為乘數(shù)整數(shù)部分位數(shù)位數(shù)) )返回返回原碼一位乘運(yùn)算實(shí)例原碼一位乘運(yùn)算實(shí)例 部分積部分積 乘數(shù)乘數(shù) 0. 0 0 0 0 0.1 0 1 1+ 0. 1 1 0 1 0. 1 1 0 1 0. 0 1 1 0 1 0 1 0 1+ 0. 1 1 0 1

7、 1. 0 0 1 1 0. 1 0 0 1 1 1 0 1 0 0. 0 1 0 0 1 1 1 0 1+ 0. 1 1 0 1 1. 0 0 0 1 0. 1 0 0 0 1 1 1 1 0返回返回 0. 1 1 0 1 0. 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 + 1 1 0 10 . 1 0 0 0 1 1 1 1例如：例如： X = 0.1101 Y = - 0.1011 手工運(yùn)算過(guò)程手工運(yùn)算過(guò)程計(jì)算機(jī)內(nèi)運(yùn)算的實(shí)現(xiàn)方法計(jì)算機(jī)內(nèi)運(yùn)算的實(shí)現(xiàn)方法則則 X* = 0.1101 Y* = 0.1011 X原原 = 0.1101 Y原原 = 1.1011 X Y原原

8、= 1.10001111補(bǔ)碼乘法補(bǔ)碼乘法運(yùn)算運(yùn)算 原碼乘法不難實(shí)現(xiàn)，但有原碼乘法不難實(shí)現(xiàn)，但有兩個(gè)問題兩個(gè)問題: 1. 符號(hào)位與數(shù)值位分別處理，不方便；符號(hào)位與數(shù)值位分別處理，不方便； 2. 若數(shù)據(jù)為補(bǔ)碼形式，可能需要多于兩次若數(shù)據(jù)為補(bǔ)碼形式，可能需要多于兩次 補(bǔ)補(bǔ)原碼變換。原碼變換。 也可以直接用補(bǔ)碼完成乘法運(yùn)算，即從補(bǔ)也可以直接用補(bǔ)碼完成乘法運(yùn)算，即從補(bǔ)碼開始，直接得到補(bǔ)碼的積。碼開始，直接得到補(bǔ)碼的積。 下面看一看補(bǔ)碼乘運(yùn)算的實(shí)現(xiàn)算法。下面看一看補(bǔ)碼乘運(yùn)算的實(shí)現(xiàn)算法。返回返回= (Yi+1 - Yi ) 2-i設(shè)設(shè) 被乘數(shù)被乘數(shù) X補(bǔ)補(bǔ) = x0. x1 x2 x n 乘乘 數(shù)數(shù) Y補(bǔ)補(bǔ)

9、 = y0. y1 y2 y n 先復(fù)習(xí)兩個(gè)概念先復(fù)習(xí)兩個(gè)概念: 已知已知 X補(bǔ)補(bǔ) = x0. x1x2 x n 時(shí)時(shí) X/2補(bǔ)補(bǔ) = x0. x0 x1 x2 xn-1 已知已知 Y補(bǔ)補(bǔ) = y0. y1 y2 yn 時(shí)時(shí) Y = - y0 yi 2-i i=1nni=0補(bǔ)碼一位乘法的實(shí)現(xiàn)補(bǔ)碼一位乘法的實(shí)現(xiàn)算法推導(dǎo)算法推導(dǎo)(比較比較法法)返回返回X Y = X - y0 yi 2-i 補(bǔ)碼一位乘法運(yùn)算補(bǔ)碼一位乘法運(yùn)算算法推導(dǎo)算法推導(dǎo)(比較法比較法)X Y補(bǔ)補(bǔ)補(bǔ)補(bǔ) 補(bǔ)補(bǔ) ?返回返回 = X (0 .y1 y2 yn) - X y0X Y補(bǔ)補(bǔ) = X (0 .y1 y2 yn) - X y0 補(bǔ)

10、補(bǔ) = X (0 .y1 y2 yn) 補(bǔ)補(bǔ)- X y0 補(bǔ)補(bǔ) = X 補(bǔ)補(bǔ) (0 .y1 y2 yn) - y0 X補(bǔ)補(bǔ) = X 補(bǔ)補(bǔ) Yni=0 證明證明 X (0 .y1 y2 yn) 補(bǔ)補(bǔ) = X 補(bǔ)補(bǔ) (0 .y1 y2 yn)(1) 當(dāng)當(dāng)X 0 時(shí)，時(shí)， X (0 .y1 y2 yn) 補(bǔ)補(bǔ) = X (0 .y1 y2 yn) = X 補(bǔ)補(bǔ) (0 .y1 y2 yn) (2) 當(dāng)當(dāng)X 0 時(shí)，時(shí)， X (0 .y1 y2 yn) 補(bǔ)補(bǔ) = 2+ X (0 .y1 y2 yn) (mod 2) = 2n+1+ X (0 .y1 y2 yn) (mod 2) = 2n+1 (0 .y1

11、 y2 yn) + X (0 .y1 y2 yn) (mod 2) = (2n+1+ X) (0 .y1 y2 yn) (mod 2) = (2+ X) (0 .y1 y2 yn) (mod 2) = X 補(bǔ)補(bǔ) (0 .y1 y2 yn) (mod 2)= -y0*20 + (y1*20-y1*2-1) + (y2*2-1 -y2*2-2) + +補(bǔ)碼一位乘法運(yùn)算補(bǔ)碼一位乘法運(yùn)算算法推導(dǎo)算法推導(dǎo)(比較法比較法)= (yi+1 - yi ) * 2-iX Y補(bǔ)補(bǔ)補(bǔ)補(bǔ) 返回返回Y補(bǔ)補(bǔ) Y=（y0 y i * 2-i )i=1n分分解為單項(xiàng)形式解為單項(xiàng)形式= -y0*20 + y1*2-1 + y2

12、*2-2 + + y n*2-n變每位上的變每位上的 1為為高高 1位上的位上的 1個(gè)個(gè)+1加本位上的加本位上的 1個(gè)個(gè)-1= (y1-y0)*20 + (y2-y1)*2-1 + + (yn+1-yn)*2-n最低最低1位后再補(bǔ)位后再補(bǔ)1位位合并同次冪的項(xiàng)合并同次冪的項(xiàng) 寫成為求累加和形式寫成為求累加和形式i=0n令令 yn+1 = 0補(bǔ)碼一位補(bǔ)碼一位乘法運(yùn)算的乘法運(yùn)算的實(shí)現(xiàn)實(shí)現(xiàn)(比較法比較法)補(bǔ)碼一位乘公式：補(bǔ)碼一位乘公式： Z 補(bǔ)補(bǔ)= X Y補(bǔ)補(bǔ) = 補(bǔ)補(bǔ)（- y0 yi 2-i ）返回返回= 補(bǔ)補(bǔ) (yi+1 - yi ) 2-ii=0ni=0n部分積遞推公式：部分積遞推公式： Z0補(bǔ)

13、補(bǔ)= 0 Z1補(bǔ)補(bǔ)= 2-1 Z0補(bǔ)補(bǔ)+ (yn+1 - yn) 補(bǔ)補(bǔ) (令令 yn+1 = 0) Zi補(bǔ)補(bǔ)= 2-1 Zi-1補(bǔ)補(bǔ)+ (yn-i+2 - yn-i+1) 補(bǔ)補(bǔ) Zn補(bǔ)補(bǔ)= 2-1 Zn-1補(bǔ)補(bǔ)+ (y2 - y1) 補(bǔ)補(bǔ) Zn+1補(bǔ)補(bǔ)= Zn補(bǔ)補(bǔ)+ (y1 - y0) 補(bǔ)補(bǔ) = X Y補(bǔ)補(bǔ) 補(bǔ)碼一位補(bǔ)碼一位乘法運(yùn)算的乘法運(yùn)算的算法規(guī)則算法規(guī)則(比較法比較法)yn yn+1= 00 時(shí)，時(shí)， Zi補(bǔ)補(bǔ)= Zi-1補(bǔ)補(bǔ)+ 0， 右移右移1位位;yn yn+1= 01 時(shí)，時(shí)， Zi補(bǔ)補(bǔ)= Zi-1補(bǔ)補(bǔ)+ X補(bǔ)，補(bǔ)， 右移右移1位位；yn yn+1= 10 時(shí)，時(shí)， Zi補(bǔ)補(bǔ)= Z

14、i-1補(bǔ)補(bǔ)+ -X補(bǔ)，補(bǔ)，右移右移1位位；yn yn+1= 11 時(shí)，時(shí)， Zi補(bǔ)補(bǔ)= Zi-1補(bǔ)補(bǔ)+ 0， 右移右移1位；位；補(bǔ)碼一位乘算法規(guī)則：補(bǔ)碼一位乘算法規(guī)則：1.1. X X、Y Y的符號(hào)位都參加運(yùn)算，部分積采用雙符號(hào)位；的符號(hào)位都參加運(yùn)算，部分積采用雙符號(hào)位；2. 2. 乘數(shù)最低位之后增加一位附加位乘數(shù)最低位之后增加一位附加位yn+1 ，且令且令yn+1=0；3. 3. 每位部分積運(yùn)算規(guī)則如下：每位部分積運(yùn)算規(guī)則如下：4. 4. 重復(fù)重復(fù)n+1n+1次比較和運(yùn)算，但只進(jìn)行次比較和運(yùn)算，但只進(jìn)行n n次右移，次右移，最后一最后一 次不移位。次不移位。 積符由運(yùn)算過(guò)程自動(dòng)產(chǎn)生。積符由運(yùn)

15、算過(guò)程自動(dòng)產(chǎn)生。補(bǔ)碼一位乘法運(yùn)算實(shí)例補(bǔ)碼一位乘法運(yùn)算實(shí)例已知已知: X補(bǔ)補(bǔ) = 0.1101 Y補(bǔ)補(bǔ) = 0.1011 部分積部分積 乘數(shù)乘數(shù) yn yn+1 0 0. 0 0 0 0 0.1 0 1 1 0+1 1. 0 0 1 1 1 1. 0 0 1 1 1 1. 1 0 0 1 1 0 1 0 1 1 1 1. 1 1 0 0 1 1 0 1 0 1+0 0. 1 1 0 1 0 0. 1 0 0 1 0 0. 0 1 0 0 1 1 1 0 1 0+1 1. 0 0 1 1 1 1. 0 1 1 1 1 1. 1 0 1 1 1 1 1 1 0 1+0 0. 1 1 0 1 0 0.

16、 1 0 0 0 1 1 1 1 0 清清0則則 -X補(bǔ)補(bǔ) = 1.0011 X Y補(bǔ)補(bǔ) = 0.10001111 補(bǔ)碼補(bǔ)碼一位乘一位乘硬件配置硬件配置及及實(shí)例演示實(shí)例演示（比較法（比較法） 補(bǔ)碼一位乘綜合演示.swf設(shè)設(shè) 被乘數(shù)被乘數(shù) X補(bǔ)補(bǔ) = x0 .x1 x2 x n 乘乘 數(shù)數(shù) Y補(bǔ)補(bǔ) = y0 .y1 y2 y n補(bǔ)碼兩位乘法的實(shí)現(xiàn)補(bǔ)碼兩位乘法的實(shí)現(xiàn)算法推導(dǎo)算法推導(dǎo)(比較法比較法)返回返回由一位乘算法得：由一位乘算法得：Zi+2補(bǔ)補(bǔ)= 2-12-1 Zi補(bǔ)補(bǔ)+ (yn-i+1 - yn-i) 補(bǔ)補(bǔ)+ (yn-i - yn-i-1) 補(bǔ)補(bǔ) = 2-2 Zi補(bǔ)補(bǔ)+ (yn-i+1 +

17、yn-i - 2 yn-i-1) 補(bǔ)補(bǔ)結(jié)論：結(jié)論： 補(bǔ)碼兩位乘比較法的部分積運(yùn)算由乘數(shù)相鄰的補(bǔ)碼兩位乘比較法的部分積運(yùn)算由乘數(shù)相鄰的三位比較決定，運(yùn)算后每次右移兩位。三位比較決定，運(yùn)算后每次右移兩位。Zi+1補(bǔ)補(bǔ)= 2-1 Zi補(bǔ)補(bǔ)+ (yn-i+1 - yn-i) 補(bǔ)補(bǔ)補(bǔ)碼兩位補(bǔ)碼兩位乘法運(yùn)算的乘法運(yùn)算的算法規(guī)則算法規(guī)則(比較法比較法)yn-1 yn yn+1= 000 時(shí)，時(shí)， Zi+2補(bǔ)補(bǔ)= Zi補(bǔ)補(bǔ)+ 0， 右移右移2位位;yn-1 yn yn+1= 001 時(shí)，時(shí)， Zi +2補(bǔ)補(bǔ)= Zi補(bǔ)補(bǔ)+ X補(bǔ)補(bǔ)， 右移右移2位位;yn-1 yn yn+1= 010 時(shí)，時(shí)， Zi +2補(bǔ)補(bǔ)=

18、 Zi補(bǔ)補(bǔ)+ X補(bǔ)補(bǔ)， 右移右移2位位;yn-1 yn yn+1= 011 時(shí)，時(shí)， Zi +2補(bǔ)補(bǔ)= Zi補(bǔ)補(bǔ)+ 2X補(bǔ)補(bǔ)， 右移右移2位位;yn-1 yn yn+1= 100 時(shí)，時(shí)， Zi +2補(bǔ)補(bǔ)= Zi補(bǔ)補(bǔ)+ 2-X補(bǔ)補(bǔ)，右移，右移2位位;yn-1 yn yn+1= 101 時(shí)，時(shí)， Zi +2補(bǔ)補(bǔ)= Zi補(bǔ)補(bǔ)+ -X補(bǔ)補(bǔ)， 右移右移2位位;yn-1 yn yn+1= 110 時(shí)，時(shí)， Zi +2補(bǔ)補(bǔ)= Zi補(bǔ)補(bǔ)+ -X補(bǔ)補(bǔ)， 右移右移2位位;yn-1 yn yn+1= 111 時(shí)，時(shí)， Zi +2補(bǔ)補(bǔ)= Zi補(bǔ)補(bǔ)+ 0， 右移右移2位位;1.1. X X、Y Y的符號(hào)位都參加運(yùn)算，

19、部分積采用的符號(hào)位都參加運(yùn)算，部分積采用三位符號(hào)位三位符號(hào)位；2.2. 乘數(shù)最低位之后增加一位附加位乘數(shù)最低位之后增加一位附加位yn+1 ，且令且令yn+1=0；3.3. 每位部分積運(yùn)算規(guī)則如下：每位部分積運(yùn)算規(guī)則如下：補(bǔ)碼兩位補(bǔ)碼兩位乘法運(yùn)算的乘法運(yùn)算的算法規(guī)則算法規(guī)則(續(xù)續(xù))(比較法比較法)4. 4. 設(shè)乘數(shù)數(shù)值部分為設(shè)乘數(shù)數(shù)值部分為n n位，位， 當(dāng)當(dāng)n n為奇數(shù)時(shí)為奇數(shù)時(shí)，乘數(shù)設(shè)，乘數(shù)設(shè)1 1位符號(hào)位位符號(hào)位，做，做(n+1)/2(n+1)/2次次運(yùn)算和移位，最后一步運(yùn)算和移位，最后一步右移右移1 1位位； 當(dāng)當(dāng)n n為偶數(shù)時(shí)為偶數(shù)時(shí)，乘數(shù)設(shè)，乘數(shù)設(shè)2 2位符號(hào)位位符號(hào)位，做，做n/2

20、+1n/2+1次次運(yùn)算和移位，最后一步運(yùn)算和移位，最后一步不右移不右移； 積符由運(yùn)算過(guò)程自動(dòng)產(chǎn)生。積符由運(yùn)算過(guò)程自動(dòng)產(chǎn)生。補(bǔ)碼兩位補(bǔ)碼兩位乘法運(yùn)算乘法運(yùn)算實(shí)例實(shí)例已知已知: X補(bǔ)補(bǔ) = 0.1101 Y補(bǔ)補(bǔ) = 0.1011 部分積部分積 乘數(shù)乘數(shù) yn yn+1 0 0. 0 0 0 0 0 1 0 1 1 0+1 1. 0 0 1 1 1 1. 0 0 1 1 1 1. 1 0 0 1 1 0 1 0 1 1 1 1. 1 1 0 0 1 1 0 1 0 1+0 0. 1 1 0 1 0 0. 1 0 0 1 0 0. 0 1 0 0 1 1 1 0 1 0+1 1. 0 0 1 1 1

21、1. 0 1 1 1 1 1. 1 0 1 1 1 1 1 1 0 1+0 0. 1 1 0 1 0 0. 1 0 0 0 1 1 1 1 0 清清0111 部分積部分積 乘乘 數(shù)數(shù) yn yn+1 0 0 0. 0 0 0 0 0 0.1 0 1 1 0+1 1 1. 0 0 1 1 1 1 1. 0 0 1 1 1 1 1. 1 1 0 0 1 1 0 0 1 0 1+1 1 1. 0 0 1 1 1 1 0. 1 1 1 1 1 1 1. 1 0 1 1 1 1 1 1 0 0 1+0 0 0. 1 1 0 1 0 0 0. 1 0 0 0 1 1 1 1 0 0 清清0212則則 -X

22、補(bǔ)補(bǔ) = 1.0011 X Y補(bǔ)補(bǔ) = 0.10001111原原 碼碼 除除 法法以定點(diǎn)小數(shù)為例以定點(diǎn)小數(shù)為例 基本公式：基本公式： 設(shè)設(shè) 被除數(shù)被除數(shù) X原原 = xf . x1 x2 x n 除除 數(shù)數(shù) Y原原 = yf . y1 y2 y n 則則: : 若若 0 X Y X Y原原 =( xf yf ). ( X* Y* ) 其中，其中， X* 和和Y*分別是分別是X和和Y的絕對(duì)值的絕對(duì)值例如：例如： X = 0.1011 Y = - 0.1101 筆算除法過(guò)程筆算除法過(guò)程 0.1101 0.1101 0.10110 -0.01101 0.010010 -0.001101 0.0001

23、0100 -0.00001101 0.00000111原碼除運(yùn)算原碼除運(yùn)算方法分析方法分析以定點(diǎn)小數(shù)為例以定點(diǎn)小數(shù)為例返回返回機(jī)器實(shí)現(xiàn)問題：機(jī)器實(shí)現(xiàn)問題： 1. 需單獨(dú)設(shè)計(jì)比較器線路；需單獨(dú)設(shè)計(jì)比較器線路； 2. 需需2n位的減法器線路。位的減法器線路。 解決方案：解決方案： 1. 比較操作改由比較操作改由“試減試減”實(shí)現(xiàn)；實(shí)現(xiàn)； 2. 將除數(shù)右移改為部分余數(shù)左移；將除數(shù)右移改為部分余數(shù)左移； 3. 減法由減法由+-Y補(bǔ)補(bǔ)轉(zhuǎn)化為加法實(shí)現(xiàn)。轉(zhuǎn)化為加法實(shí)現(xiàn)。 被除數(shù)（余數(shù)）被除數(shù)（余數(shù)） 商商 說(shuō)說(shuō) 明明 0 0. 1 0 1 1 0. 0 0 0 0+ 1 1. 0 0 1 1 + -Y *補(bǔ)補(bǔ)

24、 （減除數(shù)（減除數(shù)） 1 1. 1 1 1 0 余數(shù)余數(shù) 0, 商上商上1 0 1. 0 0 1 0 0 0 0 0 1 左移一位左移一位+ 1 1. 0 0 1 1 + -Y *補(bǔ)補(bǔ) 0 0. 0 1 0 1 余數(shù)余數(shù) 0, 商上商上1 0 0. 1 0 1 0 0 0 0 1 1 左移一位左移一位+ 1 1. 0 0 1 1 + -Y *補(bǔ)補(bǔ) 1 1. 1 1 0 1 余數(shù)余數(shù) 0, 商上商上1例如：例如： X = -0.1011 Y = - 0.1101 X原原= 1.1011 Y原原= 1.1101 X* = 0.1011 Y* = 0.1101-Y*補(bǔ)補(bǔ) = 1.0011恢恢 復(fù)復(fù)

25、余數(shù)余數(shù) 除除 法法X/Y原原=0.1101R原原=0.01112 2-4-4原碼加減交替除法原碼加減交替除法原理證明原理證明1. 若第若第 i - 1次求商，余數(shù)為次求商，余數(shù)為 R i-1 0 ， 本次商上本次商上1，且余數(shù)左移，且余數(shù)左移 1 位得位得 2R i-1 ；2. 第第 i 次求商，余數(shù)為次求商，余數(shù)為 R i =2R i-1 Y*, 若若R i 0, ,則則商商上上1，跳至跳至3 3； 若若R i 0, 則商則商0，恢復(fù)余數(shù)為正且左移得，恢復(fù)余數(shù)為正且左移得 2(R i + Y*)，跳至跳至4；3. 第第 i + 1次求商，余數(shù)為次求商，余數(shù)為 R i+1 = 2 R i Y

26、* 4. 第第 i + 1次求商，余數(shù)為次求商，余數(shù)為 R i+1 = 2( R i + Y* ) Y* = 2R i + Y* 實(shí)質(zhì)實(shí)質(zhì): : 對(duì)上次的負(fù)余數(shù)值直接左移一位對(duì)上次的負(fù)余數(shù)值直接左移一位, , 本次用本次用+Y*求商即可。求商即可。返回返回原碼加減交替除法原碼加減交替除法算法規(guī)則算法規(guī)則1.1.除法運(yùn)算前，應(yīng)滿足條件：除法運(yùn)算前，應(yīng)滿足條件：X X* *YY* *, ,且且Y Y* *00, ,否否則，按溢出或非法除數(shù)處理；則，按溢出或非法除數(shù)處理；2.2.符號(hào)位不參與運(yùn)算符號(hào)位不參與運(yùn)算，單獨(dú)處理：，單獨(dú)處理：q qf f= x= xf f y yf f ; ;3.3.部分余

27、數(shù)采用部分余數(shù)采用單符號(hào)位或雙符號(hào)位單符號(hào)位或雙符號(hào)位；4.4.每步部分余數(shù)運(yùn)算規(guī)則：每步部分余數(shù)運(yùn)算規(guī)則： 試減試減X* +- +-Y * 補(bǔ)補(bǔ)余數(shù)為正，商上余數(shù)為正，商上1 1，余數(shù)和商左移一位余數(shù)和商左移一位，減除數(shù)；，減除數(shù)；余數(shù)為負(fù)，商上余數(shù)為負(fù)，商上0 0，余數(shù)和商左移一位余數(shù)和商左移一位，加除數(shù)；，加除數(shù)；5.5.第第n+1n+1步步：若余數(shù)為正，商上：若余數(shù)為正，商上1 1，商左移一位商左移一位； 若余數(shù)為負(fù)，商上若余數(shù)為負(fù)，商上0 0，商左移一位商左移一位，但當(dāng)結(jié)果需，但當(dāng)結(jié)果需 要余數(shù)時(shí)，需恢復(fù)余數(shù)，要余數(shù)時(shí)，需恢復(fù)余數(shù)，R = = R n 2 2-n-n 。重復(fù)重復(fù)n n

28、步步 被除數(shù)（余數(shù)）被除數(shù)（余數(shù)） 商商 說(shuō)說(shuō) 明明 0 0. 1 0 1 1 0. 0 0 0 0+ 1 1. 0 0 1 1 + -Y *補(bǔ)補(bǔ) (減除數(shù)減除數(shù)) 1 1. 1 0 1 1 余數(shù)余數(shù) 0, 商上商上1 0 1. 0 0 1 0 0 0 0 0 1 左移一位左移一位+ 1 1. 0 0 1 1 + -Y *補(bǔ)補(bǔ) 0 0. 0 1 0 1 余數(shù)余數(shù) 0, 商上商上1 0 0. 1 0 1 0 0 0 0 1 1 左移一位左移一位+ 1 1. 0 0 1 1 + -Y *補(bǔ)補(bǔ) 1 1. 1 1 0 1 余數(shù)余數(shù) 0, 商上商上1 0 1 1 0 1 商商左移一位左移一位例如：例如：

29、 X = -0.1011 Y = - 0.1101 X原原= 1.1011 Y原原= 1.1101 X* = 0.1011 Y* = 0.1101-Y*補(bǔ)補(bǔ) = 1.0011加減交替加減交替 除除 法法X/Y原原= 0.1101R = 0.0111 2 2-4-4原碼加減交替除法原碼加減交替除法運(yùn)算過(guò)程演示運(yùn)算過(guò)程演示 原碼加減交替除法控制流程及實(shí)例.swf原碼加減交替除法運(yùn)算的原碼加減交替除法運(yùn)算的基本硬件配置基本硬件配置0 A n加法器加法器(n+1位位)控控 制制 門門GD0 Q n計(jì)數(shù)器計(jì)數(shù)器CV1 f0 X n移位和加移位和加/減減控制邏輯控制邏輯Y*或或 -Y *補(bǔ)補(bǔ) +1 補(bǔ)碼除

30、法運(yùn)算補(bǔ)碼除法運(yùn)算算法思想：算法思想： 被除數(shù)與除數(shù)為補(bǔ)碼表示，被除數(shù)與除數(shù)為補(bǔ)碼表示， 直接用補(bǔ)碼除，直接用補(bǔ)碼除，求出反碼商求出反碼商， 再修正為近似的補(bǔ)碼商。再修正為近似的補(bǔ)碼商。返回返回主要解決：主要解決： 上值的確定；上值的確定； 求商符；求商符； 獲得新余數(shù)；獲得新余數(shù)； 商的校正。商的校正。 補(bǔ)碼除法算法分析補(bǔ)碼除法算法分析 (1) (1) 商和新余數(shù)的確定商和新余數(shù)的確定 上商的過(guò)程實(shí)際上時(shí)比較被除數(shù)（余數(shù)）和除數(shù)所上商的過(guò)程實(shí)際上時(shí)比較被除數(shù)（余數(shù)）和除數(shù)所對(duì)應(yīng)絕對(duì)值大小的過(guò)程。對(duì)應(yīng)絕對(duì)值大小的過(guò)程。 若若X X與與Y Y同號(hào)：做減法，即同號(hào)：做減法，即 R0補(bǔ)補(bǔ) =X補(bǔ)補(bǔ)

31、+-Y補(bǔ)補(bǔ) 夠減：夠減：R0 與與Y 同號(hào)，商上同號(hào)，商上1，左移一位，減除數(shù)。，左移一位，減除數(shù)。 即即 R1補(bǔ)補(bǔ) =2R0補(bǔ)補(bǔ) +-Y補(bǔ)補(bǔ) 。 不夠減：不夠減：R0 與與Y 異號(hào)，商上異號(hào)，商上0，左移一位，加除數(shù)。，左移一位，加除數(shù)。 即即 R1補(bǔ)補(bǔ) =2R0補(bǔ)補(bǔ) +Y補(bǔ)補(bǔ) 。 補(bǔ)碼除法算法分析（續(xù)補(bǔ)碼除法算法分析（續(xù)1） 若若X X與與Y Y異號(hào)：做加法，即異號(hào)：做加法，即 R0補(bǔ)補(bǔ) =X補(bǔ)補(bǔ) +Y補(bǔ)補(bǔ) 夠減：夠減：R0 與與Y異號(hào)，商上異號(hào)，商上0，左移一位，加除數(shù)。，左移一位，加除數(shù)。 即即 R1補(bǔ)補(bǔ) = 2R0補(bǔ)補(bǔ) +Y補(bǔ)補(bǔ) 。 不夠減：不夠減：R0 與與Y同號(hào)，商上同號(hào)，商上1

32、，左移一位，減除數(shù)。，左移一位，減除數(shù)。 即即 R1補(bǔ)補(bǔ) = 2R0補(bǔ)補(bǔ) +-Y補(bǔ)補(bǔ) 。 同樣的分析方法，可以得出如下結(jié)論：同樣的分析方法，可以得出如下結(jié)論： Ri 與與Y同號(hào)，商上同號(hào)，商上1， Ri+1補(bǔ)補(bǔ) = 2Ri補(bǔ)補(bǔ) +-Y補(bǔ)補(bǔ) ; Ri 與與Y異號(hào)，商上異號(hào)，商上0， Ri+1補(bǔ)補(bǔ) = 2Ri補(bǔ)補(bǔ) +Y補(bǔ)補(bǔ) 。補(bǔ)碼除法算法分析（續(xù)補(bǔ)碼除法算法分析（續(xù)2） (2) (2) 求商符求商符 由于運(yùn)算前，滿足由于運(yùn)算前，滿足 0 0 X Y 所以第一次試減后的上商結(jié)果為：所以第一次試減后的上商結(jié)果為： 若若X X與與Y Y同號(hào)：不夠減，即同號(hào)：不夠減，即R0 與與Y異號(hào)，商上異號(hào)，商上0

33、； 若若X X與與Y Y異號(hào)：不夠減，即異號(hào)：不夠減，即R0 與與Y同號(hào)，商上同號(hào)，商上1 。 因此，商符由第一次因此，商符由第一次試減后自動(dòng)形成，且與商的數(shù)試減后自動(dòng)形成，且與商的數(shù)值位上商規(guī)則相同。值位上商規(guī)則相同。 補(bǔ)碼除法算法分析（續(xù)補(bǔ)碼除法算法分析（續(xù)3） (3) (3) 商的校正商的校正 從前面的分析知：從前面的分析知：當(dāng)商為負(fù)時(shí)，算法以反碼形式當(dāng)商為負(fù)時(shí)，算法以反碼形式上商，而按補(bǔ)碼運(yùn)算要求，應(yīng)得商的補(bǔ)碼，兩者之間上商，而按補(bǔ)碼運(yùn)算要求，應(yīng)得商的補(bǔ)碼，兩者之間相差相差2 2- -n n。為了最終得到補(bǔ)碼商，通常采用。為了最終得到補(bǔ)碼商，通常采用商末位商末位“恒置恒置1”1”的舍入

34、方法的舍入方法進(jìn)行處理。采用這種方法產(chǎn)生進(jìn)行處理。采用這種方法產(chǎn)生的誤差為：的誤差為： 2 2- -n n。這種方法簡(jiǎn)單，便于實(shí)現(xiàn)，。這種方法簡(jiǎn)單，便于實(shí)現(xiàn)，運(yùn)算運(yùn)算后不需要對(duì)商校正后不需要對(duì)商校正。 補(bǔ)碼加減交替除法補(bǔ)碼加減交替除法算法規(guī)則算法規(guī)則1.1.除法運(yùn)算前，應(yīng)滿足條件：除法運(yùn)算前，應(yīng)滿足條件：X X* *YY* *, ,且且Y Y* *00, ,否否則，按溢出或非法除數(shù)處理；則，按溢出或非法除數(shù)處理；2.2.符號(hào)位符號(hào)位參與運(yùn)算參與運(yùn)算，商符由運(yùn)算自動(dòng)產(chǎn)生，商符由運(yùn)算自動(dòng)產(chǎn)生; ;3.3.部分余數(shù)采用部分余數(shù)采用單符號(hào)位或雙符號(hào)位單符號(hào)位或雙符號(hào)位；4.4.每步部分余數(shù)運(yùn)算規(guī)則：每

35、步部分余數(shù)運(yùn)算規(guī)則： 試減：試減：X X、Y Y同號(hào)，做減法；同號(hào)，做減法；X X、Y Y同號(hào)，做加法；同號(hào)，做加法；5.5.第第n+1n+1步步：商恒置商恒置1 1，商左移一位。，商左移一位。 重復(fù)重復(fù)n n步步上商：上商：余數(shù)與余數(shù)與Y Y同號(hào)，商上同號(hào)，商上1 1，余數(shù)和商左移一位，做減法；，余數(shù)和商左移一位，做減法；余數(shù)與余數(shù)與Y Y異號(hào)，商上異號(hào)，商上0 0，余數(shù)和商左移一位，做加法；，余數(shù)和商左移一位，做加法；若要求求余數(shù)若要求求余數(shù)：若余數(shù)與若余數(shù)與Y Y同號(hào)，除法結(jié)束。同號(hào)，除法結(jié)束。若余數(shù)與若余數(shù)與Y Y異號(hào)，應(yīng)恢復(fù)余數(shù)，方法同上。異號(hào)，應(yīng)恢復(fù)余數(shù)，方法同上。R = = R

36、n 2 2-n-n 被除數(shù)（余數(shù)）被除數(shù)（余數(shù)） 商商 說(shuō)說(shuō) 明明 1 1. 0 1 1 1 0. 0 0 0 0 X與與Y異號(hào)異號(hào)+ 0 0. 1 1 0 1 +Y補(bǔ)補(bǔ) 0 0. 0 1 0 0 余數(shù)與余數(shù)與Y同號(hào)同號(hào), 商上商上1 0 0. 1 0 0 0 0 0 0 0 1 左移一位左移一位+ 1 1. 0 0 1 1 +-Y補(bǔ)補(bǔ) 1 1. 1 0 1 1 余數(shù)與余數(shù)與Y異號(hào)異號(hào), 商上商上0 1 1. 0 1 1 0 0 0 0 1 0 左移一位左移一位+ 0 0. 1 1 0 1 + Y補(bǔ)補(bǔ) 0 0. 0 0 1 1 余數(shù)與余數(shù)與Y同號(hào)同號(hào), 商上商上1 0 0. 1 0 1 0 0

37、 0 1 0 1 左移一位左移一位+ 1 1. 0 0 1 1 + -Y補(bǔ)補(bǔ) 1 1. 1 0 0 1 余數(shù)與余數(shù)與Y異號(hào)異號(hào), 商上商上0 1 1. 0 0 1 0 0 1 0 1 0 左移一位左移一位 1.0 1 0 1 商末位恒置商末位恒置1, 商左移一位商左移一位例如：例如： X = -0.1001 Y = +0.1101 X補(bǔ)補(bǔ) = 1.0111 Y補(bǔ)補(bǔ)= 0.1101 -Y補(bǔ)補(bǔ) = 1.0011補(bǔ)碼加減補(bǔ)碼加減交替除法交替除法X/Y補(bǔ)補(bǔ)= 1.0101R補(bǔ)補(bǔ)= 1.00102 2-4-4補(bǔ)碼加減交替除法補(bǔ)碼加減交替除法運(yùn)算過(guò)程演示運(yùn)算過(guò)程演示 補(bǔ)碼加減交替除法控制流程及實(shí)例.swf

38、三、快速乘除法運(yùn)算三、快速乘除法運(yùn)算 已經(jīng)講過(guò)的原碼或補(bǔ)碼一位乘除法運(yùn)算，已經(jīng)講過(guò)的原碼或補(bǔ)碼一位乘除法運(yùn)算，采用的是逐位循環(huán)迭代算法，完成時(shí)間直接取采用的是逐位循環(huán)迭代算法，完成時(shí)間直接取決于數(shù)據(jù)的位數(shù)，當(dāng)位數(shù)較多時(shí)，用時(shí)較長(zhǎng)。決于數(shù)據(jù)的位數(shù)，當(dāng)位數(shù)較多時(shí)，用時(shí)較長(zhǎng)。 提高乘除法運(yùn)算速度的出路之一，提高乘除法運(yùn)算速度的出路之一， 是每次是每次完成多位運(yùn)算，用的較多的是雙位乘法，完成多位運(yùn)算，用的較多的是雙位乘法， 跳零跳零跳一除法，更快的乘法則可以采用陣列乘法器，跳一除法，更快的乘法則可以采用陣列乘法器，可以用陣列除法器實(shí)現(xiàn)快速除法運(yùn)算。可以用陣列除法器實(shí)現(xiàn)快速除法運(yùn)算。 快速乘除法運(yùn)算不作為計(jì)算機(jī)組成原理課快速乘除法運(yùn)算不作為計(jì)算機(jī)組成原理課的基本要求，的基本要求， 同學(xué)們應(yīng)把主要注意力集中到其同學(xué)們應(yīng)把主要注意力集中到其實(shí)現(xiàn)的基本原理和對(duì)運(yùn)算器硬件的主要要求。實(shí)現(xiàn)的基