8. Sumatory.

Sumator jest to układ elektroniczny wykonujący dodawanie liczb binarnych. Sumatory są elementami jednostki arytmetyczno-logicznej (ALU) wchodzącej w skład procesora.

Operację dodawania można wykonać np. za pomocą bramek logicznych realizujących funkcje logiczne AND oraz OR. Pozwalają one wyznaczyć zarówno wartość bitu na danej pozycji (0 lub 1), jak i stwierdzić, czy zachodzi przeniesienie wartości, które należy uwzględnić przy ustaleniu wartości bitu na pozycji następnej - podobnie zresztą, jak to wykonujemy w rachunkach odręcznych. [5]

8.1. Sumatory jednobitowe.

Sumatory realizują sumę arytmetyczną dwu liczb binarnych. Dodanie dwu liczb dwójkowych (operandów) A i B ilustruje rys.8.1.

Ai	Bi	Si	Ci+1
0 0 1 1	0 1 0 1	0 1 1 0	0 0 0 1

Rys. 8.1. Suma S i przeniesienie C dodawania jednobitowych liczb dwójkowych A i B.

Zmienna S_i reprezentuje rezultat operacji, jej wartość jest sumą modulo 2 (exclusive OR) składników A_i, B_i i C_i. Zmienna Ci reprezentuje przeniesienie z pozycji młodszej sumatora wielopozycyjnego. C_i+1 jest przeniesieniem do pozycji starszej. C_i nie występuje w tzw. pólsumatorze, obecność C_i daje sumator pełny. Z wartości przedstawionych na rys. 8.1 można określić wyrażenia logiczne dla półsumatora:

1. suma S_i = A_i-B_i + ~A_iB_i = A_i (+) B_i,

2. przeniesienie C_i+1 = A_iB_i.

Zasada działania sumatora pełnego została opisana siatkami Karnaugha przedstawionymi na rysunku.8.2.

Rys. 8.2. Sumator dwuargumentowy jednobitowy: a) symbol, b) siatka zależności dla sumy, c) siatka zależności dla przeniesienia.

Z siatek tych otrzymujemy zależności:

1. suma S_i = C_i(A_iB_i + ~A_i~B_i) + ~C_i(A_i~B_i + ~A_iB_i)= Ci ~(A_i (+) B_i) + ~C_i(A_i (+) B_i) = C_i (+) B_i (+) A_i,

2. przeniesienie C_i+1 = A_iB_i + A_iC_i + B_iC_i.

Schemat sumatora pełnego (dwuargumentowego) z przeniesieniem z pozycji poprzedniej C_i oraz przeniesienie do pozycji wyższej C_i+1 przedstawiono na rys. 8.3a. Sumator jednobitowy pokazany na rys. 8.3b jest podstawową komórką występującą w sumatora średniej skali integracji: 480, 482 i 483.

Rys. 8.3. Schemat logiczny sumatora pełnego dwuargumentowego (a), jednobitowego (b).

Szczególnym przypadkiem sumatora jest układ realizujący odejmowanie dwu liczb dwójkowych. Wartości funkcji dla różnicy D i pożyczki V i-tej komórki sumatora odejmującego ilustruje tabela z rys. 8.4.

Pożyczka Vi	Odjemna Ai	Odjemnik Bi	Różnica Di	Pożyczka Vi+1
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 1 0 1 0 0 1	0 1 0 0 1 1 0 1

Rys. 8.4. Sumator jednobitowy odejmujący: a) symbol, b) siatka zależności, c) tabela zależności.

Z siatki zależności przedstawionej na rys. 8.4c znajdujemy wyrażenia logiczne dla sumatora odejmującego. Jak można zauważyć, różnica D_i jest identyczna z sumą S_i , natomiast różne są wyrażenia dla pożyczki V_i+1 i przeniesienia C_i+1. Jeśli jednak w wyrażeniach opisujących działanie sumatora odejmującego zamiast B_i wstawić ~B_i, a zamiast C_i wstawić ~V_i, otrzymujemy: C_i+1 = ~V_i+1, S_i=D_i.

Korzystając z tej własności, znajdujemy:

D_i = V_i (+)A_i(+)B_i,

~V_i+1=A_i~B_i + ~V_i(A_i+ ~B_i).

Sumator może być zatem stosowany jako układ odejmujący po dokonaniu powyższych przełączeń. [5]

8.2. Sumatory wielobitowe równoległe.

Ze względu na sposób wytwarzania przeniesień dzielimy je na:

a) sumatory z przeniesieniem szeregowym, zwane również sumatorami kaskadowymi albo iteracyjnymi,

b) sumatory z przeniesieniem równoległym.

