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 + ... = ² + ² + ² + ... = + bi + ci + ...)²
"a "b "c "(a
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 = ² = = ² )
" "xi "² "xi "² ("ui
p=1 i=-q i=-q p=1 i=-q r=0
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 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Ò! d" -1) = k(² -1) d" ² -1
"xi "(²
j=1 j=1
m = [k(² -1) +1]
îÅ‚log Å‚Å‚
²
m m-1 m-2
k d" (² -1) /(² -1) = ² + ² + ...² +1 =11...11²
jeÅ›li liczba skÅ‚adników jest d"²+1, 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, Sumatory CSA, 9 stycznia 2004 CSA 2
 Sumatory CSA
Dodawanie wieloargumentowe wielopozycyjne w systemach naturalnych
dodawanie mo\
na wykonać dwuetapowo:
" obliczyć wielopozycyjne sumy przejściowe na ka\
dej pozycji
(w dowolnej kolejności  są niezale\
ne)
" dodać liczby wielocyfrowe skomponowane z sum przejściowych
jeÅ›li liczba argumentów kd"²+1 (11²) sumy przejÅ›ciowe sÄ… dwucyfrowe
(0) xk 1 xk 2 & x m+3 x m+2 x m+1 x m
(0) yk 1 yk 2 & y m+3 y m+2 y m+1 y m
& & & & & & & &
(0) zk 1 zk 2 & z m+3 z m+2 z m+1 z m
Ä…
(0) uk 1 uk 2 u m+3 u m+2 u m+1 u m
vk vk 1 vk 2 v m+3 v m+2 v m+1
sk sk 1 sk 2 s m+3 s m+2 s m+1 s m
jeÅ›li liczba argumentów k>²+1 (11²)
dodawanie mo\
na wykonać rekurencyjnie
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 CSA 3
Sumatory CSA
Dodawanie wieloargumentowe wielopozycyjne w systemach naturalnych
jeÅ›li liczba argumentów k>²+1 (11²)
dodawanie mo\
na wykonać rekurencyjnie
(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, Sumatory CSA, 9 stycznia 2004 CSA 4
 Sumatory CSA
Sumatory przechowujÄ…ce przeniesienie (CSA)
sumator (k,m)  układ obliczający m-pozycyjną sumę k liczb jednocyfrowych
(m = [k(² -1) +1]
îÅ‚log Å‚Å‚)
²
1) 2) k k +1) 2k 1 2)
xi(1)xi(2) ... xi(k )xi(k +1).. xi(2k -m) xi(-1 xi(-1 ... xi(-1) xi(-1 .. xi(-1 -m) xi(-) xi(-2
2
(k,m) (k,m)
m
m 1) 0
ui(-2-1)
ui(m -1).. ui(1) ui(0) ui(-1-1).. ui(-1 ui(-1)
m-1 m-1) m-1)
ui(-m+) ui(-m+1 ui(-m
2
(k,m) (k,m)
k n-1 n-1 k n-1 m
(1) (2) (k ) ( p) i i ( p) i (r ) r
X + X + ...+ X = ² = = ² )
" "xi "² "xi "² ("ui
p=1 i=-q i=-q p=1 i=-q r=0
Struktura sumatora CSA zbudowanego z sumatorów (k,m)
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 CSA 5
Sumatory CSA
Struktura dwójkowych sumatorów CSA
1) 2) 3) 4) 5) 6) 1) 2) 3) 4) 5) 6)
xi(+1 xi(+1 xi(+1 xi(+1 xi(+1 xi(+1 xi(1) xi(2) xi(3) xi(4) xi(5) xi(6) xi(-1 xi(-1 xi(-1 xi(-1 xi(-1 xi(-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 drzewie CSA
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 CSA 6
 Sumatory CSA
Sumatory (k,m) w systemach dwójkowych
²=2 Ò! k d" 2m -1, m = (k + 1)
îÅ‚log Å‚Å‚
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, Sumatory CSA, 9 stycznia 2004 CSA 7
Sumatory CSA
Liczniki (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, Sumatory CSA, 9 stycznia 2004 CSA 8
 Sumatory CSA
Sumowanie k 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)
na poziomie L kL operandów Ò! na poziomie (L+1) kL+1 d" kL + / 2
ðÅ‚k ûÅ‚
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
2Å"(3 3)L E" 2Å"1,44224957L
3 5 6 9 13 18 26 38 54 78
2Å"( 2)L E" 2Å"1,41421356L
3 4 6 8 12 16 23 32 46 65
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 CSA 9
Sumatory CSA
Konstrukcja wielopoziomowego sumatora 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, Sumatory CSA, 9 stycznia 2004 CSA 10
 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
s5 s4 s3 s2 s1 s0
Czteropozycyjny sumator czterooperandowy CSA
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 CSA 11
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)
(2,2) (2,2) (2,2) (2,2)
(2,2) (2,2) (2,2)
(2,2) (2,2) (2,2)
(2,2) (2,2)
(2,2)
s5 s4 s3 s2 s1 s0
Czteropozycyjny sumator czterooperandowy CSA
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 CSA 12
 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" (² -1)²
"k
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, Sumatory CSA, 9 stycznia 2004 CSA 13
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 i +1 2i 3 +2 3 i +1 3i
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
w2 +1 w2i w3 +2 w3 +1 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 i +2 s2 i +1 s2i c3 +4 c3 +3 s3 i +2 s3 +1 s3i
i i i i i
2 +4 2 +3 2 +2 2 +1 2i
i i i i
i i i
2 2 2 2 2 23 +4 23 +3 23 i +2 23 +1 23i
Schemat dodawania w układach: a) (7,7,5), b) (7,7,7,5)
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 CSA 14
 Sumatory CSA
Dwójkowe sumatory wieloargumentowe U2 (CSA)
Rozszerzenie zakresu stosownie do liczby argumentów  o m=îÅ‚log2nÅ‚Å‚ 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 + 2i = -2k-1 + (1- xk -1)2k-1 + 2i
"xi "xi
i=0 i=0
zakodowanie stałej -n2k-1 (na m+k bitach {rk+m-1,& ,rk-1,0,0,& ,0})
o redukcja stałych bitów
o prostsze drzewo CSA
© Janusz Biernat, Sumatory CSA, 9 stycznia 2004 CSA 15