TC Moduł 2

From Studia Informatyczne

Grafika:TC_M2_Slajd1.png Układy logiczne – pojęcia podstawowe.

Grafika:TC_M2_Slajd2.png 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.

Grafika:TC_M2_Slajd3.png 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 \rightarrow 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.


Grafika:TC_M2_Slajd4.png Funkcja f może być przedstawiona w postaci tablicy prawdy. Jest to tablica o n+1 kolumnach i 2^n 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.

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

Grafika:TC_M2_Slajd6.png 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), \bar 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.


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

Grafika:TC_M2_Slajd8.png 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.


Grafika:TC_M2_Slajd9.png 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.

Grafika:TC_M2_Slajd10.png 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+\bar a =1 a \cdot \bar a = 0

Podwójna negacja:

\overline{\overline{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}=\overline{a} \cdot \overline{b} \overline{a \cdot b}=\overline{a}+\overline{b}

Grafika:TC_M2_Slajd11.png 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 \overline{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 \lor.


Grafika:TC_M2_Slajd12.png 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.

Grafika:TC_M2_Slajd13.png 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.

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

Grafika:TC_M2_Slajd15.png 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.