Chapitre II : Synthèse des systèmes séquentiels synchrones

Synthèse des systèmes séquentiels synchrones

Machines à nombre fini d’états
1. Introduction

La différence essentielle entre une fonction combinatoire et une fonction séquentielle réside
dans la capacité de cette dernière de se souvenir des événements antérieurs : une même
combinaison des entrées, à un certain instant, pourra avoir des effets différents suivant les
valeurs des combinaisons précédentes de ces mêmes entrées.
Pour traduire cet effet de mémoire on introduit la notion d’état interne de la fonction, l’action
des entrées est alors de provoquer d’éventuels changements d’état, la situation qui suit le
changement de l’une des entrées dépend de l’état précédent. Si le nouvel état est différent du
précédent on dit qu’il y a eu une transition.
Les machines à états sont des circuits de logique séquentielle servant exclusivement à générer
des signaux de commande. Il existe en effet deux grands types de signaux en électronique :
 Signaux à traiter : les données
 Signaux pilotant le traitement : les commandes
Cette classification des signaux se retrouve au niveau des architectures des systèmes
électroniques qu’on peut schématiser comme dans la figure 1, où la partie contrôle, générant
les commandes, est dissociée de la partie opérative, traitant les données. Les deux parties sont
toujours réalisées en logique séquentielle et dans une très grande majorité des cas en logique
séquentielle synchrone.

Figure1 : Architecture générique d’un circuit électronique

Pour la logique séquentielle synchrone, il existe 2 signaux de commandes importants :

 L’horloge : pour le déroulement des séquences
 Le Reset : pour l’initialisation du système

2. Définition

La machine à état (M.A.E) en anglais Finite State Machine (F.S.M) est une machine
séquentielle algorithmique caractérisée par un vecteur d’entrées, un vecteur de sorties, et
une séquence d’états définissant son comportement. Elle représente la partie contrôle, c’est
à dire le cerveau du système électronique (les contrôleurs d’ascenseurs, arbitres de bus,
circuits d’interfaces des systèmes à base de microprocesseurs, circuits de gestion des
protocoles de transmission, systèmes de cryptages, etc).Une machine à états (également
appelée automate) est un système dynamique, qui peut se trouver, à chaque instant, dans une
position parmi un nombre fini de positions possibles. Elle parcourt des cycles, en changeant
éventuellement d’état lors des transitions actives de l’horloge. L’architecture générale d’une
Prof. Mohammed SBIHI 1
Chapitre II : Synthèse des systèmes séquentiels synchrones

machine à état est présentée ci-dessous.

Figure2 : Architecturegénéraled’unemachineàétat
Un programmateur de machine à laver, par exemple, en est l’illustration typique: suite à la mise
en marche, le programmateur contrôle que la porte est fermée, si oui il commande l’ouverture
de la vanne d’arrivée de l’eau, quand la machine est pleine etc.
Pour une machine à café par exemple, les états peuvent être :
1. Attente de pièce
2. Descendre le gobelet
3. Verser la poudre de café
4. Verser l’eau chaude
5. Indiquer que c’est prêt
Cette machine peut se compliquer en prenant en compte : le choix de la boisson, le dosage du
sucre, mais elle reste néanmoins très simple par rapport à certaines machines à états
industrielles comme la conduite d’une centrale nucléaire, ou l’automatisation d’une usine de
production. D’autres types de machines à états ont des contraintes de performances très
grandes, c’est le cas de celles utilisées dans les microprocesseurs ou des processeurs
spécialisées pour le graphisme ou les télécommunications.
3. Registre d’état et Horloge
Le registre d’état, piloté par son horloge, constitue le cœur d’une machine à états. Les autres
blocs fonctionnels sont à son service.
3.1.LEREGISTRED’ÉTAT
Le registre d’état est constitué de n bascules synchrones. Son contenu représente l’état
actuel de la machine. Il s’agit d’un nombre codé en binaire sur n bits. L’entrée du registre
d’état constitue l’état futur, celui qui sera chargé lors de la prochaine transition active de
l’horloge. Le registre d’état est la mémoire de la machine.

La taille du registre d’état fixe le nombre d’états accessibles. Si n est le nombre de bascules,
le nombre d’états N = 2n.
3.2.L’HORLOGE
Le rôle de l’horloge est de fixer les instants où les transitions entre états sont prises en
compte. Entre deux fronts consécutifs de l’horloge, la machine est figée en position mémoire.
4. Diagramme d’état et Transitions
Les machines à états finis sont généralement représentées par un diagramme des états permettant
de visualiser les transitions entre les états. Les états sont alors représentés par des cercles ; le nom
rattaché à chaque état à l’intérieur de chaque cercle ; les transitions entre les états sont représentés
par des arcs dirigés reliant les cercles ; les conditions (valeurs du vecteur d’entrée) enclenchant ces
transitions sont notées sur les arcs ; et finalement la valeur des sorties est généralement indiquée
Prof. Mohammed SBIHI 2
Chapitre II : Synthèse des systèmes séquentiels synchrones

