Lecture_7_定點(diǎn)除法

1、定點(diǎn)除法運(yùn)算課程結(jié)構(gòu)計(jì)算機(jī)系計(jì)算機(jī)系統(tǒng)統(tǒng)計(jì)統(tǒng)統(tǒng)計(jì)硬件硬件運(yùn)算器運(yùn)算器數(shù)據(jù)表示數(shù)據(jù)表示數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)定點(diǎn)定點(diǎn)原碼原碼反碼反碼補(bǔ)碼補(bǔ)碼移碼移碼浮點(diǎn)浮點(diǎn)一般表示一般表示規(guī)格化規(guī)格化IEEE754非數(shù)值數(shù)非數(shù)值數(shù)據(jù)據(jù)校驗(yàn)碼校驗(yàn)碼運(yùn)算方法運(yùn)算方法定點(diǎn)數(shù)定點(diǎn)數(shù)補(bǔ)碼加減補(bǔ)碼加減乘除乘除原碼一位原碼一位乘乘補(bǔ)碼一位補(bǔ)碼一位乘乘并行乘法并行乘法原碼除法原碼除法恢復(fù)余數(shù)恢復(fù)余數(shù)加減交替加減交替浮點(diǎn)數(shù)浮點(diǎn)數(shù)加減乘除加減乘除規(guī)格化規(guī)格化溢出判斷溢出判斷運(yùn)算器運(yùn)算器一般運(yùn)算一般運(yùn)算快速運(yùn)算快速運(yùn)算典型典型ALU存儲(chǔ)器存儲(chǔ)器控制器控制器總線總線輸入輸出輸入輸出軟硬件接軟硬件接口口軟件軟件主要內(nèi)容n原碼除法恢復(fù)余數(shù)法原碼

2、除法恢復(fù)余數(shù)法n原碼除法不恢復(fù)作數(shù)法（加減交替法）原碼除法不恢復(fù)作數(shù)法（加減交替法）n補(bǔ)碼除法補(bǔ)碼除法n陣列除法器陣列除法器分析筆算除法分析筆算除法x = 0.1011 y = 0.1101 求求 xy0 . 1 0 1 10 . 1 1 0 10 . 0 1 1 0 10 . 0 1 0 0 10 . 0 0 1 1 0 10 . 0 0 0 1 0 10 . 0 0 0 0 1 1 0 10 . 0 0 0 0 0 1 1 1 1商符單獨(dú)處理商符單獨(dú)處理心算上商心算上商余數(shù)不動(dòng)低位補(bǔ)余數(shù)不動(dòng)低位補(bǔ)“0”減右移一位的除數(shù)減右移一位的除數(shù)上商位置不固定上商位置不固定xy = 0. 1 1 0

3、1余數(shù)余數(shù) 0. 0 0 0 0 0 1 1 1商符心算求得商符心算求得00 . 101000 ？筆算除法和機(jī)器除法的比較筆算除法和機(jī)器除法的比較筆算除法筆算除法 機(jī)器除法機(jī)器除法商符單獨(dú)處理商符單獨(dú)處理心算上商心算上商符號(hào)位異或形成符號(hào)位異或形成| x | | y | 0 上商上商 1| x | | y | 0 上商上商 0余數(shù)余數(shù) 不動(dòng)不動(dòng) 低位補(bǔ)低位補(bǔ)“0”減右移一位減右移一位 的除數(shù)的除數(shù)2 倍字長加法器倍字長加法器上商位置上商位置 不固定不固定余數(shù)余數(shù) 左移一位左移一位 低位補(bǔ)低位補(bǔ)“0”減減 除數(shù)除數(shù)1 倍字長加法器倍字長加法器在寄存器在寄存器 最末位上商最末位上商原碼除法原碼除法

4、以小數(shù)為例以小數(shù)為例 x 原原 = x0. x1x2 xn y 原原 = y0. y1y2 yn式中式中 x* = 0. x1x2 xn 為為 x 的絕對(duì)值的絕對(duì)值 y* = 0. y1y2 yn 為為 y 的絕對(duì)值的絕對(duì)值數(shù)值部分為絕對(duì)值相除數(shù)值部分為絕對(duì)值相除x*y*被除數(shù)不等于被除數(shù)不等于 0除數(shù)不能為除數(shù)不能為 0小數(shù)定點(diǎn)除法小數(shù)定點(diǎn)除法 x* y*整數(shù)定點(diǎn)除法整數(shù)定點(diǎn)除法 x* y*商的符號(hào)位單獨(dú)處理商的符號(hào)位單獨(dú)處理 x0 y0 原原 = (x0 y0).xyx*y*約定約定原碼除法原碼除法恢復(fù)余數(shù)法恢復(fù)余數(shù)法0 . 1 0 1 11 . 0 0 1 11 . 0 0 1 11 .

