Sumatory CSA
Prawa ł czno ci i przemienno ci dodawania
a+b+c+d+e+f+g+h+i+& ={[(a+b)+(c+d)]+[(e+f)+(g+h)]}+{[(i+&
a+b+c+d+e+f+g+h+i+& =[(a+b+c)+(d+e+f)+(g+h+i)]+[(&
prawo ł czno ci dodawania w systemie pozycyjnym
k -1 k -1 k -1 k -1
i i i i
A + B + C + ... =
"a � + "b � + "c � + ... = "(a + bi + ci + ...)�
i i i i
i=-m i=-m i=-m i=-m
dodawanie wieloargumentowe jednopozycyjne  suma w systemie pozycyjnym
i 2 m i
(ai + bi + ci + ...)� = (ui(0) + �1ui(1) + � ui(2) + ...+ +� ui(m))�
" suma jest wielocyfrowa (co najmniej dwucyfrowa)
ł czno i przemienno dodawania w systemie pozycyjnym
k n-1 n-1 k n-1 m
(1) (2) (k ) ( p) i i ( p) i (r) r
X + X + ...+ X =
" "x � = "� "x = "� ("u � )
i i i-r
p=1 i=-q i=-q p=1 i=-q r=0

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 1
 Sumatory CSA
Dodawanie wieloargumentowe jednopozycyjne w systemach naturalnych
i 2 m i
(xi(1) + xi(2) + xi(3) + ...)� = (ui(0) + �1ui(1) + � ui(2) + ...+ � ui(m))�
przy tym xi( j ),ui( j ) "{0,1,...,� -1}
suma k składników mo e by m-cyfrowa
k k
( j ) m
0 d" xi( j ) d" � -1�!
"x d" "(� -1) = k(� -1) d" � -1
i
j=1 j=1
m =
�łlog [k(� -1) +1]łł
�
m m-1 m-2
k d" (� -1) /(� -1) = � + � + ...� +1 =11...11�
dodawanie mo na wykona dwuetapowo:
" obliczy wielopozycyjne sumy przej ciowe (w dowolnej kolejno ci)
" doda liczby wielocyfrowe skomponowane z sum przej ciowych
je li liczba składników jest d"�+1, to suma jest dwucyfrowa i wynosi
{vi+1,ui} = {r, xi(1) + xi(2) + ...+ xi(� +1) - r�} gdy 0 d" xi(1) + xi(2) + ...+ xi(� +1) - r� < �

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 2
 Sumatory CSA
Dodawanie wieloargumentowe w systemach naturalnych
je li liczba argumentów k>�+1, to dodawanie mo na wykona etapami
(0) (0) ak 1 ak 2 & a m+3 a m+2 a m+1 a m
(0) (0) bk 1 bk 2 & b m+3 b m+2 b m+1 b m
(0) (0) ck 1 ck 2 & c m+3 c m+2 c m+1 c m
(0) (0) dk 1 dk 2 & d m+3 d m+2 d m+1 d m
& & & & & & & & &
+ (0) (0) pk 1 pk 2 & p m+3 p m+2 p m+1 p m
& & & & & & & & &
& & & & & & & & &
(0) (0) (0) (0) (0) (0)
(0) (0) xk 1 xk 2 & x m+3 x m+2 x m+1 x m
(1) (1) (1) (1) (1) (1)
(0) xk 1 xk 2 & x m+3 x m+2 x m+1 x m (0)
(2) (2) (2) (2) (2) (2)
xk 1 xk 2 & x m+3 x m+2 x m+1 x m (0) (0)
+ & & & & & & & & &
(0) (0) (0) (0) (0) (0) (0) (0)
& uk+1 uk uk 1 uk 2 & u m+3 u m+2 u m+1 x m
(1) (1) (1) (1) (1) (1)
& uk uk 1 uk 2 & u m+3 u m+2 u m+1
(0) (0)
& sk sk sk 1 sk 2 s m+3 s m+2 u m+1 x m

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 3
>
+1
argumentów
d" +1
arg.
2 arg
 Sumatory CSA
Redukcja argumentów w drzewie CSA
sumator (k,m)  układ obliczaj cy m-pozycyjn sum k liczb jednocyfrowych
m =
�łlog [k(� -1) +1]łł
�
xi(1)xi(2) ... xi(k )xi(k +1).. xi(2k -m) xi(1) xi(2) ... xi(k ) xi(k +1).. xi(2k -m) xi(1) xi(2)
-1 -1 -1 -1 -1 -2 -2
(k,m) (k,m)
ui(m-1)
ui( m -1).. ui(1) ui(0) ui( m-1).. ui(1) ui(0)
-2
-1 -1 -1
ui(m-1) ui(m-1) ui(m-1)
-m+2 -m+1 -m
(k,m) (k,m)
Struktura redukcji argumentów w drzewie CSA zbudowanym z modułów (k,m)
k n-1 n-1 k n-1 m
(1) (2) (k ) ( p) i i ( p) i (r) r
X + X + ...+ X =
" "x � = "� "x = "� ("u � )
i i i-r
p=1 i=-q i=-q p=1 i=-q r=0

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 4
 Sumatory CSA
Redukcja argumentów w dwójkowym drzewie CSA
xi(1) xi(2) xi(3) xi(4) xi(5) xi(6) xi(1) xi(2) xi(3) xi(4) xi(5) xi(6) xi(1) xi(2) xi(3) xi(4) xi(5) xi(6)
+1 +1 +1 +1 +1 +1 -1 -1 -1 -1 -1 -1
(3,2) (3,2) (3,2) (3,2) (3,2) (3,2)
(3,2) (3,2) (3,2)
(3,2) (3,2) (3,2)
Skala redukcji operandów w wielopoziomowym dwójkowym drzewie CSA

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 5
 Sumatory CSA
Dwójkowe sumatory wieloargumentowe (CSA)
v3 x3 y3 z3 v2 x2 y2 z2 v1 x1 y1 z1 v0 x0 y0 z0
(3,2) (3,2) (3,2) (3,2)
(3,2) (3,2) (3,2) (2,2)
FA FA FA FA

sumator ko cowy
s5 s4 s3 s2 s1 s0
Czteropozycyjny sumator czterooperandowy CSA
czas dodawania = czas redukcji + czas dodawania ko cowego

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 6
reduktor
 Sumatory CSA
Sumowanie k dwójkowych operandów n-pozycyjnych (CSA)
Pojedynczy układ (3,2) redukuje dokładnie jeden operand 1-bitowy
do redukcji k operandów n-bitowych potrzeba n(k 2) układów (3,2)
kL operandów na poziomie L �! kL+1 d" kL + / 2
�łk �ł na poziomie L+1
L
" jeden poziom CSA redukuje 3 operandy do 2  skala redukcji 3/2
" dwa poziomy CSA redukuj 4 operandy do 2  skala redukcji 2
" trzy poziomy CSA redukuj 6 operandów do 2  skala redukcji 3 3
2( 2)L d" kL d" 2(3)L
2
(lepsza ocena) 2(3 3)L d" kL d" 2(3)L (Le"3)
2
Redukcja liczby operandów w wielopoziomowej strukturze CSA
liczba poziomów L 1 2 3 4 5 6 7 8 9 10
2(3/ 2)L
3 4 6 10 15 22 34 51 76 115
maksymalna liczba operandów 3 4 6 9 13 19 28 42 63 94
L
2�"(3 3)L E" 2�"1,44224957
3 5 6 9 13 18 26 38 54 78
L
2( 2)L E" 2�"1,41421356
3 4 6 8 12 16 23 32 46 65

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 7
 Sumatory CSA
Konstrukcja wielopoziomowego sumatora CSA (1)
Wytworzenie poprawnej sumy k argumentów n-bitowych (wyrównaj krótsze!)
wymaga k-krotnego rozszerzenia zakresu (logk dodatkowych bitów):
0 d" X1, X2,..., X d" 2n -1�! 0 d" X1 + X +...+ X d" k(2n -1) < 2n+log k -1
k 2 k
" oszacowanie szeroko ci: w = n +
�łlogkłł
" liczba elementów reduktora CSA: n(k 2)
k k
" oszacowanie gł boko ci: (log1,5)-1 log d" L d" 3(log3)-1(log
2 2)
" czas dodawania: T e" 4L + 2logn
Konstrukcja jest rekurencyjna (top-down lub bottom-up  drzewo Wallace a)
top-down (od góry)
1. przył cz po 3 sygnały wej ciowe o tej samej wadze do wej modułu (3,2)
2. sygnały nieprzył czone przeka na ni szy poziom CSA
3. wytwórz wyj cia wszystkich modułów (3,2) (lub (2,2))  maj ró ne wagi!
4. zbierz sygnały o tych samych wagach
5. powtarzaj 1 4 dopóki liczba sygnałów o jakiej wadze 2i przekracza 2.
6. doł cz sumator ko cowy (najlepiej szybki: CLA, PPA, COSA)

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 8
 Sumatory CSA
Schemat konstrukcji wielopoziomowego drzewa CSA (1)
przykład  7 argumentów 4-bitowych (w=3+3, L=4)



















































� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 9
 Sumatory CSA
Schemat konstrukcji wielopoziomowego drzewa CSA (2)













































































� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 10
 Sumatory CSA
Dwójkowe sumatory wieloargumentowe U2 (CSA)
Wytworzenie poprawnej sumy k argumentów n-bitowych (wyrównaj krótsze!)
wymaga k-krotnego rozszerzenia zakresu (logk dodatkowych bitów):
- 2n-1 d" X1, X2,..., X d" 2n-1 -1�! -2n+log k -1 d" X1 + X +...+ X < 2n+log k-1
k 2 k
Rozszerzenie zakresu o m=�łlog2kłł pozycji
" doł czenie m bitów rozszerzenia lewostronnego
o wada: wiele argumentów stałych (bity rozszerzenia)
o drzewo CSA (k+m)-bitowe
" zamiana argumentów na dodatnie z korekcj , zgodnie z zale no ci
k -2 k-2
- xk-12k-1 + = -2k-1 + (1- xk -1)2k-1 +
"x 2i "x 2i
i i
i=0 i=0
zakodowanie stałej -n2k-1 (na m+k bitach {rk+m-1,& ,rk-1,0,0,& ,0})
" znaczna redukcja liczby stałych bitów
" prostsze drzewo CSA

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 11
 Sumatory CSA
Zliczanie jedynek (lub zer) w słowie n-bitowym
(prawie) trzykrotna redukcja na I poziomie sumatora
" je li n=3k, to na II poziomie jest k operandów 2-bitowych
" je li n`"3k, to na II poziomie jest �łn/3łł operandów 2-bitowych
Parametry układu (bez 2-bitowego sumatora wyj ciowego)
" liczba modułów CSA  n 2
" liczba poziomów CSA  1+ liczba poziomów redukcji �łn/3łł operandów,
log / 3 -1 3(log / 3 -1)
�łn łł �łn łł
czyli +1 d" L d" +1
log3 -1 log3
" liczba bitów wyniku  log2n
zliczanie zer  liczba jedynek w słowie zanegowanym jest równa
liczbie zer w słowie oryginalnym
zliczanie wzorców bitowych  przekształcenie słowa wej ciowego przez funkcj
f(xi, xi+1,& , xi+p)=1 �! {xi, xi+1,& , xi+p}a"wzorzec
i zliczanie jedynek funkcji f

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 12
 Sumatory CSA
Alternatywne konstrukcje wielopoziomowego drzewa CSA*
od góry (top-down) od dołu (bottom-up)  drzewo Wallace a
liczba operandów struktura liczba operandów struktura
N = N0 L
(N0/3)"(3,2) kL-1 < N < kL (N-kL-1)"(3,2)+
(N0/3)"2+|N0|3=N1 (N1/3)"(3,2) L-1 kL-2 + �łkL-2 /2�ł = kL-1 �łkL-1/3�ł "(3,2)+|kL-1|3
& & & & & & & & &
2
(6/3)"2+0=4 1+1"(3,2) 3 + �ł3/2�ł = 4 = k2 �ł3/2�ł "(3,2)+1
1
(4/3)"2+1=3 1"(3,2) 2 + �ł3/2�ł = 3 = k1 �ł2/2�ł "(3,2)
redukcja od poziomu L, kumulacja operandów od poziomu 1
łatwiejsza konstrukcja drzewa
kL+1 = kL + / 2
0
�łk �ł, k = 2
L
L operandy struktura operandy struktura operandy struktura
7 21 27 20& 27
7"(3,2) 9"(3,2) 1& 8"(3,2)+&
6
7"2=14 2+4"(3,2) 9"2=18 6"(3,2) 8"2+3=19 6"(3,2)+1
5
4"2+2=10 1+3"(3,2) 6"2=12 4"(3,2) 6"2+1=13 4"(3,2)+1
4
3"2+1=7 1+2"(3,2) 4"2=8 2+2"(3,2) 4"2+1=9 3"(3,2)
3
2"2+1=5 2+1"(3,2) 2"2+2=6 2"(3,2) 2"3=6 2"(3,2)
2
1"2+2=4 1+1"(3,2) 2"2=4 1+1"(3,2) 2"2=4 1"(3,2)+1
1
1"2+1=3 1"(3,2) 1"2+1=3 1"(3,2) 1"2+1=3 1"(3,2)

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 13
 Sumatory CSA
Dwójkowy sumator CSA tylko z modułów (3,2) i (2,2)*
v3 x3 y3 z3 v2 x2 y2 z2 v1 x1 y1 z1 v0 x0 y0 z0
(3,2) (3,2) (3,2) (3,2)
(3,2) (3,2) (3,2) (2,2)
(2,2) (2,2) (2,2) (2,2)
(2,2) (2,2) (2,2)
(2,2) (2,2)
(2,2)
sumator

ko cowy
(~RCA)
s5 s4 s3 s2 s1 s0
Czteropozycyjny sumator czterooperandowy CSA

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 14
 Sumatory CSA
Sumatory (k,m) w systemach dwójkowych*
�=2 �! k d" 2m -1, m =
�łlog (k +1)łł
2
" elementarny sumator (3,2)  sumator 1-bitowy
" licznik (k,m)  binarny sumator (k,m)
o  koduje liczb jedynek z k wej na m wyj ciach
o  drzewo (3,2) lub projekt indywidualny, np. licznik (4,3)
u(0) = (x �" y) �" (z �" v)
u(1) = (x �" y)(z + v) + ( y �" z)(x + v) + (z �" v)(x + y)
u(2) = xyzv
" reduktor (k,2)  koduje liczb jedynek z k wej na 2 wyj ciach sumy
i pewnej liczbie wyj przeniesie (kumulacja przeniesie )
k>3 operandów wej ciowych �! redukcja w układzie wielopoziomowym
" kolumny reduktorów (k,2) o wagach 2i kumulacja przeniesie
" drzewo  gał zie liczników (3,2) o wagach 2i i redukcja przeniesie

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 15
 Sumatory CSA
Liczniki jedynek (k,m) i reduktory (k,2)*
xi(1)xi(2)xi(3) xi(4)xi(5)xi(6) xi(7) xi(1)xi(2)xi(3) xi(4)xi(5)xi(6) xi(7) xi(1)xi(2)xi(3)xi(4)
(3,2) (3,2) (3,2) (3,2) (4,3)
ci+2,i
ci+1,i ci,i 2
(3,2) (3,2)
ci,i 2
ci,i 1
ci,i 1
(3,2)
(3,2) (3,2) (3,2)
si+1 si
ci+2,i
si+1 si
si+2 si+1 si
ci+1,i
Licznik (7,3) Reduktor (7,2)
Reduktor (4,2)

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 16
 Sumatory CSA
Liczniki wielokolumnowe (ks-1,..., k1, k0 , m)*
Dodawanie operandów o rosn cych wagach (ki o wadze �i, i=0,1,& ,s)
suma na m pozycjach  wektor o l składowych:
 jednooperandowa s-pozycyjna suma o wadze 20 ,
 wielooperandowe przeniesienie wektorowe o wagach operandów (2s)i
Warunek zakodowania wyniku na m pozycjach
s-1
m i
� -1 e"
"k (� -1)�
i
i=0
s-1
w systemie dwójkowym2m -1 e" ki 2i
"
i=0
warunek realizowalno ci licznika (k, k, ..., k, m)
2m -1 e" k(2s -1)
md"2s �! suma k operandów s-pozycyjnych jest najwy ej 2-operandowa
22s -1 e" 2m -1 e" k(2s -1) �! k d" 2s +1

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 17
 Sumatory CSA
Parametry optymalnych liczników s-kolumnowych*
s 1 2 3 4 5 6 7
m=2s 2 4 6 8 10 12 14
k 3 5 9 17 33 65 129
2 +1 2i 3 +2 3 +1 3i
i i i
2 2 2 2 2
a) b)
t t t3 +2 t3 +1 t3i
2 +1 2i i i
i
u2 +1 u2i u3 +2 u3 +1 u3i
i i i
v2 +1 v v3 +2 v3 +1 v3i
i 2i i i
w3 +2 w3 +1
w2 +1 w2i w3i
i i i
x2 +1 x x3 +2 x3 +1 x
i 2i i i 3i
y2 +1 y y3 +2 y3 +1 y3i
i 2i i i
z z z3 +2 z3 +1 z3i
2 +1 2i i i
i
c2 +4 c2 +3 c2 +2 i c3 +4 c3 +3 s3 +2 i
s2 +1 s2i s3 +1 s3i
i i i i i i
2 +4 2 +3 2 +2 2 +1 2i
i i i i
i i i i
2 2 2 2 2 23 +4 23 +3 23 +2 23 +1 23i
Schemat dodawania w układach: a) (7,7,5), b) (7,7,7,5)

� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009 CSA 18
 Szybkie mno enie
rok 1. C||S/P �! (S/P) + xi(A)
Krok 2. C||S/P||X/P �! 2 1(C||S/P||X/P) = ShR(C||S/P||X/P)
Krok 3. i=i+1. Je li i < k+m, wró do kroku 1.
Wynik: A�"X=(S/P||X/P)
SHR (ײ-1)
S X A
P


Iloczyn cz ciowy
Schemat blokowy układu mno cego: S/P  rejestr sum cz ciowych,
X/P  rejestr mno nika, A  rejestr mno nej, C  rejestr przeniesienia
� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 1
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 2
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 3
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 4
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 5
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 6
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 7
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 8
 Szybkie mno enie
Matrycowe układy mno ce kodu U2
iloczyny cz ciowe lub iloczyny elementarne mog by liczbami ujemnymi
k-2 m-2
�ł
�ł
j
�" xm-12m-1 + xj 2 =
�ł- �ł
�ł- ak-12k-1 + i 2i �ł
"a �ł �ł "
�ł 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 2i �ł
�ł- �ł
�ł- �ł.
" " " "a łł
i
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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 9
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 10
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 11
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 12
 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=3(m 1)+TCPA(k)e" 3m+2logk 1
(odpowiednie ł czenie poziomów daje opó nienie 6 na dwóch poziomach)
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!
� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 13
 Szybkie mno enie
Optymalne ł czenie poziomów CSA w matrycy mno cej*
a2xi
a0xi
a1xi
c# s# c# s#
a1xi+1 a0xi+1
ci+1
opó nienie przez 2 poziomy  (2+4) lub (4+2), czyli zawsze 6
� Janusz Biernat, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 14
 Szybkie mno enie
Realizacja przekodowania Bootha-McSorleya w matrycy*
" mo liwe zastosowanie algorytmu 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 15
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 16
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 17
 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 (... AHX# oraz A#XH)
 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, AK1-8-09-Sumatory CSA i multyplikatory.doc FAM 18