AC Universitatea “Ioan-Slavici” Timişoara
Seminar 3
Metode de înmulţire binară
Operaţia de înmulţire se realizează asupra operanzilor:
Înmulţitor (multiplier) notat X
Deînmulţit (multiplicand) notat Y
Operanzii sunt reprezentaţi prin numere binare.
În urma înmulţirii rezultă produsul P. Acesta se obţine prin apelarea în mod repetat la
fundamentala operaţie de adunare.
Metoda I de înmulţire convenţională denumită şi “paper and pencil”
Exemplul 1
Fie X = x3x2x1x0 = 1010 = 10102
Y = y3y2y1y0 = 1510 = 11112
P= X*Y = ?
1111 = y3y2y1y0 = Y
1010 = x3x2x1x0 = X
0000…..x0Y20
1111……x1Y21
0000…….. x2Y22
1111……… x3Y23
10010110…..P =
P = 100101102 = 15010
Exemplul 2
Fie X = x3x2x1x0 = 710 = 01112
Y = y3y2y1y0 = 310 = 00112
P= X*Y = ?
0111 = y3y2y1y0 = Y
0011 = x3x2x1x0 = X
0111…..x0Y20
0111……x1Y21
0000…….. x2Y22
0000……… x3Y23
0010101…..P =
1
AC Universitatea “Ioan-Slavici” Timişoara
P = 00101012 = 2110
Procedura se bazează pe formarea prealabilă a produselor de un bit ale operandului
Y cu xi, decalarea progresivă a acestora cu un bit înpre stânga ( xiY2i ) începând cu
bitul cel mai puţin semnificativ al lui x ( x0 ) şi în final, adunarea produselor de un bit
decalate ( xiY2i ).
P=
Metoda II de înmulţire binară
O primă îmbunătăţire formarea în manieră secvenţială a unui produs parţial
cumulative, care iniţial este 0 şi la care se adună, în mod succesiv, produse de un bit
ale lui Y corespunzător decalate la stânga.
Exemplul 1
Fie X = x3x2x1x0 = 1010 = 10102
Y = y3y2y1y0 = 1510 = 11112
P= X*Y = ?
1111…….. y3y2y1y0 = 1510
1010…….. x3x2x1x0 = 1010
00000000 ……. P0 := 0
0000 ……. x0Y20
00000000 ……. P1 := P0 + x0Y20
1111 …….. x1Y21
00011110 ......... P2 := P1 + x1Y21
0000 …….. x2Y22
00011110 ……. P3 := P2 + x2Y22
1111 ……… x3Y23
10010110 ……. P4 := P3 + x3Y23
Exemplul 2
Fie X = x3x2x1x0 = 710 = 01112
Y = y3y2y1y0 = 310 = 00112
P= X*Y = ?
2
AC Universitatea “Ioan-Slavici” Timişoara
0011…….. y3y2y1y0 = 310
0111…….. x3x2x1x0 = 710
00000000 ……. P0 := 0
0011 ……. x0Y20
00000011 ……. P1 := P0 + x0Y20
0011 …….. x1Y21
00001001 ......... P2 := P1 + x1Y21
0011 …….. x2Y22
00010101 ……. P3 := P2 + x2Y22
0000 ……… x3Y23
00010101 ……. P4 := P3 + x3Y23
Metoda III de înmulţire binară
O a doua îmbunătăţire, prin prisma spaţiului de memorare revendicat, se bazează pe
formarea în manieră secvenţială a unui produs parţial cumulativ, care iniţial este şi el
0, nefiind însă fix ca poziţie, ci el este deplasat de această dată la dreapta şi la care
se adună în mod succesiv, produse de un bit ale lui Y cu poziţia neschimbată pe
parcursul întregii operaţii.
Exemplul 1
Fie X = x3x2x1x0 = 1010 = 10102
Y = y3y2y1y0 = 1510 = 11112
P= X*Y = ?
1111 = y3y2y1y0 = 1510
1010 = x3x2x1x0 = 1010
00000000 ...................................................P0 := 0
0000 ………………………………….. .x0Y
00000000 ………………………………….. .P0 := P0 + x0Y
00000000 …………………………………..P1 := 2-1P0
1111 …………………………………..x1Y
00011110 …………………………………..P1 := P1 + x1Y
00011110 …………………………………P2 := 2-1P1
0000 …………………………………x2Y
00011110 …………………………………P2 := P2 + x2Y
00011110……………………………….. P3 := 2-1P2
1111 ………………………………… x3Y
10010110 ………………………………...P3 := P3 + x3Y
10010110 ………………………………. P4 := 2-1P3 = P
Exemplul 2
Fie X = x3x2x1x0 = 710 = 01112
Y = y3y2y1y0 = 310 = 00112
P= X*Y = ?
3
AC Universitatea “Ioan-Slavici” Timişoara
0011 = y3y2y1y0 = 310
0111 = x3x2x1x0 = 710
00000000 ...................................................P0 := 0
0011 ………………………………….. .x0Y
00000011 ………………………………….. .P0 := P0 + x0Y
00000011 …………………………………..P1 := 2-1P0
0011 …………………………………..x1Y
00001001 …………………………………..P1 := P1 + x1Y
00001001 …………………………………P2 := 2-1P1
0011 …………………………………x2Y
00010101 …………………………………P2 := P2 + x2Y
00010101 ………………………………P3 := 2-1P2
0000 ……………………………………x3Y
00010101 ………………………………...P3 := P3 + x3Y
00010101 ………………………………. P4 := 2-1P3 = P
Exerciţii
Fie numerele:
1) X = 8210
Y = 4510
2) X =33610
Y =53210
Să se realizeze operaţia de înmulţire pentru cele 2 numere, prin cele 3 metode de
înmulţire binară prezentate.