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



Pobieranie 30,97 Kb.
Data19.04.2018
Rozmiar30,97 Kb.

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 (1,4,7) -symboliczniewszystkich zmiennych). c.) numeryczna funkcji :f(x,y,z)= (1,4,6) -symbolicznie zapisanazapisana postać kanoniczna sumy , f(x,y,z)= 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 + f .Dana funkcja f(x1,x2,...,xn)pokrywa g(x1,x2,...,xn)g2+...+gi+...+gn gi 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 ) yn . W= x1,x2,...,xn -słowoDTypy układów kombinacyjnych: a.) deszyfrator xn wejściowe binarne. y = f(w). W deszyfratorze na wyjściu pojawia się sygnał xn W=SZjedynka tylko na jednym określonym wyjściu. b.) szyfrator zn (z). Jedynka pojawia się tylko na jednymx1,x2,...,xn -słowo wyjściowe W= zn, W= x1,x2,...,xn -słowoMPokreślonym wejściu. c.) matryca przełączająca xn (W) d.) układ przełączający zwejściowe , U= z1,z2,...,zn -słowo wyjściowe , U= f Układ ten realizuje konkretną funkcję B , w składUPjednym wyjściem xn 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.
(q(t),z(t)]. y(t)=[q(t),z(t)] Funkcja wyjść  q(t+1)=Funkcja przejść
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ść:
[q(t),z(t)] Dla 2 y(t)=Dla 1 [q(t)]y(t)=
Automaty bez wyjścia (stosowane w procesie kompilacji)
y= [q(t),z(t)] Model formalny tego automatu to „piątka”(pusty) q(t+1)= 
Z – zbiór sygnałów wejściowych Q – zbiór stanów - funkcja przejść qo – stan początkowy automatu F – zbiór stanówwewnętrznych 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 Qautomat. F
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 Automat z parametrem wewnętrznym Automat parametryczny 2automaty skończone 1 Maszyna TuringaAutomat ze stosem 43
Automaty skończone bez wyjścia Automaty bez wyjścia służą do akceptacji odpowiednich języków formalych. . Determistyczne DFA (Deterministic FiniteAutomaty bez wyjścia dzielą się na: 1 . Niedetermistyczne NFA (Nondeterministic Finite Automaton)Automaton) 2
Automaty determistyczne DFA
Określa się je jako „piątka”  Z – alfabet wejściowy automatu, Q – zbiór stanów - funkcja przejść, qo – stan początkowy, F – zbiórwewnętrznych automatu, stanów końcowych
Z={z1,z2,...,zn}, Q={q1,q2,...,qn}, funkcja przejść Q, L(A) – język akceptowany przez automat[z(t),q(t)], Fq(t+1)= , 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 F to wówczas słowoQ. Jeżeli p(qo,wi)=p, pjednym ze swoich stanów końcowych: wi jest akceptowalne przez automat F, to słowo wi nie jest. Jeżeli p 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: W}F,wi(qo,wi)L(A)={w/
Działanie automatu bez wyjścia okresla się za pomocą tabeli przejść lub grafu automatu DFA.Automaty bez wyjścia NFA dzielą się -moves (z pustymi-moves (bez pustych przejść), 2.NFA with na 1.NFA without 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ą . Ten typ automatu charakteryzuje się tymprzejścia opisane przez sygnał pusty że istnieją w nim pewne takie stany wewnętrzne, dla których istnieje automatyczne przejście do....
wybierana jest wówczas, 1. Ścieżka Uwagi o zachowuje stan nagdy nie da się wybrać innej ścieżki, 2.wybranie ścieżki 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
YyiQqnZAutomaty z wejściem i wyjściem zi
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  - funkcjaZ – zbiór sygnałów we, Q – zbiór stanów wew., Y – zbiór sygnałów wy, - funkcja wy, q0 – stan początkowyprzejść,
[q(t),z(t)] –AD)1 q(t+1)= [q(t),z(t)] – funkcja wyjść. Działanie automatu określonefunkcja przejść y(t)= .graf automatu AD)2.tablicę przejść, tablicę wyjść 2jest przez: 1 [q(t)] – funkcja wyjść. Działanie[q(t),z(t)] – funkcja przejść, y(t)=q(t+1)= graf automatu, oznakowaną tabelę przejść, 2automatu określone jest poprzez: 1 wyrażenie symboliczne (reprezentowane grafem automatu).3
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 . .Każdej aizj automatu Mealy’ego przyporządkowuje się stan bij automatu1 Moore’a. Ponadto stanowi początkowemu a0 przyporządkowuje się stan b0 automatu bij, T1 – tab przejść, T2 – tab wyjść, Tablic T3 powstaje przezMoore’a aizj Budujemy tablicę przejść automatu Moore’a (T4) N – liczbanałożenie T1 i T2 2 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 Tworzymy tabelę T5, gdzie zapisujemy nowe stany i redukujemy stanyindeksem. 4 ekwiwalentne.
.TablicaPrzejście z automatu Moore’a na automatu Mealy’ego 1 przejść automatu Mealy’ego jest taka sama jak tablica przejść automatu Moore’a T5. Tablicę 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 .Przeprowadzamy redukcję kolumn ekwiwalentnych (zarówno w T6 jak i w T7)i2 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




©operacji.org 2019
wyślij wiadomość

    Strona główna