Sumator kaskadowy n-bitowy jest układem powstałym przez połączenie n sumatorów jednobitowych. Schemat blokowy takiego sumatora przedstawiono na rys. 8.5. Przy sumowaniu liczb dodatnich wejście przeniesienia początkowego C₀ nie jest wykorzystywane (C₀=0).

Rys. 8.5. Schemat blokowy sumatora kaskadowego.

W sumatorze kaskadowym wszystkie cyfry dodawanych liczb dwójkowych podawane są na sumator jednocześnie. Czas uformowania się wyniku zależy od prędkości propagacji sygnału przeniesienia przez kolejne komórki sumatora. W najbardziej niekorzystnym przypadku sygnał C musi przejść przez wszystkie komórki sumatora. Czas sumowania można znacznie skrócić przez zastosowanie sumatora z równoległym przeniesieniem. Sumator z przeniesieniem równoległym generuje wszystkie wartości przeniesień jednocześnie na podstawie wartości na poszczególnych bitach obu operandów. Przeniesienie C_i+1 = A_iB_i + A_iC_i + B_iC_i = A_iB_i + (A_i+B_i)C_i można wyrazić w postaci: C_i+1= G_i+T_iC_i, gdzie: G_i=A_iB_i, T_i=A_i+B_i.

Dla modułu czterobitowego i <{0,1,2,3}:

C₄=G₃+T₃G₂+T₃T₂G₁+T₃T₂T₁G₀+T₃T₂T₁T₀ lub C₄ = G + TC₀,

gdzie G= G₃+T₃G₂+T₃T₂G₁+T₃T₂T₁G₀; T=T₃T₂T₁T₀,

gdzie:

G - przeniesienie generowane w bloku,

T - sygnał warunkujący transmisję przeniesienia początkowego C₀.

Wyrażenie dla sumy: S_i = A_i (+) B_i(+)C_i można przekształcić do postaci:

S_i = C_i(+)~(A_iB_i)(A_i+B_i)= C_i (+) ~G_iT_i.

Układy wielobitowe (nx4 bity) montuje się, wykorzystując powyższy sumator oraz expander, zwany generatorem przeniesień równoległych (4182). Ze względów praktycznych (minimalizacja struktury logicznej) zarówno w sumatorze, jak i generatorze przeniesień równoległych zamiast zmiennych G i T występują ich negacje ~G i ~T. Ze wzrostem ilości bitów przewaga sumatora z przeniesieniami równoległymi nad sumatorem z przeniesieniami kaskadowymi staje się coraz bardziej widoczna. Omówione wyżej sumatory mogą wykonywać oprócz operacji arytmetycznych również operacje logiczne. Sumator z przeniesieniami równoległymi jest zawarty w czterobitowym elemencie scalonym 4181, zwanym jednostką arytmetyczno-logiczną. [5]

8.3. Dodawanie i odejmowanie wielobitowe równoległe.

Operacji dodawania i odejmowania równoległego liczb wielobitowych dokonuje się za pomocą sumatorów wielobitowych. Dodawanie dwu liczb binarnych odbywa się przez dodanie poszczególnych pozycji binarnych, z uwzględnieniem przeniesienia z każdej pozycji. Przy zapisie binarnym liczb pozycja pierwsza jest znakiem liczby. Znak + oznacza się zerem, a znak - jedynką. Po bicie znaku następuje przecinek, a następnie zadana liczba binarna (przeniesienie z bitu znaku pominąć). Oto przykłady operacji dodawania:

+13 : 0,1101 +  2 : 0,0010 +15 : 0,1111

-13 : 1,01101 -  7 : 1,00111 - 20: 1,10100

Liczba pozycji sumatora jest określona na podstawie wyniku dodawania, nie może bowiem wystąpić jego przepełnienie. Podczas dyskusji odejmowania jednobitowego stwierdzono bardzo istotną zależność, że odejmowanie polega na dodawaniu negacji ( uzupełnienia do 1) odjemnika. Zasada ta jest również podstawą odejmowania wielobitowego. Operacje dodawania i odejmowania są zwykle realizowane w bloku arytmetycznym wykonującym też operacje mnożenia i dzielenia. W niniejszym rozdziale zostaną omówione trzy podstawowe algorytmy dodawania i odejmowania o różnym stopniu złożoności tych operacji. [2]

8.4. Dodawanie w zapisie "znak- moduł".

Operacje dodawania i odejmowania sprowadzono tu do operacji dodawania. Wyróżnia się trzy przypadki dodawania:

1. dodawanie liczb o jednakowych znakach:

+13 : 0,01101 +  7 : 0,00111 +20 : 0,10100

-13 : 1,01101 -  7 : 1,00111 -20 : 1,10100

2. dodawanie liczb o przeciwnych znakach; moduł dodajnej większy od modułu dodajnika:

