Sintesi sequenziale sincrona

Note

I metodi di sintesi di reti sequenziali sono in costante evoluzione.

Un circuito sincrono può essere modellato in modo comportamentale o strutturale.

Macchina a stati

Il valore delle uscite all’istante $t$ dipende dalla successione degli ingressi che precedono l’istante $t$, questo implica il concetto di stato.

Usiamo quindi una macchina a stati, definita dalla quintupla:

$$(I,U,S,\delta ,\lambda )$$

Dove $I$ è l’alfabeto di ingresso, $U$ è l’alfabeto d’uscita, $S$ è l’insieme degli stati, $\delta :S\times I\to S$ è la funzione stato prossimo e $\lambda$ è la funzione d’uscita.

La funzione di uscita $\lambda$ dipende dal tipo di macchina. Se è una macchina di Mealy (l’uscita dipende da stato e ingresso) allora:

$$\lambda :S\times I\to U$$

Se è una macchina di Moore (l’uscita dipende solamente dallo stato) allora:

$$\lambda :S\to U$$

Una FSM può essere descritta da una tabella degli stati, dove gli indici di colonna sono i simboli di ingresso $i_{\alpha }\in I$, e gli indici di riga sono $s_j\in S$ e indicano lo stato presente.

Per rappresentarli si usa il diagramma degli stati, cioè un grafo orientato $G(V,E,L)$, con $V$ insieme dei nodi (stati), $E$ insieme degli archi (transizioni di stato) e $L$ insieme degli ingressi e uscite (Mealy) o solo uscite (Moore).

Generalmente la struttura di una macchina a stati è:

Il problema della sintesi comportamentale consiste nell’identificazione delle funzioni $\delta$ e $\lambda$, e sintetizzare la rete combinatorie che le realizza, riducendo il più possibile il numero di flip-flop.

Per sintetizzare, si realizza la tabella degli stati, e si ottimizzano riducendo i numeri. Si costruisce poi la tabella delle transizioni e la tabella delle eccitazioni, infine si sintetizza la rete combinatoria da tale tabella.

Codifica degli stati

Esistono diversi metodi per codificare gli stati, le più conosciute sono:

• Minima: con elementi in memoria $\lceil {\log }_2|S|\rceil$.
• One-Hot: con elementi in memoria $S$.

La scelta influisce su area e performance.

Codifica degli stati

Note

Il numero di possibili codifiche per $S$ stati è:

$$\frac{(2^{\lceil {\log }_2|S|\rceil }-1)!}{(2^{\lceil {\log }_2|S|\rceil }-|S|)!\cdot \lceil {\log }_2|S|\rceil !}$$

Generalmente si usano le codifiche minime o one-hot, oppure delle euristiche specifiche.

Codifica di hamming

Si dicono codifiche di hamming quelle che cerano di minimizzare la distanza di hamming tra stati futuri e adiacenti.

Sintesi delle FSM completamente specificate

Note

Per ridurre il numero flip-flop, si può usare una codifica diversa degli stati, oppure ottimizzare il numero di stati.

Si ha che il numero di flip-flop minimo è:

$$N_{\text{FF,min}}=\lceil {\log }_2|S|\rceil$$

Tuttavia nel modello della FSM alcuni stati potrebbero essere ridondanti, pertanto identificare ed eliminare questi stati comporta reti combinatorie meno costose e un numero minore di elementi di memoria.

In primis, si eliminano gli stati non raggiungibili dallo stato iniziale.

Dalla tabella degli stati questa operazione è possibile cercando tutti gli stati raggiungibili iterativamente, partendo dallo stato di partenza.

Inoltre, si possono rimuovere molti stati tramite la proprietà degli stati indistinguibili, minimizzando gli stati.

Stati indistinguibili

Si consideri una macchina completamente specificata, e $I_a$ la generica sequenza di ingresso, $U_a$ la sequenza d’uscita associata ad $I_a$. Consideriamo inoltre due generici stati $s_i,s_j\in S$. Questi sono detti indistinguibili se:

$$s_i\sim s_j⟺U_{\alpha ,i}=\lambda (s_i,I_{\alpha })=\lambda (s_j,I_{\alpha })=U_{\alpha ,j}\forall I_{\alpha }$$

L’indistinguibilità è una relazione di equivalenza, e quindi godono di proprietà riflessive, simmetriche e transitive. In generale due stati equivalenti possono essere raggruppati in un unica classe.

L’insieme delle classi identificate determina l’insieme degli stati della macchina minima equivalente unica.

Formalmente per il partizionamento in classi $c_1,\cdots ,c_m$:

$$\begin{array}{rl}& c_1\cup c_2\cup \cdots \cup c_m=S\\ & c_i\cap c_j=\varnothing \forall i,ji\ne j\end{array}$$

Per semplificare questo tipo di analisi si usa le regola ricorsiva di Paull-Unger: Due stati sono indistinguibili se per ogni simbolo di ingresso $i_a$:

$$\lambda (s_i,i_a)=\lambda (s_j,i_a),\delta (s_i,i_a)=\delta (s_j,i_a)$$

Dopo un numero finito di passi si ricadrà nelle condizioni $s_i\nsim s_j$ oppure $s_i\sim s_j$.

Inoltre per evidenziare le indistinguibilità si può usare la tabella delle implicazioni, dove ogni elemento può contenere non equivalenza, equivalenza oppure un rimando ad analisi di altri passaggi.

Una volta costruita la tabella, si cerca l’indistinguibilità con

La macchina a stati finiti ottenuta mediante la minimizzazione degli stati gode delle proprietà:

• Equivalenza alla precedente
• Minima
• Unica

Analisi delle macchine sequenziali

Note

È possibile ottenere un modello delle funzionalità di una macchina sequenziale tramite l’analisi del circuito.

Per farlo, prima si identificano le funzioni implementate dalla rete combinatoria, e poi si rappresenta le funzioni sulla tabella degli stati.

Questo processo non è banale per bistabili di tipo D.