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.)

ABSC
0000
0110
1010
1101

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.

ABCinSCout
00000
00110
01010
01101
10010
10101
11001
11111

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

CechaPółsumatorSumator pełny
Wejścia2 (A, B)3 (A, B, Cin)
WyjściaS, CS, Cout
Bramki (wersja podstawowa)1 XOR + 1 AND2 XOR + 2 AND + 1 OR
Bramki NAND 2-wejściowe (przykład poniżej)513
Obsługa przeniesienia z niższego bituNieTak
Rola w sumatorze wielobitowymTylko 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.

BitABCinSCout
010010
111001
201101
310101

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 nRipple-carry: ostatni bit sumyPrzeniesienie z blokami carry-lookahead 4-bitowymi: ostatni bit sumy
48t4t
816t7t
1632t11t
3264t19t
64128t35t

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.