I + 13 : 0,01101 -    7 : 1,00111 + 6

II -13 : 1,01101 + 7 : 0,00111 -  6

3. do modułu dodajnej dodajemy moduł uzupełnienia do 1 (negację) dodajnika

01101 11000 00101 00110

01101 11000 00101 1 00110

4. wynikowy dodawania przypisujemy znak dodajnej; otrzymujemy:

0,00110 : +6

1,00110 : -6

5. dodawanie liczb o przeciwnych znakach; moduł dodajnika większy od modułu dodajnej:

I +10 : 0,01010 -13 : 1,01101

II -10 : 1,01010 +13 : 0,01101

6. do modułu dodajnej dodajemy moduł uzupełnienia do 1 dodajnika, wynik otrzymuje znak dodajnika.

01010 10010 11100

01010 10010 11100

7. z braku przeniesienia cyklicznego otrzymany wynik należy uzupełnić do 1 i nadać znak dodajnika.

1,0011: -3

0,00011: +3

[2]

8.5.Dodawanie w zapisie "uzupełnień do 1"

różni się od poprzedniej metody tym, że wszystkie liczby ujemne są rejestrowane w zapisie "dopełnień do 1" i dodawane wraz z bitem znaku. W metodzie tej wyróżniono cztery przypadki:

1. dodawanie liczb dodatnich jest takie samo jak w poprzedniej metodzie;

2. dodawanie liczb ujemnych: liczby ujemne są przedstawione w zapisie "uzupełnień do 1" , dodawanie odbywa się wraz z bitem znaku:

-10: 1,10101 -13: 1,10010 1,00111 1 1,01000

dodajemy przeniesienie,

3. wynikiem ostatecznym jest uzupełnienie do 1 modułu otrzymanej liczby z zachowaniem znaku; dostajemy: 1,10111: -23

4. dodawanie liczb o przeciwnych znakach ( wynik dodatni) :

-10: 1,10101 +13: 0,01101 0,00010 1	Przeniesienie z pozycji znaku,
0,00011	: + 3

5. dodawanie liczb o przeciwnych znakach (wynik ujemny):

+10: 0,01010 -13: 1,10010 1,11100

6. Otrzymany wynik jest uzupełnieniem do 1 modułu otrzymanej liczby z zachowaniem znaku: 1,00011 : -3.

[2]

8.6. Dodawanie w zapisie " uzupełnień do 2".

Podczas dyskusji nad zasadami odejmowania jednobitowego stwierdzono bardzo istotną zależność, a mianowicie odejmowanie polega na dodaniu negacji odjemnika (~B_i). Drugi wniosek dotyczył pożyczki, a więc w miejsce przeniesienia Ci sumatora należy podać wartość ~V_i. Oznacza to, że pierwsza komórka sumatora w czasie odejmowania ma na wejściu Co jedynkę logiczną, czyli do najmniej znaczącej pozycji sumatora dodajemy wartość 1. Zasada ta została wykorzystana w algorytmie "uzupełnień do 2" . Liczby ujemne są zapisywane jako dopełnienie do 1 modułu plus 1 na pozycji najmniej znaczącej. Metoda ta sprowadza się właściwie do jednego przypadku: dodawania liczb z dowolnym znakiem. Liczby dodatnie są dodawane podobnie jak w poprzednich metodach. [2]

8.6.1. Liczby ujemne:

-10 : 1,10101 1 -10 : 1,10110 -13 : 1,10011 1,01001

: ~Vi

• bez dodawania przeniesienia cyklicznego. W przypadku gdy otrzymany wynik ma znak ujemny, odczyt wartości ostatecznej polega na uzupełnieniu do 2 modułu z zachowaniem znaku. Dostajemy: 1,10111: -23. [2]

8.6.2. Dodawanie liczb o różnych znakach:

+10 : 0,01010 -13 : 1,10011 1,11101		-10 : 1,10110 +13 : 0,01101 0,00011	: +3
Wynik ujemny: znajdujemy uzupełnienie do 2 modułu, otrzymamy: 1,00011 : -3		bez dodawania przeniesienia cyklicznego.

[2]

8.6.3. Porównanie zapisów.

W operacjach dodawania i odejmowania najprostszy jest zapis "uzupełnień do 2" ze względu na prostotę układów wykonujących te operacje. Pozostałe zapisy są mniej wygodne, przy czym zapis "znak-moduł" pozwala na prostą realizację operacji mnożenia i dzielenia. Z kolei zapis "uzupełnień do 2" jest przypadkiem pośrednim (kompromisowym). Wybór zapisu będzie oczywiście rzutował na konstrukcję układów wykonujących wspomniane operacje arytmetyczne. [2]

63

---