Układy logiczne

Zaczniemy omawianie sumatorów od półsumatora, układu, który dodaje 2 bity bez uwzględnienia przeniesienia z poprzedniej pozycji.

Układ dodający 2 bity powinien mieć 2 wyjścia: wyjście sumy $s$ i wyjście przeniesienia $c$. Łatwo zauważyć, że układ półsumatora opisują 2 funkcje boolowskie $s=a\oplus b$ oraz $c=a\cdot b$, gdzie $s$ jest sumą a $c$ przeniesieniem. Układ realizujący półsumator pokazany jest na rys. 20.

Rys 1. Układ realizujący półsumator $s=a\oplus b$ (bit sumy), $c=a\cdot b$ (bit przeniesienia)

Sumator jednobitowy pełny to układ kombinacyjny dodający 2 bity z uwzględnieniem przeniesień. Sumator jednobitowy pełny ma 3 wejścia ($a_i$, $b_i$ - bity sumowane oraz $c_i$ przeniesienie z poprzedniej pozycji) oraz 2 wyjścia: wyjście sumy $s_i$ i wyjście przeniesienia na następną pozycję $c_{i+1}$. Łatwo zauważyć, że układ sumatora opisują 2 funkcje boolowskie

$s_i=a_i\oplus b_i\oplus c_i$ oraz $c_{i+1}=a_i\cdot b_i+(a_i+b_i)\cdot c_i$,

gdzie $s_i$ jest sumą, $c_{i+1}$ przeniesieniem na pozycję $i+1$ a $c_i$ przeniesieniem. na pozycję $i$. Układ realizujący sumator jednobitowy pełny pokazany jest na rys 2. Jeśli czas opóźnienia bramki oznaczymy przez $\Delta t$ to czas po którym uzyskujemy w tym układzie poprawny bit sumy to $2\Delta t$. Poprawny bit przeniesienia uzyskujemy po czasie $3\Delta t$.

Rys. 2. Układ realizujący jednobitowy sumator pełny

Sumator równoległy jest układem kombinacyjnym o strukturze pokazanej na rys. 3. Dodajemy 2 liczby $a$ i $b$ w zapisie NKB (o stałej długości $n+1$ słowa kodowego). Liczby dodawane $a$ i $b$ reprezentowane są słowami binarnymi

$a=a_n a_{n-1}...a_1a_0$ i $b=b_n b_{n-1}...b_1b_0$

Suma $s=a+b$ reprezentowana jest słowem $s_n s_{n-1}...s_1s_0$. Współpracujące ze sobą sumatory pełne realizują na kolejnych pozycjach słowa dodawanie $a_i+b_i$ (z uwzględnieniem przeniesień) a więc $s_i=a_i \oplus b_i \oplus c_i$ oraz $c_{i+1}=a_i\cdot b_i+(a_i+b_i)\cdot c_i$. Warto zauważyć, że słowo wyniku sumowania $s_n s_{n-1}...s_1s_0$ (odczytywane w $n+1$ bitowym w kodzie NKB) jest równe liczbie $s=a+b$ wtedy i tylko wtedy gdy $c_{n+1}=0$. Jeśli $c_{n+1}=1$ to mówimy, że wystąpił nadmiar przy dodawaniu w kodzie NKB. W typowych mikroprocesorach pojawienie się $c_{n+1}=1$ jest zapamiętywane, powoduje ustawienie przerzutnika znacznika przeniesienia CF (ang. carry flag) na 1. Oczywiście słowo $n+2$ bitowe $c_{n+1}s_ns_{n-1}...s_1s_0$ zawsze reprezentuje poprawnie w kodzie NKB ($n+2$ bitowym) liczbę $s$.

Rys. 3. Sumator równoległy zbudowany z jednobitowych sumatorów pełnych

Ogólnie rzecz biorąc w systemach cyfrowych słowa binarne możemy przetwarzać równolegle (tak jest szybciej) lub szeregowo czyli bit po bicie (tak jest oszczędniej tzn. mniejsza ilość 2
bramek jest potrzebna do realizacji układu).

Sumator szeregowy jest typowym układem z szeregowym przetwarzaniem informacji. Schemat układu pokazany jest na rys. 4. Układ dodaje szeregowo dwa słowa binarne $a=a_na_{n-1}...a_1a_0$ i $b=b_nb_{n-1}...b_1b_0$ bit po bicie od strony najmniej znaczących bitów tzn. w pierwszym takcie zegara podajemy na wejścia sumatora bity $a_0$ i $b_0$ w drugim $a_1$ i $b_1$ itd. Dodawanie trwa więc $n+1$ taktów zegara.

Rys. 4. Sumator szeregowy

Układ sumatora równoległego o strukturze pokazanej na Rys. 3. sumuje 2 liczby w czasie $(n+1)\Delta t$, gdzie $\Delta t$ jest czasem opóźnienia bramki. Stosując układ przewidywania przeniesień (ang. look ahead) możemy znacznie przyśpieszyć działanie układu sumatora równoległego. Żeby opisać działanie układu przewidywania przeniesień wprowadzamy dla każdej i-tej pozycji 3 pomocnicze funkcje (określające stan pozycji) zdefiniowane następująco

$P_i=a_1\oplus b_i\quad$- $P_i=1$ wtedy i tylko wtedy gdy pozycja $i$ jest w stanie propagacji

$G_i=a_ib_i\quad$- $G_i=1$ wtedy i tylko wtedy gdy pozycja $i$ jest w stanie generacji

$S_i=\overline{a_i}\cdot\overline{b_i}\quad$- $S_i=1$ wtedy i tylko wtedy gdy pozycja $i$ jest w stanie generacji 0

Zauważmy, że

$c_1=G_0+P_0c_0$

$c_2=G_1+P_1G_0+P_1P_0c_0$

$c_3=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0c_0$

$......$

$c_i=G_{i-1}+P_{i-1}G_{i-2}+P_{i-1}P_{i-2}G_{i-3}+\ldots+P_{i-1}P_{i-2}P_{i-3}...P_1G_0+P_{i-1}P_{i-2}P_{i-3}...P_0c_0$

$......$

$c_{n+1}=G_n+P_nG_{n-1}+P_nP_{n-1}G_{n-2}+\ldots+P_nP_{n-1}P_{n-2}...P_1G_0+P_nP_{n-1}P_{n-2}...P_0c_0$

Zatem gdybyśmy dysponowali bramkami o odpowiedniej ilości wejść, można by obliczyć każde przeniesienie w czasie $3\Delta t$. Układ sumatora wykorzystujący układ przewidywania przeniesień jest więc potencjalnie znacznie szybszy od zwykłego układu sumatora równoległego. Układ sumatora z przewidywaniem przeniesień pokazany jest na Rys.5.

Rys. 5. Sumator równoległy z układem przewidywania przeniesień