5、 0 0 1 10 . 0 0 0 0+ y*補(bǔ)補(bǔ)01 . 1 1 1 0余數(shù)為負(fù)，上商余數(shù)為負(fù)，上商 00 . 1 1 0 1恢復(fù)余數(shù)恢復(fù)余數(shù)00 . 1 0 0 1余數(shù)為正，上商余數(shù)為正，上商 1+ y*補(bǔ)補(bǔ)1 . 0 1 1 0011 . 0 0 1 00 11+y*補(bǔ)補(bǔ)解：解：被除數(shù)（余數(shù)）被除數(shù)（余數(shù)） 商商 說說 明明x原原 = 1.1011 y原原 = 1.1101 x0 y0 = 1 1 = 0 x = 0.1011 y = 0.1101求求 原原 xy例例10 . 1 0 1 1恢復(fù)后的余數(shù)恢復(fù)后的余數(shù)0+y*補(bǔ)補(bǔ)y*補(bǔ)補(bǔ) = 0.1101 y*補(bǔ)補(bǔ) = 1.0011邏輯左移

6、邏輯左移邏輯左移邏輯左移+ + + + +0 . 0 1 0 10 1余數(shù)為正，上商余數(shù)為正，上商 1被除數(shù)（余數(shù)）被除數(shù)（余數(shù)） 商商 說說 明明1 . 0 0 1 10 . 1 1 0 11 . 0 0 1 110 . 1 0 1 00 1 1+ y*補(bǔ)補(bǔ)1 . 1 1 0 10 1 1 余數(shù)為負(fù)，上商余數(shù)為負(fù)，上商 0恢復(fù)余數(shù)恢復(fù)余數(shù)1 . 0 1 0 00 1 1 01+ y*補(bǔ)補(bǔ)0 . 0 1 1 10 1 1 0 余數(shù)為正，上商余數(shù)為正，上商 1= 0.1101x*y* 原原xy= 0.1101上商上商 5 次次第一次上商判溢出第一次上商判溢出余數(shù)為正余數(shù)為正 上商上商 1余數(shù)為負(fù)

7、余數(shù)為負(fù) 上商上商 0，恢復(fù)余數(shù)，恢復(fù)余數(shù)移移 4 次次100 . 1 0 1 0恢復(fù)后的余數(shù)恢復(fù)后的余數(shù)0 1 1 01+y*補(bǔ)補(bǔ)邏輯左移邏輯左移邏輯左移邏輯左移+ + + +最后余數(shù)為最后余數(shù)為r rn n2 2n n( (余數(shù)與被除數(shù)同號(hào)余數(shù)與被除數(shù)同號(hào)) )主要內(nèi)容n原碼除法恢復(fù)余數(shù)法原碼除法恢復(fù)余數(shù)法n原碼除法不恢復(fù)作數(shù)法（加減交替法）原碼除法不恢復(fù)作數(shù)法（加減交替法）n補(bǔ)碼除法補(bǔ)碼除法n陣列除法器陣列除法器原碼除法原碼除法不恢復(fù)余數(shù)法（加減交替法）不恢復(fù)余數(shù)法（加減交替法） 加減交替加減交替 恢復(fù)余數(shù)法運(yùn)算規(guī)則恢復(fù)余數(shù)法運(yùn)算規(guī)則 不恢復(fù)余數(shù)法運(yùn)算規(guī)則不恢復(fù)余數(shù)法運(yùn)算規(guī)則上商上商“1

8、” 2Ri y* 上商上商“0” 2Ri + y* 在恢復(fù)余數(shù)法中，若第在恢復(fù)余數(shù)法中，若第i i次求的余數(shù)為次求的余數(shù)為R Ri i, ,下一次求的余數(shù)下一次求的余數(shù)為為R Ri+1i+1, , 則：則：若若 R Ri i0 0 商商1 1，R Ri i左移一位左移一位，然后減，然后減Y Y，得到，得到R Ri+1i+1R Ri+1i+1 = = 2 R2 Ri i - Y;- Y;若若 R Ri i0 0 商商0 0，恢復(fù)余數(shù)恢復(fù)余數(shù)，左移一位左移一位，然后減，然后減Y Y R Ri+1i+1 = = 2 2 (R(Ri i + Y) + Y) Y = 2 R Y = 2 Ri i + Y

