Logika Układów Cyfrowych-ściąga

Wyrażenia Booleowskie : zmienne booleowskie połączone znakami operacji logicznych.

Funkcje przełączające (Booleowskie) :Funkcja f(x1,..,xn) nazywa się funkcją przyłączającą ,jeżeli zarówno ona jak i jej argumenty przyjmują tylko wartość 0 lub1

Postać kanoniczna funkcji booleowskiej :Pierwotną postacią funkcji B jest tabela prawdy. Mamy 2 postacie kanoniczne funkcji B : kanoniczna sumy i kanoniczna iloczynu. Dla postaci kanonicznej sumy wybieramy te wiersze tablicy prawdy dla których funkcja przyjmuje wartość 1 . Zero traktowane jest jako negacja danego argumentu, a 1 jako argument bez negacji.

Postacie funkcji booleowskiej :a.) kanoniczna sumy (suma iloczynów wszystkich zmiennych).b.) kanoniczna iloczynu (iloczyn sum wszystkich zmiennych). c.) numeryczna funkcji :f(x,y,z)=(1,4,7) -symbolicznie zapisana postać kanoniczna sumy , f(x,y,z)=(1,4,6) -symbolicznie zapisana postać kanoniczna iloczynu. d.) normalna :występuje wtedy gdy w postaci kanonicznej sumy lub iloczynu nie występują wszystkie symbole zmiennych.

Minimalizacja funkcji B metodą siatek Karnougha (diagramów Veitcha) : a .)zakreśla się obszary 2n jedynek. b.)zakreślone obszary mogą się na siebie nakładać .c.) w postaci minimalnej zapisujemy te zmienne które się nie zmieniają

Minimalizacja funkcji B metodą Quinea Mc Cluskyego : Stosuje się ją najczęściej dla liczby zmiennych >5. Metoda ta sprowadza się do rozkładu funkcji na tak zwane implikanty proste i wyboru ze zbioru implikantów prostych minimalnej ich liczby pokrywanych przez daną funkcję. Implikantem prostym danej funkcji B nazywamy elementarny składnik występujący w zminimalizowanej normalnej postaci sumy tej funkcji, który jest pokrywany przez daną funkcję f= g1 + g2+...+gi+...+gn gif .Dana funkcja f(x1,x2,...,xn)pokrywa g(x1,x2,...,xn) jeżeli funkcja f posiada w tabeli prawdy wartość 1 we wszystkich tych wierszach w których funkcja q posiada również wartość 1.

Układy logiczne z bramkami NAND i NOR : W praktyce zamiast bramek and ,or ,not stosuje się bramki NAND :NOR ,które łatwiej jest wykonać na tranzystorach czy układach scalonych .Po za tym zapewniają one stałość amplitudy. Procedura przejścia z układu and/or/not na układ NAND(nor) : A) na podstawie wyrażenia B ,rysujemy schemat logiczny z bramkami and /or /not. B) W schemacie tym bramki and /or /not zastępujemy równoważnymi bramkami NAND/NOR . C) Przeprowadzamy uproszczenie schematu logicznego eliminując szeregowo połączone bramki.

Układy logiczne dzielą się na układy kombinacyjne i sekwencyjne. Układy kombinacyjne różnią się od sekwencyjnych tym ,że nie występuje proces pamiętania. W układach sekwencyjnych dodatkowo występuje pamięć.

Układy kombinacyjne : układy logiczne realizujące określoną funkcję B i zbudowane z bramek (funktorów logicznych ) Typy układów kombinacyjnych: a.) deszyfrator xnDyn . W= x1,x2,...,xn -słowo wejściowe binarne. y = f(w). W deszyfratorze na wyjściu pojawia się sygnał jedynka tylko na jednym określonym wyjściu. b.) szyfrator znSZ xn W= x1,x2,...,xn -słowo wyjściowe W=(z). Jedynka pojawia się tylko na jednym określonym wejściu. c.) matryca przełączająca xn MP zn, W= x1,x2,...,xn -słowo wejściowe , U= z1,z2,...,zn -słowo wyjściowe , U=(W) d.) układ przełączający z jednym wyjściem xn UP f Układ ten realizuje konkretną funkcję B , w skład takiego układu wchodzą sumatory, półsumatory , subtraktory.

Układy sekwencyjne :układy logiczne mające pamięć, zdolne do zapamiętywania swoich stanów. Składają się z bramek i pamięci. Dzielą się na : A) synchroniczne (działają w ściśle określonym momencie czasu)-występuje zegar. B) asynchroniczne (działają wówczas gdy pojawia się sygnał na wejściu). Pamięć zbudowana jest z jednobitowych elementów pamięciowych .Jednobitowym elementem pamięciowym jest przerzutnik ‘ flip-flop’.

Automaty

Automat skończony definiowany jest jako model formalny dyskretnego systemu lub procesu przebiegającego w dyskretnych chwilach czasu.Automat nazywamy skończonym, bo działa w oparciu o skończony zbiór stanów wewnętrznych automatu.

