Podręcznik

Układ kombinacyjny jest podstawowym układem logicznym umożliwiającym realizację funkcji boolowskich. Układ kombinacyjny konstruujemy z elementów logicznych po to, aby realizować funkcje lub ich zespoły opisujące bardziej skomplikowane układy cyfrowe. Dlatego rozważania o układach kombinacyjnych rozpoczynamy od pojęcia funkcji boolowskiej.

Pojęcie funkcji boolowskiej jest pojęciem podstawowym umożliwiającym modelowanie zjawisk fizycznych reprezentowanych jako odwzorowanie ciągów (wektorów) binarnych należących do zbioru X w ciągi binarne (wektory) ze zbioru Y, gdzie zbiory X, (Y) są podzbiorami n-krotnego, (m-krotnego) iloczynu kartezjańskiego zbioru B = {0, 1}.

Formalnie funkcją boolowską zmiennych binarnych x₁, …, x_n nazywamy odwzo­rowanie:

f: X ® Y, gdzie X Í Bⁿ, Y Í B^m.

Jeżeli X = Bⁿ, to funkcję taką nazywamy zupełną; w przeciwnym przypadku jest to funkcja niezupełna, zwana również funkcją nie w pełni określoną.

Najczęściej stosowane reprezentacje funkcji boolowskich to tablica prawdy oraz formuła (wyrażenie) boolowskie.

Funkcja f może być przedstawiona w postaci tablicy prawdy. Jest to tablica o n+1 kolumnach i 2ⁿ wier­szach. W kolejnych wierszach są zapisywane wszystkie wartości ciągu x₁, …, x_n, czyli wszystkie wektory x. W ostatniej kolumnie podana jest wartość y przyporządkowywana danemu wektorowi lub „–”, jeżeli funkcja dla tego wektora nie jest określona. Kolejne wektory są numerowane, przy czym wartość i podana z lewej strony w dodatkowej kolumnie jest dziesiętnym odpowiednikiem wektora x traktowanego jako liczba w zapisie dwójkowym:

$A_{D} =L( A_{NKB}) =\sum\limits ^{n-1}_{j=0} a_{j} \cdot 2^{j} =a_{n-1} \cdot2^{n-1} +\cdots +a_{2} \cdot2^{2} +a_{1} \cdot2^{1} +a_{0} \cdot2^{0}$

Na przykład przeliczenia liczb binarnych (0101)_B oraz (1010)_B (podanych w NKB – naturalnym kodzie binarnym) na liczby dziesiętne 5_D i 10_D dokonujemy następująco:

(0101)_B = 0 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰ = 5_D

(1010)_B = 1 × 2³ + 0 × 2² + 1 × 2¹ + 0 × 2⁰ = 10_D

Przykłady tablicowej reprezentacji funkcji boolowskiej podane są w tabl. 2.1a (funkcja zupełna) i tabl. 2.1b – funkcja niezupełna.

Tablica 2.1

Tablice te specyfikują funkcje boolowskie, których wektory wejściowe są dodatkowo określone liczbami dziesiętnymi. Stąd pomysł, aby specyfikacje funkcji boolowskich podawać w uproszczonej formie. Dla funkcji z tabl. 2.1a odpowiedni zapis powinien być:

f = S(1, 3, 5, 6, 7)

Natomiast funkcję z tabl. 2.1b zapisać należy z dodatkowym specyfikowaniem wektorów nieokreślonych:

f = S[1, 3, 5, 7, (2, 6)].

Rys. 2.1. Dekoder (a) wskaźnika siedmiosegmentowego (b)

Typowym zastosowaniem tablic prawdy do specyfikacji funkcji boolowskich może być opis deko­de­ra wskaźnika siedmiosegmen­towego pow­szechnie stosowanego do wyświetlania cyfr w urządzeniach pomiarowych i monitoru­jących. Deko­der taki to układ kombina­cyjny o wejściach x₃, x₂, x₁, x₀ oraz wyjściach a, b, c, ..., g (rys. 2.1a), odpowiadających segmentom wskaź­nika (rys. 2.1b). Na wejścia x podawane są liczby binarne 0000, 0001,...,1000,1001 (dziesiętnie: 0,1,...,8,9). Wyjścia a, b, c, ..., g sterują diodami świecącymi. Dioda zostaje podświetlona, gdy odpo­wiednie wyjście jest w stanie 1. W rezultacie działanie dekodera jest opisane tablicą prawdy, podaną w tablicy 2.2. W tym przypadku mamy do czynienia z funkcjami niezupełnymi. Jak się później przekonamy, omówiony dekoder nie nastręcza żadnych trudności w syntezie odpowiadającego im układu kombinacyjnego.

