Macchine e reti sequenziali

Da Hacknowledge.

Una macchina sequenziale a stati finiti è quella particolare macchina in cui le uscite dipendono non solo dagli ingressi che gli vengono mossi ma anche dallo stato in cui attualmente si trova la macchina. Pertanto, lo stesso ingresso potrebbe provocare uscite differenti se la macchina si trova in uno stato diverso dal precedente. (Per le macchine combinatorie invece lo stesso ingresso produce sempre la stessa uscita, come ad esempio fa una calcolatrice) Ogni ingresso alla macchina genera un cambiamento di stato della stessa oppure consente alla macchina di rimanere nello stato attuale. Proprio per questo motivo si è soliti dire che le macchine sequenziali, a differenza di quelle combinatorie, sono dotate di memoria, dovendo infatti memorizzare lo stato in cui esse si trovano! E’ possibile dare due definizioni matematiche di macchine sequenziali, esse sono dovute a Moore ed a Mealy, abbiamo pertanto un modello di Moore di macchina sequenziale ed un modello di Mealy.

Indice 1 Modello di Mealy 2 Modello di Moore 3 Il grafo di una rete sequenziale 4 Macchine sequenziali asincrone e sincrone

[modifica] Modello di Mealy

Secondo il modello di Mealy la macchina sequenziale (a stati finiti) è una quintupla ordinata di enti così segnati M(Q,I,U,t,ω), dove:

• Q è l’insieme di stati finiti interni alla macchina, ogni singolo stato è poi denotato con la lettera qi, il pedice lo contraddistingue da altri stati (ad esempio q1,q2,q3,…,qk);
• I è l’insieme, anch’esso finito, di stati di ingresso per la macchina;
• U è l’insieme, ancora finito, di tutte le possibili uscite della macchina;
• T è una funzione logica tale che per D appartenente a QxI → Q, T è cioè quella funzione che in base all’ingresso ricevuto e allo stato attuale della macchina genera un nuovo stato in cui la macchina si porterà se soggetta a quell’ingresso;
• ω è la funzione tale che per D appartenente a QxI → U, U è cioè quella funzione che in base all’ingresso ricevuto ed allo stato attuale della macchina genera l’uscita logica della macchina sequenziale.

[modifica] Modello di Moore

Il modello di Moore fornisce una descrizione di macchina sequenziale leggermente differente modificando la funzione logica ω che risulta essere così definita:

• ω è la funzione logica tale che per D appartenente a Q → U, D è cioè la funzione che genera l’uscita considerando il solo stato interno della macchina;

Data una macchina di Mealy è possibile realizzarne una identica secondo Moore e viceversa. E’ bene precisare che gli automi che ci apprestiamo a realizzare e/o studiare non consentono la costruzione di tutte le possibili macchine sequenziali, queste infatti risulteranno limitate nel numero di stati!

[modifica] Il grafo di una rete sequenziale

La descrizione della macchina sequenziale oltre che dalle tabelle delle funzioni T ed ω può avvenire anche secondo un grafo detto diagramma degli stati. Le tabelle di T ed ω generano il prossimo stato della macchina ottenuto incrociando i diversi valori dello stato attuale e del possibile ingresso disposti sulle righe e sulle colonne della tabella. Il grafo della macchina assume un diverso significato a seconda che si tratti del modello di Moore oppure del modello di Mealy. Secondo Mealy l’uscita è associata all’arco che collega due stati mentre secondo Moore l’uscita è associata al nodo o allo stato in cui si trova la macchina. Vediamo alcuni esempi, si vuole realizzare un automa che riconosca la sequenza binaria 101, tracciamo quindi il suo grafo e la sua tabella di transizione per gli stati:

Ancora un esempio: tracciare il grafo di una rete sequenziale in grado di riconoscere la sequenza binaria 101-1:

Una macchina sequenziale può essere realizzata con una macchina combinatoria e un elemento di ritardo collegati nel seguente modo:

L’elemento di ritardo è essenziale poiché il comportamento temporale della macchina suggerisce per la macchina sequenziale un funzionamento secondo uno spazio temporale in base alla quale vengono considerate le funzioni ingresso I(t) e di uscita U(t). Il modello di macchina combinatoria per queste funzioni che abbiamo visto nelle precedenti lezioni realizza le funzioni I(t) ed U(t) e siccome entrambe determinano il nuovo stato per la macchina sequenziale a partire dallo stato attuale esse necessitano, per il corretto funzionamento, di un elemento di ritardo che ha quindi il compito di riproporre in ingresso sia ad I(t) che ad U(t) lo stato attuale della macchina. Uno stato q di un automa si dice stabile all’ingresso i se si verifica che:

T(q,i)=q

Ovvero, uno stato è stabile rispetto ad un certo ingresso se l’automa in tali stati, sottoposto per un certo tempo all’ingresso indicato, permane nel suo stato indefinitamente. Gli ingressi in una macchina sequenziale possono essere a livello (in tal caso il riferimento è allo spazio continuo dei tempi) oppure ad impulsi (in tal caso le sequenze di ingresso significative definiscono uno spazio discreto dei tempi); come vedremo più avanti ciò richiede, per il corretto funzionamento della macchina, particolari caratteristiche delle funzioni Ted ω e quindi delle tabelle particolari dette di transizione. Come fatto per le macchine combinatorie, la minimizzazione in una macchina sequenziale, cioè la ricerca di una macchina M’ che contenga o includa una macchina M dotata di un numero minore di stati, assume per le macchine sequenziali la medesima importanza che per quelle combinatorie assume la minimizzazione delle funzioni booleane. Importanti definizioni utili alla classificazioni di macchine sequenziali sono le definizioni di macchina asincrona e sincrona. Una macchina si dice asincrona se per ciascun ingresso i e per ciascuno stato qi, la sequenza: T(qi1,i)=qi2, T(qi1,i)=qi3 termina in uno stato stabile T(qstab,i)=qstab.

[modifica] Macchine sequenziali asincrone e sincrone

Una macchina asincrona è identificabile già dal suo grafo poiché quest’ultima è dotata, per ogni suo stato, di auto-anelli i quali sono significativi del fatto che gli stati della macchina sono stabili nei confronti di certi ingressi. Una macchina si dice invece sincrona se non è asincrona. Una macchina con una sequenza di ingressi a livelli funziona solo se è asincrona! Infatti essendo la sequenza di ingressi a livelli quest’ultima fornisce ad ogni istante di tempo un valore significativo per la macchina che sarà assunto come ingresso, pertanto, se la macchina è asincrona (dotata cioè di ogni stato stabile) l’ingresso ad essa proposto provoca diverse transizioni fino a giungere in uno stato stabile dopo un periodo di evoluzione della macchina noto come periodo transitorio. Invece, per una macchina sincrona esistono degli stati non stabili rispetto a certi ingressi e quindi una qualsiasi sequenza a livelli potrebbe generare delle transizioni infinite fra gli stati poiché i valori della sequenza a livello potrebbero non terminare in uno stato stabile e proseguire all’infinito. Nel progetto di macchine sincrone l’automa va costruito con attenzione, in modo tale da arrivare sempre ad uno stato stabile qualora alla macchina venga proposto un determinato ingresso. Una macchina con ingresso a livelli è una macchina sequenziale di tipo asincrono. Per una macchina sincrona gli ingressi invece non possono essere a livelli poiché l’ingresso dovrebbe avere una durata esattamente pari al tempo di ritardo della macchina, condizione irrealizzabile a causa dei ritardi inerziali e parassiti dei circuiti elettronici, l’ingresso può allora essere di tipo impulsivo e di durata sufficiente a cambiare lo stato della macchina. Nella definizione di macchina sequenziale è emerso il problema di come memorizzare lo stato che la macchina occupa all’interno del suo grafo, per questo motivo in seguito ci occuperemo dei registri e degli elementi di memoria.