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ń