Podstawy techniki cyfrowej i
mikroprocesorowej
Układy kombinacyjne
Tomasz Piasecki
Układy kombinacyjne
" Układ kombinacyjny to urządzenie cyfrowe bądz
część
urządzenia cyfrowego, dla którego można zdefiniować
funkcję boolowską określającą słowo wyjściowe
wyłącznie na podstawie słowa wejściowego
" Jednym ze sposobów na fizyczną realizację układu
kombinacyjnego jest zestawienie obwodu z
wykorzystaniem bramek logicznych
" Bramki logiczne mogą być zestawiane z elementów
dyskretnych, produkowane w postaci układów scalonych
lub być częścią bardziej złożonego układu scalonego
" Stany logiczny na wejściach bramki najczęściej określa
się napięciem. Zdefiniowane przedziały napięć oznaczają
 0 lub  1 a bramka na wyjściu również sygnalizuje
stan logiczny poziomem napięcia.
Bramki logiczne
suma iloczyn
bufor
OR AND
suma zanegowana iloczyn zanegowany negator
NOR NAND NOT
alternatywa wykluczająca
równoważność
suma mod 2
zanegowana alternatywa wykluczająca
EXOR, XOR
EXNOR
Przykłady konstrukcji bramek
DL  logika diodowa, TTL  Transistor Transistor Logic CMOS  Complementary
bramka OR MOS
Vcc = 5 V. Tylko podanie napięcia Inwerter zbudowany z
 1 odpowiada napięciu około Vcc na A i B spowoduje tranzystorów PMOS i NMOS.
kilku V,  0 odpowiada nasycenie tranzystora  1 na A powoduje otwarcie
napięciu < 0,6V wejściowego i stan niski na NMOS, zatkanie PMOS i  0
wyjściu  bramka NAND na Q
Projektowanie układów kombinacyjnych
" Projektowanie polega na przejściu pomiędzy jednym ze sposobów
zapisania funkcji boolowskiej na układ złożony z bramek logicznych.
" Układ powinien być jak najprostszy, wykorzystywać jak najmniej
bramek. Proces upraszczania funkcji boolowskich nazywa się
minimalizacją
f =� x2 x1x0 +� x2x1x0 +� x2 x1x0 +� x2x1x0 +� x2x1x0
0 0 0 0
prawo sklejania
A�� B +� A�� B =� A
0 0 1 1
prawo pochłaniania
A�� B +� B =� A+� B
0 1 0 1
0 1 1 0
f =� (�x2 +� x2)�x1x0 +� x2x1x0 +� x2x1(�x0 +� x0)�
1 0 0 0
f =� x1x0 +� x2x1x0 +� x2x1
1 0 1 1
1 1 0 1
f =� x1x0 +� x1(�x2 x0 +� x2)�=� x1x0 +� x1(�x0 +� x2)�
1 1 1 1
f =� x1x0 +� x1x0 +� x2x1
Mapy Karnaugh
" Iloczyny elementarne z postaci kanonicznej, które można
uprościć korzystając z reguły sklejania, różnią się od
siebie negacją jednego z czynników mnożenia
x2x1x0 +� x2x1x0 =� x2x1
" Tym iloczynom odpowiadają słowa wejściowe układu
kombinacyjnego różniące się stanem jednego bitu
111 110
" W mapie Karnaugh każdy iloczyn elementarny ma
odpowiednik w postaci  1 wpisanej w diagram a
właściwości mapy ułatwiają wyszukiwanie tych
iloczynów, które odpowiadają słowom wejściowym
różniącym się tylko jednym bitem
Mapy Karnaugh
funkcja y równa jest sumie:
x1x0
00 01 11 10
x2
x2 x1x0 x2x1x0
0 0 1 0 1
x2 x1x0 x2x1x0 x2x1x0
1 0 1 1 1
x2x0
x1x0 x1x0
000 0 0 0
001 1 0 0
010 0 0 1
011 0 0 0
100 0 0 0
101 1 1 0
110 0 0 1
111 0 1 0
Mapy Karnaugh
" Minimalizacja funkcji boolowskiej
polega na wyszukiwaniu
0 0 0 1
implikantów prostych
1 1 0 1
" Jedną z form implikantów jest
1 1 0 1
wyrażenie I, dla którego prawdziwa
jest implikacja:
0 0 0 1
I=1��f=1
x3x2 x1
x1x0 " Postać minimalna funkcji składać
=� x2 x1
się może z sumy implikantów
x3x2 x1
prostych
" Mapa Karnaugh ułatwia ich
f =� x2 x1 +� x1x0
wyszukiwanie oraz odczytywanie
wyrażenia algebraicznego
odpowiadającego implikantowi
Mapy Karnaugh
funkcja y równa jest iloczynowi:
x1x0
x2 +� x1 +� x0
00 01 11 10
x2
x2 +� x1 +� x0
x2 +� x1 +� x0
0 0 1 0 1
1 0 1 1 1
(�x2 +� x1 +� x0)���(�x2 +� x1 +� x0)�=� (�x2 +� x2)�(�x1 +� x0)�=� x1 +� x0
f =� (�x1 +� x0)�(�x2 +� x1 +� x0)�
Czy wynik jest równoważny temu, uzyskanemu przy implikantach iloczynowych?
f =� x2x1 +� x1x0 +� x2x0 +� x1x0 =�
=� x2x1x0 +� x2x1 x0 +� x2x1x0 +� x2x1 x0 +� x2x1x0 +� x2 x1x0 +� x1x0 =�
=� x2x1x0 +� x2 x1x0 +� x2x1x0 +� x2x1 x0 +� x1x0 =�
=� x2x0 +� x1x0 +� x1x0
Mapy Karnaugh  przykłady implikantów
pole implikant dla  1 implikant dla  0
x3 +� x2 +� x1
x3x2 x1
a
a b
x2x1x0
x2 +� x1 +� x0
b
c c
x3 x2 x0
x3 +� x2 +� x0
c
x2 x1
d x2 +� x1
x1x0
x1 +� x0
e
d e
Mapy Karnaugh  przykłady implikantów
pole implikant dla  1 implikant dla  0
f
x2 +� x0
x2 x0
f
x1
g x1
x0
x0
h
g
h
Mapy Karnaugh
" Mapy Karnaugh dzięki takiemu układowi pól, w którym
sąsiednie pola różnią się wartością tylko jednego bitu
słowa wejściowego, pozwalają na znajdowanie
uproszczeń w stosunku do kanonicznego zapisu funkcji
boolowskiej dzięki użycia prawa sklejania
" Sklejać można pola zawierające  1 ale również  0
" Dla funkcji boolowskiej mającej wielobitowe słowo
wyjściowe należy przeprowadzić minimalizację dla
każdego bitu słowa wyjściowego z osobna
Minimalizacja funkcji boolowskiej
" Implikant to:
 wyrażenie iloczynowe I dla którego prawdziwa jest
