第四講定點(diǎn)運(yùn)算乘法

第四講定點(diǎn)運(yùn)算乘法第四講定點(diǎn)運(yùn)算乘法1、分析筆算乘法A=–0、1101B=0、1011A×B=–0、100011110、11010、101111011101000011010、10001111符號位單獨(dú)處理乘數(shù)得某一位決定就是否加被乘數(shù)4個位積一起相加乘積得位數(shù)擴(kuò)大一倍×乘積得符號心算求得

？2、筆算乘法改進(jìn)A

?B=A

?0、1011=0、1A+0、00A+0、001A+0、0001A=0、1A+0、00A+0、001(A+0、1A)=0、1A+0、01[0?

A+0、1(A+0、1A)]=0、1{A+0、1[0?

A+0、1(A+0、1A)]}=2-1{A+2-1[0?

A+2-1(A+2-1(A+0))]}①②⑧第一步被乘數(shù)A

+0第二步右移一位,得新得部分積第八步右移一位,得結(jié)果③第三步部分積+

被乘數(shù)…右移一位3、改進(jìn)后得筆算乘法過程(豎式)0、00000、11010、11010、11010、00000、1101初態(tài),部分積=0乘數(shù)為1,加被乘數(shù)乘數(shù)為1,加被乘數(shù)乘數(shù)為0,加01.001110.1001111.0001111乘數(shù)為1,加被乘數(shù)0.100011111，得結(jié)果1011=0.01101，形成新的部分積1101=0.10011，形成新的部分積1110=0.01001，形成新的部分積1111=

部分積乘數(shù)說明＋＋＋＋小結(jié)

被乘數(shù)只與部分積得高位相加

由乘數(shù)的末位決定被乘數(shù)是否與原部分積相加，然后1位形成新的部分積，同時乘數(shù)1

位（末位移丟），空出高位存放部分積的低位。硬件3

個寄存器,具有移位功能1

個全加器

乘法運(yùn)算可用加與移位實(shí)現(xiàn)

n=4,加4次,移4次4、原碼乘法(1)原碼一位乘運(yùn)算規(guī)則以小數(shù)為例設(shè)[x]原

=x0.x1x2

xn…[y]原

=y0.y1y2

yn…=(x0

y0).x*y*[x

?y]原

=(x0

y0).(0.x1x2

xn)(0.y1y2

yn)……式中x*=0.x1x2

xn

為x

的絕對值…y*=0.y1y2

yn

為y

的絕對值…乘積的符號位單獨(dú)處理x0

y0數(shù)值部分為絕對值相乘x*?

y*(2)原碼一位乘遞推公式x*?

y*=x*(0.y1y2

yn)…=x*(y12-1+y22-2++yn2-n)…=2-1(y1x*+2-1(y2x*+2-1(ynx*+0)))……z1znz0=0z1=2-1(ynx*+z0)z2=2-1(yn-1x*+z1)zn=2-1(y1x*+zn-1)……z0例21已知x=–0、1110y=0、1101求[x?y]原解:數(shù)值部分得運(yùn)算0、00000、11100、11100、00000、11100、1110部分積初態(tài)z0=0

部分積乘數(shù)說明0.011101.0001101.01101100.101101101，得

z4邏輯右移1101=0.01111，得

z10110=0.00111，得

z21011=0.10001，得

z31101=邏輯右移邏輯右移邏輯右移+++++x*+0+x*+x*②數(shù)值部分按絕對值相乘①乘積的符號位

x0

y0=10=1x*?

y*=0、10110110則[x

?

y]原

=1、10110110特點(diǎn)絕對值運(yùn)算邏輯移位例21結(jié)果用移位得次數(shù)判斷乘法就是否結(jié)束(3)原碼一位乘得硬件配置A、X、Q均n+1位移位和加受末位乘數(shù)控制0An

加法器控制門0Xn

移位和加控制計數(shù)器CSGM0Qn右移

R0→

R1→ynR2

計數(shù)器i

部分積z

被乘數(shù)x

乘數(shù)y

LDR0LDR1

T1,T2,…

Ti

QQ加法器RS啟動ynCx計數(shù)器:對移位得次數(shù)進(jìn)行計數(shù),以便判斷乘法運(yùn)算就是否結(jié)束。當(dāng)計數(shù)器i=n時,計數(shù)器i得溢出信號使控制觸發(fā)器Cx

置0,關(guān)閉時序脈沖T,乘法操作結(jié)束。大家學(xué)習(xí)辛苦了，還是要堅持繼續(xù)保持安靜(4)原碼兩位乘(提高乘法運(yùn)算速度)原碼乘符號位與數(shù)值位部分分開運(yùn)算兩位乘每次用乘數(shù)得2位判斷原部分積就是否加與如何加被乘數(shù)11100100

