Sumator (elektronika) - Adder (electronics)

Sumator jest obwód cyfrowy , który wykonuje dodawanie liczb. W wielu komputerach i innych rodzajach procesorów sumatory są używane w jednostkach arytmetyczno-logicznych lub ALU . Są one również używane w innych częściach procesora, gdzie są używane do obliczania adresów , indeksów tabel, operatorów inkrementacji i dekrementacji i podobnych operacji.

Chociaż sumatory mogą być konstruowane dla wielu reprezentacji liczb , takich jak dziesiętne kodowane binarnie lub nadmiar-3 , najczęściej używane sumatory działają na liczbach binarnych . W przypadkach, gdy dopełnienie do dwójki lub dopełnienie do jedynek jest używane do reprezentowania liczb ujemnych , trywialne jest przekształcenie sumatora w sumator-odejmowanie . Inne podpisane reprezentacje liczb wymagają większej logiki wokół podstawowego sumatora.

Dodatki binarne

Połowa sumatora

Schemat logiczny pół sumatora

Połowa sumatora w akcji

Pół żmija dodaje dwa pojedyncze cyfr binarnych A i B . Posiada dwa wyjścia, sum ( S ) i carry ( C ). Sygnał przeniesienia reprezentuje przepełnienie do następnej cyfry dodawania wielocyfrowego. Wartość sumy wynosi 2 C + S . Najprostszy projekt półsumatora, przedstawiony po prawej, zawiera bramkę XOR dla S i bramkę AND dla C . Logika Boole'a dla sumy (w tym przypadku S ) będzie A′B + AB′ , podczas gdy dla przeniesienia ( C ) będzie AB . Po dodaniu bramki OR, aby połączyć ich wyjścia przenoszenia, można połączyć dwa połówkowe sumatory, aby utworzyć pełny sumator. Półsumator dodaje dwa bity wejściowe i generuje przeniesienie i sumę, które są dwoma wyjściami półsumatora. Zmienne wejściowe pół sumatora nazywane są bitami augend i addend. Zmienne wyjściowe to suma i przeniesienie. Tabeli prawdy dla pół żmija jest:

Wejścia		Wyjścia
A	b	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Połowa sumatora używająca wyłącznie bramek NAND.

Pełny sumator

Schemat logiczny pełnego sumatora.

Pełny sumator w akcji. Pełny sumator podaje liczbę 1s na wejściu w reprezentacji binarnej.

Schematyczny symbol 1-bitowego sumatora pełnego z C _w i C _się uwagę na stronach bloku podkreślić ich stosowanie w wielobitową sumatora

Pełny sumator zbudowany z dziewięciu bramek NAND.

Pełny sumator dodaje liczb binarnych i rachunków dla wartości przewożonych jak również na zewnątrz. Jednobitowy pełny sumator dodaje trzy jednobitowe liczby, często zapisywane jako A , B i C _w ; I B są to argumenty i C _w jest nieco wykonywane z poprzedniego mniej istotny etap. Pełny sumator jest zwykle składnikiem kaskady sumatorów, które dodają liczby binarne 8, 16, 32 itd. Obwód wytwarza dwubitowe wyjście. Wyjście sumy i przeniesienia zwykle reprezentowane przez sygnały C, _{na zewnątrz} i S , przy czym suma jest równa 2 C _wyjścia + S .

Pełny sumator można zaimplementować na wiele różnych sposobów, na przykład za pomocą niestandardowego obwodu tranzystorowego lub złożonego z innych bramek. Jednym z przykładów realizacji jest z S = A ⊕ B ⊕ C _w i C _z = ( A ⋅ B ) + ( C _w ⋅ ( ⊕ B )) .

W tej implementacji ostateczna bramka OR przed wyjściem wykonania może zostać zastąpiona bramką XOR bez zmiany wynikowej logiki. Używanie tylko dwóch typów bramek jest wygodne, jeśli obwód jest implementowany przy użyciu prostych układów scalonych, które zawierają tylko jeden typ bramki na układ.