soit sur l’arc (séparée des entrées par un trait oblique : /) ou à l’intérieur du cercle (séparée du nom
de l’état par un trait oblique : /).
Exemple de machine à états finis où les sorties sont indiquées à l’intérieur des cercles :

avec :
 E0, E1 et E2 les trois états ;
 Une entrée (notée sur les arcs) ;
 Une sortie associée à chacun des trois états, respectivement 0, 0 et 1.
Cette machine permet de détecter une séquence de deux 1 consécutifs en entrée. Considérons en
effet son fonctionnement :
 Au départ, la machine est à E0 et sa sortie à 0 ;
 Tant que la machine ne reçoit pas 1, elle demeure à E0 et sa sortie à 0 ;
 Si la machine reçoit 1, elle change d’état et part vers E1 : le début de la séquence 11 est
détecté. La sortie demeure à 0 ;
 Si à cette étape, la machine reçoit en entrée 0, la séquence est brisée. La machine revient à
E0 et tout reprend depuis le début ;
 Si la machine reçoit 1 alors qu’elle se trouve en E1, elle transite vers E2 et sa sortie est alors
à 1 (pour indiquer qu’elle a reçu la séquence 11) ;
 Une fois en E2, si la machine reçoit 1, elle demeure dans le même état car la séquence
(entrée précédente -entrée actuelle) est encore 11 : la sortie est à 1 ;
 Autrement elle part en E0 et tout recommence depuis le début.
Maintenant considérons le second cas. Voici un exemple de machine à états finis où les sorties sont
indiquées sur les arcs :

Voici les éléments que l’on y trouve :

 Deux états notés E0 et E1 ;
 Un état de départ E0 ;
 Une entrée (notée sur les arcs) ;
 Des sorties associées aux transitions, 0 pour les transitions de E0 à E0 et de E0 à E1, 1 pour
les transitions de E1 à E1 et de E1 à E0.
Cette machine (aussi) permet de détecter une séquence de deux 1 consécutifs en entrée.
Considérons son fonctionnement :
 Au départ, la machine est à E0;
 Tant que la machine ne reçoit pas 1, elle demeure à E0 et sa sortie à 0 ;
 Si la machine reçoit 1, elle change d’état et part vers E1 : le début de la séquence 11 est
détecté. La sortie demeure à 0 mais elle est ici associée à la transition;
 Si à cette étape, la machine reçoit en entrée 0, la séquence est brisée. La machine revient à
E0 et tout reprend depuis le début ;
Prof. Mohammed SBIHI 3
Chapitre II : Synthèse des systèmes séquentiels synchrones

 Si la machine reçoit 1 et qu’elle se trouve en E1, elle demeure en E1 et sa sortie est alors à 1
(pour indiquer qu’elle a reçu la séquence 11). Elle reste à cet état tant et aussi longtemps
que l’entrée est 1;
 Autrement elle part en E0 et tout recommence depuis le début.
Comme on le voit, dans sa conception, cette machine est différente de la première, mais dans son
fonctionnement global, elle lui est identique.
5. Machines deMoore et machines de Mealy
Suivant la façon dont les sorties dépendent des états et des commandes, on distingue deux
types de machines à états: les machines de Moore et les machines de Mealy.
5.1.Machine de Moore
Le nom de machine de Moore fait référence au professeur Edward F. Moore de l’université de
Winsconsin-Madison aux États-unis qui en est l’inventeur. Les sorties dépendent seulement de
l’état présent n. Un circuit combinatoire d’entrée détermine, à partir des entrées et de l’état
présent n, les entrées des bascules D du registre d’état permettant de réaliser l’état futur n+1.
Les sorties sont une combinaison logique de la sortie du registre d’état et changent de manière
synchrone avec le front actif de l’horloge. L’inconvénient de cette machine, c’est son temps
de réaction à un changement sur ses entrées qui est égale à une période de l’horloge dans le
pire des cas.

Figure3 : Modèle de machine de Moore

5.2.Machine de Mealy (G.H. Mealy)