加“0”2加1倍的被乘數(shù)2加2倍的被乘數(shù)2加3倍的被乘數(shù)23？先減1倍得被乘數(shù)再加4倍得被乘數(shù)4–13100–0111

新的部分積乘數(shù)yn-1

yn(5)原碼兩位乘運(yùn)算規(guī)則111110101100011010001000操作內(nèi)容標(biāo)志位Cj乘數(shù)判斷位yn-1yn

z2,y*2,Cj

保持“0”

z2,y*2,Cj

保持“1”z–x*2,y*2,Cj

保持“1”

z+2x*2,y*2,Cj

保持“0”z+x*2,y*2,Cj

保持“0”共有操作+x*+2x*–x*2實(shí)際操作+[x*]補(bǔ)

+[2x*]補(bǔ)

+[–x*]補(bǔ)

2補(bǔ)碼移z–x*2,y*2,Cj置“1”

z+2x*2,y*2,Cj置“0”

z+x*2,y*2,Cj置“0”

例22已知x=0、111111y=–0、111001求[x·y]原000、000000000、111111000、11111100、1110010初態(tài)

z0=0+x*,Cj=0010.00110111000.111000000111111.1001000111001、111110+2x*,Cj=0111、000001–x*,Cj=1000、111111+x*,Cj=00000.0011111100111020000.1000110111001121111.111001000111002Cj部分積乘數(shù)

說明補(bǔ)碼右移補(bǔ)碼右移解:數(shù)值部分得運(yùn)算補(bǔ)碼右移++++②數(shù)值部分得運(yùn)算①乘積的符號位

x0

y0=01=1x*?

y*=0、111000000111則[x

?

y]原

=1、111000000111例22結(jié)果特點(diǎn)絕對值得補(bǔ)碼運(yùn)算算術(shù)移位用移位得次數(shù)判斷乘法就是否結(jié)束(6)原碼兩位乘與原碼一位乘比較符號位操作數(shù)移位移位次數(shù)最多加法次數(shù)x0

y0x0

y0絕對值絕對值得補(bǔ)碼邏輯右移算術(shù)右移nnn2（n為偶數(shù)）n2+1（n為偶數(shù)）思考n

為奇數(shù)時,原碼兩位乘移？次最多加？次原碼一位乘原碼兩位乘5、補(bǔ)碼乘法設(shè)被乘數(shù)乘數(shù)[x]補(bǔ)

=x0.x1x2

xn…[y]補(bǔ)

=y0.y1y2

yn…①被乘數(shù)任意,乘數(shù)為正同原碼乘但加與移位按補(bǔ)碼規(guī)則運(yùn)算乘積得符號自然形成②被乘數(shù)任意,乘數(shù)為負(fù)乘數(shù)[y]補(bǔ),去掉符號位,操作同①最后加[–x]補(bǔ),校正(1)補(bǔ)碼一位乘運(yùn)算規(guī)則以小數(shù)為例1)、當(dāng)被乘數(shù)x符號任意,乘數(shù)y符號為正時:

根據(jù)補(bǔ)碼定義:==yyyy.]y[nL210補(bǔ))(modxxxxx.x]x[nn+=+==+L1210222補(bǔ)∴

由于(y1y2…yn)就是大于或等于1得正整數(shù),根據(jù)模運(yùn)算性質(zhì)(大于2得部分全部丟掉)有:2(y1y2…yn)=2∴(mod2)即:Booth乘法公式證明2)、

