Szybkie mno\
enie
Metody przyśpieszania mno\
enia
Redukcja liczby iloczynów częściowych
" jednoczesne mno\
enie przez kilka kolejnych pozycji mno\
nika
 niezbędne u\
ycie wielokrotności mno\
nej A.
" przekodowanie mno\
nika, aby zawierał jak największą liczbę zer
 mo\
liwe w systemach o reprezentacji nadmiarowej (SD).
Szybka akumulacja iloczynów częściowych  dodawanie bez przeniesień
" u\
ycie wielooperandowego sumatora CSA
" wytwarzanie wektorowych sum częściowych i bie\
Ä…ca akumulacja
Szybkie układy mno\
Ä…ce:
" równoległe (parallel multipliers),
 jednoczesne wytworzenie wszystkich iloczynów częściowych,
 akumulacja przy u\
yciu wielooperandowego sumatora CSA
" matrycowe (array multipliers).
 u\
ycie wektorowych sum częściowych i bie\
ąca akumulacja iloczynów
© Janusz Biernat, Szybkie mno\
enie FAM 1
Szybkie mno\
enie
Schematy przyśpieszonego mno\
enia
a) b)
x0 A
x0 A
x1 A
x1 A
CSA
x2 A
x2 A
x3 A
CSA
x3 A
CSA
CSA
CPA
CPA
Układy mno\
ące: a) równoległy, b) matrycowy
© Janusz Biernat, Szybkie mno\
enie FAM 2
 Szybkie mno\
