Structure d’un circuit réalisant un automate fini

Nous souhaitons à présent construire un circuit logique dont le comportement est défini par un automate fini. Ce circuit reposera sur les composants de base que nous connaissons déjà : les portes logiques et les bascules D. Au cours de son fonctionnement , il devra :

tenir à jour son état courant,
calculer son état suivant,
calculer les valeurs de ses sorties.

Autrement dit, le circuit devra être capable de calculer les fonctions de transition ( $f_T$ ) et de sortie ( $f_Q$ ) du modèle mathématique de l’automate.

La figure ci-dessous représente la structure typique d’un circuit réalisant un automate fini. Les flèches en pointillées correspondent au cas d’une machine de Mealy.

Les fonctions $f_T$ et $f_Q$ seront réalisées sous la forme de circuits logiques combinatoires. L’état courant $s$ sera conservé dans un registre et sera mis à jour à chaque front montant d’un signal d’horloge. Entre les fronts d’horloge, $s$ sera maintenu stable et le circuit calculera son état suivant $s^*$ .

Codage des états

Dans le modèle mathématique d’un automate, les états sont représentés de façon abstraite par des éléments d’un ensemble $S$ . À l’opposé, un circuit logique ne sait manipuler que des informations binaires. Pour que l’état courant puisse être mémorisé dans un registre et servir d’entrée à des circuits logiques combinatoires, il est donc nécessaire d’associer une représentation binaire – un code – à chaque état.

Il existe différents systèmes de codage qui aboutissent, selon l’automate, à un circuit comprenant un nombre plus ou moins important de portes ou de bascules D. Dans ce cours, nous retiendrons deux solutions.

État	$s_1$	$s_0$
Recherche d’un mur	0	0
Suivi d’un mur	0	1
Rotation à gauche	1	0
Rotation à droite	1	1

Codage one-hot

Ce système de codage consiste à associer un bit à chaque état. Un automate à $N$ états utilisera un codage sur $N$ bits. Pour chaque état, un seul des $N$ bits sera à 1, les autres étant à 0, d’où le nom de ce système de codage : en français code un parmi N, en anglais one-hot encoding (OHE).

La partie commande du robot autonome a été représentée par un automate à quatre états. Nous pouvons alors associer à chaque état un code de quatre bits :

État	$s_{RM}$	$s_{SM}$	$s_{RG}$	$s_{RD}$
Recherche d’un mur	1	0	0	0
Suivi d’un mur	0	1	0	0
Rotation à gauche	0	0	1	0
Rotation à droite	0	0	0	1

Avec le codage binaire pur

Reprenons les définitions de $f_T$ et $f_{Q,Mealy}$ proposées dans la section précédente et remplaçons les symboles des états par leurs codes binaires.

Pour la fonction de transition :

$s_1$	$s_0$	$CA$	$CG$	$FR$	→	$s_1^*$	$s_0^*$
0	0	0	0	–	→	0	0
0	0	0	1	–	→	0	1
0	0	1	–	–	→	1	1
0	1	0	1	–	→	0	1
0	1	–	0	–	→	1	0
0	1	1	1	–	→	1	1
1	0	–	–	0	→	1	0
1	0	–	–	1	→	0	0
1	1	–	–	0	→	1	1
1	1	–	–	1	→	0	0

Ce tableau est tout simplement une table de vérité. Nous pouvons lui appliquer les techniques de synthèse logique que nous avons déjà exposées et aboutir au schéma suivant.

Procédons de même pour la fonction de sortie (nous n’avons conservé que les lignes qui contiennent des sorties à 1) :

$s_1$	$s_0$	$CA$	$CG$	$FR$	→	$MGA$	$MGR$	$MDA$	$MDR$
0	0	0	–	–	→	1	0	1	0
0	1	0	1	–	→	1	0	1	0
1	0	–	–	0	→	0	1	1	0
1	1	–	–	0	→	1	0	0	1

Avec le codage one-hot

Ce système de codage permet d’aboutir très rapidement à des équations logiques en partant du graphe d’états. Il n’est pas nécessaire de détailler les fonctions $f_T$ et $f_Q$ ni de construire des tables de vérité. Pour faciliter la compréhension de ce qui va suivre, nous rappelons ci-dessous le graphe d’états du robot autonome dans le cas d’une machine de Moore.

La démarche est la suivante : pour chacun des états, posons-nous la question « Sous quelles conditions le circuit sera-t-il dans cet état au prochain front d’horloge ? ».

Par exemple, pour atteindre l’état Rotation à droite, il faut vérifier l’une des conditions suivantes

