Układy kombinacyjne - sposoby opisu

Podstawowym sposobem przedstawiania funkcji logicznej (przełączającej) jest opis słowny, którego przykład podano poniżej.

Wyznaczyć funkcję przełączającą układu, który stanem F=1 wyróżnia wśród liczb wejściowych z przedziału 0-7, podawanych w naturalnym kodzie binarnym takie, w których liczba jedynek jest parzysta.

Na podstawie opisu słownego można sporządzić tablicę wartości zwaną niekiedy tablicą wierności lub tablicą prawdy (ang. Truth table). Postać tablicy prawdy dla n zmiennych przedstawia rys. 1.

Rys. 1Tabela prawdy dla funkcji logicznej n zmiennych.

W kolejnych wierszach, kolumny drugiej, wpisujemy wszystkie kombinacje zero-jedynkowe zmiennych niezależnych. Ostatnia kolumna jest przeznaczona do zapisania wartości funkcji dla poszczególnych kombinacji zero-jedynkowych. Aby wszystkie możliwe kombinacje zmiennych zostały wyczerpane, wypisujemy je tak, aby tworzyły kolejne liczby dziesiętne zapisane w systemie dwójkowym.

Rys. 2 Tabela prawdy dla przykładowej funkcji logicznej.

Spróbujmy utworzyć tablicę prawdy dla podanego wcześniej przykładu słownego opisu funkcji logicznej. Tworzona przez nas tablica będzie zawierać, pomijając nagłówek, osiem wierszy i powinna przyjąć postać jak na rys. 2.

Oprócz omówionych wcześniej dwóch sposobów opisu funkcji logicznej istnieje trzecia możliwość, za pomocą algebry Boole'a, o której wspominałem na pierwszym wykładzie. Postać ta nie jest zazwyczaj tworzona bezpośrednio z opisu słownego, lecz pośrednio z tablicy prawdy.

Dowolną funkcję logiczną n zmiennych można przedstawić jako:

(1)

gdzie:

a_i­ = 0 lub 1;

I_i - reprezentuje postać w naturalnym kodzie binarnym wartości i;

- znak oznaczający sumę logiczną.

Współczynnik a_i przyjmuje wartość 1, gdy dla danego i zachodzi równość F_i = I_i = 1, natomiast wartość 0, gdy F_i = I_i = 0.

Ta postać algebraiczna zapisu funkcji logicznej nosi nazwę kanonicznej formy sumacyjnej lub postaci normalnej sumy.

Spróbujmy funkcję logiczną, zadaną tablicą prawdy z rys. 2 wyrazić jako kanoniczną formę sumacyjną. Jak wynika a tablicy prawdy (rys. 2), funkcja przyjmuje wartość 1 w wierszach 3, 5, 6, natomiast wartość zero w pozostałych. Zatem rozpatrywana funkcja wyrażona jako kanoniczna forma sumacyjna przyjmie postać jak poniżej.

Każdy składnik typu 0*I_i = 0 nie zmienia wartości funkcji, może więc być usunięty. Zatem funkcja przyjmie postać:

(2)

Jako składniki sumy wchodzą te iloczyny I_i, które odpowiadają kombinacjom zero-jedynkowym zmiennych niezależnych i, dla których funkcja przyjmuje wartość 1.

Jeśli funkcja zależna jest od wielu zmiennych, to tworzenie postaci kanonicznej jest pracochłonne i dlatego często stosowany jest zapis skrócony (liczbowy), polegający na wypisywaniu odpowiednich liczb dziesiętnych, symbolizujących składniki, dla których funkcja przyjmuje wartość 1.

Spróbujmy więc wyrazić analizowaną funkcję logiczną (2) w postaci zapisu liczbowego kanonicznej formy sumacyjnej.

Drugą postacią algebraiczną funkcji n zmiennych jest kanoniczna forma iloczynowa zwana również postacią normalną iloczynu. Funkcja logiczna w tej postaci przedstawiana jest w sposób następujący:

(3)

gdzie:

a_i­ = 0 lub 1;

S_i - reprezentuje postać w naturalnym kodzie binarnym wartości i;

- znak oznaczający iloczyn logiczny.

