Najlepsza odpowiedź
Tabele prawdy to tabela, która daje wynik funkcji boolowskiej dla dowolnej możliwej kombinacji wejścia. Sumator pełny to funkcja boolowska (lub element sprzętowy ją implementujący), która biorąc pod uwagę dwie 2-bitowe liczby całkowite, daje sumę tych liczb całkowitych, łącznie z przeniesieniem. (Półsumator dodaje tylko liczby, ale ignoruje przeniesienie). Jeśli masz dwie 2-bitowe liczby całkowite jako dane wejściowe, istnieje 16 możliwych danych wejściowych, więc Twoja tabela będzie miała 16 wierszy. Oto jak to może wyglądać, jeśli twoje dane wejściowe to a i b z bitami, wyjście to xabx 00 00 000 00 01 001 00 10 010 00 1 1 011 01 00 001 01 01 010 01 10011 01 11 100 11 00011 10 01 011 10 10 100 10 11 101 11 00 011 11 01 100 11 10 101 11 11 110
Odpowiedź
Prosta odpowiedź brzmi „cokolwiek projektant tego chce”.
Kiedy pod koniec lat siedemdziesiątych zacząłem zajmować się projektowaniem komputerów, miałem doświadczenie w matematyce i, w mniejszym stopniu, w programowaniu. Niektóre z wczesnych prac obejmowały projektowanie i wdrażanie zestawów instrukcji oraz w szczególności operacji arytmetycznych. Wszystko to wymagało ode mnie zrozumienia arytmetyki komputerowej, a ze względu na tło zrobiłem to z nieco abstrakcyjnego, matematycznego punktu widzenia. Było to w przeciwieństwie do tego, co zostało przedstawione w wielu podręcznikach do elektroniki i projektowania komputerów, które określają funkcje (np. sumatory) i ich implementację, ale nie zawsze dają motywację.
Motywacja Aby zaimplementować sumator, należy wziąć dwa zestawy bitów („słów”) reprezentujących liczby i wygenerować wynik reprezentujący sumę tych bitów. Należy zadać trzy kluczowe pytania. Po pierwsze, jakie liczby próbujemy przedstawić. Po drugie, jak te liczby są przedstawiane jako bity. I po trzecie, co powinno się stać, jeśli suma tych dwóch liczb nie może być reprezentowana jako zbiór bitów.
Typową sytuacją (N-bit, little endian, liczba całkowita bez znaku) jest to, że N-bitowe słowo reprezentuje liczby całkowite [0,2^N-1], , a słowo B[N-1]...B[0] reprezentuje wartość ΣB[i]2^i: i in [0,N-1]. Trzecie pytanie jest problemem – suma dwóch danych wejściowych może mieścić się w zakresie [0,2*(2^N-1)] , a więc są wyniki, których nie można przedstawić.
A prosta podręcznikowa implementacja „N-bitowego dodatku” buduje go z N „1-bitowych pełnych sumatorów”. Oprócz 2 zestawów N bitów operandu istnieje bit przeniesienia (wymuszony do zera) i bit przeniesienia. Jeśli matematyczny wynik dodawania można przedstawić, to N-bitowe wyniki sumatora będą poprawną reprezentacją wyniku, a wykonanie będzie równe 0. Jeśli, z drugiej strony, matematyczny wynik dodawanie nie może być reprezentowane, wtedy N-bitowe wyniki z sumatora będą poprawną reprezentacją wyniku modulo 2 ^ N, a wykonanie wyniesie 1. Podsumowując, sumator zawsze daje poprawny wynik modulo 2 ^ N i wykonanie wskazują, że poprawnego wyniku nie można przedstawić. Niektóre systemy komputerowe będą chciały traktować to jako błąd, być może zapisując go jako flagę lub powodując wyjątek.
Inną częstą sytuacją (N-bit, little endian, liczba całkowita dopełniająca do dwóch ze znakiem) jest to, że N-bitowe słowo reprezentuje liczby całkowite [-2^(N-1),2^(N-1)-1], , a słowo B[N-1]...B[0] reprezentuje wartość -B[N-1]*2^N + ΣB[i]2^i: i in [0,N-1]*. Znowu istnieją wyniki, których nie można przedstawić. Opisany wcześniej sumator wygenerował poprawny wynik dla wszystkich możliwych do przedstawienia wyników (dlatego użyto arytmetyki uzupełnień dwójki). Jednak przeprowadzenie nie wskazuje, czy wynik jest możliwy do przedstawienia. (Rozważmy -1 + 1 = 0, co daje wykonanie i 0 + 0 = 0, co nie daje). W przypadku dopełnienia do dwóch warunkiem, który reprezentuje wynik nieprzedstawialny (powszechnie nazywany „przepełnieniem”) jest to, że bit znaku (najbardziej znaczący bit) wyniku jest „nieoczekiwany” – to znaczy suma dwóch liczb ujemnych wydaje się być dodatnia lub suma dwóch liczb dodatnich wydaje się być ujemna (ćwiczenie dla czytelnika, aby pokazać, że zawsze można przedstawić sumę dwóch liczb różnych znaków).
Niektóre inne reprezentacje mogą używać tych samych sumatorów jako liczby całkowite ze znakiem i bez znaku. W przypadku reprezentacji ułamkowych, w których wartość słowa jest wartością słowa, traktowaną jako liczba całkowita, podzielona przez potęgę dwóch, sumator daje poprawny wynik, gdy wartość jest reprezentowalna. Jednak w systemach wykorzystujących te reprezentacje czasami pożądane zachowanie polega na tym, że wyniki „nasycają się” – to znaczy wynik jest poza zakresem, suma jest odpowiednio najbardziej dodatnią lub najbardziej ujemną wartością. Inne systemy 2 jedną z wartości (zazwyczaj 10… 0) do wykorzystania jako wartość błędu, która będzie następnie propagowana przez dalsze operacje. W takim przypadku potrzebny będzie specjalny dodatek.
* To sformułowanie wyraźnie określa formę uzupełnienia do dwóch – wartość słowa ze znakiem to wartość słowa bez znaku minus 2 ^ N razy górny bit (bit znaku). Równoważnie wartość można zapisać -B[N-1]*2^(N-1) + ΣB[i]2^i: i in [0,N-2], co odpowiada górnemu bitowi reprezentującemu 0 lub -1 zamiast 0 lub +1.