TC Moduł 2

Układy logiczne – pojęcia podstawowe.

---

Podstawą teoretyczną techniki cyfrowej są układy logiczne. Funkcjonalnie układy logiczne klasyfikujemy na układy kombinacyjne i układy sekwencyjne. Wykład rozpoczynamy od układów kombinacyjnych. 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_1,...,x_n$ nazywamy odwzorowanie $f:X\to Y$, gdzie $X\subseteq B^n,Y\subseteq B^m$. Jeżeli $X=B^n$, 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 $2n$ wierszach. W kolejnych wierszach są zapisywane wszystkie wartości ciągu $x_1,...,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.

---

Oto przykłady uproszczonego zapisu funkcji boolowskich. Podane zapisy specyfikują funkcje boolowskie, których wektory wejściowe określone są liczbami dziesiętnymi.

---

Funkcje boolowskie reprezentowane odwzorowaniem $f$, jakkolwiek możliwe do bezpośredniej realizacji technicznej, nie są najlepszą formą do zastosowań. Znacznie wygodniejsze są reprezentacje funkcji w postaci formuł boolowskich. Ich zaleta wynika przede wszystkim z łatwej realizacji elementów logicznych zwanych bramkami logicznymi, które to elementy stanowią naturalną realizację formuł (wyrażeń) boolowskich, gdzie występują w postaci operatorów. Formuła boolowska to wyrażenie, w którym zmienne boolowskie połączone są operatorami: $+(OR),\cdot (AND),\overline{x}(NOT)$. Operatory te zdefiniowane są w tabelce podanej na planszy dla działań dwuargumentowych AND i OR i jednoargumentowego NOT, ale ich uogólnienie na operatory wieloargumentowe jest oczywiste.

---

Dla funkcji opisanej tablicą prawdy podaną w tabelce na planszy podajemy sposób tworzenia formuły boolowskiej.

---

A na tej planszy pokazana jest realizacja tej funkcji na bramkach AND, OR, NOT. W układzie kombinacyjnym z rysunku na planszy 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_1=x_2=0,x_3=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_1=x_2=x_3=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.

---

W dwuelementowej algebrze Boole'a wprowadza się też inne działania (operatory). Do najważniejszych z nich należą: zanegowany iloczyn (NAND), zanegowana suma (NOR), suma wyłączająca (tzw. suma modulo 2 lub różnica symetryczna, oznaczana EXOR). Operatorom tym odpowiadają stosowne symbole bramek.

---

Nie kwestionowaną 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. Własności stałych: $a+0=a$ $a+1=1$ $a\cdot 0=0$ $a\cdot 1=a$ Własności negacji: $a+\overline{a}=1$ $a\cdot \overline{a}=0$ Podwójna negacja: $\overline{\stackrel{‾}{a}}=a$ Idempotentność: $a+a=a$ $a\cdot a=a$ Przemienność: $a+b=b+a$ $a\cdot b=b\cdot a$ Łączność: $a+(b+c)=(a+b)+c$ $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ Rozdzielność: $(a+b)\cdot (a+c)=a+b\cdot c$ $a\cdot (b+c)=a\cdot b+a\cdot c$ Pochłanianie: $a+a\cdot b=a$ $a\cdot (a+b)=a$ Prawa De Morgana: $\overline{a+b}=\bar{a}\cdot \bar{b}$ $\overline{a\cdot b}=\bar{a}+\bar{b}$

---

W algebrze Boole’a, operacje "$+$" (dysjunkcja) i "$\cdot$" (koniunkcja) nazywa się również przez analogię do arytmetyki odpowiednio dodawaniem i mnożeniem. Operacje dodawania i mnożenia są przemienne oraz rozdzielne względem siebie. Elementy binarne 0 oraz 1 spełniają rolę elementu neutralnego odpowiednio względem operacji dodawania i mnożenia. Dla każdego elementu $a$ istnieje element $\bar{a}$, nazywany negacją, spełniający odpowiednie własności. Starszeństwo działań w algebrze Boole'a jest takie same jak w zwykłej arytmetyce (np. wyrażenie $a+bc$ interpretujemy jako $a+(bc)$, a nie jako $(a+b)c$, a nawiasy są opuszczane tam, gdzie nie prowadzi to do nieporozumień; opuszczamy także znak mnożenia "$\cdot$", a zamiast symbolu "$+$", często używamy symbolu $\vee$.

---

Stosując prawa algebry Boole’a, poprzednio podane wyrażenie na $f$ można uprościć w sposób pokazany na planszy. Ostatecznie wyrażenie to można zrealizować w układzie kombinacyjnym, którego struktura – znacznie prostsza od poprzedniej realizacji – jest pokazana na rysunku. 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.

---

Na planszy pokazujemy cały proces syntezy funkcji boolowskiej tzn. przejście od tablicy prawdy, której odpowiada skomplikowane wyrażenie boolowskie. Wyrażenie to można zrealizować bezpośrednio, ale taka realizacja nie jest korzystna z technicznego punktu widzenia. Znacznie lepsza jest realizacja funkcji zminimalizowanej.

---

Sens fizyczny minimalizacji i jej ogromne znaczenie praktyczne wynika z faktu, że oba układy: pierwotny i zminimalizowany działają identycznie.

---

Z tych powodów zastosowania omówionego procesu syntezy są w dzisiejszej technice ogromne i dotyczą tak ważnych zagadnień jak np. projektowanie skrzynek permutacyjnych układów kryptograficznych oraz projektowanie układów arytmetyki rozproszonej powszechnie stosowanych w cyfrowym przetwarzaniu sygnałów i obrazów.