Apprendre › Chapitre 11
Machines à états de Moore et de Mealy : conception complète
7 min de lecture · Équipe bitGateLab
Une machine à états finis (FSM) est un circuit séquentiel qui « se souvient » de l'étape où en est un processus. Feux de circulation, serrures à code, commandes d'ascenseur et récepteurs de communication série sont des machines à états. Vous allez voir ici les deux modèles classiques, Moore et Mealy, et suivre une conception complète, de la description en langage courant jusqu'aux équations des bascules, avec un détecteur de la séquence 101.
Les parties d'une machine à états
Toute FSM synchrone comporte trois blocs :
- Registre d'état : n bascules (presque toujours de type D) qui mémorisent l'état courant ; elles suffisent pour un maximum de 2n états.
- Logique d'état suivant : combinatoire ; elle calcule le prochain état à partir de l'état courant et des entrées.
- Logique de sortie : combinatoire ; elle calcule les sorties.
La différence entre les deux modèles tient au dernier bloc :
- Moore : les sorties ne dépendent que de l'état courant. On les écrit à l'intérieur du cercle de chaque état (par exemple S3/1).
- Mealy : les sorties dépendent de l'état et des entrées. On les écrit sur les flèches (entrée/sortie, par exemple 1/1).
Le problème : détecteur de la séquence 101
Une entrée série X arrive synchronisée avec l'horloge, à raison d'un bit par cycle. La sortie Z doit valoir 1 chaque fois que les trois derniers bits reçus sont 1, 0, 1. Le chevauchement est autorisé : dans la suite 10101, il y a deux détections, car le dernier 1 de la première séquence est le premier de la suivante.
La première étape consiste à décider ce que la machine doit retenir. Chaque état représente « la part de la séquence déjà reçue » :
- S0 : rien d'utile pour l'instant.
- S1 : le dernier bit était 1.
- S2 : les derniers bits étaient 1, 0.
- S3 : je viens de recevoir 1, 0, 1 (Z = 1).
Diagramme et table d'états (Moore)
Pour chaque état et chaque valeur de X, posez-vous la question : avec ce nouveau bit, quel est le plus long suffixe qui coïncide avec le début de 101 ? Ce suffixe définit l'état suivant.
| État courant | X = 0 | X = 1 | Z |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 |
Arrêtez-vous sur deux transitions où l'on se trompe souvent. En S1 arrive un autre 1 : la suite se termine par 11, et le dernier 1 peut toujours servir de début ; la machine reste donc en S1. En S3 arrive un 0 : la suite se termine par 1010, dont le suffixe 10 coïncide avec le début de 101 ; elle va donc en S2 et non en S0. C'est ce qui permet le chevauchement.
Codage des états et équations
Avec 4 états, 2 bascules D suffisent (Q1 Q0). Le codage le plus direct est le codage binaire : S0 = 00, S1 = 01, S2 = 10, S3 = 11. Avec des bascules D, la table d'excitation est triviale, car D = Q+.
| Q1 | Q0 | X | Q1+ = D1 | Q0+ = D0 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
Simplification :
- D0 vaut 1 exactement sur les lignes où X = 1, donc D0 = X. C'est logique : avec ce codage, Q0 = 1 signifie « le dernier bit était 1 ».
- D1 = Σm(2, 5, 6) avec les variables dans l'ordre Q1 Q0 X. Les mintermes 2 (010) et 6 (110) sont adjacents et forment Q0·X. Le 5 (101) n'a pas de voisin à 1 et reste seul : Q1·Q0·X. D1 = Q0·X + Q1·Q0·X.
- La sortie de Moore ne dépend que de l'état : Z = Q1·Q0.
Le circuit comporte 2 bascules D, une AND à 2 entrées pour Z et, pour D1, une AND à 2 entrées, une AND à 3 entrées et une OR à 2 entrées (plus les inverseurs de Q0 et de X).
Vérification avec une séquence de test
Entrée X = 1 0 1 0 1 1 0 1, en partant de S0. État après chaque front :
| Front | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| X | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| État | S1 | S2 | S3 | S2 | S3 | S1 | S2 | S3 |
| Z | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
Il y a trois détections : sur les bits 1 à 3, 3 à 5 (chevauchement) et 6 à 8. Vérifiez le front 4 avec les équations : état S3 = 11 et X = 0, D1 = 1·1 + 1·0·0 = 1 et D0 = 0, état suivant 10 = S2. Cela concorde.
La version Mealy
Dans une machine de Mealy, la sortie est portée par la transition ; l'état S3 devient donc inutile : la détection a lieu « à l'arrivée du 1 alors que l'on est en S2 ». Avec trois états A (rien), B (dernier bit à 1) et C (derniers bits 1, 0) :
| État | X = 0 | X = 1 |
|---|---|---|
| A | A / 0 | B / 0 |
| B | C / 0 | B / 0 |
| C | A / 0 | B / 1 |
Il faut toujours 2 bascules, mais la sortie Z = 1 apparaît dans le cycle même où arrive le dernier 1, soit un cycle plus tôt que dans la version Moore.
Erreurs fréquentes
- Renvoyer vers S0 toutes les transitions qui « échouent », sans vérifier quelle partie de la séquence reste utilisable ; on perd ainsi les détections avec chevauchement.
- Écrire les sorties sur les flèches dans une machine de Moore, ou à l'intérieur des états dans une machine de Mealy.
- Oublier les combinaisons de bascules inutilisées (par exemple, le code 11 dans la version Mealy) : il faut décider où elles mènent, ou les marquer comme X et vérifier que la machine revient dans la séquence.
- Lire la sortie d'une machine de Mealy à n'importe quel moment : elle doit être échantillonnée juste avant le front, lorsque l'entrée est déjà stable.
- Changer l'entrée X juste sur le front de l'horloge en testant la machine.
Essayez dans le simulateur
Une fois les équations obtenues, réaliser le détecteur prend quelques minutes, et le chronogramme vous permet de vérifier chaque transition.
- Placez deux bascules D sur la même horloge ; nommez leurs sorties Q1 et Q0.
- Reliez l'entrée X directement à D0.
- Réalisez D1 = Q0·X + Q1·Q0·X avec deux inverseurs, deux AND et une OR, et reliez le résultat à D1.
- Reliez une AND de Q1 et Q0 à un voyant pour Z.
- Changez X avant chaque front en suivant la séquence 1 0 1 0 1 1 0 1 et observez dans le chronogramme que Z s'allume après les fronts 3, 5 et 8.
Exercices
- Avec chevauchement, combien de fois la machine détecte-t-elle 101 dans la suite 1010101 ?
Réponse
Trois fois : sur les bits 1 à 3, 3 à 5 et 5 à 7.
- Refaites la table de Moore du détecteur de 101 sans chevauchement (après une détection, on repart de zéro).
Réponse
Seule la ligne S3 change : avec X = 0 elle va en S0 et avec X = 1 elle va en S1. Les autres lignes restent identiques.
- Avec le codage de la version Mealy A = 00, B = 01, C = 10, déterminez Z.
Réponse
Z = 1 uniquement dans l'état C avec X = 1 : Z = Q1·Q0·X. Si le code 11 n'apparaît jamais, on peut le marquer comme X et il reste Z = Q1·X.
- Combien de bascules faut-il au minimum pour une machine à 9 états ?
Réponse
4, car 23 = 8 ne suffit pas, alors que 24 = 16 suffit.
Pour revoir les bascules qui forment le registre d'état, consultez verrous et bascules.