implikacja I=1 �� Y=1
 wyrażenie sumowe S dla którego prawdziwa jest implikacja
S=0 �� Y = 0
" Minimalizacja polega na znalezieniu implikantów prostych.
" Implikantami są np. pojedyncze wyrażenia postaci
kanonicznych ale nie zawsze są one implikantami prostymi.
Implikanty prostsze powstają dzięki zastosowaniu prawa
sklejania do implikantów różniących się negacją tylko jednego
czynnika w wyrażeniu je opisującym
" Mapa Karnaugh może mieć praktyczne zastosowanie w
minimalizacji funkcji w których słowo wejściowe nie jest
dłuższe niż 6 bitów. Siatkę można rozszerzyć na 8 kolumn
i/lub wierszy, również kodując stany odpowiadające
kolumnom/wierszom wg kodu Gray'a
Mapy Karnaugh  przykłady implikantów
" Przy zaznaczaniu implikantów na
0 0 0 0
siatkach o boku 8 należy pamiętać o
tym, że implikanty przecinające osie
0 1 1 1
symetrii muszą być względem nich
0 0 0 1
symetryczne
1 0 0 1
1 0 0 1 f =�
x3 x2 x0 +� x3 x2x0 +� x4x2x1x0
0 0 0 0
0 1 1 0
0 0 0 0
Mapy Karnaugh - przykłady
Y1 = f(X) Y2 = f(X)
y0 =�
��(�1,3,5,7)�
��(�0,2,4,6,7)�
3
3
y1 =�
��(�0,4,2,6)�
��(�0,1,2,3,5,7)�
3
3
��(�0,2,5,6)�
y0 =�
��(�1,2,3,4)�
3
3
��(�0,2,4,5,7,8,10,12,13,15)� y1 =�
��(�1,3,4,5,6)�
4
3
��(�0,1,2,3,12,13,14,15)�
y0 =�
��(�0,2,4,5,6,7,13,15)�
4
4
��(�1,2,5,6,7,9,10,13,15)�
y1 =�
��(�1,2,5,8,9,10,13)�
4
4
Metoda Quine'a  McCluskeya
" Mapa Karnaugh nie jest jedyną metodą. Drugą z
popularnych metod jest metoda Quine'a  McCluskeya
" Metoda ta również polega na uproszczeniu znajdowania
termów czy implikantów, które różnią się jednym bitem i
można wobec nich zastosować regułę sklejania. Binarne
słowa wejściowe, dla których implikanty są prawdziwe,
wypisuje się w kolejnych grupach różniących się liczbą
 1 w słowie