Être dans l’état Recherche d’un mur et détecter un mur à l’avant ( $CA$ ).
Être dans l’état Suivi d’un mur et détecter des murs à l’avant et à gauche ( $CA \cdot CG$ ).
Être dans l’état Rotation à droite et ne pas avoir terminé la rotation ( $\overline{FR}$ ).

Ces trois conditions peuvent être immédiatement exprimées sous la forme d’une équation logique :

s_{RD}^* = s_{RM} \cdot CA + s_{SM} \cdot CA \cdot CG + s_{RD} \cdot \overline{FR}

Un raisonnement similaire permet d’aboutir aux équations des trois autres bits d’états :

\begin{aligned} s_{RM}^* &= s_{RD} \cdot FR + s_{RG} \cdot FR + s_{RM} \cdot \overline{CA} \cdot \overline{CG} \\ s_{SM}^* &= s_{RM} \cdot \overline{CA} \cdot CG + s_{SM} \cdot \overline{CA} \cdot CG \\ s_{RG}^* &= s_{SM} \cdot \overline{CG} + s_{RG} \cdot \overline{FR} \end{aligned}

Dans une machine de Moore, les sorties dépendent uniquement de l’état courant. Les équations logiques des sorties s’obtiennent en regardant dans quels états chaque sortie est activée.

\begin{aligned} MGA &= s_{RM} + s_{SM} + s_{RD} \\ MGR &= s_{RG} \\ MDA &= s_{RM} + s_{SM} + s_{RG} \\ MDR &= s_{RD} \end{aligned}

Dans une machine de Mealy, il faut tenir compte de l’état courant et des conditions associées à chaque action.

Si les actions ont été représentées sur les transitions, comme sur le graphe d’états ci-dessus, il faut combiner l’état d’origine de chaque transition avec la condition de cette transition.

\begin{aligned} MGA &= s_{RM} \cdot \overline{CA} + s_{SM} \cdot \overline{CA} \cdot CG + s_{RD} \cdot \overline{FR} \\ MGR &= s_{RG} \cdot \overline{FR} \\ MDA &= s_{RM} \cdot \overline{CA} + s_{SM} \cdot \overline{CA} \cdot CG + s_{RG} \cdot \overline{FR} \\ MDR &= s_{RD} \cdot \overline{FR} \end{aligned}

La figure ci-dessous représente le résultat complet de la synthèse dans le cas d’une machine de Mealy avec le codage one-hot.

Conséquences du choix d’un système de codage

Selon la machine à états, le choix du codage pourra avoir une influence sur le matériel nécessaire.

Avec le codage binaire pur, le calcul de l’état suivant et des sorties nécessite un décodage des bits représentant l’état courant. D’après ce que nous avons expliqué dans le chapitre sur les circuits logiques combinatoires, un décodage consiste en fait à convertir une valeur en binaire pur vers un code one-hot ! On peut en déduire que l’utilisation du codage one-hot dès le départ aboutit à une réalisation plus simple des fonctions de transition et de sortie. Cependant, les optimisations logiques peuvent rendre cette différence peu significative.

En revanche, le codage one-hot impose un nombre de bascules D égal au nombre d’états : pour une machine à 1000 états, il faut 1000 bascules. Avec le codage binaire pur, le nombre de bascules D augmente de façon logarithmique avec le nombre d’états : pour une machine à 1000 états, il faut 10 bascules ; pour une machine à 2000 états, 11 bascules suffisent.

Avant de choisir le codage one-hot, il faut donc déterminer si les économies réalisées sur les circuits combinatoires ne sont pas contrebalancées par l’ajout d’un grand nombre de bascules.

Résumé

Un automate fini peut être synthétisé sous la forme d’un circuit logique séquentiel.

Dans ce circuit, un registre tient à jour l’état courant tandis que des circuits combinatoires réalisent les fonctions de transition et de sortie.

Le circuit met à jour son état au rythme d’un signal d’horloge. Entre les fronts d’horloge, il calcule son état suivant et ses sorties.

Il existe différents systèmes de codage des états. Nous avons détaillé deux exemples.

Le codage binaire pur consiste à numéroter les états en binaire. Il permet de représenter les fonctions de transition et de sortie sous la forme de tables de vérité. Il minimise le nombre de bascules D utilisées pour mémoriser l’état.
Le codage un parmi N (one-hot encoding) consiste à affecter un bit à chaque état. Il permet d’effectuer directement une mise en équation des fonctions de transition et de sortie. Il minimise le nombre de portes logiques nécessaires pour réaliser ces deux fonctions.

Synthèse des automates finis