6/9/2014
Logički automati. Primjeri sinteze sekvencijalnih mreža. Vanr.prof.dr.Lejla Banjanović‐
Mehmedović
Definicija sekvencijalnih mreža
x1(t)
z1(t)
x2((t))
z2(t)
Y1
Yr
...
KOMBINACIONA
MREŽA
...
Xn(t)
zp(t)
sistema se definiše funkcijom u vremenu sa n ulaznih promenljivih i p izlaznih promenljivih
Z1
...
X1(t)
...
...
xN (t)
DIGITALNI
SISTEM
 Opšti model digitalnog ...
Zm
Y1(t)...Y
(t) Yp(t)
MEMORIJA
Ukoliko vrijednosti izlaznih promenljivih zavise ne samo od trenutnih
vrednosti ulaznih promenljivih nego i od prošlih vrijednosti (parova
ulaza-izlaza) za digitalni sistem se kaže da je sekvencijalni sistem ili
automat.
PLS
Mašine konačnog stanja
2
1
6/9/2014
Sekvencijalna kola
 Sekvencijalne mreže se redovno nazivaju i logičkim j
j
g
automatima jer se često primenjuju u oblasti automatskog upravljanja.  Kod n‐bitnih sekvencijalnih mreža postoje 2n različitih stanja.  Zbog konačnog broja stanja, sekvencijalne mreže se još nazivaju i automatima sa konačnim brojem stanja (engl. Finite state machine) PLS
Mašine konačnog stanja
3
Vremensko ponašanje automata
 Izlaz automata u trenutku t, označen sa z(t), zavisi od




PLS
ulazne vremenski zavisne funkcije u intervalu (‐∞, t).
Vrijednosti ulazne vremenske funkcije x(‐∞, t) grupiše se u
klase tako da sve vremenske funkcije koje imaju isti uticaj
na izlaz u trenutku t, pripadaju istoj klasi.
Klase predstavljaju STANJA koja se označavaju promenljivom S. Njima se izražava uticaj prošlih ulaza na trenutne i buduće vrijednosti izlaza
trenutne i buduće vrijednosti izlaza.
U praktičnim sistemima broj klasa je konačan.
Ukoliko su ulazna i izlazna abeceda stanja konačne,
automat se naziva KONAČNIM.
Mašine konačnog stanja
4
2
6/9/2014
Formalni matematički opis sekvencijalnih sistema
 Apstraktni automat je matematički model prekidačkog upravljačkog automata koji se zadaje skupom od
k
d
k
d šest elemenata: l

X = (x1, x2, ..., xn)
Y = (y1, y2, ..., ym)
S = (s
( 1,, s2,, ..., s
, k)
S0
δ
λ
PLS
W=(X, Y, S, δ, λ, S0)
‐ skup ulaznih signala ili ulazna abeceda
(ulazna riječ automata)
‐ skup izlaznih signala ili izlazna abeceda
(izlazna riječ automata)
‐ skup stanja ili abeceda stanja
p
j
j
‐ početno stanje
‐ funkcija prelaza koja realizuje abecedno preslikavanje skupa S  X  S
‐ funkcija izlaza koja realizuje preslikavanje skupa S  X  Y
Mašine konačnog stanja
5
Vremensko modelovanje automata
 Zavisnost izlaza u trenutku t od ulaza i stanja u istom vremenskom trenutku izražava se tzv FUNKCIJOM IZLAZA
izražava se tzv. FUNKCIJOM IZLAZA
Z(t) = λ( X(t), S(t) )
 Uticaj ulazne vremenske funkcije se izražava i u odnosu na promjenu stanja, odnosno, novo stanje zavisi od trenutnog stanja i ulaza. U tom slučaju govori se o FUNKCIJI PRELAZA
S(t+∆) = δ( S(t), X(t) )
pri čemu je S(t) trenutno (sadašnje), a S(t+∆) slijedeće (naredno) stanje.
 Pošto sinhroni sekvencijalni sistemi mogu mjenjati stanje u diskretnim trenucima kontinualna promenljiva t se zamjenjuje diskretnom promenljivom definisanom pozitivnim cjelim brojem.
 Sistem je u stanju S(i) u vremenskom intervalu (t‐1=i‐1, t=i). Sinhrona sekvencijalna mreža se može opisati kao
Z(t) = λ( S(t), X(t) )
S(t+1) = δ( S(t), X(t) )
PLS
Mašine konačnog stanja
6
3
6/9/2014
Sinhrone i asinhrone sekvencijalne mreže
 Kod sinhronih mreža ulazi, izlazi i interna stanja se mjenjaju u diskretnim vremenskim trenucima, definisanim preko sinhronizacionog ulaza osnovnom frekvencijom takta sistema.
TAKT
X
S
Z
a)
Kod asinhronih sekvencijalnih mreža stanja se mogu mjenjati u bilo koje vrijeme, a ulazi mogu biti nivovski signali koji se javljaju u proizvoljnom intervalu vremena.
PLS
Mašine konačnog stanja
X
S
Z
b)
7
Logički automati
 Pored memorije, sekvencijalne mreže sadrže i j ,
