Półsumator (half adder) dodaje dwa bity A i B i daje sumę S oraz przeniesienie C. Sumator pełny (full adder) dodaje trzy bity: A, B oraz przeniesienie z poprzedniej pozycji Cin, i daje S oraz Cout. Dlatego półsumator wystarcza tylko na najmłodszym bicie liczby, a każdy wyższy bit wymaga sumatora pełnego. Z n sumatorów pełnych połączonych w szereg powstaje sumator n-bitowy, a jego szybkość ogranicza droga, którą przechodzi przeniesienie.
Półsumator: wzory i tabela prawdy
Suma jest funkcją XOR wejść, a przeniesienie funkcją AND: S = A ⊕ B, C = A · B. (Zapis „S = A + B” z wielu opisów oznacza tu dodawanie arytmetyczne, a nie sumę logiczną OR.)
| A | B | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Sumator pełny: wzory i tabela prawdy
Suma to parzystość trzech wejść: S = A ⊕ B ⊕ Cin. Przeniesienie powstaje, gdy co najmniej dwa z trzech wejść mają wartość 1: Cout = A·B + A·Cin + B·Cin. Ta sama funkcja zapisana inaczej, Cout = A·B + Cin·(A ⊕ B), pokazuje budowę z dwóch półsumatorów i bramki OR.
| A | B | Cin | S | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Kontrola arytmetyczna każdego wiersza: A + B + Cin = 2·Cout + S. Wiersz 1, 1, 1 daje 3 = 2·1 + 1, czyli S = 1 i Cout = 1. Obie tabele można odtworzyć skryptem z następnej sekcji.
Porównanie w skrócie
| Cecha | Półsumator | Sumator pełny |
|---|---|---|
| Wejścia | 2 (A, B) | 3 (A, B, Cin) |
| Wyjścia | S, C | S, Cout |
| Bramki (wersja podstawowa) | 1 XOR + 1 AND | 2 XOR + 2 AND + 1 OR |
| Bramki NAND 2-wejściowe (przykład poniżej) | 5 | 13 |
| Obsługa przeniesienia z niższego bitu | Nie | Tak |
| Rola w sumatorze wielobitowym | Tylko bit najmłodszy (lub budulec sumatora pełnego) | Każdy kolejny bit |
Oba układy są kombinacyjne: wyjścia zależą wyłącznie od bieżących wejść i nie ma w nich pamięci. Sumator pełny nie jest „lepszą wersją” półsumatora. Jest to układ do innego zadania.
Realizacja na bramkach NAND
Każdą funkcję logiczną można zbudować z samych bramek NAND. Półsumator wymaga pięciu: n1 = NAND(A,B), n2 = NAND(A,n1), n3 = NAND(B,n1), S = NAND(n2,n3), C = NAND(n1,n1) (negacja n1). Sumator pełny to dwa półsumatory i bramka OR złożona z trzech NAND (negacje obu przeniesień i NAND ich wyników): 5 + 5 + 3 = 13 bramek. Liczba bramek zależy od przyjętej topologii; ta wersja jest jedną z możliwych, nie najmniejszą.
Sprawdzenie jest mechaniczne. Poniższy kod w Pythonie przelicza obie tabele prawdy z wzorów, porównuje je z siecią NAND i sprawdza tożsamość A + B + Cin = 2·Cout + S:
from itertools import product
nand = lambda x, y: 1 - (x & y)
def ha(a, b):
n1 = nand(a, b)
s = nand(nand(a, n1), nand(b, n1))
return s, nand(n1, n1)
def fa(a, b, cin):
s1, c1 = ha(a, b)
s, c2 = ha(s1, cin)
return s, nand(nand(c1, c1), nand(c2, c2))
for a, b in product((0, 1), repeat=2):
assert ha(a, b) == (a ^ b, a & b)
for a, b, c in product((0, 1), repeat=3):
s, co = fa(a, b, c)
assert s == a ^ b ^ c
assert co == (a & b) | (a & c) | (b & c)
assert a + b + c == 2 * co + s
print("OK")
Dodawanie wielobitowe krok po kroku (przykład)
Dodajemy 1011₂ (11) i 0110₂ (6) w czterech sumatorach pełnych, od bitu najmłodszego, z Cin = 0 na wejściu pierwszego stopnia.
| Bit | A | B | Cin | S | Cout |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 1 | 0 | 1 |
| 3 | 1 | 0 | 1 | 0 | 1 |
Suma czterech bitów to 0001₂ z przeniesieniem wyjściowym 1, czyli 1 0001₂ = 17 = 11 + 6. Przeniesienie wyjściowe ostatniego stopnia jest bitem 4 wyniku albo sygnałem przepełnienia, jeśli wynik ma się zmieścić w czterech bitach.
Opóźnienie łańcucha przeniesień
W sumatorze z przeniesieniem szeregowym (ripple-carry) bit i czeka na Cout bitu i − 1. Cały wynik jest gotowy dopiero po przejściu przeniesienia przez wszystkie stopnie, więc czas rośnie liniowo z liczbą bitów.
Przykład założeniowy: wszystkie bramki mają to samo opóźnienie t, bramki mają dowolną liczbę wejść, a sygnały A, B i Cin pojawiają się w chwili 0. Wtedy P = A ⊕ B i G = A·B są gotowe po 1t, a przeniesienie Cout = G + P·Cin wymaga jeszcze AND i OR, czyli 2t od chwili, gdy Cin jest dostępne. Ostatni bit sumy S = P ⊕ C dochodzi o jedno t po przeniesieniu do niego.
| Liczba bitów n | Ripple-carry: ostatni bit sumy | Przeniesienie z blokami carry-lookahead 4-bitowymi: ostatni bit sumy |
|---|---|---|
| 4 | 8t | 4t |
| 8 | 16t | 7t |
| 16 | 32t | 11t |
| 32 | 64t | 19t |
| 64 | 128t | 35t |
Dla ripple-carry wynik to po prostu 2n·t. W wariancie z wyprzedzeniem każdy czterobitowy blok liczy swoje przeniesienia równolegle, a bloki łączy się szeregowo, co daje przy dużych n około 0,5t na bit zamiast 2t. To uproszczony model w jednostkach t. Rzeczywiste opóźnienie zależy od technologii, obciążenia wyjść, liczby wejść bramek (duże bramki są wolniejsze) i dokładnej struktury układu. Skalę czasu bierze się z karty katalogowej układu albo z analizy czasowej w narzędziu do syntezy.
Sumator z wyprzedzeniem (carry-lookahead)
Idea sprowadza się do dwóch sygnałów dla każdego bitu: G = A·B (bit sam generuje przeniesienie) i P = A ⊕ B (bit przenosi dalej przeniesienie z dołu). Wtedy dla czterech bitów C1 = G0 + P0·Cin, C2 = G1 + P1·G0 + P1·P0·Cin i tak dalej: wszystkie przeniesienia wynikają z dwóch poziomów bramek, bez czekania na poprzedni stopień. Płaci się liczbą bramek i większą liczbą wejść w bramkach. W gotowych układach scalonych spotyka się 4-bitowe sumatory z szybkim przeniesieniem (np. rodzina 74x283); konkretne czasy propagacji i napięcia zasilania trzeba brać z karty katalogowej wybranego układu.
Kiedy który układ i co z tego wynika dla płytki
- Półsumator bywa jedynym potrzebnym elementem przy zliczaniu (inkrementacja o 1, pierwszy bit sumy) i jako budulec sumatora pełnego.
- Sumator pełny jest podstawą każdego sumatora wielobitowego i jednostki arytmetyczno-logicznej.
- W praktyce dodawanie wykonuje procesor, układ FPGA albo gotowy układ scalony 4-bitowy. Samodzielne sumatory z pojedynczych bramek buduje się głównie dla nauki albo w prostej logice dyskretnej.
- Na płytce drukowanej rzeczywisty margines czasowy zależy też od opóźnień ścieżek i obciążeń wyjść. Jest to część analizy czasowej całej logiki, a nie samego sumatora.
Pomysł na układ cyfrowy przechodzi na płytkę przez przemyślany schemat, listę elementów i kontrolę reguł. Typowe błędy tego etapu opisujemy w artykule o projektowaniu niestandardowego układu PCB, a sposoby sprawdzania gotowej płytki w tekście o programowaniu i testowaniu PCB.
Czego nie zweryfikowano: czasów propagacji konkretnych układów scalonych, zużycia energii oraz liczby bramek po syntezie w konkretnym narzędziu. Tabele prawdy, sieć NAND i przykład 11 + 6 sprawdzono skryptem. Czasy w tabeli opóźnień pochodzą z modelu z jednakowymi bramkami i nie opisują rzeczywistego układu.