NOR Pełny sumator

Pełną dodatek może być również wykonana z dwóch połówek sumatorów przez połączenie A i B z wejściem pół sumatora, a przy jego sumy wyjściowego S jako jeden z sygnałów wejściowych do drugiej połowy sumatora i C, _w co drugim wejściu i na koniec wyjścia przenoszenia z dwóch półsumatorów są połączone z bramką OR. Wyjście sumy z drugiej połowy sumatora jest końcowym wyjściem sumy ( S ) pełnego sumatora, a wyjście z bramki OR jest końcowym wyjściem przeniesienia ( C _out ). Ścieżka krytyczna pełnego sumatora biegnie przez obu bramek XOR i kończy w sumie nieco s . Zakładając, że bramka XOR potrzebuje 1 opóźnienia do ukończenia, opóźnienie narzucone przez ścieżkę krytyczną pełnego sumatora jest równe

${\ Displaystyle T_ {\ tekst {FA}} = 2 \ cdot T_ {\ tekst {XOR}} = 2D.}$

Ścieżka krytyczna przeniesienia przebiega przez jedną bramkę XOR w sumatorze i przez 2 bramki (AND i OR) w bloku przenoszenia, a zatem, jeśli bramki AND lub OR trwają 1 opóźnienie, ma opóźnienie wynoszące

${\ Displaystyle T_ {\ tekst {c}} = T_ {\ tekst {XOR}} + T_ {\ tekst {AND}} + T_ {\ tekst {OR}} = D + D + D = 3D.}$

Pełny sumator można zaimplementować za pomocą dziewięciu bramek NAND .

Tabeli prawdy dla pełnego sumatora jest:

Wejścia			Wyjścia
A	b	C w	C out	S
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Odwracanie wszystkich wejść pełnego sumatora odwraca również wszystkie jego wyjścia, co można wykorzystać w projektowaniu szybkich sumatorów z przenoszeniem tętnień, ponieważ nie ma potrzeby odwracania przeniesienia

Przykład pełnego sumatora z odwróconymi wyjściami w CMOS

Sumatory obsługujące wiele bitów

Dodatek do przenoszenia tętnienia

4-bitowy sumator z pokazanym logicznym schematem blokowym

Dziesiętny 4-cyfrowy sumator przenoszenia tętnienia. FA = sumator pełny, HA = sumator połówkowy.

Możliwe jest stworzenie układu logicznego przy użyciu wielu pełnych sumatorów do dodawania liczb N- bitowych. Każdy pełny sumator wejścia na C _w , którym jest C _z poprzedniego sumatora. Ten rodzaj sumatora nazywany jest sumatorem ripple-carry (RCA), ponieważ każdy bit przenoszenia „ marszczy ” do następnego pełnego sumatora. Zauważ, że pierwszy (i tylko pierwszy) pełny sumator może być zastąpiony przez sumator połówkowy (przy założeniu, że C _in = 0).

Układ sumatora ripple-carry jest prosty, co pozwala na szybki czas projektowania; jednakże sumator przenoszący tętnienia jest stosunkowo wolny, ponieważ każdy pełny sumator musi czekać na obliczenie bitu przenoszenia z poprzedniego pełnego sumatora. Opóźnienie brama może być łatwo obliczona poprzez kontrolę pełnego obwodu sumującego. Każdy pełny sumator wymaga trzech poziomów logiki. W 32-bitowym sumatorze ripple-carry są 32 pełne sumatory, więc opóźnienie ścieżki krytycznej (najgorszy przypadek) wynosi 3 (od wejścia do przeniesienia w pierwszym sumatorze) + 31 × 2 (dla propagacji przeniesienia w ostatnich sumatorach) = 65 opóźnienia bram. Ogólne równanie dla najgorszego przypadku opóźnienia dla n -bitowego sumatora tętnienia przenoszenia, uwzględniającego zarówno bity sumy, jak i bity przeniesienia, jest