當(dāng)被乘數(shù)x符號任意,乘數(shù)y符號為負(fù)時:)(modyyyy.]y[n22121+==L補(bǔ)xxx.x]x[n210=L補(bǔ)∵∴又因(0、y1y2…yn)>0所以:(mod2)=[x]補(bǔ)·=[x]補(bǔ)·y

為推導(dǎo)出邏輯實(shí)現(xiàn)得分步算法,將上式展開得到各項部分積累加得形式。(yn+1就是增加得附加位,初值為0)公式展開遞推公式[z0]補(bǔ)=0[z1]補(bǔ)=2-1{(yn+1–yn)[x]補(bǔ)+[z0]補(bǔ)}yn+1=0[zn]補(bǔ)=2-1{(y2–y1)[x]補(bǔ)+[zn-1]補(bǔ)}…[x

·

y]補(bǔ)=[zn]補(bǔ)+(y1–y0)[x]補(bǔ)最后一步不移位如何實(shí)現(xiàn)

yi+1–yi

?000110111+[x]補(bǔ)

1+[–x]補(bǔ)

1101-10yi

yi+1操作yi+1–yi由此可見:每次都就是在前次部分積得基礎(chǔ)上,由(yi+1-yi)決定對[x]補(bǔ)得操作,然后再右移一位,得到新得部分積;重復(fù)進(jìn)行。yn+1,yn得作用:開始操作時,補(bǔ)充一位yn+1,使其初始為0。由yn+1yn

判斷進(jìn)行什么操作;然后再由ynyn-1

判斷第二步進(jìn)行什么操作…。

若

ynyn＋1=０1則

yi＋1-yi=1做加[x]補(bǔ)運(yùn)算;ynyn＋1=１０則

yi＋1-yi=-１做加[-x]補(bǔ)運(yùn)算;ynyn＋1=１1ynyn＋1=0０則yi＋1-yi=0

[zi]加0,即保持不變;

補(bǔ)碼一位乘得運(yùn)算規(guī)則(1)如果yn=yn+1,則部分積[zi]加0,再右移一位;(2)如果ynyn+1=01

,則部分積[zi]加[x]補(bǔ),再右移一位;(2)如果ynyn+1=10

,則部分積[zi]加[-x]補(bǔ),再右移一位;

如此重復(fù)n+1步,但最后一步不移位。包括一位符號位,所得乘積為2n+1位,其中n為尾數(shù)位數(shù)。算法流程圖

開始結(jié)束[zi]補(bǔ)+[x]補(bǔ)→[zi]補(bǔ)[zi]補(bǔ)+[-x]補(bǔ)→[zi]補(bǔ)[z]補(bǔ)=0,i=0ynyn+1=?[zi]補(bǔ)不變i=n+1？[zi]補(bǔ),y右移一位，i=i+1011000或11YN例23已知x=+0、0011y=–0、1011求[x·y]補(bǔ)解:00、000011、110111、110100、001111、110100、001111、11011、0101000.0001111.11011100.000111111.11011111

[x]補(bǔ)

=0、0011

[y]補(bǔ)

=1、0101[–x]補(bǔ)

=1、1101+[–x]補(bǔ)11.11101101011+[x]補(bǔ)00.00001110101+[–x]補(bǔ)11.1110111101100.00001111101+[–x]補(bǔ)+[x]補(bǔ)∴

[x·y]補(bǔ)

=1、11011111

最后一步不移位補(bǔ)碼右移補(bǔ)碼右移補(bǔ)碼右移補(bǔ)碼右移+++++00、00001、00110yn+1=0+00、1011ynyn+1=10,加[-x]補(bǔ)

00、1011

00、0101110011右移一位+00、0000ynyn+1=11,加000、010100、0010111001右移一位+11、0101ynyn+1=01,加[x]補(bǔ)

11、011111、1011111100右移一位+00、0000ynyn+1=00,加011、101111、1101111110右移一位+00、1011ynyn+1=10,加[-x]補(bǔ)

00、1000111110最后一位不移位例:[x]補(bǔ)=1、0101,[y]補(bǔ)=1、0011,求[x·y]補(bǔ)=？[-x]補(bǔ)=0、1011[x·y]補(bǔ)=0、10001111部分積乘數(shù)ynyn+1說明000000101100yn+1=0+000000ynyn+1=00,加0000000

000000010110右移一位+110011ynyn+1=10,加[-x]補(bǔ)

110011111001101011右移一位+000000ynyn+1=11,加011、100111、1100110101右移一位+001101ynyn+1=01,加[x]補(bǔ)

001001000100111010右移一位+110011ynyn+1=10,加[-x]補(bǔ)

110111111010最后一位不移位[x]補(bǔ)=001101,[y]補(bǔ)=10110,[-x]補(bǔ)=110011[x·y]補(bǔ)=1部分積乘數(shù)ynyn+1說明例:x=13,y=-10求x·y=？x·y=-010000010=-82H=-130(2)Booth算法得硬件配置A、X、Q均n+2位移位和加受末兩位乘數(shù)控制0An+1n+2位加法器控制門0Xn+10Qn

n+1移位和加控制邏輯計數(shù)器CGM00,110110右移4、補(bǔ)碼一位乘邏輯原理圖

R0→

R1→ynyn+1R2

計數(shù)器i

部分積z

被乘數(shù)x乘數(shù)y

+1LDR0LDR1

T1,T2,…+1

Ti

QQ加法器RS啟動Cx

f

+-yn+1ynyn+1yn多開關(guān)路原反1001QQ[注]被乘數(shù)寄存器R2得每一位用原碼(觸發(fā)器Q端)或反碼(觸發(fā)器Q端)經(jīng)多路開關(guān)送出;送[-x]補(bǔ)時,即送R2反碼且在加法器最末為加1;(2)R0保存部分積,其符號與加法器符號位

f始終一致。(3)當(dāng)計數(shù)器i=n+1時,封鎖LDR1、LDR0信號,使最后一步不移位。不帶符號得陣列乘法器設(shè)有兩個不帶符號得二進(jìn)制整數(shù)A＝am－1…a1a0,B＝bn－1…b1b0它們得數(shù)值分別為a與b,即: