Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Macchine a stati finiti

Elettronica lineare e digitale: didattica ed applicazioni

Moderatori: Foto Utentecarloc, Foto Utenteg.schgor, Foto UtenteDirtyDeeds, Foto UtenteIsidoroKZ, Foto UtenteBrunoValente

0
voti

[1] Macchine a stati finiti

Messaggioda Foto Utentexshell » 29 ott 2008, 17:16

Buongiorno a tutti.

Non so se questa è la sezione adatta... casomai cancellate questo topic.

Tempo fa avevo studiato la progettazione delle macchine a stati finiti col metodo ASM (Abstract State Machine, che non c'entra niente con l'assembly). Con il metodo ASM si progettavano delle macchine a stati finiti considerando dei blocchi di stato (dei rettangoli), dei blocchi decisionali (dei rombi) e dei blocchi condizionali (degli ovali, solo per la macchina di Mealy, non per quella di Moore).

Ora, io so che ogni blocco di stato è costituito da un bistabile... e quindi il circuito della macchina a stati finiti è costituito da molti bistabili (flip-flop) collegati fra loro. Qualcuno sa come trasformare l'abstract state machine in schema circuitale costituito da bistabili?

Ormai le macchine a stati finiti non si usano più, perché sono circuiti giganteschi, quindi adesso sono state sostituite dai circuiti integrati, molto più piccoli e agevoli, ma mi interesserebbe lo stesso conoscere la struttura della MSF.

Inoltre, gentilmente, potrei sapere quando si inseriscono i blocchi condizionali nella macchina di Mealy? Io sapevo che possono essere aggiunti dopo un blocco decisionale per risparmiare uno stato, quando non si ritorna al blocco di stato precedente. E' vero?

Ringrazio in anticipo per le risposte.
Avatar utente
Foto Utentexshell
0 3
 
Messaggi: 14
Iscritto il: 14 apr 2008, 17:44

0
voti

[2] Re: Macchine a stati finiti

Messaggioda Foto Utenteg.schgor » 29 ott 2008, 18:24

Penso che questo possa rispondere ai quesiti posti:
http://www.cs.umd.edu/class/sum2003/cms ... /impl.html
(altrimenti suggerirei di definire un esempio concreto da risolvere).
Avatar utente
Foto Utenteg.schgor
54,6k 9 12 13
G.Master EY
G.Master EY
 
Messaggi: 16430
Iscritto il: 25 ott 2005, 9:58
Località: MILANO

0
voti

[3] Re: Macchine a stati finiti

Messaggioda Foto Utentexshell » 29 ott 2008, 19:10

La rigrazio per la risposta... però non riesco a capire benissimo il contenuto della pagina web che mi ha fornito.

Le chiedo dunque un favorone, se ha pazienza... le propongo un esercizio che ho svolto.

TESTO:
Programmare una macchina a stati finiti con il metodo dell'abstract state machine. La macchina possiede in ingresso una linea seriale LIN, sincrona con il clock esterno alla macchina. La macchina controlla due bistabili SR asincroni tramite le uscite S1, R1, S2, R2 e genera anche due uscite RDY e ERR.

La macchina riceve sulla linea seriale LIN dei pacchetti: ogni pacchetto è costituito da 5 bit. Il primo bit (bit di start) è sempre al valore logico 1. Il secondo e il terzo bit rappresentano l'informazione da trasmettere. Il secondo bit è trasmesso per mezzo del primo bistabile sull'uscita U1, il terzo bit è trasmesso dal secondo bistabile sull'uscita U2. Il quarto è il quinto bit rappresentano i bit finali (bit di stop) e sono entrambi al valore logico 0. Se il pacchetto è ricevuto correttamente, cioè se i bit di stop sono entrambi a zero, la macchina attiva l'uscita RDY, altrimenti attiva l'uscita ERR. Le uscite RDY e ERR devono essere mantenute fino alla ricezione del pacchetto successivo. Ogni pacchetto è diviso da almeno 3 bit al valore logico 0.

Questa è l'immagine dello schema ASM della macchina a stati finiti che ho fatto io:
Immagine

Due domande:
1.
    Il testo specifica che ogni pacchetto è diviso da 3 bit a zero... questa informazione serve semplicemente per semplificare le cose o devo fare pure il controllo dei 3 bit al valore logico 0? (Però non è specificato cosa potrebbe succedere se al posto dei 3 bit a zero arrivasse un 1...). Nello schema che ho fatto, non ho eseguito il controllo dei 3 bit a 0. Ho fatto bene?
2.
    Come posso trasformare tale schema in circuito con i bistabili collegati? Da quali tipi di bistabili è composta? SR, JK, D, T?
3.
    Quella che ho fatto è la Macchina di Gordon Moore... come potrei trasformala in Macchina di Mealy, con le uscite condizionate?
Avatar utente
Foto Utentexshell
0 3
 