Automat skończony najlepiej rozpatrywać jako czarna skrzynka

Q - zbiór stanów wewnętrznych automatu, Z – zbiór sygnałów wejściowych, Y – zbiór sygnałów wyjściowych

Na tych trzech zbiorach określone są funkcje charakteryzujące działanie automatów skończonych.

Funkcja przejść  q(t+1)=[q(t),z(t)] Funkcja wyjść  y(t)=(q(t),z(t)].

Rozróżniamy dwa typy automatów z wejściem i wyjściem: 1. automat Mealy’ego 2. automat Moore’a

Funkcja przejść jest taka sama dla automatu Mealy’ego i Moore’a, różnią się tylko funkcją wyjść:

Dla 1 y(t)=[q(t),z(t)] Dla 2 y(t)=[q(t)]

Automaty bez wyjścia (stosowane w procesie kompilacji)

y= (pusty) q(t+1)=[q(t),z(t)] Model formalny tego automatu to „piątka” 

Z – zbiór sygnałów wejściowych Q – zbiór stanów wewnętrznych  - funkcja przejść qo – stan początkowy automatu F – zbiór stanów końcowych automatu. Automaty bez wyjścia służą do akceptacji języków formalnych. Jeżeli po odczycie całego słowa automat znajdzie się w jednym z określonych stanów końcowych F, to mówimy, że słowo wejściowe zostało zaakceptowane przez automat. FQ

Automaty bez wejścia (automaty skończone z wyjściem). Służą do modelowania układów generujących słowa jakiegoś języka.

Bardziej złożone automaty skończone 1 Automat parametryczny 2Automat z parametrem wewnętrznym 3Automat ze stosem 4 Maszyna Turinga

Automaty skończone bez wyjścia Automaty bez wyjścia służą do akceptacji odpowiednich języków formalych. Automaty bez wyjścia dzielą się na: 1. Determistyczne DFA (Deterministic Finite Automaton) 2. Niedetermistyczne NFA (Nondeterministic Finite Automaton)

Automaty determistyczne DFA

Określa się je jako „piątka”  Z – alfabet wejściowy automatu, Q – zbiór stanów wewnętrznych automatu,  - funkcja przejść, qo – stan początkowy, F – zbiór stanów końcowych

Z={z1,z2,...,zn}, Q={q1,q2,...,qn}, funkcja przejść q(t+1)=[z(t),q(t)], FQ, L(A) – język akceptowany przez automat , W={w1,w2,...,wn}. Słowo zbudowane z liter alfabetu wejściowego jest akceptowalne przez automat DFA wtedy, gdy pod wpływem tego słowa automat znajdzie się w jednym ze swoich stanów końcowych: (qo,wi)=p, pQ. Jeżeli pF to wówczas słowo wi jest akceptowalne przez automat . Jeżeli pF, to słowo wi nie jest akceptowalne.Językiem akceptowalnym przez automat bez wyjścia jest zbiór słów zbudowany z liter alfabetu wejściowego i zapisany w następujący sposób: L(A)={w/(qo,wi)F,wiW}

Działanie automatu bez wyjścia okresla się za pomocą tabeli przejść lub grafu automatu DFA.Automaty bez wyjścia NFA dzielą się na 1.NFA without -moves (bez pustych przejść), 2.NFA with -moves (z pustymi przejściami) AD)1 w grafie tego automatu występują niejednoznaczne przejścia, np. pod wpływem sygnału z1 automat może przejść ze stanu q1 do stanu q2 lub q3. Automat NFA również określony jest przez „piątkę”  (q(t),z(t))={q1(t+1),q2(t+1),...,qn(t+1)}. AD)2 W grafie tego automatu istnieją przejścia opisane przez sygnał pusty . Ten typ automatu charakteryzuje się tym że istnieją w nim pewne takie stany wewnętrzne, dla których istnieje automatyczne przejście do....

Uwagi o  1. Ścieżka  wybierana jest wówczas, gdy nie da się wybrać innej ścieżki, 2.wybranie ścieżki  zachowuje stan na wejściu, jego wartość rozpatrywana jest podobnie w następnym stanie. Zbiór słów akceptowalnych jest nieskończenie wielki. Zbiór słów akceptowalnych przez ten automat można zapisać za pomocą wyrażenia regularnego 0*1*2*. Wyrażenia regularne Język akceptowany przez automaty skończone bez wyjścia (DFA i NFA) najdogodniej wyraża się za pomocą tzw. wyrażeń regularnych. Język jest to zbiór słów akceptowanych przez dany automat. Wyrażenie regularne jest to wyrażenie opisujące pojedynczy zbiór słów lub zbiór słów będących produktem wykonywania na zbiorach słów operacji sumy, konkatenacji iteracji.

Ekwiwalentność między wyrażeniem regularnym a automatem NFA z pustymi przejściami akceptującym język reprezentowanym przez to wyrażenie.Tw. Jeżeli „r” jest wyrażeniem regularnym to istnieje automat NFA z pustymi przejściami (z jednym stanem końcowym), który akceptuje język (zbiór słów) opisany przez to wyrażenie.

