Appunti lezione Calcolatori elettronici

Macchina di Moore

Macchina di Mealy

La macchina di Mealy, a differenza di quella di Moore, deve sapere sia lo stato corrente

che l’input per passare allo stato successivo

Rappresentazioni macchine di Moore e Mealy

Per rappresentare una macchina a stati `e possibile utilizzare due formalismi:

• diagramma degli stati: è un grafo che mostra graficamente le relazioni tra gli stati e le

transizioni, identificando anche i caratteri di output.

• tabella degli stati e delle transizioni: è una rappresentazione equivalente in forma

tabellare.

Diagramma degli stati:

Tabella degli stati e delle transizioni:

Equivalenza tra modelli

Esiste sempre una trasformazione tra una macchina di Mealy e una macchina di Moore,

quindi i due modelli sono equivalenti.

• Trasformazione da Moore a Mealy:

– gli alfabeti di input e output sono gli stessi;

– gli stati sono gli stessi;

– se in uno stato si raggiunto da una transizione causata da un carattere ij viene generato

un output ok, quello stesso output viene generato durante la transizione ij verso lo stato si.

• Trasformazione da Mealy a Moore:

– questa trasformazione `e meno immediata;

– possiamo avere più transizioni verso lo stesso stato che generano output differenti;

– in questo caso, lo stato di destinazione deve essere decomposto in più stati differenti;

– stati Mealy ≤ stati Moor

Sintesi delle macchine

Per realizzare circuitalmente una macchina è necessario:

• realizzare il blocco M: lo facciamo utilizzando un numero sufficiente di flip flop D;

• realizzare la rete δ: è necessario realizzare un circuito di commutazione per aggiornare

lo stato di ciascun flip flop D (equazione di eccitazione di un flip flop);

• realizzare la rete ω: `e necessario realizzare un circuito di commutazione per generare

ciascun bit dei caratteri di output.

Trattandosi di reti combinatorie, `e possibile utilizzare le tecniche di sintesi e

minimizzazione (Karnaugh, analiticamente) che abbiamo studiato per le funzioni booleane.

La sintesi può essere svolta a partire dalla tabella degli stati e transizioni.

Esempio Sintesi della macchina che accetta la stringa ”mamma” in input.

•Diagramma degli stati: