Temat:
Operacje logiczne i kombinacyjne układy cyfrowe.
Rozdziały wykładu:
1. Ogólna definicja układu cyfrowego
2. Funkcje logiczne i kombinacyjne układy cyfrowe
3. Proste kombinacyjne układy cyfrowe
4. Programowalne układy logiczne
Ogólna definicja układu cyfrowego
Podstawowymi składnikami budowy sprzętu cyfrowego są układy cyfrowe
(ang. digital circuits).
Układ cyfrowy można przedstawić jako blok posiadający n wejść i m wyjść,
na których zakłada się obecność sygnałów cyfrowych (ang. digital signals).
X1 Y1
X2 Y2
. .
. .
. .
Xn Ym
Reprezentacja blokowa układu cyfrowego
Sygnały cyfrowe przyjmują wartości pochodzące ze skończonego zbioru
wartości dopuszczalnych tzw. sygnałów dyskretnych ( ang. discrete signals).
Przykładem są np. sygnały binarne czyli dwuwartościowe (ang. binary signals
lub two-value signals).
Sygnały dyskretne czyli cyfrowe należy odróżnić od sygnałów analogowych
(ang. analog signals), które mogą przyjmować wszystkie wartości rzeczywiste
z zdanego przedziału.
Układy, w których występują sygnały analogowe nazywamy układami
analogowymi (ang. analog circuits).
Komputery zbudowane wyłącznie z ukłądów cyfrowych nazywamy
komputerami cyfrowymi (ang. digital computers).
Komputery zbudowane wyłącznie z układów analogowych nazywamy
komputerami analogowymi (ang. analog computers).
Komputery zbudowane z układów cyfrowych i analogowych nazywamy
komputerami hybrydowymi (ang. hybrid computers).
W organizacji logicznej i czasami architekturze komputerowej istotne jest
opisanie działania układów cyfrowych poprzez podanie zależności sygnałów
wyjściowych od sygnałów wejściowych.
Zależności te rozpatrujemy w dyskretnym czasie, czyli złożonym z
kolejnych chwil czasowych.
Wyróżniamy dwa typy układów cyfrowych ze względu na rodzaj zależności
między wejściami i wyjściami.
" Jeżeli każdy sygnał wyjściowy w danej chwili zależy wyłącznie od
sygnałów obecnych w tej chwili na wszystkich wejściach układu, to taki
układ nazywamy układem kombinacyjnym ( ang. combinational circuit).
Układy kombinacyjne nie posiadają pamięci, tzn. ich zachowanie w
przeszłości nie jest w żaden sposób w nich rejestrowane i nie ma wpływu
na ich zachowanie w bieżącej chwili .
" Jeżeli każdy sygnał wyjściowy w danej chwili zależy od sygnałów na
wszystkich wejściach układu oraz od sekwencji sygnałów, które były
podawane na wejścia w chwilach poprzednich to taki układ nazywamy
układem sekwencyjnym (ang. sequential circuit).
W zależności od liczby wartości, która mogą przyjmować sygnały w układach
cyfrowych mówimy o :
" binarnych układach cyfrowych,
" trójkowych (trójwartościowych) układach cyfrowych,
itd.
Funkcje logiczne i kombinacyjne układy cyfrowe
Działanie kombinacyjnego układu cyfrowego można opisać za pomocą
funkcji Yi = f (X1, X2, ..., Xn), opisującej wszystkie wyjścia Yi układu w
zależności od wartości na wszystkich wejściach Xj.
Funkcję f nazywamy funkcją wyjść układu,(ang. output function).
Jeśli układ ma n wejść, to funkcję f nazywamy funkcją n zmiennych.
Jeśli wejścia i wyjścia są dwuwartościowe to układ nazywamy binarnym
układem cyfrowym, (ang. binary digital circuit).
Podstawowym sposobem zapisu funkcji f jest podanie dla f tzw. tablicy
prawdy (ang. truth table).
A B Ci S Co
0 0 0 0 0
0 1 0 1 0
1 0 0 1 0
1 1 0 0 1
0 0 1 1 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 1
Tablica prawdy sumatora jednobitowego
Bity A, B, przeniesienie początkowe Ci  zmienne (sygnały) wejściowe.
Sumator wytwarza wartości bitu sumy S i przeniesienia Co zmienne
(sygnały) wyjściowe.
Innym sposobem opisu funkcji logicznej sÄ… tablice Karnaugh a, (ang.
Karnaugh table).
" Wiersze i kolumny są przypisane kombinacjom wartości podzbiorów
zmiennych wejściowych.
" W polach przypisanych różnym kombinacjom wartości zmiennych
wejściowych wpisujemy wartości funkcji.
" W ten sposób opisujemy funkcję f przez podanie jej wartości dla
wszystkich kombinacji sygnałów wejściowych
Tablice Karnaugha dla wyjścia bitu sumy S i wyjścia przeniesienia C0
sumatora 1-bitowego podane są poniżej.
S C0
AB 00 01 11 10 AB 00 01 11 10
Ci Ci
0 0 1 0 1 0 0 0 1 0
1 1 0 1 0 1 0 1 1 1
Tablice Karnaugha dla sumatora 1-bitowego
Na podstawie tablicy prawdy albo tablicy Karnaugha danej funkcji wyjść
układu można zaprojektować wnętrze układu cyfrowego, który ma wytwarzać
zadane sygnały wyjściowe na podstawie zadanych sygnałów podawanych na
wejścia.
Odwzorowanie jedynek zawartych w tych tablicach na tzw. podstawowe
(elementarne) funkcje logiczne, które są bezpośrednio realizowalne przez
podstawowe (elementarne) układy logiczne.
Wyrażenia logiczne (ang. logical statements) służą do opisania funkcji
kombinacyjnych układów logicznych, tzn. określenia (wyliczenia przy użyciu
specjalnych operacji logicznych) wyjść układu w zależności od wejść (w
funkcji wejść).
Operacje logiczne pochodzą z tzw algebry Boole'a, która jest rachunkiem
wykonywanym na zmiennych przyjmujących określoną liczbę wartości. W
przypadku układów cyfrowych, których wejścia i wyjścia są binarne, operacje
te dotyczyć będą zmiennych 2-wartościowych czyli binarnych a algebra
będzie tzw. binarna.
Operacje binarnej algebry Boole'a są następujące:
iloczyn logiczny a '" b lub ab (dla operacji na dwu zmiennych a, b)
suma logiczna a (" b lub a + b (dla operacji na dwu zmiennych a, b)
negacja
a
Wartości operacji logicznych określone są zgodnie z tabelką
b iloczyn suma negacja a negacja b
0 0 0 0 1 1
0 1 0 1 1 0
1 0 0 1 0 1
1 1 1 1 0 0
Operacje iloczynu logicznej i sumy logicznej mogą zawierać dowolną liczbę
zmiennych,
np. a '" b '" c '" d czyli (abcd) lub e (" f (" g (" h czyli (e+f+g+h).
Wyrażenia logiczne stanowią sumę logiczną iloczynów logicznych (tzw.
termów) zapisujących wszystkie te kombinacje zmiennych wejściowych,
którym w tabeli prawdy funkcji lub w tablicy Karnaugha odpowiadają
wartości wyjść równe l.
Jeżeli dla xl=l, x2=0, x3 =1, x4=0 wyjście układu ma wartość l, to term
zapisujemy jako iloczyn logiczny
x1 x2 x3x4
Ma on rzeczywiście wartość l, gdy te zmienne mają wartości jak wyżej.
Stąd opisując termami wszystkie "jedynki" wyjścia układu i sumując je
logicznie, tworzymy zapis funkcji tego wyjścia w postaci wyrażenia
logicznego.
Funkcje tę nazywa się logiczną lub czasem przełączającą (ang. logical
function , switching function).
Dla najprostszej realizacji układów cyfrowych:
" buduje się najpierw składowe układy cyfrowe realizujące wszystkie termy
" wyjścia tych układów podaje się na wejścia układu realizującego sumę
logicznÄ….
Wyjście sumy stanowi wyjście całego układu opisanego danym wyrażeniem
logicznym.
Układy realizujące pojedyncze operacje logiczne, nazywamy funktorami
logicznymi lub bramkami logicznymi (ang. logical gates)
Podstawowe funkcje i funktory logiczne
Nazwa funkcji Symbol graficzny Tablica prawdy
A B X
A
0 0 0
X
AND
B
1 0 0
0 1 0
1 1 1
A B X
A
0 0 0
X
OR
B
1 0 1
0 1 1
1 1 1
A X
NOT A X
0 1
1 0
A B X
A
0 0 1
X
NAND
B
1 0 1
0 1 1
1 1 0
A B X
A
0 0 1
X
NOR
B
1 0 0
0 1 0
1 1 0
A B X
A
0 0 0
X
XOR
B
1 0 1
0 1 1
1 1 0
Inne używane symbole funktorów logicznych
AND
OR
XOR
Wzmacniacz z
negacjÄ…
Sposób budowania układów logicznych na podstawie ich
tablicy Karnaugha
Załóżmy, że chcemy zbudować czterowejściowy układ logiczny, o wejściach
A, B, C, D i wyjściu Y.
A
B
Y
C
D
Chcemy aby, układ zachowywał się zgodnie z podaną poniżej tablicą
Karnaugha (tzn aby wytwarzał jedynki na swoim wyjściu Y tylko dla takich
kombinacji wartości wejść A, B, C, D które odpowiadają jedynkom w tablicy,
dla pozostałych kombinacji wejść wartość Y ma być równa 0).
CD 00 01 11
10
AB
00 0 1 1 0
01 0 1 1 0
11 0 0 0 1
10 1 1 0 1
Funkcja logiczna Y = f(A, B, C, D), uzyskana przez opisanie wszystkich
 jedynek w tablicy Karnaugha prze iloczyny prostych lub zanegowanych
zmiennych A, B, C, D ma postać:
Y = ABCD (" ABCD (" ABCD (" ABCD (" ABCD (" ABCD (" ABCD (" ABC D
Zanegowane zmienne umieszczamy w iloczynach tam, gdzie do kombinacji
wartości sygnałów odpowiadających jedynce wchodzi wartość 0 tych
zmiennych.
Możemy zbudować elementarny układ iloczynu logicznego  bramkę AND
dla każdego iloczynu (termu) występującego w wyrażeniu logicznym
opisującym wyjście Y i zsumować logicznie wyjścia ze wszystkich bramek
AND w jednym układzie sumy logicznej OR.
Układ ten zawiera 9 funktorów logicznych: 8 bramek AND i jedna bramkę
OR.
A
B
C
D
Y
A
B
C
D
Spróbujmy opisać iloczynami takie grupy jedynek, które dadzą się opisać
iloczynem logicznym z mniejszą liczba zmiennych niż wszystkie ABCD.
A
atwo zauważyć, że będą to grupy, które dadzą się objąć w tablicy obwiednią:
kwadratową lub prostokątną (można je prowadzić z zawinięciem poprzez
granice tablicy).
Grupy takich jedynek dla naszej tablicy Karnaugha pokazuje rysunek
poniżej:
CD 00 01 11
10
AB
AD
00 0 1 1 0
01 0 1 1 0
11 0 0 0 1
10 1 1 0 1
AÅ"CD
AB Å"C
Widoczne grupy jedynek można zapisać jako iloczyny podane na rysunku.
Funkcję logiczną Y możemy więc zapisać w znacznie prostszy sposób niż
poprzednio, jako sumę logiczną trzech tylko termów:
Y = AD (" ABC (" ACD
Każdy z termów występujących w powyższym wyrażeniu logicznym możemy
teraz zrealizować w osobnym układzie iloczynu logicznego i następnie
zsumować w jednym układzie sumy logicznej.
A
D
A
Y
B
C
A
C
D
W ten sposób udało nam się zbudować prostszy układ logiczny realizujący
naszÄ… funkcjÄ™ logicznÄ… Y = f(A, B, C, D).
Tylko 4 funktory, mniej wejść - w szczególności bramka sumy logicznej ma
tylko 3 wejścia, zamiast 8, jak w poprzedniej wersji układu.
Znajdowanie takich realizacji funkcji logicznych, które dają minimalne liczby
użytych elementarnych bramek logicznych nosi nazwę minimalizacji funkcji
logicznych (ang. logical function minimization).
Minimalizacja funkcji logicznych ma jeszcze wiele innych metod, ale
najprostsza jest opisana powyżej metoda oparta na analizie i grupowaniu
jedynek w tablicy Karnaugha.
Proste kombinacyjne układy cyfrowe
Binarne układy logiczne możemy budować w dwu technikach:
Pozytywnej, w której sygnał aktywny , niosący w sobie informację ma
wartość  1 ,
Negatywnej, w której sygnał aktywny , niosący w sobie informację ma
wartość  0
a) Układ logiczny b) Tablica prawdy
X
A0
X Y A0 A1 A2 A3
0 0 1 0 0 0
A1
0 1 0 1 0 0
Y
1 0 0 0 1 0
A2
1 1 0 0 0 1
A3
Dekoder dwuwejściowy w technice pozytywnej
Realizacja układu dekodera dwuwejściowego w technice negatywnej jest
podana poniżej .
W technice negatywnej używamy funktorów zanegowanych funkcji
logicznych.
Na schematach układów logicznych w tej technice negatywne aktywne
sygnały oznaczamy przez zanegowanie nazw zmiennych wyjściowych
układu.
a) Układ logiczny b) Tablica prawdy
aktywny stan niski
Układ logiczny
A0 A3
X Y A1 A2
X
A 0
0 0 1 1 1 0
Y
0 1 1 1 0 1
A 1
1 0 1 0 1 1
1 1 0 1 1 1
A 2
A 3
Dekoder dwuwejściowy w technice negatywnej
Multiplekser jest układem kombinacyjnym, który przekazuje na swoje
wyjście sygnały z jednego ze swoich wielu wejść, które jest wybrane przez
sygnał wybierający.
X Y S F
X
0 0 0 0
0 1 0 0
F
1 0 0 1
1 1 0 1
Y 0 0 1 0
0 1 1 1
S  sygnał wybierający 1 0 1 0
1 1 1 1
Multiplekser dwuwejściowy
Multipleksery i demultipleksery służą do sterowania przesyłaniem informacji
z wielu z
ródeł do wielu odbiorników poprzez wspólną szynę
jednokierunkowÄ….
y
ródło 1
y
ródło 2 Odbiornik 1
Multi- Demulti-
szyna
plekser plekser
y
ródło 3 Odbiornik 2
y
ródło 4
Sterowanie
Sterowanie
Typowymi układami kombinacyjnymi są sumatory binarne (ang. binary
adders). Sumatory binarne możemy podzielić ze względu na liczbę
sumowanych bitów na:
sumatory elementarne  które, sumują dwa bity argumentów i bit
przeniesienia wejściowego, sumatory wielobitowe  które, sumują liczby
wielobitowe.
Elementarne sumatory binarne budujemy z półsumatorów (ang. half adders),
które sumują dwa bity argumentów i wytwarzają bit sumy (ang. sum bit) oraz
bit przeniesienia (ang. carry).
A, B  wejścia bitów argumentów, C  wyjście przeniesienia półsumatora,
Ci, Co  wejście i wyjście przeniesienia sumatora elementarnego (od ang.
input , output), S  wyjścia bitu sumy .
Układ logiczny Tablica prawdy Symbol
A
S
B
A S
A B S C
0 0 0 0
PS
0 1 1 0
B C
C 1 0 1 0
1 1 0 1
Półsumator
S = A Ë% B, C = A B
Sumator elementarny możemy zbudować z dwu pół-sumatorów.
S
S
Ci
PS S
A
B
C
S
A SUM
C0
PS
Ci C 0
B C
a) Układ logiczny b) Symbol układu
A B Ci S Co
0 0 0 0 0
0 1 0 1 0
1 0 0 1 0
S= AË% BË% C
1 1 0 0 1
0 0 1 1 0
Co=AB + ACi +BCi
0 1 1 0 1
1 0 1 0 1
1 1 1 1 1
c) Tabela prawdy
Sumatory wielobitowe budujemy w najprostszy sposób przez kaskadowe
połączenie wielu sumatorów elementarnych, podając wyjścia przeniesień ze
stopni poprzednich na wejścia przeniesień stopni następnych.
Symbol graficzny sumatora wielobitowego używany w schematach
blokowych komputerów jest pokazany na przykładzie poniżej.
A3 A2 A1 A0 B3 B2 B1 B0
C4 SS S2 S1
S0
3
Symbol sumatora wielobitowego (4-bitowego)
Bramka trójstanowa.
Wejścia tej bramki przyjmują sygnały dwuwartościowe  0 lub 1. Wyjście tej
bramki może przyjmować trzy wartości  0, 1 i tzw. wartość trzecią (stan
trzeci) oznaczony cyfrÄ… 2.
Stan trzeci odpowiada odcięciu (rozwarciu połączenia) wyjścia bramki
trójstanowej od reszty układów (nazywany jest stanem wysokiej impedancji).
a) działanie bramki b) tablica prawdy bramki
trójstanowej trójstanowej
A X
B
Wejście Wyjście
C
C AB X
00 1
01 1
1
10 1
11 0
00 2
01 2
A X
0
10 2
B
11 2
C
Bramki trójstanowe umożliwiają podłączanie wielu układów logicznych do
wspólnych dwukierunkowych dróg przesyłania binarnych sygnałów
logicznych. Można to prześledzić na przykładzie zwrotnicy.
Do układu
Do szyny
pamięciowego
Wybór kierunku
Sterowanie zwrotnicÄ…
Układ zwrotnicy szyny
0- do szyny, 1  do układu 0  otwarte, 1 - zamknięte
Układ powyższy zapewnia możliwość przesyłania danych poprzez wspólne
linie przesyłowe w obu kierunkach (szynę).
Układ wymaga podania binarnych sygnałów: Wybór kierunku i Sterowanie
zwrotnicÄ….
Jeżeli Sterowanie zwrotnicą jest równe 0, to wszystkie bramki trójstanowe są
w stanie trzecim i zwrotnica nie łączy szyny z układem pamięciowym.
Jeśli Sterowanie Zwrotnicą jest równe 1 to Wybór kierunku określa parę
bramek trójstanowych, które przewodzą w określonym kierunku  od lub do
szyny. Jednocześnie, dwie pozostałe bramki odcinają nie używane linie idące
do układu pamięciowego od szyny.
Programowalne układy logiczne
Dla Å‚atwej realizacji dowolnych funkcji logicznych stosowane sÄ…
programowalne układy (struktury) logiczne (ang. programmable logical
devices - PLD).
Ich struktura naśladuje ogólną strukturę wyrażenia logicznego, która stanowi
sumę logiczną iloczynów elementarnych zmiennych wejściowych (termów).
Są to zatem układy zbudowane z dwu połączonych ze sobą kaskadowo
układów o regularnej strukturze: tzw. matryc logicznych (ang. logical arrays).
PLD
X 0
X 1
Matryca
AND
X n-2
X n-1
1 2 3 4 k
Z 0
Z 1
Matryca
OR
Z p-1
Ogólna struktura programowalnego układu logicznego
Zmienne wej
Å›
ciowe
Zmienne wyj
Å›
ciowe
W praktyce najbardziej popularne są dwa główne typy programowalnych
ukladów logicznych.
Jeden typ to programowalne matryce logiczne typu PLA (ang. programmable
logic arrays  PLA), w których programuje się obydwie matryce.
Drugi typ programowalnych układów logicznych to tzw. programowalne
matryce logiczne typu PAL (ang. programmable array logic  PAL), w
których programuje się jedynie matryce bramkową AND.
X n-1 X 0
Programowalne układy OR
1
2
k-1
k
Programowanle układy AND
Z Z 0
p-1
Struktura programowalnej matrycy logicznej typu PLA
Programowanie polega na przerwaniu (przepaleniu)  niepotrzebnych
podłączeń linii wejściowych do bramki tak, by nie przerwane połączenia
doprowadzały do bramki sygnały odpowiadające żądanemu iloczynowi
elementarnemu.
W matrycy AND wytwarza siÄ™ wszystkie potrzebne iloczyny elementarne
zadanej funkcji logicznej.
Wyjścia bramek realizujących te iloczyny elementarne podłącza się do tego
samego układu sumy logicznej (OR), w drugiej matrycy logicznej tzw.
matrycy OR.
Każda bramka OR sumuje zatem pewna liczbę iloczynów logicznych i
wytwarza przez to innÄ… funkcjÄ™ logicznÄ….
Zatem programowalna matryca logiczna realizuje jednocześnie wiele funkcji
logicznych zmiennych binarnych z tego samego zbioru, po jednej na każdym
wyjściu z matrycy OR.
X n-1 X 0
Ustalone układy OR
1
2
k-1
k
Programowanle układy AND
Z Z 0
p-1
Struktura programowalnej matrycy logicznej typu PAL.
Układami kombinacyjnymi o podobnej budowie są również pamięci stałe typu
ROM. Mają one jednak ustalone przez producenta układu scalonego obydwie
matryce AND oraz OR.
Do programowalnych matryc logicznych zaliczamy również programowalne
pamięci stałe typu PROM, w których można "zaprogramować" dane, zawarte
w matrycy OR.
Pamięci ROM oraz PROM będą dokładniej omówione na wykładzie
dotyczącym organizacji pamięci w komputerach.