Szybkie mno enie
Schematy przy pieszonego mno enia
x0 A x0 A
x1 A
x1 A
CSA
x2 A
x2 A
x3 A
CSA
x3 A
CSA
CSA
CPA
CPA
akumulacja równoległa akumulacja sekwencyjna
" akumulacja równoległa  drzewiasta struktura CSA,
" akumulacja sekwencyjna  liniowa struktura CSA, matryca mno ca
© Janusz Biernat, Szybkie mnozenie'04 FAM 1
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 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
matryca mno ca drzewo CSA
drzewo CSA
" szybka redukcja operandów w najdłu szej kolumnie
" redukcja do 1 operandów najni szych wag (krótsze ko cowe dodawanie)
© Janusz Biernat, Szybkie mnozenie'04 FAM 2
 Szybkie mno enie
Optymalizacja struktury CSA (1)
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 mnozenie'04 FAM 3
Szybkie mno enie
Optymalizacja struktury CSA (1)
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 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
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 o o o o o o o o o o o o o
© Janusz Biernat, Szybkie mnozenie'04 FAM 4
 Szybkie mno enie
Redukcja liczby iloczynów cz ciowych  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 mnozenie'04 FAM 5
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 mnozenie'04 FAM 6
 Szybkie mno enie
Algorytm Bootha
Uzasadnienie teoretyczne  równowa no X=2X-X
n-2 n-2 n-1
îÅ‚-
X = xn-12n + 2i+1Å‚Å‚ - xn-12n-1 + xi 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 mnozenie'04 FAM 7
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 mnozenie'04 FAM 8
 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 0 1 01 0 1 0 1 ).
© Janusz Biernat, Szybkie mnozenie'04 FAM 9
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 mnozenie'04 FAM 10
 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 działanie 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 mnozenie'04 FAM 11
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 mnozenie'04 FAM 12
 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 mnozenie'04 FAM 13
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 mnozenie'04 FAM 14
 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 pozycji j w i-tym kroku akumulacji
© Janusz Biernat, Szybkie mnozenie'04 FAM 15
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 mnozenie'04 FAM 16
 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 mnozenie'04 FAM 17
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 mnozenie'04 FAM 18
 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 mnozenie'04 FAM 19
Szybkie mno enie
Algorytm Baugha-Wooley a
zamiana ujemnych iloczynów cz ciowych na dodatnie:
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 -1
- ak -12k -1 j 2 = ak -1 - 2k +m-2 +
ìÅ‚
"x "(1- x )2 + 2k ÷Å‚.
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 mnozenie'04 FAM 20
 Szybkie mno enie
Akumulacja iloczynów cz ciowych w kodzie U2
i= p-2 i= p-2
Poniewa - zp-12p-1 + zi 2i = -2p-1 + (1- zp-1)2p-1 + zi 2i ,
" "
i=0 i=0
wi c ka dy iloczyn cz ciowy 2i xi A mo na zast pi przez:
j=m-2
j (
2i xi A = [(1- (xiam-1))2m-1 + (xiaj )2 ] = -2i+m-1 + 2i A+i)
"
j=0
Iloczyn mo na wi c obliczy jako (a(ji) = a xi = aj gdy xi =1; 0 gdy xi = 0):
j
k -2 m-2 k -2
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
j i j
AÅ" X = -2m-1 - ak -1xm-12k -1 + xm-12 + - ak -1xi 2k -1 + xi 2 =
ìÅ‚ ÷Å‚
"a "2 ìÅ‚ "a ÷Å‚
j j
j=0 i=0 j=0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
k-2 k-2 m-2 k-2
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
( j j i ( (i) j
= 2m-1 akm1-1) 2k-1 + - a(jm-1))2 - ÷Å‚
ìÅ‚
"(1 "2 Å‚Å‚ + "2 ìÅ‚(1- aki-)1)2k-1 + "a 2 - 2k-1 ÷Å‚,
- j
j=0 j=0 i=0 j=0
íÅ‚ íÅ‚ Å‚Å‚
Ostatecznie otrzymujemy:
k -2 m-2 k -2
Å„Å‚ üÅ‚ Å„Å‚ üÅ‚
( -1) j i ( ) -1 (i) j -1 -1
A X = 2m-1òÅ‚akm1 2k -1 + a(jm-1) )2 +1żł + 2 + 2k - 2m+k
òÅ‚(1- żł
- "(1- "2 aki-1)2k + "a j
j=0 i=0 j=0
ół þÅ‚ ół þÅ‚
czyli:
~( m-2
(
AX = -2m+k -1 + 2m-1(-A+m-1)) + 2i A+i) + 2k -1
"
i=0
© Janusz Biernat, Szybkie mnozenie'04 FAM 21
Szybkie mno enie
Konstrukcja matrycy mno cej
" negowanie bitów najwy szego iloczynu cz ciowego (dopełnianie),
" dodanie stałych koryguj cych 2k -1 i  2k +m-1 oraz 2m-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& negacja najbardziej znacz cego bita operandu, o  negacja bita)
" koryguj ca  1 na pozycji k 1 (2k 1) Ò! s+1=2c++s* Ò! s*=1•"s, c+=s
" dodanie 2m 1  modyfikacja półsumatora pozycji m 1 w pierwszej linii
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 mnozenie'04 FAM 22
 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 mnozenie'04 FAM 23
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ó 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 mnozenie'04 FAM 24
 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 ,
ìÅ‚ ÷Å‚ìÅ‚ ÷Å‚
" " " " " "
s j-i j-i
íÅ‚ 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 = xni+ j 2 .
"a 2 , Xi = "
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 mnozenie'04 FAM 25
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 X A1 X
1 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 mnozenie'04 FAM 26
 Szybkie mno enie
Mno enie wielokrotnej precyzji
Mno enie liczb dodatnich
" bezpo rednie zastosowanie schematu wyrównania
Mno enie długich liczb znakowanych (U2)
" najwy sze iloczyny (... A3X# oraz A#X3)
 mno enie liczby dodatniej przez znakowan !
 dodawanie dodatniej i znakowanej !
Rozwi zanie 1:
" przekodowanie na dodatnie (podobnie jak w mno eniu bez rozszerze )
" korekcja (podobnie jak w mno eniu bez rozszerze )
Rozwi zanie 2:
" przekodowanie na warto ci bezwzgl dne
" mno enie dodatnich i wytworzenie znaku
" przekodowanie iloczynu na kod uzupełnieniowy
© Janusz Biernat, Szybkie mnozenie'04 FAM 27
Szybkie mno enie
Mno enie U2  jeszcze inne przekodowanie
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 + x )2 + 2k -1,
" "a -1 j
"(1- ak -1 j
j k
j=0 j=0 j=0
© Janusz Biernat, Szybkie mnozenie'04 FAM 28