Les sorties dépendent de l’état présent n mais aussi de la valeur des entrées. La sortie peut
donc changer de manière asynchrone en fonction de la valeur des entrées. Son temps de
réaction à un changement sur Xi est bien meilleur (c’est un temps de propagation
combinatoire). Il existe une variante synchrone de la machine de Mealy avec un registre placé
sur les sorties et activé par l’horloge. Toutefois, la machine de Moore est plus adaptée pour
réaliser une machine d’état totalement synchrone.

Figure4 : Modèle de machine de Mealy

Prof. Mohammed SBIHI 4

Chapitre II : Synthèse des systèmes séquentiels synchrones

6. Conception d’une machine de Moore

Les étapes à suivre pour concevoir une machine à états finis selon le modèle de la machine de
Moore à partir d’un cahier des charges sont :
1. Dessiner le diagramme des états
2. Poser la table des états
3. Définir la table de transition
4. Déterminer les expressions des entrées des bascules
5. Déterminer les expressions des sorties
6. Faire le schéma
Pour illustrer ce procédé, nous allons considérer l’exemple suivant :
Réalisons un jeu de lumière à l’aide de 5 lampes qui fait la séquence suivante :
00000 ; 10001 ; 01010 ; 00100 ; 11111 ; 00000 ; 11111 ; 00000 ; 11111 ; 00000
En plus de cette séquence, on ajoute un bouton « m » au système qui permet de figer le système au
dernier état rencontré. En fin, le système peut utiliser 3 sorties seulement étant donnée la façon de
les allumer.

6.1. Diagramme des états 6.2. Table des états

La table des états consiste à traduire le diagramme des états

présenté ci-contre :

État futur
État actuel Sorties
Entrée (m)
(s0s1s2)
0 1
E1 E2 E1 000
E2 E3 E2 100
E3 E4 E3 010
E4 E5 E4 001
E5 E6 E5 111
E6 E7 E6 000
E7 E8 E7 111
E8 E9 E8 000
E9 E1 E9 111
Il y a trois colonnes principales. La première correspond à
l’état initial ; la seconde à l’état futur, et elle est subdivisée
en colonnes selon les valeurs des entrées ; la troisième
correspond à la sortie. Comme nous avons affaire à une
machine de Moore, la sortie de dépend que de l’état actuel.

Prof. Mohammed SBIHI 5

Chapitre II : Synthèse des systèmes séquentiels synchrones

6.3. Table de transitions

Le table de transition est l’équivalent de la table des états, à cette différence près que les états sont
encodés sous une forme binaire. Dans le cas qui nous concerne, nous avons 9 états. Il nous faut
donc encoder ces états avec 4 bits au minimum, que l’on notera e3e2e1e0.

État futur (e3+e2+e1+e0+)

État actuel Sorties
Entrée (m)
(e3e2e1e0) (s0s1s2)
0 1
0000 0001 0000 000
0001 0010 0001 100
0010 0011 0010 010
0011 0100 0011 001
0100 0101 0100 111
0101 0110 0101 000
0110 0111 0110 111
0111 1000 0111 000
1000 0000 1000 111

Cette table va nous permettre de procéder aux deux étapes suivantes. Mais avant de continuer,
considérons le schéma suivant:

Ce schéma est exactement le même que celui que nous avons vu précédemment, mais légèrement
modifié pour mettre en évidence les circuits que nous allons implémenter.

Pour ce qui est de la mémoire, nous avons 4 bits à enregistrer (e3e2e1e0), nous allons par conséquent
utiliser quatre bascules D.

6.4. Expressions des entrées des bascules

Cette étape consiste à trouver le circuit combinatoire permettant d’évaluer l’état futur en fonction
de l’état actuel et des entrées :

Nous avons donc 5 entrées e3e2e1e0 et m pour le bouton et 4 sorties e3+e2+e1+e0+ :

Karnaugh pour e3+ Karnaugh pour e2+

Prof. Mohammed SBIHI 6

Chapitre II : Synthèse des systèmes séquentiels synchrones

Karnaugh pour e1+ Karnaugh pour e0+

Ce qui nous permet d’écrire :

 ̅
 ̅ ̅ ̅ ̅
 ̅ ̅ ̅
 ̅ ̅ ̅

6.5. Expressions des sorties

Cette étape consiste à trouver le circuit combinatoire permettant d’évaluer les sorties en fonction de
l’état actuel :

Nous avons donc 4 entrées e3e2e1e0 et 3 sorties s0s1s2 :

Karnaugh pour s0 Karnaugh pour s1 Karnaugh pour s2

Ce qui nous permet d’écrire :

 ̅ ̅ ̅
 ̅ ̅
 ̅ ̅

Prof. Mohammed SBIHI 7

Chapitre II : Synthèse des systèmes séquentiels synchrones

6.6. Schéma

Prof. Mohammed SBIHI 8