Diagramma degli stati

[Shika93]

Ho un dubbio sulla costruzione del diagramma degli stati (questo per intenderci)

E' una sciocchezza farli se si ha la tabella della verità con stato presente, input e stato futuro.
Ma se non mi viene data, come faccio a ricavarlo da un qualunque circuito?

Noi abbiamo fatto diversi esempi tipo con FF J-K, D ecc dove le tabelle le si hanno già; ma se non ho niente, mi viene chiesto di progettare un qualunque circuito sequenziale che deve fare un certo lavoro, non penso che mi venga data la tabella degli stati, ma solo qual è lo scopo del circuito che devo realizzare.

[g.schgor]

Il diagramma degli stati deve essere ricavato dalla descrizione dettagliata
delle sequenze da realizzare (chiamata in gergo " specifica" e redatta
in genere dal committente).
E' indubbiamente uno dei punti critici, in quanto una descrizione a parole
non è quasi mai interpretabile univocamente. Sta nell'esperienza del
progettista del dispositivo individuare eventuali alternative e giungere
ad una sequenza definita.

[Shika93]

Quindi mi viene sempre data sempre la tabella degli stati?
Per esempio, se mi si chiede di progettare un contatore modulo 8, la tabella degli stati me la posso ricavare io perché non devo fare altro che quando ho lo stato presente a 000 devo andare in 001; quando ho lo stato presente a 001 devo andare in 010 e così via; ma se mi si chiede qualcosa di più complessa chessò tipo progettare un ascensore, devo avere già la tabella o me la devo ricavare in qualche modo?

[Shika93]

Per esempio, ho trovato un esercizio d'esame.

Progettare una rete sequenziale che riveli la presenza delle sequenze e , anche sovrapposte. La rete ha un solo ingresso e una sola uscita che vale se rivela una delle due sequenze, e vale altrimenti.

a)Costruire il diagramma degli stati
b)Minimizzare gli stati
c)Codificare gli stati e fare la sintesi della rete con FFT

esempio:



Io il punto a l'ho fatto così (non è completo)

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Dove gli stati

Non è completo nel senso che mancano i rimanenti stati ma non saprei come e dove metterli.

[DanteCpp]

Supponiamo di dover progettare un'ascensore per un palazzo di 3 piani [0:2], l'ascensore è dotato di 4 tasti. Il tasto "0" porta al piano terra o ci rimane se si è già la, cosi via per il tasto "1" e "2". In'oltre c'è un tasto speciale "E", emergency. Quest'ultimo stato porta l'ascensore al piano terra e impedisce ogni suo futuro movimento.

un ottimo strumento matematico, per definire il comportamento del nostro ascensore sono gli automi a stati finiti, di cui puoi trovare una definizione formale in quest' articolo: http://www.electroyou.it/dantecpp/wiki/automi-e-linguaggi-formali.

Il primo passo è identificare l'insieme degli stati dell'FSA (Finite State Automaton), quest'insieme ha un'elemento per ogni possibile configurazione in cui si può trovare l'ascensore.

Esso può:
1) essere al piano terra con la possibilità di muoversi (P0)
2) essere al primo piano con la possibilità di muoversi (P1)
3) essere al secondo terra con la possibilità di muoversi (P2)
4) essere bloccato al piano terra (EE)

Quindi definiamo l'insieme degli stati Q = {P0,P1,P2,EE}.

Il secondo passo della definizione dell'automa è identificare il suo alfabeto, esso coincide con le etichette dei tasti dell'ascensore.
Quindi = {0,1,2,E}.

L'ultimo passo è definire la funzione di transizione , ragionando in questo modo:

Se siamo al piano terra e premiamo il tasto 0, restiamo al piano terra; quindi P0 = (P0,0).
Se siamo al piano terra e premiamo il tasto 1, finiamo al primo piano; quindi P1 = (P0,1).
Se ci troviamo in allora EE = (q,E).

E cosi via!

In fine tracciamo il graffo dell'automa (Q,):

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

In effetti si potrebbe anche disegnare direttamente il graffo a stati; ma se cerchi un'algoritmo, bé, tutti questi formalismi potrebbero aiutarti a costruirti un buon schema mentale.

Dante.

[Shika93]

Giusto una cosa sul grafo. Se sono in con ingresso dovrei andare in no?
perché è al contrario lì? Cioè da con ingresso vado in ?

Tornando al mio esempio, mi mancherebbero quindi gli stati di "reset" che fanno tornare il sistema al punto di partenza una volta identificata la sequenza?

Che sarebbe cioè la freccia che da B va ad A, da C torna ad A (riconosciuta la prima sequenza, quindi resetto);
da B torna ad A (quando trovo un 1) e da A resto in A (quando trovo un 1)

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

[DanteCpp]

P0 non rappresenta il piano terra, bensì rappresenta l'ascensore che si trova al piano terra con la possibilità di muoversi. Mentre lo stato EE designa l'ascensore che si trova al piano terra senza possibilità di muoversi.

Per quanto riguarda il tuo esercizio avrei una domanda, l'esempio che hai postato faceva parte della specifica oppure l'hai aggiunto tu?

[Shika93]

Ah si ok, mi era sfuggita sta cosa.

No, l'esempio non l'ho fatto io. C'era scritto sotto i tre punti. L'ha messo il prof.
Il fatto è che non capisco che prosegue così in maniera periodica oppure cambia ogni volta. Neanche i tre puntini ho inventato io...

Alla fine le sequenze sono queste

[DanteCpp]

Penso che i puntini indichino che la stringa possa essere arbitrariamente lunga, ma sempre costruita sull'alfabeto 0,1. Prova a vedere il seguente automa con output, che ho sintetizzato. Se non m'è sfuggito qualcosa dovrebbe rispettare la specifica!

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

[c1b8]

Potrei sbagliare, ma quando sono in D e ricevo uno '0' io sarei rimasto in D, non sarei tornato in A.