9、 ; + Y ;x = 0.1011 y = 0.1101 求求 原原xy解：解：例例0 . 1 0 1 11 . 0 0 1 10 . 1 1 0 11 . 0 0 1 11 . 0 0 1 10 . 1 1 0 10 . 0 0 0 0+ y*補(bǔ)補(bǔ)01 . 1 1 1 0余數(shù)為負(fù)，上商余數(shù)為負(fù)，上商 01 . 1 1 0 001+y*補(bǔ)補(bǔ)00 . 1 0 0 1余數(shù)為正，上商余數(shù)為正，上商 1+ y*補(bǔ)補(bǔ)1 . 0 0 1 00 11+ y*補(bǔ)補(bǔ)+y*補(bǔ)補(bǔ)0 . 1 0 1 00 1 111 . 1 0 1 00 1 1 010 . 0 1 0 10 1余數(shù)為正，上商余數(shù)為正，上商 10

10、. 0 1 1 10 1 1 0 余數(shù)為正，上商余數(shù)為正，上商 11 . 1 1 0 10 1 1余數(shù)為負(fù)，上商余數(shù)為負(fù)，上商 0 x原原 = 1.1011y*補(bǔ)補(bǔ) = 0.1101y*補(bǔ)補(bǔ) = 1.0011y原原 = 1.11011101邏輯邏輯左移左移x*補(bǔ)補(bǔ) = 0.1011邏輯邏輯左移左移邏輯邏輯左移左移邏輯邏輯左移左移 x0 y0 = 1 1 = 0 x*y*= 0.1101 = 0.1101 原原xy上商上商 n+1 次次結(jié)果結(jié)果特點(diǎn)特點(diǎn)用移位的次數(shù)判斷除法是否結(jié)束用移位的次數(shù)判斷除法是否結(jié)束第一次上商判溢出第一次上商判溢出移移 n 次次，加加 n+1 次次如果最后一次上商如果最后

11、一次上商0（余數(shù)為負(fù)），還需要再（余數(shù)為負(fù)），還需要再恢復(fù)余數(shù)恢復(fù)余數(shù)原碼加減交替除法硬件配置原碼加減交替除法硬件配置A、B、Q 均均 n +1 位位用用 Qn 控制加減交替控制加減交替 0 A 被除數(shù)被除數(shù),余數(shù)余數(shù) nn + 1 位加法器位加法器 控控 制制 門門0 B 除數(shù)除數(shù) n0 Q 商商 n 計(jì)數(shù)器計(jì)數(shù)器 CGD加加減減移位和加控制邏輯移位和加控制邏輯 S V 左移左移取反主要內(nèi)容n原碼除法恢復(fù)余數(shù)法原碼除法恢復(fù)余數(shù)法n原碼除法不恢復(fù)作數(shù)法（加減交替法）原碼除法不恢復(fù)作數(shù)法（加減交替法）n補(bǔ)碼除法補(bǔ)碼除法n陣列除法器陣列除法器補(bǔ)碼除法（自學(xué)）補(bǔ)碼除法（自學(xué)）n補(bǔ)碼除法規(guī)則比原碼復(fù)雜

12、；補(bǔ)碼除法規(guī)則比原碼復(fù)雜；n當(dāng)除數(shù)和被除數(shù)用補(bǔ)碼表示時(shí)，判別是否夠減，要比較它當(dāng)除數(shù)和被除數(shù)用補(bǔ)碼表示時(shí)，判別是否夠減，要比較它們絕對(duì)值的大小，因此，若兩數(shù)同符號(hào)，要用減，若異號(hào)，們絕對(duì)值的大小，因此，若兩數(shù)同符號(hào)，要用減，若異號(hào)，則要用加。則要用加。n對(duì)于判斷是否夠減，及確定本次上商對(duì)于判斷是否夠減，及確定本次上商1還是還是0的規(guī)則，還與的規(guī)則，還與結(jié)果的符號(hào)有關(guān)。結(jié)果的符號(hào)有關(guān)。n當(dāng)商為正時(shí)，商的每一位上值與原碼表示一致；當(dāng)商為負(fù)當(dāng)商為正時(shí)，商的每一位上值與原碼表示一致；當(dāng)商為負(fù)時(shí)，商的各位應(yīng)是補(bǔ)碼形式的值，一般先按反碼值上商，時(shí)，商的各位應(yīng)是補(bǔ)碼形式的值，一般先按反碼值上商，除法完成后，

