Wykład 4 Automaty, algebry i cyfrowe układy logiczne
12/3/2008 architektura komputerów w. 4 Automaty, algebry i cyfrowe układy logiczne Nieformalne wprowadzenie do logiki binarnej Określone są wartości logiczne: 1 (jedynka logiczna) 0 (zero logiczne) dla których używane są oznaczenia równoważne : 1 = prawda, Truth, H 0 = fałsz, False, L Określone są podstawowe działania na zmiennych logicznych (A,B,C,X,Q itp.) mnożenie (działanie oznaczane jest przez *, , AND, Ł) suma (działanie oznaczane jest przez +, OR, )
negacja (działanie oznaczane jest przez , NOT, ) architektura komputerów w 4 1 12/3/2008 Nieformalne wprowadzenie do logiki binarnej Następujące równania definiują działanie operacji logicznych iloczyn logiczny suma logiczna negacja 0 * 0 = 0 0 + 0 = 0 0 = 1 0 * 1 = 0 0 + 1 = 1 1 = 0 1 * 0 = 0 1 + 0 = 1 1 * 1 = 1 1 + 1 = 1 W równoważny sposób definiują działanie operacji logicznych tablice prawdy AND OR X Y Z = X * Y X Y Z = X + Y NOT 0 0 0 0 0 0 X Z = X 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 Nieformalne wprowadzenie do logiki binarnej Zmienne logiczne połączone symbolami operacji logicznych noszą nazwę wyrażeń logicznych (boole owskich) f = x y(z+ x) z+ x y architektura komputerów w 4 2 12/3/2008 Realizacja techniczna - bramki i układy logiczne Układy elektroniczne, które akceptują na wejściu i podają na wyjściu sygnały ustalone jako odpowiadające logicznej 1 i logicznemu 0 a których działanie można opisać operacjami logicznymi nazywane są bramkami logicznymi. Realizacja techniczna - bramki i układy logiczne Układy elektroniczne, które akceptują na wejściu i podają na wyjściu sygnały ustalone jako odpowiadające logicznej 1 i logicznemu 0 a których działanie można opisać operacjami logicznymi nazywane są bramkami logicznymi. architektura komputerów w 4 3 12/3/2008 Sieci logiczne. Elementarne układy kombinacyjne Nazwa Symbol graficzny Wyrażenie logiczne NOT y=x x y x1 y NAND y=x1x2 x2 x1 y NOR y=x1+x2 x2 x1 AND y y=x1x2 x2 x1 OR y=x1+x2 y x2 x1 XOR Y=x2x1+ x2x1 y x2 Realizacja techniczna - bramki i układy logiczne Układy zbudowane z bramek logicznych noszą nazwę układów (sieci) logicznych Przykład: F = X+ (Y Z) architektura komputerów w 4 4 12/3/2008 Realizacja techniczna - bramki i układy logiczne Układy zbudowane z bramek logicznych noszą nazwę układów (sieci) logicznych Przykład: f = x y(z+ x) z+ x y Nieco teorii architektura komputerów w 4 5 12/3/2008 Algebra Boole a Za historycznie pierwszą prace dotyczącą teorii sieci przełączających uważana jest praca Shannona A Symbolic Analysis of Relay and Switching Circuits (1938) Ideą było opracowanie systemu matematycznego pozwalającego na systematyczny opis i analizę układów przełączających. Shannon zastosował klasyczny rachunek zdań. Istnieje system algebraiczny, który zawiera aparat formalny do badania i syntezy sieci przełączających, równoważny rachunkowi zdań. To algebra Boole a Algebra Boole a opis aksjomatyczny Algebrą Boole a jest system: _ BOOL= gdzie B ma co najmniej dwa różne elementy 0 i 1 są stałymi nazywanymi zerem i jedynka boolowską - jest działaniem jednoargumentowym nazywanym dopełnieniem (negacją) +, są działaniami dwuargumentowymi (dodawaniem i mnożeniem) i dla dowolnych a,b i c B spełnione są następujące aksjomaty 1. (a + b) + c = a + ( b + c) łączność operacji + 2. (a b) c = a ( b c) łączność operacji 3. a + b = b + a przemienność operacji + 4. a b = b a przemienność operacji 5. ($!0)a + 0 = 0 + a = a istnienie elementu identycznościowego operacji + 6. ($!1)a 1 = 1 a = a istnienie elementu identycznościowego operacji + 7 a + (b c) = (a+b) (a+c) rozdzielność + względem 8. a (b + c) = (a b) + (a c) rozdzielność względem + 9. a + a = 1 i a a = 0 istnienie dopełnienia architektura komputerów w 4 6 12/3/2008 Algebra Boole a wyrażenia boolowskie Definicja. Wyrażenie boolowskie generowane przez zmienne x1,...,xn jest określone w następujący sposób: (1) 0 i 1 są wyrażeniami boolowskimi (2) jeżeli xi jest zmienną to xi jest wyrażeniem boolowskim dla i =1,...,n (3) jeżeli A jest wyrażeniem boolowskim to A jest wyrażeniem boolowskim (4) jeżeli A i B są wyrażeniami boolowskimi to A B jest wyrażeniem boolowskim (5) jeżeli A i B są wyrażeniami boolowskimi to A + B jest wyrażeniem boolowskim Przykład. Zbadajmy, czy A = x1 (x2 + x3) jest wyrażeniem boolowskim. Algebra Boole a prawa de Morgana i przekształcenia wyrażeń boolowskich a + b = a b a b = a + b architektura komputerów w 4 7 12/3/2008 Algebra Boole a prawa de Morgana i przekształcenia wyrażeń boolowskich Przekształcenia wyrażeń boolowskich x y = xy + xy = xy xy = (x+y)(x+y) = xx +xy+yx + yy = xy + x y Prawo de Morgana Prawo de Morgana Aksjomat 8 Aksjomat 9 Algebra Boole a funkcje boolowskie Definicja. Funkcją boolowską lub funkcją przełączającą f(x1,...,xn) nazywamy każde odwzorowanie zbioru {0,1}n w zbiór {0,1} Ponieważ zbiór {0,1}n ma 2n elementów a zbiór {0,1} dwa elementy to n Twierdzenie. Istnieje 22 funkcji przełączających n zmiennych _ Dla funkcji boolowskich zdefiniowane są operacje +, , oraz . architektura komputerów w 4 8 12/3/2008 Algebra Boole a funkcje boolowskie Funkcję boolowską można przedstawić w formie tzw tablicy prawdy Przykład. x1 x2 x3 f 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 Algebra Boole a funkcje boolowskie W praktyce funkcje boolowskie reprezentowane są przez wyrażenia boolowskie. Zwykle istnieje wiele wyrażeń boolowskich reprezentujących tę samą funkcję. Jeżeli x1,...,xn są zmiennymi boolowskimi to wyrażenie boolowskie będące konkatenacją wszystkich zmiennych lub ich negacji nosi nazwę iloczynu elementarnego. (np. dla n=3 x1 x2 x3 , x1 x2 x3 ) Podobnie wyrażenie boolowskie będące sumą wszystkich zmiennych lub ich negacji nosi nazwę sumy elementarnej. (np. dla n=3 x1 +x2 +x3 , x1 +x2 +x3 ) Jedna wyróżniona forma zapisu wyrażenia nosi nazwę postaci kanonicznej. Istnieją dwie równoważne postaci kanoniczne: kanoniczna postać sumy f(x1,...,xn) = SiI1 Pi oraz kanoniczna postać iloczynu: f(x1,...,xn) = PiI0 Si gdzie I1 i I0 są zbiorami tych indeksów, dla których f(x1,...,xn) przyjmuje odpowiednio wartość 1 lub wartość 0, Pi są iloczynami elementarnymi a Si elementarnymi sumami. architektura komputerów w 4 9 12/3/2008 Algebra Boole a funkcje boolowskie x x x f 1 2 3 Przykład 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 Funkcję boolowską przedstawioną wyżej opisuje odpowiadające jej wyrażenie kanoniczne sumy. f(x,y,z)=0x1x2x3 + 0x1x2x3 + 1x1x2x3 + 0x1x2x3 + 1x1x2x3 + 1x1x2x3 + 0x1x2x3 + 1x1x2x3 f(x,y,z)=x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 Algebra Boole a funkcje boolowskie x x x f 1 2 3 Przykład 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 lub równoważne mu wyrażenie kanoniczne iloczynu f(x,y,z)=(x1+x2+x3)(x1+x2+x3)(x1+x2+x3)(x1+x2+x3) architektura komputerów w 4 10 12/3/2008 Algebra Boole a funkcje boolowskie Użyte operacje sumy, iloczynu i negacji stanowią system funkcjonalnie pełny, to znaczy, że dal każdej funkcji logicznej można utworzyć wyrażenie ją reprezentujące zapisane za pomocą tylko tych operacji. Istnieją inne systemy funkcjonalnie pełne, np. Operacja NAND operacja NOR Algebra Boole a funkcje boolowskie Funkcje jednej zmiennej: f(x)=0 Stała zero f(x)=x powtórzenie f(x)=x negacja f(x)=1 Stała jeden Ważniejsze funkcje dwóch zmiennych Wyrażenie równoważne nazwa postaci normalnej zupełnej Iloczyn (AND) x x 2 1 x +x Suma (OR) 2 1 różnica (XOR) x x + x x 2 1 2 1 symetryczna architektura komputerów w 4 11 12/3/2008 Automat Definicja 1. Automatem nazywane jest urządzenie samoczynnie wykonujące czynności, zgodnie z założonym z góry algorytmem działania. Automat, którego cechą charakterystyczną jest to, że jest określony na zbiorze skończonych wartości dyskretnych i działa w dyskretnych odcinkach czasu jest nazywany automatem skończonym. Automat może być przedstawiony jako układ o n wejściach i m wyjściach. y1 x1 y2 x2 A xn ym Uporządkowany ciąg {xi}i=1..n nazywany jest wektorem (słowem) wejściowym. Podobnie ciąg {yi}i=1..m nazywany jest wektorem wyjściowym. Automat Szczególną klasą automatów są takie, dla których określony jest jeden, dwuelementowy zbiór wartości jakie mogą przyjmować zarówno składowe wektora wejściowego {xi}i=1..n jak i wektora wyjściowego {yi}i=1..m . architektura komputerów w 4 12 12/3/2008 Automat kombinacyjny Definicja 2. Sieć (układ, automat) kombinacyjna jest siecią, której wyjścia w chwili t zależą jedynie od wejść w chwili t. Działanie takiego automatu opisuje funkcja F={fi (x1,...,x)l=1..n}.J=1...m. Automat kombinacyjny Przykład: Chcemy zbudować automat dany funkcją logiczną x x x f 1 2 3 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 wyrażenia kanoniczne: architektura komputerów w 4 13 12/3/2008 Automat kombinacyjny Automat kombinacyjny architektura komputerów w 4 14 12/3/2008 Sieci logiczne. Postępowanie mające na celu znalezienie struktury wewnętrznej układu, który będzie działał zgodnie z założonym modelem - synteza. Postępowanie mające na celu identyfikację sposobu działania układu na podstawie badania jego struktury - analiza. Sieci logiczne. Układy kombinacyjne - synteza Algorytm: opis układu (funkcja(e) boole a) minimalizacja funkcji boolowskich (karty Karnaugha) schemat logiczny architektura komputerów w 4 15 12/3/2008 Sieci logiczne. Układy kombinacyjne - przykłady a b c1 c2 c3 c4 0 0 0 1 1 1 a c1 0 1 1 0 1 1 b 1 0 1 1 0 1 1 1 1 1 1 0 c2 c3 c3 c4 Dekoder 2 na 4 Sieci logiczne. Układy kombinacyjne - przykłady a b s f 0 0 0 0 A 0 1 0 0 1 0 0 1 F 1 1 0 1 S 0 0 1 0 0 1 1 1 B 1 0 1 0 1 1 1 1 F=AS+BS Multiplekser architektura komputerów w 4 16 12/3/2008 Sieci logiczne. Układy kombinacyjne - przykłady X1 X1 Y1 Y1 X2 X2 Y2 Y2 X1 Y1 X2 Y1=X1X2 Y2=X1X2 Y2 Schematy logiczne zrealizowane z użyciem bramek AND i OR, AND i XOR oraz NAND Sieci logiczne. Układy kombinacyjne - przykłady architektura komputerów w 4 17 12/3/2008 Automat Definicja 3. Sieć (układ, maszyna) sekwencyjna jest urządzeniem, którego wyjścia w chwili t zależą od wszystkich wejść w chwilach p, gdzie 0 Ł p < t. Automat taki może być opisany sekwencją słów wejściowych i odpowiadających im sekwencji słów wyjściowych. Automat deterministyczny to taki, który na określona sekwencje słów wejściowych odpowiada zawsze tą samą sekwencją słów wyjściowych. Automat sekwencyjny może być traktowany jako automat z pamięcią. Zawartość tej pamięci - stan automatu. Działanie takiego automatu opisuje para funkcji: funkcja przejść a(X,Q) gdzie X jest zbiorem słów wejściowych a Q zbiorem stanów automatu oraz funkcja wyjść l(Q) (lub równoważnie l(X,Q)) Funkcja wejść określa jakie słowo wejściowe (czyli jaka kombinacja stanów na wejściach automatu) powoduje przejście ze stanu, w jakim automat się znajduje do pewnego stanu następnego. Funkcja wyjść określa słowo wyjściowe (czyli stan na wyjściach automatu) Automat Przykład: Chcemy zdefiniować automat (zamek szyfrowy), który posiada jedno wyjście otwierające zamek i klawiaturę, na której, aby zamek otworzyć trzeba wcisnąć kolejno klawisze 4 2 5 1. Klawiatura posiada pięć klawiszy (1,2,3,4 i 5) Funkcję przejść można przedstawić w formie grafu, którego węzły reprezentują stany automatu a gałęzie przejścia między stanami 3 1 1 4 5 1 4 2 1 2 3 4 5/Y 5 2 3 4 podobnie będą wyglądały przejścia ze stanu 4 architektura komputerów w 4 18 12/3/2008 Sieci logiczne. Elementarne układy sekwencyjne. Synteza. Warunki pracy układu zadane są przez wykres czasowy (poniżej), x1 y1 x2 y2 Układ zaprojektowany metodą tablic kolejności łączeń Sieci logiczne. Elementarne układy sekwencyjne Definicja. Sieć (układ, maszyna) sekwencyjna jest urządzeniem, którego wyjścia w chwili t zależą od wszystkich wejść w chwilach p, gdzie 0 Ł p < t. Jeżeli układ działa według własnej skali czasu mówimy o układzie asynchronicznym. Układy z zewnętrzną skalą czasu nazywamy układami synchronicznymi. W praktyce działanie układu synchronizuje najczęściej sygnał zewnętrzny o regularnym przebiegu, nazywany zegarem. Podstawowe elementy pamięciowe nazywane są przerzutnikami. Przerzutnik zależnie od typu ma co najmniej dwa wejścia i zwykle dwa wyjścia architektura komputerów w 4 19 12/3/2008 Sieci logiczne. Elementarne układy sekwencyjne. Przerzutnik RS 00 01 11 10 RS R Q 0 0 1 X 0 1 1 1 X 0 Q S Q Q Q - stan wyjść w chwili t Q - stan wyjść w chwili t+1 Sieci logiczne. Elementarne układy sekwencyjne. Przerzutnik D 0 1 D 0 0 1 Q 1 0 1 C Q Q Q D C D Q Przerzutnik typu D typu latch (zatrzask) architektura komputerów w 4 20 12/3/2008 Sieci logiczne. Elementarne układy sekwencyjne. Przerzutnik D PRE D Q Q CLR Przerzutnik typu D wyzwalany zboczem (narastającym) z wejściami zerującym i ustawiającym (SN7474) i jego symbol graficzny Sieci logiczne. Układy sekwencyjne. Rejestr równoległy. RD 5-bitowy rejestr równoległy z układami zapisu i I0 D Q odczytu zbudowany z przerzutników typu D B0 WR wyzwalanych zboczem opadającym Q I1 D Q B1 Q I2 D Q B2 Q I3 D Q B3 Q I4 D Q B4 Q architektura komputerów w 4 21 12/3/2008 Sieci logiczne. Układy sekwencyjne. Q4 Q3 Q2 Q1 Q0 I D Q D Q D Q D Q D Q Q Q Q Q Q C 5-bitowy rejestr przesuwający (zapis szeregowy, odczyt równoległy) zbudowany z przerzutników typu D wyzwalanych zboczem opadającym Sieci logiczne. Układy sekwencyjne. Q0 Q1 Q2 D Q D Q D Q C Q Q Q C Q0 Q1 Q2 3-bitowy licznik asynchroniczny. Typ przerzutników jak poprzednio. architektura komputerów w 4 22