Automa di Mealy

[jayeffe]

Ciao a tutti, sto riscontrando molta difficoltà su alcuni esercizi riguardanti gli automi a stati finiti.
In particolar modo quello che viene chiamato riconoscitore di sequenze.
Volevo quindi chiarire alcuni dubbi.

Ad esempio questo era il testo dell'esercizio:
Progettare un circuito che, dopo aver ricevuto la sequenza 111 o la sequenza 100, produca in output 1 ogni qualvolta il numero di 0 ricevuti risulti divisibile per 4 ricevuti (escludendo quelli ricevuti prima che la sequenza 111 o 100 si sia verificata).

Girando online o su qualche libro non sono riuscito a trovare un preciso algoritmo per costruire il grafo, che non riesco mai a disegnare.
Volevo capire come faccio a sapere quanti stati dovrò utilizzare, e soprattutto come vanno collegati tra loro gli stati.
Ho capito che devo valutare quando uno stato riceve bit uno e bit zero e capire se passa ad uno stato successivo oppure no ma non riesco mai a trovarmi.

Inoltre leggevo in rete che per capire se uno stato è "collegabile con un altro" bisogna valutare se tra gli stati presi in considerazione si ha variazione di un solo bit..

[rugweri]

Partiamo da un presupposto: DIMENTICA TUTTO QUELLO CHE HAI LETTO SU INTERNET. Si studia sui libri, non su siti web dove chi sa chi scrive ciò che gli gira per la testa.
Detto questo, andiamo avanti... per poterti rispondere, occorre determinare un dettaglio non indifferente: tu hai idea di cosa sia una macchina a stati finiti? Nel dubbio, te lo spiego io:

Una macchina a stati finiti deterministica è il modello matematico di un "computer limitatamente potente" (diciamo così, giusto per capirci), ed è definita, nell'ambito del progetto dei sistemi digitali, in una forma detta transductor form (o transducer form, fa lo stesso): una sestupla dove è l'alfabeto d'ingresso, è l'alfabeto d'uscita, è l'insieme degli stati, è la funzione di transizione dello stato, è la funzione che determina il valore dell'uscita e è l'insieme degli stati iniziali della macchina. Se dipende solo dallo stato corrente, ovvero , la macchina a stati finiti è una macchina di Moore; se invece dipende anche dall'ingresso, ovvero , la macchina a stati finiti è una macchina di Mealy.

Perché queste definizioni sono importanti? Innanzitutto, perché operare con entità che non si conoscono è una cretinata, e secondariamente perché la definizione della funzione di transizione dello stato risponde a una tua domanda: se noti, essa ha come dominio il prodotto cartesiano dell'alfabeto d'ingresso e dell'insieme degli stati e come immagine l'insieme degli stati, ovvero associa uno stato successivo ad ogni coppia ingresso-stato. In altri termini, la transizione da uno stato all'altro è determinata dallo stato presente e dal simbolo dell'alfabeto d'ingresso appena ricevuto.

Andiamo al tuo progetto: si tratta di un circuito logico, quindi sappiamo per certo che e .
ORA FERMIAMOCI.
Abbiamo ancora detto pochissimo del tuo progetto, ma già siamo giunti a un dettaglio importante: dato l'alfabeto di input, possiamo determinare la risposta ad una delle tue domande: le condizioni di transizione da uno stato all'altro saranno, dato per assodato lo stato in cui si trova la FSM, nella forma input = 0 o input = 1, perché il nostro alfabeto include solo quei due simboli, e dunque non ci aspettiamo che il nostro input abbia un altro valore.
Ora, valutiamo un attimo cosa deve fare il tuo circuito... io non ho capito una sillaba della tua specifica, la quale è redatta in una lingua che - permettimi di dirtelo - somiglia solo vagamente all'italiano, quindi me la "invento": poniamo che il tuo circuito debba buttar fuori un 1 ogni volta che riconosce una sequenza 111 o 100, e poi resettarsi in attesa di una nuova sequenza. Con questa specifica, il circuito opera sostanzialmente così:

- Stato 0, attesa dell'ingresso: se arriva un 1, allora sta iniziando una sequenza che potrebbe interessarci e quindi ci spostiamo allo stato 1, mentre se arriva uno 0 non ce ne frega niente e quindi possiamo rimanere in attesa.
- Stato 1, attendiamo l'input: se è uno 0, potremmo essere in presenza della seconda sequenza che ci interessa, quindi spostiamoci allo stato 2; se è un 1, potremmo essere in presenza della prima sequenza, quindi ci spostiamo allo stato 3.
- Stato 2, attendiamo l'input: se è un 1, non abbiamo completato la sequenza e torniamo allo stato 1 (NON allo stato 0, attenzione: non abbiamo completato la sequenza, ma l'ultimo input ricevuto è comunque un 1, quindi la sequenza potrebbe iniziare ora!); se è uno 0, siamo assolutamente in presenza della seconda sequenza di interesse, quindi andiamo allo stato 4 e mettiamo in output un 1.
- Stato 3, attendiamo l'input: se è un 1, siamo in presenza della prima sequenza, dunque andiamo allo stato 4 e mettiamo in output un 1; se è uno 0, non siamo in presenza di alcuna sequenza utile, quindi torniamo allo stato 0.
- Stato 4: abbiamo ottenuto una sequenza di interesse, quindi torniamo allo stato 0. Scartiamo l'input ricevuto in questo stato (se fai una cosa del genere in un circuito reale potenzialmente ti rendi passibile di violenza fisica... ma è tardi e sono stanco, quindi tagliamo corto e facciamo così).

Tutto 'sto discorso può essere rappresentato da questo diagramma (sono le due di notte... spero di averlo fatto bene):

Come vedi, di tutti quei trip assurdi che ti stavi facendo non c'è traccia... alcuni di essi hanno un fondamento reale, ma per ora lasciamoli stare: in questa prima fase, cerca di capire le (tante) cose che abbiamo appena visto, poi pensiamo al resto.

Ora, un ultimo dettaglio e poi me ne vado a letto: quella che ti ho proposto è una FSM che rappresenta la nostra specifica... ma non l'unica FSM: progettisti differenti potrebbero tirar fuori automi differenti. Giusto per farti un esempio: lo stato 4 non ci serve, quindi potremmo eliminarlo e far "ritornare" gli stati 2 e 3 allo stato 0, così:

Inutile dire che questo design è decisamente migliore: ha uno stato in meno, e soprattutto non si mangia l'input quando conclude la sequenza.

[jayeffe]

Ciao , innanzi tutto grazie per la risposta .

Mi trovo con tutti e due gli schemi
in linea generale pero non riesco a capire come creare le transizioni e come collegare gli stati tra loro ..
Non so se esiste qualche regola che vale in ogni caso.. se ad esempio devo guardare gli ultimi due bit della sequenza ...

[rugweri]

in linea generale pero non riesco a capire come creare le transizioni e come collegare gli stati tra loro ..
Non so se esiste qualche regola che vale in ogni caso.. se ad esempio devo guardare gli ultimi due bit della sequenza ...

Lascia stare i bit di codifica degli stati, che non c'entrano niente: la FSM è un modello computazionale, quindi deve descrivere il comportamento del tuo sistema, null'altro. Come sono codificati gli stati alla FSM non interessa: quello è un aspetto che devi vedere tu DOPO, quando implementi il circuito reale.

Mi sto convincendo che tu non abbia la minima idea di come si conduca l'attività di progettazione... ti fornisco una scaletta rigida, che ricalca sostanzialmente quello che ho fatto nel post precedente, per progettare una FSM:

1 - Definisci le specifiche del tuo sistema in modo comprensibile e - per quanto possibile - non ambiguo.
2 - Definisci uno stato iniziale, in cui il tuo sistema resta semplicemente in attesa.
3 - Domandati: da questo stato iniziale, cosa può succedere? Se arriva l'input 1, cosa fa il sistema? Se arriva l'input 0, cosa fa il sistema? Se il sistema deve rispondere ad un certo input, allora devi definire un nuovo stato e una transizione, quest'ultima caratterizzata dal valore dell'input (e dal relativo output, se è una macchina di Mealy), altrimenti definisci semplicemente un ciclo sullo stato in cui ti trovi.
4 - Ripeti il punto 3 su ciascuno degli stati trovati: otterrai altri stati, su cui ripetere il punto 3 per ottenere altri stati, su cui ripetere il punto 3... e così via, finché non hai descritto per intero la specifica.


Proviamo ad applicare questo metodo alla mia specifica del post precedente in modo da ottenere la prima delle FSM che ti ho proposto:
1 - Le specifiche le abbiamo già:

poniamo che il tuo circuito debba buttar fuori un 1 ogni volta che riconosce una sequenza 111 o 100, e poi resettarsi in attesa di una nuova sequenza.

Poniamo inoltre che ogni sequenza sia separata dalla successiva da almeno 1 bit irrilevante, così possiamo utilizzare la FSM che avevo formulato prima.
2 - Definiamo lo stato iniziale, che è lo stato 0: qui il circuito non fa nulla, aspetta e basta.
3 - Se arriva uno 0, cosa fa il circuito? Niente, perché lo 0 non indica nessuna sequenza interessante, quindi possiamo rimanere in attesa.
Se arriva un 1, cosa fa il circuito? Si tratta di un bit che ci interessa, perché potrebbe dare inizio a una sequenza: spostiamoci in uno stato che dica "ho ricevuto il primo 1". Possiamo formalizzare questa cosa definendo un nuovo stato, lo stato 1, e una transizione dallo stato 0 allo stato 1 caratterizzata dal fatto di avvenire solo se riceviamo un input pari a 1.
4 - Ripetiamo il processo sullo stato 1: cosa succede se arriva uno 0? Potremmo essere in presenza della seconda sequenza, quindi muoviamoci in uno stato che dice "ho ricevuto uno 0 dopo aver ricevuto un 1" e definiamo dallo stato 1 ad esso una transizione che avviene solo se l'input vale 0: abbiamo lo stato 2.
Cosa succede se arriva un 1? Potremmo essere in presenza della prima sequenza, quindi muoviamoci in uno stato che dice "ho ricevuto un 1 dopo aver ricevuto un 1" e definiamo una transizione dallo stato 1 che avviene solo se l'input vale 0: abbiamo lo stato 3.
5 - Applichiamo lo stesso discorso allo stato 2: che succede se arriva uno 0? Abbiamo completato una sequenza, quindi definiamo uno stato "ho completato una sequenza" e definiamo una transizione come abbiamo fatto anche prima, solo che questa volta dobbiamo pure mandare un 1 come output. Che succede se arriva un 1? Non abbiamo concluso la sequenza,ma abbiamo ricevuto quello che potrebbe essere il primo 1 di una sequenza, quindi torniamo allo stato "ho ricevuto un 1".
6 - Applichiamo lo stesso discorso allo stato 3: se riceviamo uno 0, non abbiamo completato la sequenza, quindi possiamo tornare all'inizio e riprendere a girare a vuoto; se riceviamo un 1, completiamo una sequenza, quindi possiamo definire uno stato "ho completato una sequenza", che però è esattamente uguale a quello che abbiamo definito per lo stato 2, quindi possiamo ri-utilizzare lo stesso stato.
7 - Dopo aver completato la sequenza, che facciamo? Ovviamente torniamo, qualsiasi sia l'ingresso, allo stato d'attesa, perché dobbiamo aspettare che un'altra sequenza abbia inizio.

Ora fermiamoci, così tu puoi riflettere su quanto abbiamo appena fatto. Pensaci bene e prova a risolvere qualche esercizio usando questo metodo, così puoi elaborarlo e capirne il senso; appena hai fatto questo e hai capito il metodo, passiamo ai bit che codificano gli stati e tutto il resto.