${\ Displaystyle T_ {\ tekst {CRA}} (n) = T_ {\ tekst {HA}} + (n-1) \ cdot T_ {\ tekst {c}} + T_ {\ tekst {s}} = T_ {\text{FA}}+(n-1)\cdot T_{c}=3D+(n-1)\cdot 2D=(2n+1)\cdot D.}$

Konstrukcja ze zmienną polaryzacją przenoszenia i zoptymalizowanymi bramkami AND-OR-Invert może być około dwa razy szybsza.

4-bitowy sumator z wyprzedzaniem przeniesienia

Dodatek do przenoszenia z wyprzedzeniem

Aby skrócić czas obliczeń, inżynierowie opracowali szybsze sposoby dodawania dwóch liczb binarnych za pomocą sumatorów typu carry-lookahead (CLA). Działają, tworząc dwa sygnały ( P i G ) dla każdej pozycji bitowej, w oparciu o to, czy przeniesienie jest propagowane z mniej znaczącej pozycji bitowej (co najmniej jedno wejście to 1), generowane w tej pozycji bitowej (oba wejścia mają wartość 1 ) lub zabity w tej pozycji bitowej (oba wejścia mają wartość 0). W większości przypadków P jest po prostu sumą wyjściową pół sumatora, a G jest wyjściem przenoszenia tego samego sumatora. Po wygenerowaniu P i G tworzone są przeniesienia dla każdej pozycji bitowej. Niektóre zaawansowane architektury typu carry-lookahead to łańcuch przenoszenia Manchester , sumator Brent-Kung (BKA) i sumator Kogge-Stone (KSA).

Niektóre inne wielobitowe architektury sumatorów dzielą sumator na bloki. Istnieje możliwość zmiany długości tych bloków w oparciu o opóźnienie propagacji obwodów w celu optymalizacji czasu obliczeń. Te sumatory oparte na blokach obejmują sumator przeniesienia (lub pomijania przeniesienia), który określi wartości P i G dla każdego bloku, a nie dla każdego bitu, oraz sumator wyboru przeniesienia, który wstępnie generuje sumę i wartości przeniesienia dla każdego możliwego przeniesienia wejście (0 lub 1) do bloku, używając multiplekserów do wyboru odpowiedniego wyniku, gdy znany jest bit przeniesienia.

64-bitowy dodatek

Łącząc wiele sumatorów typu carry-lookahead, można tworzyć nawet większe sumatory. Może to być używane na wielu poziomach, aby tworzyć jeszcze większe sumatory. Na przykład następujący sumator jest sumatorem 64-bitowym, który wykorzystuje cztery 16-bitowe CLA z dwoma poziomami jednostek przenoszących z wyprzedzeniem .

Inne konstrukcje Adder zawierać dodatek carry-select , warunkowe sumy dodatek , carry-pomijania sumator i wykonać uzupełnianie dodatek.

Przenoś i oszczędzaj sumatory

Jeśli obwód sumujący ma obliczyć sumę trzech lub więcej liczb, może być korzystne, aby nie propagować wyniku przeniesienia. Zamiast tego używane są sumatory z trzema wejściami, generujące dwa wyniki: sumę i przeniesienie. Suma i przeniesienie mogą być wprowadzone na dwa wejścia kolejnego sumatora 3-liczbowego bez konieczności oczekiwania na propagację sygnału przeniesienia. Jednak po wszystkich etapach dodawania należy użyć konwencjonalnego sumatora (takiego jak ripple-carry lub lookahead), aby połączyć końcową sumę i wyniki przeniesienia.

Kompresory 3:2

Pełny sumator może być postrzegany jako kompresor stratny 3:2 : sumuje trzy wejścia jednobitowe i zwraca wynik jako pojedynczą liczbę dwubitową; oznacza to, że mapuje 8 wartości wejściowych na 4 wartości wyjściowe. Na przykład wejście binarne o wartości 101 daje wynik 1 + 0 + 1 = 10 (liczba dziesiętna 2). Wykonanie reprezentuje pierwszy bit wyniku, podczas gdy suma reprezentuje bit zero. Podobnie, półsumator może być używany jako kompresor stratny 2:2 , kompresując cztery możliwe wejścia do trzech możliwych wyjść.