j
kombinacione elemente (mreže). Na osnovu unutrašnje strukture razlikujemo dvije vrste logičkih automata:
 Mealy‐ev automat
 Moorov automat
PLS
Mašine konačnog stanja
8
4
6/9/2014
Milijev i Murov automat
X(t)
K M1
 U odnosu na funkciju izlaza u praksi se sreću dva slučaja:
REGISTAR
STANJA
 Automati prve vrste ili Milijevi (Mealy) automati definišu funkciju izlaza u obliku
Z(t)= λ( S(t), X(t) )
ST
S(t)
K M2
Z(t)
Milijev automat
X(t)
K M1
 Automati druge vrste ili automati Mura (Moore) definišu funkciju izlaza
Z(t)= λ( S(t) ) REGISTAR
STANJA
ST
S(t)
K M2
Z(t)
PLS
Mašine konačnog stanja
Murov automat
9
Zadavanje konačnog automata tabličnom metodom 1/2
 Milijev automat se opisuje tablicama prelaza i izlaza
Primjer 1: automat prve vrste (Milijev automat)
PLS
Mašine konačnog stanja
10
5
6/9/2014
Zadavanje konačnog automata tabličnom metodom 2/2
Primjer 2: nepotpuno definisan automat
Primjer 3: Murov automat (automat druge vrste)
Uopšteni Murov automat
PLS
Konačan Murov automat
Mašine konačnog stanja
11
Zadavanje konačnog automata grafom 1/3
 Graf automata je orijentisani graf čiji čvorovi odgovaraju stanjima, a lukovi prelazima između stanja.
l k i l i i
đ t j
 Dva čvora grafa automata Si i Sj (polazno i stanje prelaza) spajaju se lukovima usmjerenim od Si ka Sj ako u automatu postoji prelaz iz Si u Sj, tj. ako je Sj= δ(Si, Xr) pri nekom ulaznom signalu Xr.
 Luku (Si, Sj) grafa automata dodeljuje se ulazni signal X i izlazni signal Y=λ(S, X) ako je on definisan, a u protivnom se stavlja crtica.
 Ako prelaz automata iz stanja Si u Sj proizilazi pod uticajem nekoliko ulaznih signala, luku (Si, Sj) dodeljuju se svi ti ulazni signali i odgovarajući izlazni signali.
 Pri opisu Murovog automata u vidu grafa izlazni signal Ys=λ(Si) zapisuje se unutar čvora Si ili odmah pored njega
PLS
Mašine konačnog stanja
12
6
6/9/2014
Zadavanje konačnog automata grafom 2/3
 Luk u nekom čvoru Si može biti:
 povratni (Si, Si)
 odlazni (Si, Sj)
 dolazni (Sj, Si)
 Prema vrsti lukova u čvoru S, stanja automata su:
,
j
 izolovana ako čvor ima samo povratne grane
 prelazna
ako u čvoru nema dolaznih lukova
 ustaljena ako čvor nema odlaznih lukova.
PLS
Mašine konačnog stanja
13
Zadavanje konačnog automata grafom 3/3
Y1
X2
Y1
Y1
Y2
X1
Y2
X2
S0
X1
X2
S1
Y1
X1
Y2
Y1
X1
Y1
Y2
X2
Y1
X2
S0
X2
S3
X1
X1
Y1
X1
S1
X2
Y3
X2
X1
S3
X1
Y2
Y3
automat A2
X2
S4
Y3
S2
X1
X2
S2
automat A1
PLS
S1
X1
S0
S2
X2
Y3
automat A3
Mašine konačnog stanja
14
7
6/9/2014
Zadavanje konačnog automata matričnom metodom 1/2
 Matrično zadavanje automata vrši se preko kvadratne matrice t i C=Cij 
C Cij  čiji redovi
d i odgovaraju polaznim d
j l
i stanjima, a kolone stanjima prelaza.  Element Cij=Xp/Yq koji stoji na presjeku i‐te vrste i j‐te kolone u slučaju Milijevog automata, odgovara ulaznom signalu Xp koji izaziva prelaz iz stanja Si u Sj i izlaznom signalu Yq, koji se izdaje pri tom prelazu.
Automat A1
PLS
Mašine konačnog stanja
15
Zadavanje konačnog automata matričnom metodom 2/2
 Primjer zadavanja Murovog automata
Automat A3
PLS
Mašine konačnog stanja
16
8
6/9/2014
Elementarni automati i mreže
 Dva osnovna tipa memorijskih elemenata
 LEČ
 FLIP‐FLOP