Wyraźmy rozpatrywaną przez nas funkcję logiczną, opisaną tablicą prawdy z rys. 2, jako kanoniczną formę iloczynową. Jak widzimy z tablicy prawdy funkcja przyjmuje wartość 0 w wierszach 0, 1, 2, 4, 7 a wartość 1 w pozostałych, dlatego też jej kanoniczna forma iloczynowa będzie następująca:

Jak można zauważyć, każdy czynnik typu 1 + S_i = 1 nie zmienia wartości funkcji, może więc zostać wyeliminowany. Stąd też rozpatrywana funkcja po tym uproszczeniu przyjmie postać:

(4)

Jako czynniki do iloczynu wchodzą te sumy S_i, które odpowiadają kombinacjom zero-jedynkowym zmiennych niezależnych, dla których funkcja przyjmuje wartość 0.

Jeśli funkcja zależy od wielu argumentów, to tworzenie kanonicznej formy iloczynowej jest pracochłonne i podobnie jak w przypadku kanonicznej formy sumacyjnej można zastosować skrócony zapis liczbowy.

Funkcja (4) w zapisana jako liczbowa kanoniczna forma iloczynowa przyjmie postać następującą:

Przykład 1

Podać kanoniczną formę iloczynową oraz kanoniczną formę sumacyjną dla funkcji logicznej, która stanem 1 sygnalizuje pojawienie się na wejściu liczby podzielnej przez 2. Liczby są z zakresu 0-7 i są przedstawiane w naturalnym kodzie binarnym.

1. Opracowanie tabeli prawdy dla funkcji przełączającej na podstawie opisu słownego.

i	x0	x1	x2	F
0 1 2 3 4 5 6 7	0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 0 1 0 1 0 1 0

2. Wyznaczenie kanonicznej formy sumacyjnej.

Ponieważ 0 * I_i = 0 nie zmienia wartości funkcji, stąd:

Korzystamy z warunku, że: w wyniku czego otrzymujemy:

3. Wyznaczeni kanonicznej formy iloczynowej.

Ponieważ 1 + S_i = 1 nie zmienia wartości funkcji, stąd:

W celu uproszczenia otrzymanej funkcji powielane jest wyrażenie drugie na podstawie warunku, że x * x = x. Kolejnym krokiem jest podwójnie zanegowanie wszystkich wyrażeń oraz wykorzystanie odpowiednich praw DeMorgana.

Przykład 2

Podać kanoniczną formę iloczynową oraz kanoniczną formę sumacyjną dla funkcji logicznej opisującej działanie trzech sędziów. Każdy z sędziów ma jeden głos. Werdykt jest przychylny jeżeli co najmniej dwóch sędziów głosowało za.

1. Opracowanie tabeli prawdy dla funkcji przełączającej na podstawie opisu słownego.

i	x0	x1	x2	F
0 1 2 3 4 5 6 7	0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 0 0 1 0 1 1 1

2. Wyznaczenie kanonicznej formy sumacyjnej.




Ponieważ 0 * I_i = 0 nie zmienia wartości funkcji, stąd:




3. Wyznaczeni kanonicznej formy iloczynowej.




Ponieważ 1 + S_i = 1 nie zmienia wartości funkcji, stąd:




W dotychczasowych rozważaniach, dotyczących sposobów zapisu funkcji logicznych, przyjmowały one ściśle określone wartości dla wszystkich 2ⁿ kombinacji zmiennych wejściowych. Może jednak zdarzyć się przypadek, gdy na wejściach układu kombinacyjnego nie wystąpią wszystkie możliwe kombinacje lub gdy stan sygnału wyjściowego F_i układu jest nie określony (obojętny) przy pewnych stanach wejściowych x_i. Wówczas tabela prawdy, będzie określona częściowo, z pominięciem nieokreślonych wektorów wejściowych x. Jeśli dany wektor wejściowy x_i nigdy się na wejściach układu nie pojawia można przyjąć, że dla tego wektora funkcja przyjmuje wartość 0 lub 1 zależnie od potrzeb. Możliwość przyjęcia dowolnej wartości funkcji dla pewnych wektorów wejściowych jest bardzo przydatna w procesie minimalizacji. W tablicy prawdy, w miejscach, gdzie wartość funkcji jest nie określona, wpisuje się umowny symbol np. -, ∅, x.

Wykład 2

5

Podstawy układów cyfrowych. Opracował: J.Chudzikiewicz

---