Takie kompresory można wykorzystać do przyspieszenia sumowania trzech lub więcej dodatków. Jeśli dodatki mają dokładnie trzy, układ jest znany jako addend z zachowaniem przeniesienia . Jeśli są cztery lub więcej dodatków, potrzebna jest więcej niż jedna warstwa kompresorów i istnieją różne możliwe projekty obwodu: najczęściej spotykane są drzewa Dadda i Wallace . Ten rodzaj obwodu jest najczęściej używany w mnożnikach , dlatego obwody te są również znane jako mnożniki Dadda i Wallace.

Pełny sumator kwantowy

Quantum Pełna Adder, używając Toffoli i CNOT bramy. Bramka CNOT otoczona kropkowanym kwadratem na tym rysunku może zostać pominięta, jeśli nie jest wymagane nieobliczanie w celu przywrócenia wyjścia B.

Przy użyciu jedynie Toffoli i CNOT logicznych kwantową bramek , jest możliwe wytwarzanie obwodów kwantowej wykonuje dodatkowo.

Ten sam obwód może być również używany w klasycznych obliczeniach odwracalnych .

Zobacz też

• Mnożnik binarny
• Odejmowanie
• Mikser elektroniczny — do dodawania sygnałów analogowych

Bibliografia

Dalsza lektura

• Liu, Tso-Kai; Hohulin, Keith R.; Shiau, Lih-Er; Muroga, Saburo (styczeń 1974). „Optymalne jednobitowe pełne sumatory z różnymi typami bramek”. Transakcje IEEE na komputerach . Laboratoria Bell: IEEE . C-23 (1): 63-70. doi : 10.1109/TC.1974.223778 . ISSN  0018-9340 . S2CID  7746693 .
• Lai, Hung Chi; Muroga, Saburo (wrzesień 1979). „Minimalne binarne sumatory równoległe z bramkami NOR (NAND)”. Transakcje IEEE na komputerach . IEEE . C-28 (9): 648-659. doi : 10.1109/TC.1979.1675433 . S2CID  23026844 .
• Miód pitny, rzeźbiarz; Conway, Lynn (1980) [grudzień 1979]. Wprowadzenie do systemów VLSI (1 wyd.). Czytanie, MA, USA: Addison-Wesley . Kod Bibcode : 1980aw...książka.....M . Numer ISBN 978-0-20104358-7. Źródło 2018-05-12 .
• Davio, Marc; Dechamps, Jean-Pierre; Thayse, André (1983). Systemy cyfrowe z implementacją algorytmu (1 wyd.). Laboratorium Badawcze Philipsa , Bruksela, Belgia: John Wiley & Sons , publikacja Wiley-Interscience. Numer ISBN 978-0-471-10413-1. LCCN  82-2710 .

Zewnętrzne linki

• Algorytmy sprzętowe dla modułów arytmetycznych zawierają opis kilku układów sumatorów z liczbami.
• 8-bitowy pełny dodatek i odejmowanie , demonstracja interaktywnego pełnego dodawania wbudowanego w JavaScript wyłącznie do celów edukacyjnych.
• Interaktywna symulacja pełnego dodawania (wymaga Java), interaktywny obwód pełnego dodawania zbudowany z symulatora obwodów online Teahlab.
• Interaktywna symulacja Half Adder (wymaga Java), obwód Half Adder zbudowany na symulatorze obwodów Teahlab.
• 4-bitowa symulacja pełnego dodawania wbudowana w Verilog i towarzyszący jej samouczek wideo Ripple Carry Full Adder
• Shirriff, Ken (listopad 2020). „Inżynieria odwrotna obwodu carry-lookahead w procesorze Intel 8008” .