S
R
PLS
‐ signali upravljanja kontrolisani nivoom
‐ signali kontrole odmjeravaju se na rastuću ivicu takt signala
1
X
2
Y
Mašine konačnog stanja
17
Sinteza logičkih automata
 Dijagrami stanja ili kombinacione tablice
 Kodiranje stanja (minimalan broj flip‐flopova, složenost kombinacione mreže, izbor tipa flip‐
flopova)
 Jednačine kombinacione mreže logičkog automata. Najjednostavnija jednačina za kombinacione mreže flip‐flop‐ova se dobija za D flip‐flop: na D ulaz treba dovesti novo (sljedeće) stanje flip‐flop‐a.  Povezivanjem kombinacione mreže sa odgovarajućim flip‐flop‐ovima nastaje kompletna mreža.
PLS
Mašine konačnog stanja
18
9
6/9/2014
Dijagram i tabela stanja
 (a) Sekvencijalna mreža, (b) dijagram stanja u slučaju Mealy‐jevog modela, (c) dijagram
stanja u slučaju Mooreovog modela.
PLS
Mašine konačnog stanja
19
Jednačine upravljanja za flip‐flop‐
ove
 Eksitaciona i izlazna kombinaciona tabela Mealy‐jevog automata
PLS
Mašine konačnog stanja
20
10
6/9/2014
Jednačine upravljanja za flip‐flop‐
ove
Eksitaciona i izlazna kombinaciona tabela
Moore-ovog automata
PLS
Mašine konačnog stanja
21
Formiranje kompletne sekvencijalne mreže
 Logička mreža koja realizuje Mealy‐jev automat
PLS
Mašine konačnog stanja
22
11
6/9/2014
Formiranje kompletne sekvencijalne mreže
 Logička mreža koja realizuje Moore‐ov automat
PLS
Mašine konačnog stanja
23
Programiranje ponašanja – slijedjenje zida
4-24
PLS
Mašine
konačnog
stanja
12
6/9/2014
Programiranje ponašanja – slijedjenje zida
 Više “brkova” dozvoljava sofisticirani način detekcije oblika objekta:
 Različiti oblici razmatrani kao nove ivice prema kojima se orjentiše:
PLS
Mašine konačnog stanja
4-25
Specifikacija dijagrama stanja i tabele istine
PLS
Mašine konačnog stanja
26
13
6/9/2014
Primjer: Mrav u labirintu
SENZORI: antene L i R, svaka 1 ako su
kontaktu sa nečim.
AKTUATORI: Korak naprijed F, 10stepeni okret TL i TR (lijevo, desno).
CILJ: NAPRAVITI MRAVA DOVOLJNO
PAMETNIM DA IZAĐE IZ LABIRINTA.
STRATEGIJA: “Desna antena prema
zidu“
PLS
Mašine konačnog stanja
27
Primjer: Mrav u labirintu
Akcija: idi naprijed sve dok ne udariš u
nešto!
PLS
Mašine konačnog stanja
28
14
6/9/2014
Primjer: Mrav u labirintu
Akcija: Okret na lijevo (CCW), tako da
ništa više ne dotičeš
PLS
Mašine konačnog stanja
29
Primjer: Mrav u labirintu
Akcija: Korak i okret malo na desno,
pogled prema zidu
PLS
Mašine konačnog stanja
30
15
6/9/2014
Primjer: Mrav u labirintu
Akcija: Korak i okret malo na lijevo dok
ne dotakneš ponovo
PLS
Mašine konačnog stanja
31
Primjer: Mrav u labirintu
Akcija: Korak i okret na desno sve dok
ne udari u okomit zid
PLS
Mašine konačnog stanja
32
16
6/9/2014
Primjer: Mrav u labirintu
Potrebna redukcija ekvivalentnih stanja!
PLS
Mašine konačnog stanja
33
Primjer: Mrav u labirintu
Evolucija: spajanje Wall1 i Corner stanja
u jedno stanje!
PLS
Mašine konačnog stanja
34
17
6/9/2014
Primjer: Mrav u labirintu
 Implementacija kroz tabele stanja i logičke jednačine
PLS
Mašine konačnog stanja
35
Primjer: Mrav u labirintu
 Implementacija sekvencijalne mreže
PLS
Mašine konačnog stanja
36
18
6/9/2014
Sekvencijalne mreže vs. mikrokontroleri
 Ulogu prikazanih sekvencijalnih mreža (praćenje ulaznih sekvenci) može da obavlja i jedan mikrokontroler koji je programiran na odgovarajući način.  Međutim, hardverska rješenja u ovakvim slučajevima su neuporedivo jednostavnija i brzina njihovog rada je
 znatno veća.
PLS
Mašine konačnog stanja
37
19
Download

Predavanje 10 - Vanr.prof.dr. Lejla Banjanović