13、再用最低位加除法完成后，再用最低位加1，形成正確的補(bǔ)碼值。，形成正確的補(bǔ)碼值。如何判斷是否夠減？如何上商？如何確定商符？Ri補(bǔ)補(bǔ)= 0.1000 x補(bǔ)補(bǔ) = 1.1101 y補(bǔ)補(bǔ) = 1.0101補(bǔ)碼除法補(bǔ)碼除法(1) 商值的確定商值的確定x = 0.1011y = 0.0011 x補(bǔ)補(bǔ) = 0.1011 y補(bǔ)補(bǔ) = 0.0011x補(bǔ)補(bǔ) = 0.1011y補(bǔ)補(bǔ) = 1.1101Ri補(bǔ)補(bǔ)= 0.1000 x = 0.0011y = 0.1011x補(bǔ)補(bǔ) = 1.1101y補(bǔ)補(bǔ) = 0.1011x*y*Ri補(bǔ)補(bǔ)與與y補(bǔ)補(bǔ)同號(hào)同號(hào)“夠減夠減”x*y*Ri補(bǔ)補(bǔ)與與y補(bǔ)補(bǔ)異號(hào)異號(hào)“不夠減不夠減”+ 比較被

14、除數(shù)和除數(shù)比較被除數(shù)和除數(shù)絕對(duì)值絕對(duì)值的大小的大小(可以十進(jìn)制數(shù)為例可以十進(jìn)制數(shù)為例)x 與與 y 同號(hào)同號(hào)注意此處是注意此處是x x* *,y,y* *小結(jié)小結(jié)x = 0.1011y = 0.0011 x補(bǔ)補(bǔ) = 0.1011 y補(bǔ)補(bǔ) = 1.1101x補(bǔ)補(bǔ) = 0.1011y補(bǔ)補(bǔ) = 1.1101Ri補(bǔ)補(bǔ)= 0.1000 x = 0.0011y = 0.1011 x補(bǔ)補(bǔ) = 1.1101 y補(bǔ)補(bǔ) = 0.1011x補(bǔ)補(bǔ) = 1.1101y補(bǔ)補(bǔ) = 0.1011Ri補(bǔ)補(bǔ)= 0.1000 x*y*Ri補(bǔ)補(bǔ)與與y補(bǔ)補(bǔ)異號(hào)異號(hào)“夠減夠減”x*y*Ri補(bǔ)補(bǔ)與與y補(bǔ)補(bǔ)同號(hào)同號(hào)“不夠減不夠減”+x 與與

15、 y 異號(hào)異號(hào)x補(bǔ)補(bǔ)和和y補(bǔ)補(bǔ)求求 Ri補(bǔ)補(bǔ)Ri補(bǔ)補(bǔ)與與 y補(bǔ)補(bǔ)同號(hào)同號(hào)異號(hào)異號(hào)x補(bǔ)補(bǔ) y補(bǔ)補(bǔ)x補(bǔ)補(bǔ)+ y補(bǔ)補(bǔ)同號(hào)，同號(hào)，“夠減夠減”異號(hào)，異號(hào)，“夠減夠減”補(bǔ)碼除法補(bǔ)碼除法(1) 商值的確定商值的確定 商值的確定商值的確定x補(bǔ)補(bǔ)與與 y補(bǔ)補(bǔ)同號(hào)同號(hào)正正商商按原碼上商按原碼上商“夠減夠減”上上“1”“不夠減不夠減”上上“0”x補(bǔ)補(bǔ)與與 y補(bǔ)補(bǔ)異號(hào)異號(hào)負(fù)負(fù)商商按反碼上商按反碼上商“夠減夠減”上上“0”“不夠減不夠減”上上“1”原碼原碼0. 1反碼反碼 1. 1末位恒置末位恒置“1”法法小小 結(jié)結(jié)簡簡 化化 為為（同號(hào)）（同號(hào)）（異號(hào)）（異號(hào)）（異號(hào)）（異號(hào)）（同號(hào)）（同號(hào)）. 1x補(bǔ)補(bǔ)與與 y補(bǔ)