[g.schgor]

Forse può esserti d'aiuto questo articolo

[jayeffe]

Grazie a tutti per le risposte, ho provato un esercizio di un riconoscitore di sequenze
011 e 1110 che restituisce 1 quando incontra tali sequenze, senza resettarsi.
Ragionando sono riuscito ad arrivare a questo grafo e ho fatto il test con Jflap

per ragionare meglio, per ogni stato mi sono dato una sequenza: ad esempio lo stato q2 riceve in ingresso 1 e mi sono immaginato una sequenza 111110 0 ad esempio 100001 , giusto per capire come muovermi.
andando a testare mi trovo.

[rugweri]

Il tuo esercizio mi sembra(*) giusto, bravo

Ora, voglio proporti un piccolo quesito su cui ragionare: q6 è davvero necessario? Non ti sembra che somigli un po' troppo a qualche altro stato?


Prenditi il tuo tempo e pensaci... appena sei pronto, scrivi la risposta(**) e poi fammi sapere se vuoi andare avanti con la "lezione", così finalmente chiariamo quella roba sulla codifica degli stati



(*) Non ho il tempo di testarlo (figurati poi farne la verifica rigorosa ), ma provando ad eseguire il progetto su carta in due minuti ottengo un risultato "compatibile" (more on this later )

(**) Non ti fare prendere dall'ansia: non sono il tuo professore, non ti faccio ripetere l'esame se sbagli È solo per farti riflettere un po' sull'ottimizzazione della tua FSM... non è scontato che tu ci arrivi in questa fase, soprattutto basandoti sulla sola osservazione della FSM In seguito, se ti va, posso spiegarti una tecnica base di ottimizzazione... ma non corriamo: prima rifletti sul quesito che ti ho posto, poi chiariamo gli altri tuoi dubbi e solo alla fine aggiungiamo nozioni ulteriori

[jayeffe]

Ciao, grazie per l'aiuto che mi stai dando, non riesco a capire come eliminare lo stato ma sono comunque molto soddisfatto che ho finalmente capito come si fanno.
Per il resto, nel mio esame di reti logiche o progettazione digitale questo esercizio vale 12 punti e sicuramente il prof mi avrebbe scalato almeno 3 punti per lo stato in più

[rugweri]

sicuramente il prof mi avrebbe scalato almeno 3 punti per lo stato in più

...Ma immagino che non vi abbia mai spiegato come ridurre lo spazio degli stati, né vi avrà mai proposto un metodo rigoroso di progetto... poi mi chiedono perché secondo me certi docenti sono totalmente inadeguati...

Va be', dell'ottimizzazione parleremo a tempo debito... per il momento, ti fornisco solo la soluzione al mio quesito: lo stato q6 è uguale a q1 Facci caso:
- Viene raggiunto solo se l'ingresso è 0
- Quando ti ci trovi e ricevi uno 0, ci rimani e l'uscita è 0
- Quando ti ci trovi e ricevi un 1, vai allo stato q3 e l'uscita è 0

In pratica, la FSM ottimizzata risulterebbe così:

Ora, la fatidica domanda: te la senti di continuare, oppure vuoi fermarti ancora un po' su quello che abbiamo visto finora?


PS: il tuo corso ha una pagina online, qualcosa che io possa leggere per capire che programma svolgete e quali testi usate? Te lo chiedo perché quelle informazioni mi aiuterebbero a impostare meglio le spiegazioni e soprattutto pensare a una bibliografia da proporti

[jayeffe]

In realtà il materiale didattico del corso sono le slide disponibili su richiesta.
Ci sono vari libri che vengono consigliati tra cui "Progettazione Digitale " F.Fummi , che a mio parere si discosta da come è impostato il discorso.
Invece il testo "Fundament of logic Design" rispecchia pienamente le slide .
Difatti tutti gli esempi del libro sono riportati nelle slide.