SYNTEZA UKŁADÓW KOMBINACYJNYCH
1.
Układy kombinacyjne - wiadomości ogólne
Logiczne układy kombinacyjne są to układy, w których sygnały wyj. w danej chwili czasu zależne są
tylko od aktualnych sygnałów wejściowych i nie zależą od sygnałów wejściowych w przeszłości. Są to
układy bez pamięci (ich analogowym odpowiednikiem są układy bezinercyjne np. sieci R).
Zależność między sygnałami WE i WY można dla nich określić podając funkcję Y=f(X).
Podstawowym sposobem przedstawiania funkcji logicznych (przełączających) jest opis słowny.
Musi on jednoznacznie określać przypadki, w których sygnały wyjściowe mają wartość 0 lub 1.
Układy cyfrowe przetwarzają informacje binarne i dla ich opisu konieczny jest aparat
matematyczny operujący dwoma symbolami.
Okazało się że algebra sformułowana w połowie XIX wieku przez angielskiego logika G. Boole’a
jest dobrym narzędziem opisu tych układów (postać algebraiczna).
Również wykres czasowy jest dobrym sposobem na przedstawienie zapisu funkcji.
Inna formą zapisu funkcji logicznej jest tablica, w której wszystkim możliwym wartościom
argumentów przyporządkowuje się odpowiednie wartości funkcji.
Tablica wartości jest bardziej konkretną i pełną postacią zapisu funkcji niż opis słowny i dlatego często z
opisu słownego przechodzi się do tablicy, sprawdzając przy tym, czy posiadane informacje o funkcji są
pełne i wystarczają do wypełnienia wszystkich pozycji.
Niekiedy zdarza się, że wartość funkcji przy pewnych kombinacjach sygnałów wejściowych jest
dowolna lub nieokreślona np. gdy taka kombinacja wejściowa nigdy w rzeczywistości nie występuje.
Funkcja nosi wówczas nazwę funkcji niepełnej (niezupełnej, nie w pełni określonej), a w jej tablicy, w
odpowiednich pozycjach kolumny y
, wstawia się kreskę.
W praktyce wygodniej posługiwać się innymi postaciami tabeli wartości. Najbardziej użyteczna
jest tablica Karnaugha.
2. Synteza układów kombinacyjnych
W celu dokonania syntezy układu kombinacyjnego należy:
1.
Na podstawie zadanego opisu słownego określić funkcję logiczną rozpatrywanego problemu, np. za
pomocą zespołu funkcji lub tabelą wiążącą każde wyjście układu z wejściami.
2.
Dokonać minimalizacji funkcji logicznej wykorzystując metody algebraiczne lub tablice Karnaugha.
3.
Sporządzić schemat układu logicznego, realizującego zminimalizowaną funkcję logiczną.
Logiczny u
kład kombinacyjny UK o m wejściach i n wyjściach nazywamy układ, w którym każdej z
możliwych kombinacji sygnałów wejściowych przyporządkowana jest jedna i tylko jedna kombinacja
sygnałów wyjściowych.
Rys. 1. Schemat blokowy układu kombinacyjnego
Jeżeli sygnały wejściowe potraktujemy jako zmienne binarne x
1
,...,x
m
, tj. dowolne elementy zbioru {0,1} ,
a sygnały wyjściowe y
1
,...,y
n
jako wartości binarne funkcji zmiennych binarnych x
1
,...,x
m
, to możemy
powiedzieć, że układ kombinacyjny jest opisany przez n funkcji boolowskich określonych na zbiorze m
zmiennych wejściowych.
Układ funkcji boolowskich można zapisać w postaci tablicy o (m+n) kolumnach i 2
m
wierszach.
W wierszach kolumn od 1 do m
będą zapisane wszystkie kombinacje wartości binarnych zmiennych
x
1
,...,x
m
, a w kolumnach od m+1 do m+n
– odpowiadające tym kombinacjom wartości binarne funkcji
wyjściowych.
x
1
x
2
y
1
y
2
0
0
1
0
0
1
-
1
1
0
1
-
1
1
0
0
Przykład
Podać opis układu kombinacyjnego mnożącego dwie dwubitowe liczby binarne.
Układ posiada 4 we i 4 wy bo (11)
2
x (11)
2
= (1001)
2
= 9
10
Oznaczając wejścia przez x
1
, x
2
i y
1
, y
2
oraz wyjścia z
1
, z
2
, z
3
i z
4
otrzymujemy tabelę:
x
1
x
2
y
1
y
2
z
1
z
2
z
3
z
4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
1
1
0
1
1
0
1
1
0
0
0
0
0
0
1
1
0
1
0
0
1
1
1
1
1
0
0
1
1
0
1
1
1
1
1
0
0
1
2
1
2
1
1
y
y
x
x
z
2
1
2
1
2
1
2
1
2
1
2
1
2
y
y
x
x
y
y
x
x
y
y
x
x
z
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
3
y
y
x
x
y
y
x
x
y
y
x
x
y
y
x
x
y
y
x
x
y
y
x
x
z
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
4
y
y
x
x
y
y
x
x
y
y
x
x
y
y
x
x
z
Funkcja
boolowska może być przedstawiona w postaci sumy pełnych iloczynów zmiennych x
1
,...,x
m
lub
w postaci
iloczynu pełnych sum tych zmiennych w sposób następujący:
i
m
i
i
m
a
K
x
x
x
f
1
2
0
2
1
)
,....,
,
(
lub
)
(
)
,....,
,
(
1
2
0
2
1
i
m
i
i
m
a
D
x
x
x
f
gdzie:
K -
iloczyn pełny, D - suma pełna, a – wartość funkcji dla konkretnych argumentów
Powyższe zależności umożliwiają łatwe przejście od tablicy wartości funkcji (lub równoważnego zapisu)
do wyrażenia logicznego.
Tablica wartości przedstawia kolejne wartości a
i
.
Ponieważ 0 x K
i
= 0 oraz 1 x K
i
= K
i
, dla przedstawienia funkcji wg zależności z wykorzystaniem
iloczynów pełnych należy wybrać sumę tych K
i
, dla których a
i
= 1
Przykładowa tablica wartości
i
x
1
x
2
x
3
y
1
0
0
0
0
2
0
0
1
1
3
0
1
0
0
4
0
1
1
1
5
1
0
0
0
6
1
0
1
1
7
1
1
0
1
8
1
1
1
1
Dla podanej tablicy wyrażenie logiczne ma następującą postać:
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
y
7
6
5
3
1
3
2
1
)
,
,
(
K
K
K
K
K
x
x
x
y
Formułę taką można uzyskać bezpośrednio z tablicy, biorąc pod uwagę jedynie te wiersze, dla których
y = 1
i przypisując wartościom x
i
= 1
zmienną x
i
a wartościom x
i
= 0
zmienną
i
x
.
Tak utworzone iloczyny pełne należy dodać. Uzyskana postać funkcji jest jedną z postaci kanonicznych
funkcji logicznej i nosi nazwę zupełnej normalnej postaci sumacyjnej (ZNPS).
Z za
sad jej tworzenia wynika, że każda funkcja może mieć tylko jedną taką postać.
Wykorzystując wzory na zapis funkcji, wzory wykorzystujące sumy pełne należy zauważyć, że
0 + D
i
= D
i
, 1 + D
i
= 1
więc w odpowiednich wyrażeniach należy wypisać iloczyn tych D
i
, dla których a
i
= 0.
Wyrażenie dla powyższej tabeli:
)
)(
)(
(
)
,
,
(
3
2
1
3
2
1
3
2
1
4
2
0
3
2
1
x
x
x
x
x
x
x
x
x
y
czyli
D
D
D
x
x
x
y
Formułę tę można otrzymać bezpośrednio z tablicy, biorąc pod uwagę jedynie te wiersze, dla których
y = 0
i przypisując wartościom x
i
= 0
zmienną x
i
a wartościom x
i
= 1 zmie
nną
i
x
.
Tak utworzone sumy pełne należy pomnożyć.
Uzyskana postać funkcji nosi nazwę zupełnej normalnej postaci iloczynu (ZNPI) i również jest jedna
dla każdej funkcji.
Postać kanoniczną często zapisuje się w skrócie, w postaci zbioru indeksów (bez symbolów K i
D), z odpowiednim symbolem operacji np.
y(x
1
, x
2
, x
3
) = (1, 3, 5, 6, 7)
oraz
y(x
1
, x
2
, x
3
) = (0, 2, 4)
Dla funkcji bez wartości nieokreślonych, występujące w tych dwóch postaciach liczby indeksowe muszą
wyczerpywać wszystkie możliwe wartości od 0 do 2
m
-
1, co umożliwia łatwe wyznaczenie jednej postaci
na podstawie znajomości drugiej (przez uzupełnienie liczb).
Np.
jeśli
y
1
(x
1
, x
2
) = (0, 1) ,
to
y
1
(x
1
, x
2
) = (2, 3)
jeśli
y
2
(x
1
, x
2
, x
3
) = (4, 5, 7)
to
y
2
(x
1
, x
2
, x
3
) = (0, 1, 2, 3, 6)
Gdy funkcja jest niepełna, indeks odpowiadający kombinacji nieokreślonej może wystąpić zarówno w
jednej postaci jak i w drugiej, gdyż y może być zarówno 0 jak i 1.
Oznacza się to przez wzięcie odpowiedniego składnika w nawias np.
y (x
1
, x
2
) = [2, (1)] czyli
)
(
)
(
2
1
2
1
2
,
1
x
x
x
x
x
x
y
oraz
y (x
1
, x
2
) = [ 0, 3, (1)] czyli
)]
)[(
)(
(
)
(
2
1
2
1
2
1
2
,
1
x
x
x
x
x
x
x
x
y
Minimalizacja funkcji
Zakładając, że do realizacji schematu logicznego postaci kanonicznych sumy i iloczynu dla
p
rzykładu z tablicą wartości użyjemy elementów NOT, AND i OR, łatwo policzyć że realizacja postaci
kanonicznej sumy wymaga 3 elementów NOT, 5 elementów AND i jeden element OR.
Odpowiednia postać kanoniczna iloczynu może być zrealizowana za pomocą
2 x NOT, 3 x OR i 1 x AND.
Można przypuszczać, że druga wersja będzie tańsza i prostsza, a więc lepsza.
Na ogół, układ o mniejszej liczbie elementów logicznych jest tańszy i bardziej niezawodny, a
spośród dwóch układów o tej samej liczbie elementów lepszy jest ten, który operuje mniejszą liczbą
sygnałów (mniej wejść mają wszystkie jego elementy).
Niezależnie od zastosowanych dalej elementów schematu logicznego, bardzo ważnym etapem
syntezy jest poszukiwanie takiej postaci funkcji przełączającej, w której występuje minimalna liczba liter
(tzn. zmiennych lub ich negacji).
Realizacja funkcji logicznej przedstawionej w postaci kanonicznej nie jest zazwyczaj
realizacją najprostszą.
Oczywiście jest możliwe minimalizowanie funkcji logicznych dokonując przekształceń algebraicznych.
Postacie kanoniczne tych funkcji przekształca się zgodnie z prawami oraz twierdzeniami algebry Boole’a
tak, aby uzyskać wyrażenie równoważne, ale tańsze wg przyjętych kryteriów kosztów. Otrzymane
wyrażenia zależą w dużej mierze od umiejętności projektanta.
Inny sposób poszukiwania postaci minimalnej funkcji opiera się na tzw. regułach
sklejania:
A
x
A
Ax
B
x
B
x
B
)
)(
(
gdzie A i B zmienne lub funkcje przełączające.
Reguły te można wyrazić następująco:
Suma lub iloc
zyn dwóch wyrażeń różniących się między sobą tylko na jednej pozycji –
znakiem negacji, mogą być zastąpione jednym wyrażeniem, bez litery stanowiącej różnicę.
Np.
3
2
3
2
1
3
2
1
2
1
3
2
1
3
2
1
1
1
2
2
1
2
1
2
1
)
)(
(
1
)
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Wyrażenia podlegające sklejaniu nazywane są wyrażeniami sąsiednimi.
Jeśli w otrzymanych postaciach kanonicznych funkcji takie wyrażenia sąsiednie występują, to postać
kanoniczną można uprościć, z wyraźną korzyścią dla realizacji technicznej.
x
1
x
y
2
1
1
0
0
Postać kanoniczną sumy z omawianego przykładu można zminimalizować w następujący
sposób:
2
1
3
2
1
3
2
3
2
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
)
(
)
(
)
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
y
Wpisano dwukrotnie iloczyn
3
2
1
x
x
x
, ponieważ A = A + A tzn. każdy składnik może się powtarzać bez
zmiany wartości funkcji.
Przeprowadzając sklejanie w postaci kanonicznej iloczynu (dla tego samego przykładu) otrzymuje się:
)
)(
(
)
)(
)(
(
3
2
3
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
y
Z zasady rozdzielności a+bc = (a + b)(a + c) wynika, że obydwa wyniki są sobie równe.
Prostsza jest realizacja
2
1
3
x
x
x
w której potrzebujemy 1 x OR i 1 x AND.
Różnica między realizacją zupełnej postaci kanonicznej i postaci minimalnej jest więc duża.
W wyniku sklejania
uzyskuje się wyrażenia, które już nie są postaciami kanonicznymi, ale zachowują
postać sumy iloczynów oraz iloczynu sum.
Wyrażenia tego typu przyjęto nazywać normalną postacią sumy NPS (normalną postacią alternatywy) i
normalną postacią iloczynu NPI (normalną postacią koniunkcyjną).
W przypadku złożonych funkcji wielu zmiennych wyszukiwanie wyrażeń sąsiednich i sklejanie w podany
sposób staje się bardzo uciążliwe, zwłaszcza że do otrzymania postaci minimalnej trzeba dokonać
wszystkich możliwych sklejeń.
Istnieją inżynierskie metody upraszczające procedurę minimalizacji gdy liczba zmiennych nie
przekracza 6, lub gdy liczba wyrazów zadanej postaci kanonicznej nie jest zbyt duża.
W
innych przypadkach rozwiązań minimalnych trzeba szukać za pomocą cyfrowych maszyn
matematycznych.
Metoda Karnaugha
Jest to graficzna metoda minimalizacji, powszechnie nazywana metodą tablic Karnaugha.
Metoda ta ułatwia sklejanie przez takie usytuowanie na płaszczyźnie wyrażeń postaci kanonicznej, aby
wyrażenia sąsiednie podlegające sklejeniu były umieszczone blisko siebie, a więc były sąsiednimi
również w sensie geograficznym.
Jeżeli rozpatrywany układ ma n elementów dwustanowych, to liczba możliwych stanów tego
układu wynosi 2
n
.
W tablicy prawdy stany te przedstawiamy w 2
n
wierszach, w tablicy Karnaugha w 2
n
kratkach.
W przypadku n
parzystego, tablica Karnaugha będzie miała kształt kwadratu zawierającego 2
0,5n
x 2
0,5n
kratek, a w przypadku nieparzystych n
kształt prostokąta zawierającego 2
0,5(n+1)
x 2
0,5(n-1)
kratek.
Każda kratka tablicy Karnaugha odpowiada jednej kombinacji wartości zmiennych wejściowych,
czyli każdej kratce odpowiada jeden wiersz tablicy prawdy.
Jeśli np. układ zawiera dwie zmienne x
1
i x
2
(dwa elementy wejściowe) to liczba
możliwych kombinacji stanów tych zmiennych wynosi 2
2
= 4. Tablica prawdy
miałaby 4 wiersze
x
x
1
2
00 01
10 11
0
1
0
1
0
1
0
00
x
4
1
1
x
01
2
5
3
x
6
11 10
3
7
2
0
1
00
00
4
1
01
x
01
3
5
4
x
6
11 10
3
7
2
9
15
8
10
13
14
11
12
10
11
x
2
x
Tablice Karnaugha dla 3 i 4 zmiennych.
Aby ułatwić wpisywanie w przypadku, gdy funkcja jest zadana w postaci
liczb dziesiętnych, w tablicach wpisano odpowiednie liczby
Cechą charakterystyczną tablicy Karnaugha jest sposób ustawienia jej wierszy i kolumn. Użyty do
tego celu kod Graya
sprawia, że sąsiednie kratki tablicy odpowiadają ciągom zero-jedynkowym
różniącym się tylko jednym elementem (za kratki sąsiednie uważa się również te, które leżą na
przeciwnych końcach jednego wiersza lub kolumny).
Jeżeli w dwóch sąsiednich kratkach wypełnionej tablicy Karnaugha znajdują się jednakowe
symbole (0 lub 1), to odp
owiadające tym kratkom wyrażenia można skleić, co odpowiada usunięciu litery,
która w ramach sklejanej grupy zmienia wartość.
Takie sąsiednie kratki tablicy tworzące pary, łączy się linią dla zaznaczenia możliwości sklejania.
Gdy wyróżnione kratki
-
zawie
rają jedynki, zamiast odpowiadającego im wyrażenia
x
A
Ax
można przyjąć A
-
zawierają zera, zamiast
)
)(
(
x
B
x
B
można przyjąć B.
Wersje usytuowania takich par dla trzech i czterech zmiennych.
Na rysunkach podane są wyniki sklejenia, przy czym na pierwszym miejscu umieszczono wyrażenia
opisujące grupę jedynek, a na drugim grupę zer.
Dwie kratki tworzące parę o jednakowych symbolach można skleić z inną parą o takich samych
symbolach, jeśli obie pary tworzą kwadrat lub prostokąt
Jednakowe symbole objęte prostokątem można więc opisać iloczynem (jedynki) lub sumą (zera) w które
wchodzą tylko litery o wartościach nie zmieniających się w ramach tej grupy.
Minimalizację funkcji przełączających niewielkiej liczby zmiennych (do 6 zmiennych) najwygodniej jest
przeprowadzić na tablicy Karnaugha. Dzięki temu, że opis wartości zmiennych w tablicy Karnaugha
dokonany jest w kodzie Graya, ciągi wartości zmiennych opisujących kratki tablicy leżące obok siebie,
różnią się tylko na jednej pozycji, czyli odpowiednie pełne iloczyny (sumy) są sąsiednie.
Proste iloczyny (sumy
) na tablicy Karnaugha wyznacza się łącząc ze sobą sąsiednie jedynki (zera)
w grupy składające się z 2
n
(2, 4, 8,16, ...) kr
atek. Należy przy tym pamiętać, że brzegi tablicy również
sąsiadują ze sobą.
x
3
0
1
11
1
01
10
x
x
00
2
3
1
x
; x
+
x
3
x
1
3
10
x
;
2
00
x
x
x
01
x
0
x
2
1
11
3
x
1
+
3
2
3
x
1
0
1
;
01
3
+
x
x
10
x
x
1
00
11
2
1
x
3
x
10
1
0
;
2
00
x
x
01
1
3
3
x
3
11
x
x
x
x
10
1
00
11
0
x
01
2
;
x
3
x
1
1
1
x
11
3
x
3
10
x
2
0
1
3
00
1
x
x ;
01
Rys. ..
Przykłady sklejania funkcji trzech zmiennych
Na rys.
następnym przedstawiono tablicę Karnaugha funkcji nie w pełni określonej.
Rys. 3.
Tablica Karnaugha funkcji nie w pełni określonej
Kr
atki zawierające kreski mogą być łączone zarówno z jedynkami jak i zerami funkcji. Dla tablicy
4 i 6 zmiennych sąsiednimi są brzegi tablicy - dolny i górny oraz prawy i lewy, rys. 4 i rys. 6. Dla tablicy 5
zmiennych pojęcie sąsiedztwa jest bardziej skomplikowane. Oprócz zwykłego sąsiedztwa, sąsiednie są
również klatki symetryczne względem pionowej i poziomej osi tablicy, zaznaczonej na rys. 5 i 6 grubą
kreską. Na rysunkach tych zaznaczono niektóre sąsiednie kratki.
Rys. 4
. Przykłady sklejania funkcji czterech zmiennych
Rys. 5
. Przykładowa tablica Karnaugha dla funkcji pięciu zmiennych
Rys. 6
. Przykładowa tablica Karnaugha dla funkcji sześciu zmiennych
2.
Realizacja układów kombinacyjnych
Przykład
Na rys. 7
przedstawiono tablicę Karnaugha funkcji czterech zmiennych.
Rys. 7. Tablica Karnaugha funkcji czterech zmiennych
Funkcję przełączającą zapisaną w tablicy Karnaugha można przedstawić w postaci boolowskiej
Chcąc powyższą funkcję zrealizować używając elementów NAND należy dokonać jej przekształcenia.
Korzystając z praw de Morgana przekształca się funkcję przełączającą do postaci
Na rys. 8
przedstawiono schemat układu realizującego funkcję przełączającą y przy użyciu bramek
NAND.
Rys. 8
. Schemat układu zrealizowanego przy użyciu bramek NAND
Literatura:
1. Majewski W., Albicki A. „Projektowanie cyfrowych układów telekomunikacyjnych”.
WKŁ, Warszawa 1977.
2. Pieńkoś J.,Turczyński J. „Układy scalone TTL w systemach cyfrowych” .
WKŁ, Warszawa 1980.