" Algorytmizacja tej metody pozwala na jej łatwą
implementację komputerową jednak duża złożoność
obliczeniowa powoduje, że dla dużych układów
kombinacyjnych bardziej optymalne są metody
heurestyczne, które nie zapewniają znalezienia optimum
ale działają szybciej.
Metoda Quine'a  McCluskeya
f =�
��(�0,2,3,4,5,6)�
3
funkcja ta przyjmuje wartości po zgrupowaniu tych słów
 1 dla słów wejściowych: w grupy zawierające 0, 1, 2
itd. jedynki otrzymujemy:
000 000
010 010
011 100
100 011
101 101
110 110
Metoda Quine'a  McCluskeya
po zakończeniu znajdowania implikantów
porównujemy słowa każde z
trzeba wybrać grupę tych, które będą razem
każdym w obrębie
implikowały całą funkcję, wyszukiwanie
sąsiadujących grup zaznaczając
rozpoczynamy od implikantów najprostszych
 x bit, który zostanie
wyeliminowany dzięki regule
sklejania, wyniki zapisując w
sąsiedniej kolumnie
f =� x0 +� x2x1 +� x2 x1
xx0 0x0 x00 01x x10 10x
000 0x0 xx0
000 + + +
010 x00
010 + + + +
100 01x
011 +
011 x10
100 + + +
101 10x
101 +
110 1x0
110 + +
słowa
te implikanty pokrywały się
wejściowe
z implikantem prostszym
Metoda Quine'a  McCluskeya
f =�
��(�0,2,4,5,6,8,10,12,13,14,15)�
4
0000
00x0 0xx0 xxx0
xxx0 x10x 11xx
0010
0x00 x0x0
0000 +
0100
x000 xx00
0010 +
1000
0x10 xx10
0100 + +
0101
x010 x1x0
0101 +
0110
010x x10x
0110 +
1010
01x0 1xx0
1000 +
1100
x100 11xx
1010 +
1101
10x0
1100 + + +
1110
x101
1101 + +
1111
x110
1110 + +
1x10
1111 +
11x0
11x1
f =� x0 +� x2 x1 +� x3x2
111x
Budowanie układu na podstawie funkcji
Po wykonaniu minimalizacji funkcji boolowskiej, na podstawie powstałego
wyrażenia algebraicznego można skonstruować układ kombinacyjny
wykorzystujący bramki logiczne odpowiadające operacjom algebry Boole a
f =� x2 x1 +� x1x0
x2
x2 x1
x1 AND
x2 x1 +� x1x0
OR
AND
x0
x1x0
Budowanie układu na podstawie funkcji
x0
x2 x1
f =� x2x1x0 +� x2x0 +� x1x0 +� x2 x1x0
Przy funkcjach o dużym stopniu
złożoności wygodne jest układanie
schematu w postaci grup linii
wejściowych i połączeń do bramek
prostopadłych do siebie.
Mapy Karnaugh i funkcje niezupełne
" Funkcje niezupełne nie dla
wszystkich słów wejściowych mają
0 0 0 0
określoną wartość
1 - - 0
" Minimalizując tego typu funkcje
1 - - 0
wykorzystujemy ten fakt
przyjmując, że w miejscach
0 0 0 0
nieokreślonych wystąpią takie stany
logiczne, które pozwolą na lepszą
y =� x2 x1x0
y =� x2 x1
minimalizację funkcji
1 - 0 0
- - 0 0
- - - 0
- - - -
EXOR
0 1 f =� x1x0 +� x1x0 =� x1 �� x0
0 0 0 1
1 0
0 1 1 0
1 0 1 0
1 0
g =� x1x0 +� x1x0 =� x1 �� x0
1 1 0 1
0 1
0 1 1 0
y =� x2x0 +� x2 x0 =� x2 �� x0
1 0 0 1
1 0 1 0
y =� x1x0 +� x1x0 =� x2 �� x0
1 0 1 0
EXOR
y =� x2 x1x0 +� x2x1x0 +� x2 x1x0 +� x2x1x0 =�
0 1 0 1
=� x2(�x1x0 +� x1x0)�+� x2(�x1x0 +� x1x0)�=�
1 0 1 0
=� x2(�x1 �� x0)�+� x2(�x1 �� x0)�=�
=� x2 �� x1 �� x0
0 1 0 1
0 1 0 1
0 1 0 1
0 1 0 1
0 1 0 1 0 1 0 1
0 1 0 1 1 0 1 0
1 0 1 0 0 1 0 1
1 0 1 0 1 0 1 0