Automaty , w których nie zachodzi potrzeba zapamiętywania informacji (całości lub częsci) wprowadzanej lub przekształcanej nazywamy Automatami bez pamięci. Czyli automaty te są niezależne od czasu. Nazywane też jako automaty kombinacyjne. Układem kombinacyjnym będziemy nazywali obiekt abstrakcyjny (lub fizyczny) realizujący daną funkcje kombinacyjną. Wyróżniamy ukł kom. jednowyjściowe (y=f(a,b,c,d))i wielowyjściowy (yi=fi(a,b,c,d)) i=1,2,3.... Rozmieszczenie elementów przełączających i sposób ich połączenia nazywamy strukturą układu kombinacyjnego

Automaty z wejściem i wyjściem ziZqnQyiY

Wyróżniamy 2 typy automatów z wejściem i wyjściem: 1. Automat Mealy’ego 2. a. Moore’a. Automaty z we i wy definiowane są jako następujące szóstki  Z – zbiór sygnałów we, Q – zbiór stanów wew., Y – zbiór sygnałów wy,  - funkcja przejść,  - funkcja wy, q0 – stan początkowy

AD)1 q(t+1)=[q(t),z(t)] – funkcja przejść y(t)=[q(t),z(t)] – funkcja wyjść. Działanie automatu określone jest przez: 1.tablicę przejść, tablicę wyjść 2.graf automatu AD)2 q(t+1)=[q(t),z(t)] – funkcja przejść, y(t)=[q(t)] – funkcja wyjść. Działanie automatu określone jest poprzez: 1 oznakowaną tabelę przejść, 2 graf automatu, 3 wyrażenie symboliczne (reprezentowane grafem automatu).

Przejście z automatu Mealy’ego na automat Moore’a def. Dwa automaty i posiadające jednakowe alfabety wej i wyj nazywamy ekwiwalentne, jeżeli dla dowolnego słowa podanego na wejście obu automatów, przy jednakowych stanach początkowych, słowo na wyjściu automatu jest takie samo jak słowo na wyjściu automatu . 1.Każdej aizj automatu Mealy’ego przyporządkowuje się stan bij automatu Moore’a. Ponadto stanowi początkowemu a0 przyporządkowuje się stan b0 automatu Moore’a aizjbij, T1 – tab przejść, T2 – tab wyjść, Tablic T3 powstaje przez nałożenie T1 i T2 2 Budujemy tablicę przejść automatu Moore’a (T4) N – liczba stanów automatu Moore’a ; N=n*m.+1 (n – liczba wierszy T3, m – liczba kolumn T3)

Dla każdego stanu wew automatu Mealy’ego przyporządkowujemy stan wew automatu Moore’a wg następującej zasady: jeżeli dany stan bij jest przyporządkowany elementowi ak, to w kolumnie bij tab T4 należy zapisać stany znajdujące się w kolumnie ak tab T3. Dla b0 sygnał wyjściowy jest dowolny. 3 Minimalizacja tabeli T4: T4 minimalizujemy przez szukanie kolumn ekwiwalentnych, tzn. kolumn, których wiersze 1,3,4 tab T4 są takie same. Zamiast kilku kolumn ekwiwalentnych zapisujemy jedną kolumnę i stany bij zamieniamy na stany z jednym indeksem. 4 Tworzymy tabelę T5, gdzie zapisujemy nowe stany i redukujemy stany ekwiwalentne.

Przejście z automatu Moore’a na automatu Mealy’ego 1.Tablica przejść automatu Mealy’ego jest taka sama jak tablica przejść automatu . Tae’a T5e. Wblicę wyjść automatu Mealy’ego otrzymuje się w ten sposób, że w miejsce symboli bij tablicy przejść automatu Mealy’ego Tab T6 wpisujemy symbole yn przyporządkowuje tym symbolom w wierszach 1 i 2 tablicy T5 Moore’a 2.Przeprowadzamy redukcję kolumn ekwiwalentnych (zarówno w T6 jak i w T7)i zapisujemy ostateczną tabelę przejść i wyjść dla automatu Mealy’ego.

Synteza strukturalna automatów na przykładzie automatu Moorea : Synteza strukturalna automatów polega na określeniu struktury logicznej automatu. Punktem wyjścia dla synteza strukturalnej jest oznakowana tabela przejść automatu Moorea.

A) Kodowanie stanów wewnętrznych liczbami binarnymi, stany wew automatu są pamiętane w pamieci zbudowanej z przerzutników. B) Kodowanie sygnałów wej i wyj C) Kodowanie tablicy przejść automatu. D) Kodowanie tablicy wyjść E) Dobranie odpowiedniego typu przekaźnika jako elementu pamiętającego F)Określenie tablicy wzbudzeń elementów pamięciowych automatu G) Określenie funkcji zakodowanych

wyjść automatu H) Rysowanie schematu blokowego automatu Moorea I)Rysowanie schematu logicznego