Cours FSM v2.0.1 PDF

Machines
à états finis
ENIT - Génie Électrique
BOURGUIBA Riadh
[email protected]
2
1. Généralités
Logique combinatoire
Un circuit logique est dit combinatoire, si ses sorties sont déterminées uniquement
par une combinaison de ses entrées.
=> Si on applique, à des instants différents, les même entrées à un circuit logique
combinatoire, on obtiendra toujours les mêmes sorties, quels que soient ces
instants.
Logique séquentielle
Un circuit logique est dit séquentiel, si ses sorties sont déterminées par une
combinaison de ses entrées et par la séquence de ses entrées précédentes depuis
un état initial connu.
=> Si on applique, à des instants différents, les même entrées à un circuit logique
séquentiel, on obtiendra des sorties différentes, selon l'histoire du système entre
ces deux instants.
Un circuit logique séquentiel conserve son histoire récente dans une mémoire appelée
registre d'état.
ENIT - Génie Electrique - v2.0.1
3
1. Généralités
Un automate, également appelé machine à états, est un concept
mathématique abstrait.
Il offre un formalisme très utile en informatique ou en électronique pour

modéliser des comportements, des processus de contrôle ou des
protocoles.
En effet, tout circuit logique possédant un emplacement de mémorisation,

ne serait-ce qu'un seul bit, est une machine à état.
Dès lors, il peut être parfois avantageux d'utiliser le concept de machine à

états pour décrire le comportement d'un tel système.
Dans un circuit réel, le registre d'état a une taille finie et le nombre d'états
qu'il peut prendre est limité. Les machines à états réelles sont donc des
machines à nombre d'états finis, abusivement appelées machines à états
finis, ou Finite State Machine (FSM) en anglais.
4
1. Généralités
Un machine à états finis peut être décrite de deux manières :
Son graphe d'états : Il s'agit d'un graphe orienté et étiqueté,
où les nœuds (cercles) représentent les états du système, les
arcs (flèches) indiquent les transitions et les étiquettes rappellent
les conditions de transition.
Sa table des transitions : C'est un tableau à trois colonnes, qui

indique pour chaque état actuel, les états futurs possibles et les
conditions de transition.

5
1. Généralités
Tous les systèmes séquentiels n'ont pas vocation à être modélisés
par une machine à états (ex. : compteur, mémoire RAM, etc.).
Généralement, les machines à états rencontrées dans les systèmes
numériques, peuvent être modélisés avec moins d'une dizaine
d'états (habituellement 2 à 4 états suffisent).
Lorsque le nombre d'états est grand (> 10), on peut souvent
décomposer le graphe en un graphe hiérarchique (plusieurs FSM qui
interagissent).
Si le nombre d'états est beaucoup trop grand (plusieurs dizaines), il
peut être préférable d'utiliser un autre formalisme que celui des
machines à états.

6
1. Généralités
D'un point de vue pratique, il existe :
Des machines à états asynchrones, donc n'utilisant pas de signal d'horloge

pour leur registre d'état. Les éléments de mémorisation sont asynchrones :
RAM asynchrone, latch RS, latch JK, latch D, etc.
Des machine à états synchrones, donc utilisant un signal d'horloge pour leur
registre d'état. Les éléments de mémorisation sont synchrones : RAM
synhrone, bascule RS, bascule JK, bascule D, etc.
Dans ce cours, nous ne considèreront que les machines synchrones.
Deux mathématiciens et informaticiens américains se sont penchés sur les

machines à états au milieu des années 50 et ont proposé chacun son modèle :
George H. Mealy (1927-2010)

Edward F. Moore (1925-2003)

7
2. Machine de Mealy
L'histoire du système est conservée dans le registre d'états.

Les sorties dépendent de l'état présent et des entrées.

8
2. Machine de Mealy
Les sorties sont obtenues par combinaison de l'état présent, qui évolue de façon
synchrone, et des entrées qui sont a priori asynchrones.
=> Les sorties sont asynchrones et peuvent varier dans un même état.
=> Seule la dernière valeur de l'état futur sera retenue.

9
2. Machine de Mealy
Table des transitions
L’état futur, comme les sorties, dépendent des entrées.
État État futur Sorties

présent
00 01 10 11 00 01 10 11
A
B
C

10
2. Machine de Mealy
Diagramme des états
Etat : Il est représenté par un cercle, sur lequel on indique le nom de l'état.
Transition : Elle est représentée par une flèche qui porte sa condition de
déclenchement et les valeurs de sortie correspondantes.
Exemple :
Cette machine possède une entrée, calcule une sortie et peut prendre deux états.

3. Machine de Mealy 11
avec sorties sur registre
En plaçant un registre après les sorties, on parvient à synchroniser les

sorties avec l'horloge au prix d'un cycle de latence.
=> Les entrées n'agissent plus directement sur les sorties, qui désormais
restent stables pendant tout le cycle d'horloge.

3. Machine de Mealy 12
Ceci a deux avantages :
Créer 2 étages, mais qui s'exécutent en parallèle sur les mêmes entrées
(effet pipeline très limité).
L'analyse des timings devient possible, puisque le bloc de calcul des
sorties est séparé des blocs combinatoires qui suivront la machine, et
que l'on ne connaît pas toujours (concept de bloc IP).

13
4. Machine de Moore
L'histoire du système est conservée dans le registre d'états.

Les entrées agissent uniquement sur l'état futur.
Les sorties ne dépendent que de l'état présent.

14
4. Machine de Moore
=> Les sorties sont constantes dans un état donné et ne peuvent varier que
suite à un front d'horloge, moyennant le temps de traversée du bloc combinatoire.

15
4. Machine de Moore
Diagramme des états
Etat : Il est représenté par un cercle sur lequel on indique son nom, ainsi que
les valeurs des sorties.
Transition : Elle est représentée par une flèche, qui porte la condition de
déclenchement.
Exemple :

16
4. Machine de Moore
Table des transitions
Les sorties ne dépendent pas des entrées.
État État futur Sorties présentes

présent
00 01 10 11
A
B
C

5. Machine de Moore 17
Si on place un registre sur les sorties, on resynchronise les sorties

avec l'horloge, au prix d'un cycle de latence, mais avec une période
plus courte.

5. Machine de Moore 18
Comme pour la machine de Mealy, l'analyse des timings est possible,

puisque le bloc de calcul des sorties est séparé des blocs combinatoires qui
suivront la machine, et que l'on ne connaît pas toujours (concept d'IP).
De plus les deux étages obtenus sont généralement bien équilibrés, d'où
un effet pipeline réel.

19
6. Mealy vs Moore
Comment choisir entre une machine de Mealy et une machine de
Moore ?
Sur un plan théorique, il existe toujours une machine de Moore
équivalente à une Machine de Mealy, et inversement.
Les contraintes du système (réactivité) ou de réalisation (surface,
vitesse, consommation, etc.), nous imposent parfois le choix.
En l'absence de contrainte, l'être humain a généralement
tendance à raisonner en termes de machine de Mealy.

20
6. Mealy vs Moore
Mealy
Le nombre d'états est généralement plus faible dans le cas d'une machine de
Mealy, puisqu'elle peut réagir sans changer d'état. => La logique de calcul de
l'état futur est donc plus simple et plus rapide.
En revanche, la logique de calcul des sorties est beaucoup plus complexe, car
il faut réagir aux entrées immédiatement.
=> Le chemin critique peut être long...

21
6. Mealy vs Moore
Moore
Le nombre d'états d'une machine de Moore équivalente est plus grand, car il
faut changer d'état pour réagir.
En revanche, les sorties sont fixes dans chaque état, donc le calcul des sorties
est relativement simple, voir immédiat.
=> Le chemin critique se trouve relativement bien partagé entre les deux
blocs logiques. L'effet pipeline sera meilleur et le cycle d'horloge plus court.

22
6. Mealy vs Moore
Mealy avec registre
L'ajout d'un registre en sortie permet de stabiliser les sorties, mais présente
deux inconvénients :
Il prive la machine de Mealy d'un avantage : sa réactivité.
Il ajoute un cycle de latence avec une période déjà longue.
Ce registre n'apporte finalement pas grand-chose du point de vue des
performances.
Moore avec registre
Le registre supplémentaire permet d'exploiter pleinement la technique du
pipeline.
=> L’ajout du registre va essentiellement dépendre de l'accélération due à

l'effet pipeline.

Cours FSM v2.0.1 PDF

Transféré par

Droits d'auteur :

Formats disponibles

Cours FSM v2.0.1 PDF

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours FSM v2.0.1 PDF

Transféré par

Droits d'auteur :

Formats disponibles

Machines

Il offre un formalisme très utile en informatique ou en électronique pour

En effet, tout circuit logique possédant un emplacement de mémorisation,

Dès lors, il peut être parfois avantageux d'utiliser le concept de machine à

Sa table des transitions : C'est un tableau à trois colonnes, qui

ENIT - Génie Electrique - v2.0.1

ENIT - Génie Electrique - v2.0.1

Des machines à états asynchrones, donc n'utilisant pas de signal d'horloge

Deux mathématiciens et informaticiens américains se sont penchés sur les

George H. Mealy (1927-2010)

ENIT - Génie Electrique - v2.0.1

L'histoire du système est conservée dans le registre d'états.

ENIT - Génie Electrique - v2.0.1

=> Les sorties sont asynchrones et peuvent varier dans un même état.

=> Seule la dernière valeur de l'état futur sera retenue.

ENIT - Génie Electrique - v2.0.1

L’état futur, comme les sorties, dépendent des entrées.

État État futur Sorties

ENIT - Génie Electrique - v2.0.1

ENIT - Génie Electrique - v2.0.1

En plaçant un registre après les sorties, on parvient à synchroniser les

ENIT - Génie Electrique - v2.0.1

Ceci a deux avantages :

ENIT - Génie Electrique - v2.0.1

L'histoire du système est conservée dans le registre d'états.

ENIT - Génie Electrique - v2.0.1

ENIT - Génie Electrique - v2.0.1

ENIT - Génie Electrique - v2.0.1

Les sorties ne dépendent pas des entrées.

État État futur Sorties présentes

ENIT - Génie Electrique - v2.0.1

Si on place un registre sur les sorties, on resynchronise les sorties

ENIT - Génie Electrique - v2.0.1

Comme pour la machine de Mealy, l'analyse des timings est possible,

ENIT - Génie Electrique - v2.0.1

ENIT - Génie Electrique - v2.0.1

ENIT - Génie Electrique - v2.0.1

ENIT - Génie Electrique - v2.0.1

=> L’ajout du registre va essentiellement dépendre de l'accélération due à

ENIT - Génie Electrique - v2.0.1

Vous aimerez peut-être aussi