Automa di Mealy

[rugweri]

Slide disponibili "su richiesta"? Ho quasi paura a indagare ulteriormente...
Per quanto riguarda i libri, non conosco quello di Fummi (ma conosco l'autore, anche perché ha contribuito all'edizione degli interventi di una conferenza sui metodi formali che ho letto di recente), e di quello di Roth-Kinney ho obiettivamente poco da dire: il classico libro-calderone che viene consigliato agli studenti che affrontano per la prima volta un argomento, una roba che mostra loro le "dimensioni" della materia senza però fare doverosamente il punto sulle nozioni importanti. Non capisco davvero che senso abbia usare un testo del genere, quando ci sono in giro libri fatti davvero bene...


Detto questo, io continuerei con la spiegazione
Dopo aver progettato la FSM, dobbiamo ovviamente darle un senso pratico, ovvero convertirla in un circuito digitale; questo richiede tre fasi:

- Ottimizzazione della FSM, ovvero minimizzazione del numero degli stati
- Scelta della codifica degli stati, da cui derivano le dimensioni dei registri del circuito
- Riscrittura della FSM come tabella di verità e derivazione da essa della logica combinatoria

Iniziamo

OTTIMIZZAZIONE
Anzitutto, la fase di ottimizzazione richiede di definire il concetto di "equivalenza tra gli stati"; nell'ambito dell'algoritmo che ti propongo io, chiamato implication table algorithm, due stati sono considerati equivalenti semplicemente se non puoi dimostrare che non lo sono (furba 'sta cosa, no? ). L'algoritmo, molto semplice, si sviluppa così:

- Redigere una tabella che elenchi tutti gli stati, le loro evoluzioni e le loro uscite; per la FSM che avevi fatto tu, otteniamo una cosa del genere:

fsmt.png (6.89 KiB) Osservato 3958 volte

- Realizzare l'implication table vera e propria, che è derivata dalla tabella di cui sopra marcando con X (ovvero, definendo a priori non equivalenti) gli stati con uscite diverse e scrivendo per tutti gli altri le condizioni che li renderebbero equivalenti (ovviamente, uno stato è sempre equivalente a se stesso):

- Derivare iterativamente la non equivalenza: se ci fai caso, la condizione non potrà mai essere soddisfatta, perché (come abbiamo indicato anche nell'apposita cella della implication table) i due stati hanno uscite diverse. Questo vuol dire che è falsa anche , perché dipendeva da Q2 e Q3, e per lo stesso motivo è falsa anche . Osserviamo poi che è falsa anche , perché i due stati hanno uscite diverse... va be', hai capito il concetto, inutile che io ti elenchi tutte le disuguaglianze. Il risultato è che la nostra implication table assume questa forma:

- Prendere tutte le uguaglianze che non è stato possibile negare: esse sono valide. Nel nostro esempio, non siamo riusciti a negare , quindi (in virtù della nostra definizione di equivalenza) possiamo dire che questi due stati sono equivalenti e unirli in un nuovo stato, che chiameremo . La tabella che descrive la nostra FSM, a questo punto, è così strutturata:

fsmt2.png (7.04 KiB) Osservato 3958 volte

CODIFICA DEGLI STATI
Ora, abbiamo concluso la fase di ottimizzazione, e possiamo passare alla fase successiva: sappiamo quanti stati ci servono, ma come li salviamo nel nostro circuito digitale? Come sequenze di bit, ovviamente!!
In due parole, ciò che dobbiamo fare ora è determinare che codice dare a ciascuno stato... le scelte sono praticamente infinite:
- Possiamo assegnare a ogni stato la codifica binaria su tre bit (abbiamo sei stati, quindi ce ne occorrono per forza tre) del suo numero: , ...
- Possiamo utilizzare una codifica one-hot, ottenendo , , e così via.
- Possiamo inventarci una codifica di qualsiasi tipo, a nostro gusto.
Tendenzialmente, si preferiscono le codifiche in grado di ottenere il miglior risultato in termini di dimensioni del circuito e prestazioni... ma non è facile, anche perché ci sono un bel po' di codifiche possibili (tant'è che tendenzialmente il compito è svolto da moduli appositi dei software di sintesi). Immagino che voi non abbiate studiato gli algoritmi di minimizzazione simbolica o che altro, quindi non mi dilungherò oltre.
Ti faccio notare solo un dettaglio: hai visto che alla fine la codifica degli stati non ti interessava, in fase di progetto? Abbiamo progettato e ottimizzato la FSM senza mai parlarne, e le abbiamo dedicato un breve discorso solo ora


DERIVAZIONE DELLA LOGICA COMBINATORIA
Siamo all'ultima fase del nostro flusso di progetto: ora, ci tocca solo derivare la logica combinatoria che calcolerà gli stati futuri e le uscite. Per fare questo, possiamo avvalerci di una banalissima tabella di verità, che costruiamo così:

- Gli ingressi della tabella sono gli ingressi della FSM, e inoltre consideriamo come ingressi i bit dello stato presente.
- Le uscite della tabella sono le uscite della FSM, e inoltre consideriamo come uscite i bit dello stato futuro.

Perché questa "ripartizione" delle variabili di stato? È presto detto: come forse avrai intuito, l'implementazione di una FSM è molto schematica, e precisamente rispetta sempre il controller model formulato da Huffman:

Guarda bene questo schema: le uscite dei registri (ovvero, le variabili che descrivono lo stato presente) vanno in ingresso alla logica combinatoria, mentre gli ingressi dei registri (ovvero, le variabili che descrivono lo stadio futuro) ne escono

Come avrai capito, a questo punto la codifica degli stati è importante, se non altro perché una buona codifica permette di realizzare una logica più semplice... più avanti nei tuoi studi (se prenderai la strada che ho scelto io) vedrai un po' come funziona tutta 'sta storia e come si sceglie una buona codifica
In ogni caso, torniamo a noi: scritta la tabella di verità, la derivazione del circuito può essere realizzata con tecniche che credo tu già conosca... poi, puoi (anzi, mi correggo: devi, se si parla di un progetto reale) infilarci in mezzo procedure di minimizzazione e tutto quello che vuoi, ma il principio è sempre lo stesso.


FINE


Ok, abbiamo finito la spiegazione: ora dovresti essere in grado - al netto della destrezza che si acquisisce con la pratica - di progettare una semplice macchina a stati finiti e derivare un circuito che la implementi

Una brevissima premessa: tutti i libri che ti sto proponendo sono ovviamente sovrabbondanti rispetto alle tue necessità, quindi non preoccuparti se alcuni dettagli ti sfuggono o se certi argomenti ti sembrano troppo "astratti": come ti ho detto, a tempo debito e se lo vorrai avrai modo (sperando che ti troverai in un ateneo decente, in quel momento) di approfondire

[1] C. Bolchini, C. Brandolese, F. Salice, D. Sciuto, Reti logiche, Apogeo, 2004
[2] P.P. Chu, RTL hardware design using VHDL, Wiley, 2006
[3] G. De Micheli, Synthesis and optimization of digital circuits, McGraw-Hill, 1994
[4] D.D. Gajski, Principles of digital design, Prentice Hall, 1996
[5] G.D. Hachtel, F. Somenzi, Logic synthesis and verification algorithms, Kluwer, 2002
[6] M. Morris Mano, C.R. Kime, T. Martin, Logic and computer design fundamentals, Pearson, 2015
[7] F. Vahid, Digital design, Wiley, 2005

[RenzoDF]

... di quello di Roth-Kinney ho obiettivamente poco da dire: il classico libro-calderone ... Non capisco davvero che senso abbia usare un testo del genere, ...

Concordo pienamente; un testo che a dir poco non ha ne capo ne coda.

[jayeffe]

Ciao, non riuscivo ad accedere al sito, comunque al di la di questo sto facendo esercizi e mi sto trovando.
Ieri ho provato a svolgere anche un'altra tipologia di esame che era quella con 2 ingressi e una sola uscita e sto riscontrando un po di difficoltà, non so se cambia il ragionamento..


Per quanto riguarda il libro calderone, mi sto trovando malissimo, inoltre le slide del corso rispecchiano quel libro ..
gia ad esempio di questo libro che mi hai citato
[6] M. Morris Mano, C.R. Kime, T. Martin, Logic and computer design fundamentals, Pearson, 2015 è molto piu pratico, discorsivo e lo preferisco.

[rugweri]

Ieri ho provato a svolgere anche un'altra tipologia di esame che era quella con 2 ingressi e una sola uscita e sto riscontrando un po di difficoltà, non so se cambia il ragionamento..

Se segui il metodo che abbiamo formulato (il quale, facci caso, non è legato al caso che stavamo trattando: è un metodo assolutamente generale), la soluzione vien quasi da sè
Giustamente, con due ingressi ogni stato ha quattro possibili transizioni, e dunque la FSM è un po' più incasinata... ma al netto di questo, non cambia nulla: il modello computazionale della FSM resta valido

[jayeffe]

Perfetto, comunque nel fare gli esercizi ho notato che nello scrivere gli stati, ad esempio

s0 00
s1 01 ecc
cioè nella codifica degli stati in binario, alcuni libri usano il "Gray Code "

e dunque nello stato che per me è S2 0vvero 10 , viene chiamato s3 ..
Leggevo in rete che non è necessario usarlo .. ora non so se ho capito male ..
Intanto in alcuni esercizi che mi capitano 3 stati non ho difficoltà visto che si tratta di usare

00
01
11
10 .. in quelli a tre bit lo trovo meno immediato

[rugweri]

Come ti ho detto anche prima, quella della codifica è una scelta che va fatta solo dopo il progetto della FSM, non è univoca (ci sono ovviamente codifiche migliori di altre, ma credere di poter determinare a mano la migliore tra tutte è da Nobel della coglioneria) ed è condizionata da tante cose: ad esempio, se lo stato evolve verso lo stato sarebbe positivo avere per i due stati dei codici molto simili.
Visto che il vostro "meraviglioso" docente non vi ha spiegato alcunché in merito, io non perderei troppo tempo nella ricerca della codifica più adeguata: semplicemente, scegli quella che ti viene più semplice e usala, o al più chiediti quale codifica credi possa semplificare la determinazione della sezione combinatoria