16、補(bǔ)商商Ri補(bǔ)補(bǔ)與與 y補(bǔ)補(bǔ)商商 值值夠減夠減不夠減不夠減夠減夠減不夠減不夠減同同 號(hào)號(hào)異異 號(hào)號(hào)正正負(fù)負(fù)1001原碼上商原碼上商反碼上商反碼上商Ri補(bǔ)補(bǔ)與與y補(bǔ)補(bǔ)商值商值同同 號(hào)號(hào)異異 號(hào)號(hào)10最大誤差為最大誤差為2 2n n(2) 商符的形成商符的形成 除法過程中自然形成除法過程中自然形成x補(bǔ)補(bǔ)和和y補(bǔ)補(bǔ)同號(hào)同號(hào)x補(bǔ)補(bǔ)y補(bǔ)補(bǔ)比較比較Ri補(bǔ)補(bǔ)和和y補(bǔ)補(bǔ)同號(hào)同號(hào)(夠夠)“1”異號(hào)異號(hào)(不夠不夠)“0”原碼上商原碼上商小數(shù)除法小數(shù)除法 第一次第一次“不夠不夠”上上“0”正商正商x補(bǔ)補(bǔ)和和y補(bǔ)補(bǔ)異號(hào)異號(hào)x補(bǔ)補(bǔ)+y補(bǔ)補(bǔ)比較比較Ri補(bǔ)補(bǔ)和和y補(bǔ)補(bǔ)異號(hào)異號(hào)(夠夠)“0”同號(hào)同號(hào)(不夠不夠)“1”反碼上商反

17、碼上商小數(shù)除法小數(shù)除法 第一次第一次“不夠不夠”上上“1”負(fù)商負(fù)商補(bǔ)碼除法補(bǔ)碼除法(3) 新余數(shù)的形成新余數(shù)的形成加減交替加減交替Ri補(bǔ)補(bǔ)和和 y補(bǔ)補(bǔ)商商新余數(shù)新余數(shù)同同 號(hào)號(hào)異異 號(hào)號(hào)102Ri補(bǔ)補(bǔ) + y補(bǔ)補(bǔ)2Ri補(bǔ)補(bǔ) + y 補(bǔ)補(bǔ)補(bǔ)碼除法補(bǔ)碼除法例例設(shè)設(shè) x = 0.1011 y = 0.1101 求求 并還原成真值并還原成真值 補(bǔ)補(bǔ)xy解：解： x補(bǔ)補(bǔ) = 1.0101 y補(bǔ)補(bǔ) = 0.1101 y補(bǔ)補(bǔ) = 1.00111 . 0 1 0 10 . 1 1 0 11 . 0 0 1 10 . 1 1 0 10 . 1 1 0 10 . 0 0 0 0異號(hào)做加法異號(hào)做加法10 . 0 0

18、 1 0同號(hào)上同號(hào)上“1”1 . 0 1 1 11 異號(hào)上異號(hào)上“0”+y補(bǔ)補(bǔ)1 . 1 0 1 11 0 異號(hào)上異號(hào)上“0”+y補(bǔ)補(bǔ)0 . 0 0 1 11 0 0同號(hào)上同號(hào)上“1”0 . 0 1 0 0110 . 1 1 1 01 011 . 0 1 1 01 0 01末位恒置末位恒置“1”0 . 0 1 1 01 0 0 1 1 補(bǔ)補(bǔ)= 1.0011xy0011+y補(bǔ)補(bǔ)xy= 0.1101則則邏輯邏輯左移左移邏輯邏輯左移左移邏輯邏輯左移左移邏輯邏輯左移左移(4) 小結(jié)小結(jié)設(shè)數(shù)值部分為設(shè)數(shù)值部分為n位。補(bǔ)碼除法共上商位。補(bǔ)碼除法共上商 n +1 次次（末位恒置（末位恒置 1），其中第一次為商符），其中第一次為商符第一次商可判溢出第一次商可判溢出加加 n 次次 移移 n 次次用移位的次數(shù)判斷除法是否結(jié)束用移位的次數(shù)判斷除法是否結(jié)束精度誤差最大為精度誤差最大為 2-n補(bǔ)碼除法補(bǔ)碼除法補(bǔ)碼除和原碼除（加減交替法）比較補(bǔ)碼除和原碼除（加減交替法）比較x0 y0自然形成自然形成絕對(duì)值補(bǔ)碼絕對(duì)值補(bǔ)碼補(bǔ)碼補(bǔ)碼余數(shù)的正負(fù)余數(shù)的正負(fù)比較余數(shù)和除數(shù)的符號(hào)比較余數(shù)和除數(shù)的符號(hào) n +1 n +1原碼除原碼除補(bǔ)碼除補(bǔ)碼除商符商符操作數(shù)操作數(shù)上商原則上商原則上商次數(shù)上商次數(shù)加法