enie
Przekodowanie Bootha
" zastąpienie serii dodawań jednym odejmowaniem i jednym dodawaniem
2s-1 + 2s-2 + ... + 2l +1 + 2l = 2s - 2l
|{...0[11...11]0...}U2|=|{...1[00...00]0...}U2| |{...0[00...01]0...}U2,
|{...0[11...11]0...}SD|= |{...1[00...0 1]0...}SD|
reguła Bootha a" przekodowanie mno\
nika na kod SD
" reprezentacja w systemie NB lub U2 jest reprezentacjÄ… w systemie SD, ale
przekodowanie według reguły Bootha:
" U2 SD  wykonalne, bo [x1...11]0...= [(1-x)0...00]0... - [00...01]0...
" NB SD  niewykonalne bez rozszerzenia gdy {1,1,& ,1,0,x,& }, bo
xe"0 '" z `" 1 Ò! |{1,x,...,x,x}SD| > |{z,y,y,...,y}SD|
Ò! konieczne rozszerzenie {1,& ,1,0,x,& }NB= {0,1, & ,1,0,x,& }U2
© Janusz Biernat, Szybkie mno\
enie FAM 3
Szybkie mno\
enie
Algorytm Bootha
Uzasadnienie teoretyczne  równowa\
ność X=2X-X
n-2 n-2 n-1
îÅ‚- îÅ‚-
X = xn-12n + xi 2i+1Å‚Å‚ - xn-12n-1 + 2i Å‚Å‚ =
" "x śł "(x - xi )2i - x-1
i i-1
ïÅ‚ śł ïÅ‚
ðÅ‚ i=0 ûÅ‚ ðÅ‚ i=0 ûÅ‚ i=0
xi "{0,1} Ò! yi = xi-1 - xi "{-1,0,1} (x 1=0)
|{xn 1,xn 2,xn 1,& ,x1,x0}U2|=|{(xn 2 xn 1),(xn 3 xn 2),& ,(x0 x1),(x 1 x0)}SD|
Przekodowanie Bootha ( yi = xi-1 - xi)
xi xi 1 yi operacja komentarz
0 0 0  ciÄ…g zer
0 1 1 koniec ciÄ…gu jedynek
+A
1 0 poczÄ…tek ciÄ…gu jedynek
1 -A
1 1 0  ciÄ…g jedynek
Wady:
 zmienna liczba działań arytmetycznych, zale\
na od kodu liczby,
 nieefektywne kodowanie izolowanych jedynek  ...010101(0) ...1 1 1 11 1 .
© Janusz Biernat, Szybkie mno\
enie FAM 4
 Szybkie mno\
enie
Alternatywne przekodowanie Bootha
n-1 n-2
X =
"(x - xi)2i - x-1 = 2"(x - xi+1)2i - x0.
i-1 i
i=0 i=0
Ò! alternatywne przekodowanie mno\
nika Y = {yn-1,..., y1, y0}
yi = xi - xi+1, 0 d" i d" n -1,
Poniewa\
X = 2Y - x0, więc
" wartością początkową akumulowanej sumy iloczynów jest - x0A,
" zamiast mno\
nej A nale\
y w algorytmie u\
yć jej podwojenia 2A,
" yi (przekodowanie alternatywne) = yi+1(przekodowanie proste)
Przekodowanie alternatywne NB/U2 SD zawsze wykonalne:
" U2 SD  rozszerzenie xn = xn-1, Ò! yn-1 = 0
" NB SD  rozszerzenie xn = 0 Ò! yn-1 = xn-1
© Janusz Biernat, Szybkie mno\
enie FAM 5
Szybkie mno\
enie
Przekodowanie rozszerzone (w bazie 22)  algorytm Bootha-McSorleya
n-1
Na podstawie X =
"(x - xi )2i - x-1 mamy (k = îÅ‚n / 2Å‚Å‚)
i-1
i=0
k -1 k -1
j +1
X = - x2 )22 j +
"(x -1 j 2 j j +1
"(x - x2 )22 - x-1 =
2 j
j =0 j =0
k -1 k -1
= - x2 + 2x2 - 2x2 )22 j - x-1 = )22 j - x-1
"(x -1 j j j +1 2 j +1 j j
"(-2x + x2 + x2 -1
2 j
j =0 j =0
xi "{0,1} Ò! yi = -2x2 j+1 + x2 j + x2 j-1 "{-2,-1, 0,+1,+2} (x = 0)
-1
Ò! wynik przeksztaÅ‚ceÅ„: Y = {yn-1,..., y1, y0}SD (y# "{1,0,1}) takie, \
e
- 2x2i+1 + x2i + x2i-1 = 2y2i+1 + y2i
" rozwiązanie jednoznaczne gdy y2 j+1 y2 j = 0 (e" połowa cyfr Y to zera)
" mo\
liwe zmniejszenie liczby zer mno\
nika (00101010 01 0 1 01 0 1 ).
© Janusz Biernat, Szybkie mno\
enie FAM 6
 Szybkie mno\
enie
Algorytm Bootha-McSorleya  praktyczna realizacja
Ka\
da z kolejnych par bitów mno\
nika zawiera co najmniej jedno 0
1
Ò! liczba iloczynów częściowych d" n.
2
" dla pary pozycji x2i+1, x2i wykonuje siÄ™ dodawanie (x2i + x2i-1 - 2x2i+1 )A
Przekodowanie rozszerzone (Bootha-McSorleya)
x2i+1 x2i x2i 1 y2i+1 y2i Działanie Komentarz
0 0 0 0 0  ciÄ…g zer
0 1 0 0 1 +A izolowana jedynka
1 0 0 0 -2A
poczÄ…tek ciÄ…gu jedynek
1
1 1 0 0 poczÄ…tek ciÄ…gu jedynek
1 -A
0 0 1 0 1 +A koniec ciÄ…gu jedynek
0 1 1 1 0 +2A koniec ciÄ…gu jedynek
1 0 1 0 izolowane zero
1 -A
1 1 1 0 0  ciÄ…g jedynek
analizowane sÄ… pary bitów Ò! rozszerzenie mno\
nika do parzystej liczby bitów
© Janusz Biernat, Szybkie mno\
enie FAM 7
Szybkie mno\
enie
Alternatywne przekodowanie Bootha-McSorleya
n-2 îÅ‚n / 2Å‚Å‚-1
j
X = 2 - xj +1)2 - x0 = 2
"(x "(-2x + x2i+1 + x2i)22i - x0.
j 2i+2
j =0 i=0
(-2x2i+2 + x2i+1 + x2i ) "{-2,-1,0,1,2} wynik przekodowania: YSD taka, \
e
- 2x2i+2 + x2i+1 + x2i = 2y2i+1 + y2i oraz y2i+1 y2i = 0
Alternatywne przekodowanie Bootha-McSorleya
x2i+2 x2i+1 x2i y2i+1 y2i operacja Komentarz
0 0 0 0 0  ciÄ…g zer
0 0 1 0 1 +2A poczÄ…tek ciÄ…gu jedynek
0 1 0 0 1 +2A izolowana jedynka
0 1 1 1 0 +4A poczÄ…tek ciÄ…gu jedynek
1 0 0 0 -4A
koniec ciÄ…gu jedynek
1
1 0 1 0 izolowane zero
1 -2A
1 1 0 0 koniec ciÄ…gu jedynek
1 -2A
1 1 1 0 0  ciÄ…g jedynek
© Janusz Biernat, Szybkie mno\
enie FAM 8
 Szybkie mno\
enie
Realizacja przekodowania Bootha-McSorleya
sr+v av+1 av
xr 1
xr
xr+1
r = 2i + p, v = j + p
FA
( p = 0  prosty))
( p = 1  alternatywny))
sr+v+2
"  brak podwojenia = xr•"xr 1,
"  odejmowanie = xr+1,
"  brak zerowania = (xr•"xr+1)+(xr•"xr 1),
© Janusz Biernat, Szybkie mno\
enie FAM 9
Szybkie mno\
enie
Algorytm Bootha/Bootha-McSorleya  przykłady
X= {1,1,0,1,0,1}U2  w bazie 2  Y = {0,1,1,1,1 1},
 alternatywne w bazie 4  Y = {00,0 1,0 1}, P0= x0A
Y(2) Y(4R)
1 1 1 1 0 1 1 1 1 1 0 1
A=-3
0 1 1 1 1 1 0 0 0 1 0 1
X=-11
0 0 0 0 0 0 0 0 0 0 0 0  x0A 0 0 0 0 0 0 0 1 1
P0=
 A 0 0 0 0 0 0 0 0 0 1 1  2A 0 0 0 0 0 0 1 1
+A 1 1 1 1 1 1 1 1 0 1  2A 0 0 0 0 1 1
 A 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1
+A 1 1 1 1 1 1 0 1
 A 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0 0 0 1
XA=33
Uwaga: W polach zacienionych wpisano cyfry rozszerzenia znakowego.
© Janusz Biernat, Szybkie mno\
enie FAM 10
 Szybkie mno\
enie
Przekodowanie kanoniczne
MinimalnÄ… dla danego mno\
nika liczbę dodawań lub odejmowań określa waga
(| yn-1 | + | yn-2 | +...+ | y0 |) jego minimalnej reprezentacji w kodzie SD.
X = {xn-1,..., x1, x0}U2 Ymin = {yn-1,..., y1, y0}SD  przekodowanie kanoniczne
Przekodowanie kanoniczne  algorytm (p0=0)
xi 1 xi pi pi+1 yi Komentarz
0 0 0 0 0 ciÄ…g zer
0 1 0 0 1 izolowana jedynka
1 0 0 0 0 ciÄ…g zer
1 1 0 1 PoczÄ…tek ciÄ…gu jedynek
1
0 0 1 0 1 koniec ciÄ…gu jedynek
0 1 1 1 0 ciÄ…g jedynek
1 0 1 1 izolowane zero
1
1 1 1 1 0 ciÄ…g jedynek
Skomplikowana i czasochłonna procedura przekodowania rzadko stosowane
© Janusz Biernat, Szybkie mno\
enie FAM 11
Szybkie mno\
enie
Przekodowanie mno\
nika w systemie uzupełnień do 1
W systemie U1, na podstawie równowa\
ności X=2X-X mamy
n-2 n-2
îÅ‚- îÅ‚-
X = xn-1 (2n - 2ulp) + xi 2i+1 Å‚Å‚ - xn-1 (2n-1 - ulp) + xi 2i Å‚Å‚ ,
" "
ïÅ‚ śł ïÅ‚ śł
ðÅ‚ i=0 ûÅ‚ ðÅ‚ i=0 ûÅ‚
skÄ…d wynika
n-1
X =
"(x - xi )2i - x-1 + xn-1ulp.
i-1
i=0
Poniewa\
ulp=1, a rozszerzeniem liczby w kodzie U1 jest x-1 = xn-1, zatem
n-1
X =
"(x - xi )2i.
i-1
i=0
Podobnie
n-2
X = 2 - xi+1)2i + (xn-1 - x0 ).
"(x
i
i=0
" algorytm analogiczny jak w U2, lecz inna wartość początkowa akumulacji
" sumowanie z uwzględnieniem rozszerzeń prawo- i lewostronnych
© Janusz Biernat, Szybkie mno\
enie FAM 12
 Szybkie mno\
enie
Strukturalizacja układów mno\
Ä…cych
" układ mno\
Ä…cy kn×kn  zÅ‚o\
enie układów mno\
Ä…cych n×n:
j
k -1 k -1 k -1 2k -2 k -1
ëÅ‚
jn jn
AX = As 2sn öÅ‚ëÅ‚ X 2sn öÅ‚ = 2 Ai X + 2 Ai X ,
ìÅ‚ ÷Å‚ìÅ‚ ÷Å‚
" " " " -i j-i
" "
s j
íÅ‚ s=0 Å‚Å‚íÅ‚ s=0 Å‚Å‚ j =0 i=0 j=k i= j -k +1
albo w postaci skróconej
min( j,k -1)
2k -2
jn
AX = 2 Ai X
" "
j-i
j=0 i=max(0, j-k +1)
n-1 n-1
j j
gdzie Ai =
"a 2 , Xi = "x 2 .
ni+ j ni+ j
j =0 j =0
wyrównywanie (alignment)
" ka\
dy 2n-pozycyjny iloczyn Ai Xs-i ma wagÄ™ 2ns
(AX)s = [As X ,As-1 X1,...,A1 X ,A0 X ]
0 s-1 s
" efekt  akumulacja 2k-1 wielooperandów ró\
nego rozmiaru
zamiast k2 operandów o identycznej wielkości
© Janusz Biernat, Szybkie mno\
enie FAM 13
Szybkie mno\
enie
Wyrównanie operandów
27n 26n 25n 24n 23n 22n 2n 20
A3 X
0
A3 X1 A2 X
0
A3 X2 A2 X1 A1 X
0
A3 X A2 X A1 X1 A0 X
3 2 0
A2 X3 A1 X A0 X1
2
A1 X A0 X
3 2
A0 X
3
Wyrównanie operandów w układzie mno\
Ä…cym 4n×4n
" w kodzie U2 i U1  niezbędne uwzględnienie rozszerzenia znakowego
efekt  liczba operandów w j-ej grupie wynosi 2j+1 osiągając maksimum 4k-3,
niweczy to zysk wynikajÄ…cy ze strukturalizacji.
przekonstruowanie sumatora wielooperandowego CSA.
© Janusz Biernat, Szybkie mno\
enie FAM 14
 Szybkie mno\
enie
Akumulacja iloczynów częściowych
" sumatory wielooperandowe CSA
" ró\
ne wagi iloczynów częściowych ró\
na liczba operandów jednej wagi
a) A 9 8 7 6 5 4 3 2 1 0 b) A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o
o o o o o o o o o
o o o o o o o
Oryginalna (a) i przeorganizowana (b) matryca 36 iloczynów elementarnych
powstałych w wyniku mno\
enia nieznakowanych operandów 6-bitowych
" redukcja operandów na poziomie l-tym, tak aby wynikowa liczba
operandów w ka\
dej kolumnie dała się zredukować na (l-1) poziomach.
© Janusz Biernat, Szybkie mno\
enie FAM 15
Szybkie mno\
enie
Akumulacja iloczynów częściowych w sumatorze CSA  poziom najwy\
szy
redukcja maksymalna drzewo Wallace a
A 9 8 7 6 5 4 3 2 1 0 A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o
o o o o o o o o o o
o o o o o o
o o
CSA, poziom 3  wejścia układów (3,2) lub (2,2)
A 9 8 7 6 5 4 3 2 1 0 A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o
o o o o o o o o o
CSA, poziom 3  wynik redukcji: wyjścia układów (3,2) lub (2,2)
© Janusz Biernat, Szybkie mno\
enie FAM 16
 Szybkie mno\
enie
Akumulacja iloczynów częściowych w sumatorze CSA  poziom pośredni
redukcja maksymalna drzewo Wallace a
A 9 8 7 6 5 4 3 2 1 0 A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o
CSA, poziom 2  wejścia układów (3,2) lub (2,2)
A 9 8 7 6 5 4 3 2 1 0 A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o
o o o o o o o o o o o o
CSA, poziom 2  wynik redukcji: wyjścia układów (3,2) lub (2,2)
© Janusz Biernat, Szybkie mno\
enie FAM 17
Szybkie mno\
enie
Akumulacja iloczynów częściowych w sumatorze CSA  poziom najni\
szy
redukcja maksymalna drzewo Wallace a
A 9 8 7 6 5 4 3 2 1 0 A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o
o o o o o o o o o o o o
CSA, poziom 1  wejścia układów (3,2)
A 9 8 7 6 5 4 3 2 1 0 A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o
CSA, poziom 1  wyjścia układów (3,2)
Redukcja 6 iloczynów częściowych: a) metoda maksymalnej redukcji na
ka\
dym poziomie (18FA+2HA), b) projektowanie zbie\
ne do drzewa Wallace a
(16FA+4HA)
© Janusz Biernat, Szybkie mno\
enie FAM 18
 Szybkie mno\
enie
Matrycowe układy mno\
Ä…ce  schemat mno\
enia
a4 a3 a2 a1 a0
x4 x3 x2 x1 x0
×
a4x0 a3x0 a2x0 a1x0 a0x0
+ a3x1 a2x1 a1x1 a0x1
a4x1 s41 s31 s21 s11
c41 c31 c21 c11
+ a3x2 a2x2 a1x2 a0x2
a4x2 s52 s42 s32 s22
c52 c42 c32 c22
+ a3x3 a2x3 a1x3 a0x3
a4x3 s63 s53 s43 s33
c63 c52 c42 c32
+ a3x3 a2x3 a1x3 a0x3
a4x3 s74 s64 s54 s44
+ c74 c64 c54 c44
s9 s8 s7 s6 s5 s4 s3 s2 s1 s0
sji oraz cji  sumy i przeniesienia na j-ej pozycji w i-tym kroku akumulacji
© Janusz Biernat, Szybkie mno\
enie FAM 19
Szybkie mno\
enie
Matryca mno\
Ä…ca kodu naturalnego (Brauna)
a4x0 a3x0 a2x0 a1x0 a0x0
CSA
a3x1 a2x1 a1x1 a0x1
HA HA HA HA
a4x1
CSA
a3x2 a2x2 a1x2 a0x2
FA FA FA FA
a4x2
a3x3 a2x3 a1x3 a0x3
FA FA FA FA
a4x3
CSA
a3x4 a2x4 a1x4 a0x4
FA FA FA FA
a4x4
FA FA FA HA
CPA
p9 p8 p7 p6 p5 p4 p3 p2 p1 p0
© Janusz Biernat, Szybkie mno\
enie FAM 20
 Szybkie mno\
enie
Multiplikator Brauna (Braun multiplier)
a4 a3 a2 a1 a0
x0
s0
x1
HA HA HA HA
s1
x2
FA FA FA FA
s2
x3
FA FA FA FA
s3
x4
FA FA FA FA
s4
FA FA FA HA
s9 s8 s7 s6 s5
© Janusz Biernat, Szybkie mno\
enie FAM 21
Szybkie mno\
enie
Matrycowe układy mno\
Ä…ce kodu U2
iloczyny częściowe lub iloczyny elementarne mogą być liczbami ujemnymi
m-2
öÅ‚
ëÅ‚- ak-12k-1 + k-2 2i öÅ‚
j
ìÅ‚- xj 2 =
÷Å‚
ìÅ‚ "a Å‚Å‚ Å" ëÅ‚ xm-12m-1 + "
÷Å‚
i
íÅ‚ i=0 j=0
íÅ‚ Å‚Å‚
m-2 k-2 m-2 k-2
ëÅ‚ öÅ‚
ëÅ‚-
j
= xm-1ak-12m+k-2 + xjai 2i+ j + ak-12k-1 xj 2 + xm-12m-1 i 2i öÅ‚.
ìÅ‚- ÷Å‚
÷Å‚
" " " ìÅ‚ "a Å‚Å‚
j=0 i=0 j=0 íÅ‚ i=0
íÅ‚ Å‚Å‚
" wagi operandów (1-bitowych iloczynów) mogą być ujemne
wystarczy zmienić znaki wag wejść i wyjść niektórych sumatorów
" zastąpienie sumatorów FA realizujących dodawanie x+y+z=2c+s
układami odejmującymi FS (x-y-z=-2c+s) lub FSD (x+y-z=2c-s)
" struktura logiczna FS i FSD identyczna
" przeciwne wagi wejść i wyjść, bo
x-y-z=-(z+y-x) oraz -(2c-s)=-2c+s
© Janusz Biernat, Szybkie mno\
enie FAM 22
 Szybkie mno\
enie
Matryca mno\
ąca kodu uzupełnieniowego
a4 a3 a2 a1 a0
x0
s0
x1
HS HA HA HA
s1
x2
FS FS FA FA
s2
x3
FS FS FS FA
s3
x4
FS FS FS FS
s4
FS FS FS HS
s9 s8 s7 s6 s5
("  wejścia o ujemnej wadze)
© Janusz Biernat, Szybkie mno\
enie FAM 23
Szybkie mno\
enie
Algorytm Baugha-Wooley a
Podstawienie:
k-2 k -2
- xm-12m-1 i 2i = xm-1ëÅ‚- 2k +m-2 + ai )2i+m-1 + 2m-1 öÅ‚,
"a ìÅ‚ "(1- ÷Å‚
i=0 íÅ‚ i=0 Å‚Å‚
m-2 m-2
ëÅ‚ öÅ‚
j j+k -1
- ak -12k -1 xj 2 = ak -1 2k +m-2 + x )2 + 2k -1 .
ìÅ‚- ÷Å‚
" "(1- j
j=0 j=0
íÅ‚ Å‚Å‚
korekcyjne dodawanie argumentów:
(1 ak 1) 2k+m 2+ak 1 2k 1
2k+m 1 + (1 xm 1) 2k+m 2+xm 1 2m 1
a4(1 x0) a3x0 a2x0 a1x0 a0x0
a4(1 x1) a3x1 a2x1 a1x1 a0x1
a4(1 x2) a3x2 a2x2 a1x2 a0x2
a4(1 x3) a3x3 a2x3 a1x3 a0x3
(1 a4) a4
1 (1 x3) x3
s8 s7 s6 s5 S4 s3 s2 s1 s0
© Janusz Biernat, Szybkie mno\
enie FAM 24
 Szybkie mno\
enie
Akumulacja iloczynów częściowych w kodzie U2
k-2 m-2
öÅ‚
j
ZastÄ…pienie ujemnych iloczynów w ëÅ‚- ak-12k-1 + 2i öÅ‚ Å" xm-12m-1 + xj 2
ìÅ‚- ÷Å‚
ìÅ‚ "a Å‚Å‚ ëÅ‚ "
÷Å‚
i
íÅ‚ i=0 j=0
íÅ‚ Å‚Å‚
k -2 k -2 k -2
- xm-12m-1 i 2i = - xm-12i+m-1 = -2k +m-2 + ai xm-1)2i+m-1 + 2m-1,
"a "a "(1-
i
i=0 i=0 i=0
m-2 m-2 m-2
j j+k -1 j+k -1
- ak -12k -1 x 2 = - x 2 = -2k +m-2 + ak -1x )2 + 2k -1,
" "a -1 j
"(1- j
j k
j=0 j=0 j=0
lub przekodowanie w celu eliminacji rozszerzeń:
k -2 m-2 k -2
ëÅ‚ öÅ‚
j i j
AÅ" X = -2m-1 ak -1xm-12k -1 + xm-12 + ìÅ‚- xi 2k -1 + xi 2 =
ìÅ‚- ÷Å‚ ÷Å‚
"a "2 ëÅ‚ ak -1 j
"a öÅ‚
j
j=0 i=0 j=0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
k-2 k-2 m-2 k-2
ëÅ‚
( -1) j j i ( (i) j
= 2m-1 akm1 2k-1 + ÷Å‚ ìÅ‚ ÷Å‚
ìÅ‚
"(1- a(jm-1))2 - "2 öÅ‚ + "2 ëÅ‚(1- aki)1)2k-1 + "a 2 - 2k-1 öÅ‚,
- - j
j=0 j=0 i=0 j=0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
gdzie a(ji) = a xi  j-ty bit i-tego iloczynu częściowego (aj lub 0 gdy xi=0) daje:
j
m-2 k -2 k -2
j ( j ) ( j) ( -1)
A X = ) 2k-1 + 2i üÅ‚ + 2m-1Å„Å‚akm1 2k-1 + ai(m-1) ) 2i +1üÅ‚ + 2k-1 - 2m+k-1
òÅ‚ "a żł òÅ‚ -
"2 Å„Å‚(1- ak -1 i
"(1- żł
j=0 ół i=0 þÅ‚ ół i=0 þÅ‚
© Janusz Biernat, Szybkie mno\
enie FAM 25
Szybkie mno\
enie
Schemat akumulacji
" negowanie bitów najwy\
szego iloczynu częściowego (dopełnianie),
" dodanie stałych korygujących 2m-1 i  2k +m-1 oraz 2k -1 (uzupełnianie)
1
1 0 0 0 1
o o o o o o o
f&
o o o o o o o
f&
o o o o o o o
f&
o o o o o o o
f&
(f& dopełnienie najbardziej znaczącego bita operandu, o  negacja bita)
" korygujÄ…ca  1 na pozycji m 1 (2m 1) Ò! s+1=2c++s* Ò! s*=1•"s, c+=s
" dodanie 2k 1  modyfikacja półsumatora pozycji k 1 w wierszu pierwszym
x+y+1=2c++s Ò! s = x •" y, c+ = x + y lub s = x •" y , c+ = x Å" y
" dodanie  2n+l 1  korekcja przeniesienia z najwy\
szej pozycji iloczynu ,
zgodnie z zale\
noÅ›ciÄ… c +1=2c++s, czyli c+=c oraz s=1•"c
" matryca kwadratowa (k=m)  (2k 1+2k 1=2k) Ò! korekcja na pozycji k
© Janusz Biernat, Szybkie mno\
enie FAM 26
 Szybkie mno\
enie
Matryca mno\
ąca kodu uzupełnieniowego
a4 a3 a2 a1 a0
x0
s0
x1
HA HA HA HA
s1
x2
FA FA FA FA
s2
x3
FA FA FA FA
s3
x4
FA FA FA FA
s4
FA FA FA FA
c9 s9 s8 s7 s6 s5
© Janusz Biernat, Szybkie mno\
enie FAM 27
Szybkie mno\
enie
Charakterystyki matryc mno\
Ä…cych
zło\
oność (mno\
nik m-bitowy, mno\
na k-bitowa)
" A=8(m 1)k (dodatkowa bramka AND na ka\
dy akumulowany bit)
" T=4(m 1)+TCPA(k) e"2(2m+logk 2)
podatność na przetwarzanie potokowe (pipelining)
" dla danej pary operandów w danej chwili jest wykonywane dodawanie
tylko na jednym poziomie układu matrycowego,
" na innych poziomach mo\
na w tym samym czasie wykonać wcześniejsze
lub póz
niejsze fazy mno\
enia innych par operandów
" niezbędne rozbudowanie o dodatkowe układy transmitujące wyniki
dodawania na mniej znaczących pozycjach oraz układ synchronizacji.
" przepustowość układu zale\
y od szybkości końcowego dodawania
w seryjnym mno\
eniu końcowy CPA jako kaskada CSA
szybkość bliska szybkości dodawania 1-bitowego!
" mo\
liwe zastosowanie algorytmu Bootha/McSorleya
© Janusz Biernat, Szybkie mno\
enie FAM 28