Messaggi: 14
Iscritto il: 14 apr 2008, 17:44

0
voti

[4] Re: Macchine a stati finiti

Messaggioda Foto Utenteg.schgor » 30 ott 2008, 1:16

Rispondo alle domande:
1) Ritengo che un controllo sui 3bit =0 finali vada fatto (ma questo mi sembra secondario)
2,3) La struttura indicata e' una fow-chart piu' che una tavola degli stati.

Credo vada innanzitutto chiarito che tipo di soluzione e' richiesta: da quanto si puo' vedere
nella trattazione da me segnalata, il numero di FF occorrente puo' essere minimizzato ricorrendo
ad una ROM (che evidenzia le condizioni di transizione).In questo caso i FF non hanno piu' un
significato "fisico", ma servono da indirizzo della ROM.
Altro tipo di soluzione (che seguirebbe meglio la tua struttura) e' invece una serie di FF
che memorizza i bit entranti (ma non so se questo rientrerebbe nella definizione di macchina
di Mealy).
Ti chiedo quindi di precisare (in base ad eventuali esempi del tuo testo) quale scegliere.
Avatar utente
Foto Utenteg.schgor
54,6k 9 12 13
G.Master EY
G.Master EY
 
Messaggi: 16430
Iscritto il: 25 ott 2005, 9:58
Località: MILANO

0
voti

[5] Re: Macchine a stati finiti

Messaggioda Foto Utentexshell » 30 ott 2008, 10:04

g.schgor ha scritto:Rispondo alle domande:
La struttura indicata e' una fow-chart piu' che una tavola degli stati.


Il mio professore di elettronica digitale ci ha fornito un software per scrivere quegli schemi, come l'esempio precedente, presentandoceli come ASM. L'ASM è diverso dai flow-chart?

g.schgor ha scritto:Credo vada innanzitutto chiarito che tipo di soluzione e' richiesta: da quanto si puo' vedere
nella trattazione da me segnalata, il numero di FF occorrente puo' essere minimizzato ricorrendo
ad una ROM (che evidenzia le condizioni di transizione).In questo caso i FF non hanno piu' un
significato "fisico", ma servono da indirizzo della ROM.
Altro tipo di soluzione (che seguirebbe meglio la tua struttura) e' invece una serie di FF
che memorizza i bit entranti (ma non so se questo rientrerebbe nella definizione di macchina
di Mealy).
Ti chiedo quindi di precisare (in base ad eventuali esempi del tuo testo) quale scegliere.


Elenco in poche parole cosa ha spiegato il professore e cosa ha richiesto di fare:
Prima ha descritto la struttura logica dei vari flip-flop, successivamente ha presentato i registri PIPO, SISO, SIPO e PISO, infine la struttura "logica", con il metodo ASM (come il diagramma di flusso precedente). Ha anche accennato alla possibilità di trasformare il metodo ASM in uno schema logico (utilizzando le porte logiche).

Ho corretto il diagramma precedente con il controllo dei bit di stop a zero (non so se sia giusto):
Immagine

Infine ho caricato la macchina a stati finiti in un altro programma, per costruirne lo schema:
Immagine

Dal professore non è stato aggiunto altro.

La mia domanda è quindi: come si può trasformare, utilizzando le porte logiche, quel blocco che sintetizza la MSF?
Avatar utente
Foto Utentexshell
0 3
 
Messaggi: 14
Iscritto il: 14 apr 2008, 17:44

0
voti

[6] Re: Macchine a stati finiti

Messaggioda Foto Utenteg.schgor » 30 ott 2008, 12:15

Occorre definire quanti e che tipo di FF costituiscono il circuito "innominato"
Supponiamo 3 D-FF (8 possibili righe di tabella, per 2, in quanto la macchina di
Mealy considera anche lo stato degli ingressi, qui solo 1, che chiamiamo X)

Allora la tabella dovra' avere in ingresso i 3 stati dei FF + X ed in uscita i 3 stati
di abilitazione FF + le 6 uscite indicate dal blocco.
La compilazione della tabella e' facilitata dal fatto che in questo caso i 3 FF
eseguono in pratica un conteggio binario dei bit in arrivo, e che i corrispondenti
stati delle uscite sono noti.

Si tratta poi di implementare la tabella: semplicemente in una ROM (come nella
trattazione citata inizalmente), oppure con una configurazione di logica combinatoria
che fornisca gli appropriati segnali d'uscita in corrispondenza di ogni combinazione
degli ingressi.

Non so se tutto questo e' sufficientemente chiaro (altrimenti approfondiamo)
Raccomando di tener presente le figure "Sequential Circuit" e "Final Diagram" della
trattazione citata.
Avatar utente
Foto Utenteg.schgor
54,6k 9 12 13
G.Master EY
G.Master EY
 
Messaggi: 16430
Iscritto il: 25 ott 2005, 9:58
Località: MILANO