Tablica 2.2

Można jednak podać zastosowania bardziej skomplikowane. Na przykład układ kryptograficzny realizujący tzw. algorytm DES (Data Encryption Standard), jest wyposażony w klucze S, których działanie specyfikuje się funkcjami boolowskimi o 6 wejściach i 4 wyjściach. Przykładowa specyfikacja dla klucza S₁ jest podana w tablicy 2.3.

Tablica 2.3

Jeśli wejścia klucza S₁ oznaczymy x₁,...,x₆, a wyjścia y_1, y_2, y_3, y_4, to zapis w tablicy 2.3 rozumiemy następująco: dla wektora x = (000000) wyjścia y są liczbą binarną, której zapis dziesiętny jest L = 14 (czyli 1110), dla x = (000001), L = 4, wreszcie dla x = (111111), L = 13.

Funkcje boolowskie reprezentowane odwzorowaniem f, jakkolwiek możliwe do bezpośredniej realizacji technicznej, nie są najlepszą formą do zastosowań w strukturach bramkowych. Znacznie wygodniejsze w tym przypadku są reprezentacje funkcji w postaci wyrażeń boolowskich (formuł boolowskich). Ich zaleta wynika przede wszystkim z łatwej realizacji elementów logicznych zwanych bramkami logicznymi, które to elementy stanowią naturalną realizację wyrażeń boolowskich, gdzie występują w postaci operatorów.

Dla funkcji opisanej tablicą prawdy podaną w tabl. 2.1a odpowiednia formuła boolowska jest następująca:

$f={\bar{x}}_1{\bar{x}}_2x_3+{\bar{x}}_1x_2x_3+x_1{\bar{x}}_2x_3+x_1x_2{\bar{x}}_3+x_1x_2x_3$

a jej realizacja na bramkach AND, OR, NOT pokazana jest na rys. 2.2.

W układzie kombinacyjnym z rys. 2.2 funkcja f, realizowana na jego wyjściu f, reprezentuje odwzorowanie z tabelki prawdy, co łatwo sprawdzić wprowadzając na wejścia układu odpowiednie wektory binarne i obliczając wartość uzyskaną na wyjściu y. Na przykład dla x₁ = x₂ = 0, x₃ = 1 na wyjściu bramki AND1 pojawi się sygnał o wartości 1, i w rezultacie wyjście y przyjmie wartość 1.

Natomiast dla x₁ = x₂ = x₃ = 0 na wyjściach wszystkich bramek AND będzie 0, a więc jednocześnie y przyjmie wartość 0, co jest zgodne z tablicą prawdy.

Rys. 2.2. Realizacja funkcji f: a) bezpośrednio, b) po uproszczeniu wg zasad algebry Boole’a

Niekwestionowaną zaletą formuł boolowskich jest możliwość ich upraszczania, a co zatem idzie możliwość uzyskiwania realizacji oszczędniejszych z punktu widzenia liczby bramek. Zasady formalne upraszczania formuł boolowskich związane są z prawami i własnościami algebry Boole’a. Stosując prawa algebry Boole’a, poprzednio podane wyrażenie na f można uprościć w sposób podany w następującym przykładzie.

Ostatecznie wyrażenie to można zrealizować w układzie kombinacyjnym, którego struktura – znacznie prostsza od poprzedniej realizacji – jest pokazana na rys. 2.2b.

Sens fizyczny minimalizacji i jej ogromne znaczenie praktyczne wynika z faktu, że oba układy: pierwotny i zminimalizowany działają identycznie. Zatem upraszczając wyrażenia boolowskie będziemy mogli jednocześnie uprościć ich realizację, np. zmniejszyć liczbę zastosowanych bramek co decyduje o kosztach realizacji i tym samym jest głównym czynnikiem zwiększającym konkurencyjność naszego produktu na rynku.

Zasygnalizowany tu proces upraszczania wyrażeń boolowskich ma ogromne znaczenie praktyczne i opracowano  dla jego potrzeb wiele zaawan­sowanych metod syntezy, które z technicznego punktu widzenia nazywa się metodami minimalizacji funkcji boolowskich. Wiele z nich doczekało się realizacji w postaci zaawansowanych narzędzi komputerowych i stanowi podstawę nowoczesnej syntezy logicznej.