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

？2、筆算乘法改進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))]}①②⑧第一步被乘數A

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

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

部分積乘數說明＋＋＋＋小結

被乘數只與部分積得高位相加

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

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

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

個全加器

乘法運算可用加與移位實現

n=4,加4次,移4次4、原碼乘法(1)原碼一位乘運算規則以小數為例設[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

的絕對值…乘積的符號位單獨處理x0

y0數值部分為絕對值相乘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]原解:數值部分得運算0、00000、11100、11100、00000、11100、1110部分積初態z0=0

部分積乘數說明0.011101.0001101.01101100.101101101，得

z4邏輯右移1101=0.01111，得

z10110=0.00111，得

z21011=0.10001，得

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

x0

y0=10=1x*?

y*=0、10110110則[x

?

y]原

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

加法器控制門0Xn

移位和加控制計數器CSGM0Qn右移

R0→

R1→ynR2

計數器i

部分積z

被乘數x

乘數y

LDR0LDR1

T1,T2,…

Ti

QQ加法器RS啟動ynCx計數器:對移位得次數進行計數,以便判斷乘法運算就是否結束。當計數器i=n時,計數器i得溢出信號使控制觸發器Cx

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

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

新的部分積乘數yn-1

yn(5)原碼兩位乘運算規則111110101100011010001000操作內容標志位Cj乘數判斷位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實際操作+[x*]補

+[2x*]補

+[–x*]補

2補碼移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初態

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

說明補碼右移補碼右移解:數值部分得運算補碼右移++++②數值部分得運算①乘積的符號位

x0

y0=01=1x*?

y*=0、111000000111則[x

?

y]原

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

y0x0

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

為奇數時,原碼兩位乘移？次最多加？次原碼一位乘原碼兩位乘5、補碼乘法設被乘數乘數[x]補

=x0.x1x2

xn…[y]補

=y0.y1y2

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

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

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

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

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

·

y]補=[zn]補+(y1–y0)[x]補最后一步不移位如何實現

yi+1–yi

?000110111+[x]補

1+[–x]補

1101-10yi

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

判斷進行什么操作;然后再由ynyn-1

判斷第二步進行什么操作…。

若

ynyn＋1=０1則

yi＋1-yi=1做加[x]補運算;ynyn＋1=１０則

yi＋1-yi=-１做加[-x]補運算;ynyn＋1=１1ynyn＋1=0０則yi＋1-yi=0

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

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

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

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

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

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

[x]補

=0、0011

[y]補

=1、0101[–x]補

=1、1101+[–x]補11.11101101011+[x]補00.00001110101+[–x]補11.1110111101100.00001111101+[–x]補+[x]補∴

[x·y]補

=1、11011111

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

00、1011

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

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

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

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

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

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

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

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

R0→

R1→ynyn+1R2

計數器i

部分積z

被乘數x乘數y

+1LDR0LDR1

T1,T2,…+1

Ti

QQ加法器RS啟動Cx

f

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

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