0
voti

[7] Re: Macchine a stati finiti

Messaggioda Foto Utentexshell » 31 ott 2008, 14:02

La ringrazio ancora per le risposte.

La macchina a stati finiti "innominata", avendo 14 blocchi di stato (nell'ultima mia versione) dovrebbe essere cotituita da quattro FF. Non so bene quale tipo di FF possa essere utilizzato... Lei ha proposto D. La macchina a stati finiti può essere costituita da FF di diverso tipo, come SR o JK, oppure servono solo i FF D?

Riguardo alle parti che compongono la MSF, quest'ultima dovrebbe essere formata (se non erro) da tre blocchi:

1) Rete combinatoria dello stato successivo
2) Registro di memorizzazione stato
3) Rete combinatoria dello stato precedente

Per progettare tali blocchi, devo utilizzare delle tabelle come ha suggerito lei e poi sintetizzarle con le mappe di Karnaugh? Come potrei scrivere delle tabelle di una MSF?
Avatar utente
Foto Utentexshell
0 3
 
Messaggi: 14
Iscritto il: 14 apr 2008, 17:44

0
voti

[8] Re: Macchine a stati finiti

Messaggioda Foto Utenteg.schgor » 31 ott 2008, 17:50

A me sembra che in realta' debbano bastare 3 FF (corrispondenti agli 8 bit del pacchetto)
La scelta dei D-FF e' arbitraria (ritengo solo piu' comodo fissare con l'Enable lo stato che
il FF assumera' dopo il clock). Ovviamente cambiando tipo, cambia la tabella degli Enable.

Allora, chiamando Q1,Q2,Q3 le uscite dei FF ed X lo stato dell'ingresso, l'indirizzo delle righe
della tabella sara' Q3/Q2/Q1/X
mentre le colonne della tabella saranno En3/En2/En1/S1/R1/S2/R2/RD/ER

All'inizio (indirizzo 0000) dovrebbe corrispondere una riga di tutti 0 (qualsiasi clock non
commuta nessun FF, quindi non cioe' avanzamento finche' X=0)
Quando X=1 (indirizzo seconda riga 0001) dobbiamo abilitare il primo FF (En1=1 che controlla
l'ingresso D di questo): il primo fronte d'onda del clock portera' Q1=1 e cambiera' l'indirizzo:
se, prima che arrivi un altro clock, X=0 andra' alla 3a riga, se X=1 alla 4a.
3a e 4a riga riguardano il bit dl primo dato; nelle uscite dovra' essere a seconda di X, R1=1
oppure S1=1.
e cosi' via....
Credo a questo punto che il meccanismo sia chiaro, quindi per ora mi fermo qui (in
attesa di commenti)
Avatar utente
Foto Utenteg.schgor
54,6k 9 12 13
G.Master EY
G.Master EY
 
Messaggi: 16430
Iscritto il: 25 ott 2005, 9:58
Località: MILANO

0
voti

[9] Re: Macchine a stati finiti

Messaggioda Foto Utentegiadad » 1 nov 2008, 16:43

Ciao...
da quello che ho capito il tuo problema è quello di dover sintetizzare la MSF. Dovrebbe essere abbastanza semplice se ho capito il problema. Innanzitutto devi capire quali e quante operazioni devi svolgere in modo da definire quale operazione effettuare tramite degli ingressi di selezione e quali segnali deve generare la MSF per controllare il sistema. Devi definirli per ogni stato e fare la tua ASM.
Poi devi valutare quanti stati hai e in base a questo scegliere il numero di bit che ti servono per rappresentare gli stati, se usi una codifica Gray è meglio in modo ca cambiare un solo bit tra uno stato e il successivo. A questo punto devi sintetizzare gli stati ad esempio con le mappe di Karnaugh (non so se l'ho scritto correttamente). La stessa cosa la devi fare per i segnali generati dalla ASM in modo da definire le uscite della macchina. A questo punto metti tutto insieme ed avrai delle evoluzioni che dipenderanno dai segnali di selezione della macchina e ovviamente dal clock che gli vai a fornire.
Spero di esserti stato di aiuto, ciao
Avatar utente
Foto Utentegiadad
0 1
 
Messaggi: 1
Iscritto il: 1 nov 2008, 16:25

0
voti

[10] Re: Macchine a stati finiti

Messaggioda Foto Utentexshell » 1 nov 2008, 21:45

Nonostante la vostra grande disponibilità e la buona volontà che ci metto per cercar di capire, non riesco...

La tabella non la so proprio scrivere...
Allegati
msf.zip
Abbozzo tabella...
(1.78 KiB) Scaricato 224 volte
Avatar utente
Foto Utentexshell
0 3
 
Messaggi: 14
Iscritto il: 14 apr 2008, 17:44

Prossimo

Torna a Elettronica generale

Chi c’è in linea

Visitano il forum: Nessuno e 50 ospiti