Chapitre 16 — Systèmes séquentiels complexes
Machines à états finis : représentation, conception et applications
| Finalité du chapitre — Passer d’un cahier des charges séquentiel à une machine à états complète : états, transitions, sorties, codage, équations, réalisation et validation. |
Niveau conseillé : Bac+1 / Bac+2 — Cycle préparatoire, BTS, BUT, licence ou formation d’ingénieur
Objectifs pédagogiques
- Comprendre le rôle de l’état présent et de l’état futur dans un système séquentiel.
- Représenter un comportement par un diagramme d’états, une table de transition et une table de sortie.
- Distinguer les modèles de Moore et de Mealy et choisir le modèle adapté.
- Coder les états et déterminer les équations de transition, d’excitation et de sortie.
- Concevoir, simuler et vérifier une machine à états à partir d’un cahier des charges.
- Analyser des applications courantes : détection de séquence, feu tricolore, distributeur, contrôle d’accès et commande de moteur.
Prérequis
- Algèbre de Boole et simplification logique.
- Bascules D, JK et T.
- Lecture des chronogrammes.
- Circuits synchrones et notions de setup, hold et propagation.
Plan du chapitre
1. 16.1 Notion d’état
2. 16.2 Représentation d’une machine à états
3. 16.3 Modèles de Moore et de Mealy
4. 16.4 Méthode complète de conception
5. Exemples d’applications
6. Travaux dirigés et activité pratique
7. Synthèse, glossaire, auto-évaluation et corrigés
16.1 Notion d’état
Un système séquentiel complexe est un circuit dont les sorties ne dépendent pas seulement des entrées actuelles, mais aussi de l’histoire récente du système. Cette histoire est résumée par une information appelée état interne.
| Idée essentielle — Deux circuits recevant les mêmes entrées au même instant peuvent produire des sorties différentes s’ils ne se trouvent pas dans le même état interne. |
16.1.1 État présent
L’état présent, noté généralement Q(t), représente la mémoire du système à l’instant considéré. Il est mémorisé dans un registre d’état constitué de bascules. Chaque état correspond à une situation significative du fonctionnement : attente, validation, paiement incomplet, porte ouverte, moteur en marche, etc.
- Il décrit la situation actuelle du système.
- Il est conservé entre deux fronts actifs de l’horloge.
- Il sert au calcul de l’état futur et, selon le modèle, des sorties.
16.1.2 État futur
L’état futur, noté Q(t+1) ou Q⁺, est l’état qui sera chargé dans le registre au prochain front actif. Il est calculé par une logique combinatoire à partir de l’état présent et des entrées :
Q⁺ = f(Q, X)
La fonction f est appelée fonction de transition. Elle traduit les règles d’évolution imposées par le cahier des charges.
16.1.3 Variables d’entrée
Les variables d’entrée, regroupées dans le vecteur X, décrivent les événements ou conditions observés par le système : bouton appuyé, capteur actif, bit reçu, crédit ajouté, fin de temporisation, défaut détecté, etc.
| Entrée synchrone — Une entrée synchrone est interprétée au voisinage d’un front d’horloge. Une entrée asynchrone doit généralement être synchronisée avant d’être utilisée par la machine à états. |
16.1.4 Variables de sortie
Les sorties, regroupées dans le vecteur Y, commandent les actionneurs ou renseignent l’environnement : LED, relais, autorisation d’accès, commande moteur, délivrance d’un produit, signal d’alarme, etc.
Selon l’architecture choisie :
- Moore : Y = g(Q). Les sorties dépendent uniquement de l’état présent.
- Mealy : Y = g(Q, X). Les sorties dépendent de l’état présent et des entrées.
Figure 16.1 — Architecture générale d’une machine à états finis.
16.1.5 Évolution temporelle
Entre deux fronts actifs, le registre conserve son état. La logique combinatoire calcule en permanence l’état futur. Au front suivant, cet état futur devient l’état présent. Cette séparation permet une conception structurée et prévisible.
Instant | Entrée X | État présent Q | État futur Q⁺ | Sortie Y |
t₀ | 0 | S0 | S0 | 0 |
t₁ | 1 | S0 | S1 | 0 |
t₂ | 0 | S1 | S2 | 0 |
t₃ | 1 | S2 | S3 | 1 |
16.2 Représentation d’une machine à états
Une machine à états peut être décrite sous plusieurs formes équivalentes. Chacune met en évidence un aspect particulier : la logique du comportement, la structure tabulaire ou la réalisation matérielle.
16.2.1 Diagramme d’états
Le diagramme d’états est une représentation graphique constituée de cercles et de flèches :
- Chaque cercle représente un état.
- Chaque flèche représente une transition.
- La condition inscrite sur une flèche indique l’entrée ou l’événement provoquant la transition.
- Dans une machine de Moore, les sorties sont généralement inscrites dans les états.
- Dans une machine de Mealy, les sorties sont associées aux transitions sous la forme entrée/sortie.
| État initial — Une flèche venant de l’extérieur du diagramme désigne l’état atteint après l’initialisation ou le Reset. |
Figure 16.2 — Exemple de diagramme d’états pour détecter la séquence 101.
16.2.2 Table de transition
La table de transition indique, pour chaque combinaison de l’état présent et des entrées, l’état futur. Elle constitue le lien entre le diagramme et les équations logiques.
État présent | X=0 : état futur | X=1 : état futur |
S0 | S0 | S1 |
S1 | S2 | S1 |
S2 | S0 | S3 |
S3 | S2 | S1 |
16.2.3 Table de sortie
Dans un modèle de Moore, une ligne par état suffit. Dans un modèle de Mealy, il faut préciser la sortie pour chaque couple état–entrée.
État | Sortie Z (Moore) |
S0 | 0 |
S1 | 0 |
S2 | 0 |
S3 | 1 |
16.2.4 Codage des états
Les noms symboliques S0, S1, S2… doivent être remplacés par des mots binaires mémorisables dans des bascules. Pour N états, le nombre minimal de bits est :
n = ⌈log₂(N)⌉
Pour quatre états, deux bascules suffisent. Un codage possible est S0=00, S1=01, S2=10 et S3=11.
Méthode | Principe | Avantage principal | Limite |
Binaire compact | Utilise le nombre minimal de bits | Peu de bascules | Logique parfois complexe |
One-hot | Une bascule par état | Équations simples et rapides | Plus de bascules |
Gray | Un seul bit change entre états voisins | Réduit certains aléas | Pas toujours possible pour tout graphe |
Personnalisé | Codage choisi pour simplifier les équations | Optimisation ciblée | Demande une étude préalable |
16.2.5 États non utilisés
Avec n bascules, 2ⁿ combinaisons existent. Si toutes ne sont pas affectées, les combinaisons restantes sont des états non utilisés. La conception doit préciser leur évolution afin que le système revienne vers un état valide après une perturbation.
| Machine auto-correctrice — Une machine est dite auto-correctrice si tout état interdit conduit en un nombre fini de cycles vers un état valide, souvent l’état initial. |
16.3 Modèles de Moore et de Mealy
Figure 16.3 — Dépendance des sorties dans les modèles de Moore et de Mealy.
16.3.1 Modèle de Moore
Dans une machine de Moore, les sorties sont entièrement déterminées par l’état présent. Une modification d’entrée peut influencer l’état futur, mais la sortie ne change normalement qu’après le front d’horloge qui provoque le changement d’état.
- Sorties stables entre les fronts d’horloge.
- Diagramme souvent plus lisible.
- Risque d’aléas de sortie généralement plus faible.
- Peut nécessiter davantage d’états et introduire un cycle de latence.
16.3.2 Modèle de Mealy
Dans une machine de Mealy, la sortie dépend simultanément de l’état présent et des entrées. Elle peut donc réagir immédiatement à une variation d’entrée, sans attendre le prochain changement d’état.
- Réponse plus rapide.
- Nombre d’états souvent plus faible.
- Sorties sensibles aux variations ou parasites des entrées.
- Les entrées doivent être propres et correctement synchronisées.
16.3.3 Comparaison
Critère | Moore | Mealy |
| Dépendance de la sortie | État seulement | État et entrées |
| Moment de réaction | Après changement d’état | Potentiellement immédiat |
Nombre d’états | Souvent plus élevé | Souvent plus faible |
| Stabilité des sorties | Élevée | Dépend de la stabilité des entrées |
| Notation du diagramme | Sortie dans le cercle | Entrée/sortie sur la flèche |
Usage conseillé | Commandes sûres et synchrones | Détection rapide et optimisation d’états |
16.3.4 Équivalence fonctionnelle
Un même comportement peut généralement être réalisé dans les deux modèles. La conversion de Mealy vers Moore peut demander l’ajout d’états pour associer chaque sortie à un état stable. La conversion inverse peut réduire le nombre d’états en plaçant les sorties sur les transitions.
| Choix pratique — Pour commander un actionneur critique, Moore est souvent préférable. Pour détecter rapidement une condition sur un flux binaire, Mealy peut être plus efficace. |
16.4 Méthode complète de conception
Figure 16.4 — Démarche complète de conception d’une machine à états.
Étape 1 — Analyser le cahier des charges
Il faut identifier les comportements attendus, les événements, les priorités, les délais, les conditions de sécurité, l’état initial et les situations exceptionnelles. Les formulations ambiguës doivent être transformées en règles précises.
Étape 2 — Identifier les entrées et les sorties
Type | Questions à poser | Exemples |
Entrées | Quels événements le système observe-t-il ? | capteur, bouton, bit, fin de temporisation |
Sorties | Que doit commander ou signaler le système ? | moteur, LED, relais, validation |
Horloge / Reset | Quand les décisions sont-elles prises ? Comment initialiser ? | front montant, Reset actif à 0 |
Étape 3 — Définir les états
Un état doit résumer toute l’information historique nécessaire pour décider du comportement futur. Deux situations peuvent partager un même état si, pour toute suite d’entrées possible, elles entraînent les mêmes sorties et les mêmes évolutions.
| Erreur fréquente — Créer un état pour chaque combinaison d’entrées. Les états représentent la mémoire du passé, pas les entrées présentes. |
Étape 4 — Construire le diagramme d’états
Pour chaque état, examiner toutes les combinaisons d’entrées possibles. Chaque cas doit conduire à une transition définie. Le diagramme doit être complet, déterministe et cohérent.
Étape 5 — Établir les tables
La table de transition et la table de sortie sont déduites directement du diagramme. Elles permettent de vérifier qu’aucun cas n’a été oublié.
Étape 6 — Coder les états
Le codage est choisi selon les contraintes : nombre de bascules, simplicité logique, vitesse, consommation, sécurité et technologie cible. Pour un exercice manuel, le codage binaire compact est souvent retenu.
Étape 7 — Choisir les bascules
Bascule | Relation utile | Avantage en conception |
D | D = Q⁺ | Méthode la plus directe |
T | T = Q ⊕ Q⁺ | Pratique pour les basculements |
JK | J et K obtenus par la table d’excitation | Peut simplifier certains compteurs |
Étape 8 — Déterminer les équations d’excitation
Après remplacement des états symboliques par leur code, chaque bit de l’état futur est exprimé en fonction des bits de l’état présent et des entrées. Avec des bascules D, l’entrée Dᵢ est directement égale au bit Qᵢ⁺ correspondant. Les fonctions sont ensuite simplifiées par Karnaugh ou algèbre de Boole.
Étape 9 — Déterminer les équations de sortie
Dans un modèle de Moore, les équations utilisent uniquement les bits d’état. Dans un modèle de Mealy, elles utilisent également les entrées. Les sorties critiques peuvent être enregistrées afin d’éviter les glitches.
Étape 10 — Réaliser et vérifier le circuit
- Dessiner le registre d’état, la logique de transition et la logique de sortie.
- Vérifier l’initialisation et les états non utilisés.
- Simuler toutes les transitions et les cas limites.
- Contrôler les chronogrammes et les contraintes temporelles.
- Comparer le comportement obtenu au cahier des charges.
Exemples d’applications
A. Détecteur de séquence binaire
Le système reçoit un bit à chaque front d’horloge et doit activer Z lorsque les derniers bits reçus correspondent à une séquence donnée. Les états représentent les préfixes déjà reconnus. Pour la séquence 101, les états peuvent représenter : aucun bit utile, «1», «10» et séquence complète.
| Chevauchement — Un détecteur avec chevauchement réutilise les derniers bits de la séquence détectée comme début possible de la séquence suivante. |
B. Commande d’un feu tricolore
Chaque état correspond à une couleur active. Les transitions sont déclenchées par des fins de temporisation. Un modèle de Moore convient naturellement, car les sorties lumineuses dépendent directement de l’état.
C. Distributeur automatique
Les états représentent le crédit cumulé. Les entrées correspondent aux pièces introduites et les sorties commandent la délivrance du produit et éventuellement la monnaie. Un modèle de Mealy peut réduire le nombre d’états en produisant immédiatement la sortie de délivrance sur une transition.
État | Signification | Entrée 1 unité | Entrée 2 unités |
S0 | Crédit 0 | S1 | S2 |
S1 | Crédit 1 | S2 | Délivrer puis S0 |
S2 | Crédit 2 | Délivrer puis S0 | Délivrer + rendre 1 puis S0 |
D. Système de contrôle d’accès
Les états mémorisent la progression dans la saisie d’un code. Les entrées sont les touches ou symboles reçus. Les sorties commandent l’ouverture, l’alarme ou la remise à zéro. Il faut prévoir les erreurs, l’abandon, le délai maximal et le nombre de tentatives.
E. Commande simple d’un moteur
Une machine peut gérer les états ARRÊT, MARCHE_AVANT, MARCHE_ARRIÈRE et DÉFAUT. Les transitions tiennent compte des commandes utilisateur, des fins de course et des protections. Les sorties vers les contacteurs doivent être mutuellement exclusives.
| Sécurité — Les transitions vers l’état DÉFAUT doivent avoir la priorité. Le Reset du défaut ne doit être accepté que lorsque les conditions de sécurité sont rétablies. |
Étude de cas détaillée — Détecteur de 101 avec chevauchement
1. Cahier des charges
À chaque front montant, un bit X est lu. La sortie Z doit valoir 1 lorsqu’une séquence 101 vient d’être reçue. Les détections successives peuvent se chevaucher.
2. Définition des états
État | Information mémorisée |
S0 | Aucun préfixe utile |
S1 | Le dernier bit utile est 1 |
S2 | Les deux derniers bits utiles sont 10 |
S3 | La séquence 101 vient d’être reconnue |
3. Codage
Choix : S0=00, S1=01, S2=10, S3=11, avec Q1Q0 comme registre d’état.
4. Table de transition et de sortie
Q1Q0 | X | Q1⁺Q0⁺ | Z |
00 | 0 | 00 | 0 |
00 | 1 | 01 | 0 |
01 | 0 | 10 | 0 |
01 | 1 | 01 | 0 |
10 | 0 | 00 | 0 |
10 | 1 | 11 | 0 |
11 | 0 | 10 | 1 |
11 | 1 | 01 | 1 |
5. Équations avec bascules D
Après simplification, on obtient un jeu possible d’équations :
D₁ = Q₀·X̅ + Q₁·Q̅₀·X
D₀ = X
Z = Q₁·Q₀
Ces équations dépendent du codage retenu. Un autre codage peut conduire à des expressions différentes tout en réalisant le même comportement.
6. Vérification
Pour la suite X = 1,0,1,0,1, les états évoluent S0→S1→S2→S3→S2→S3. La sortie est donc activée après les troisième et cinquième bits, ce qui confirme la détection avec chevauchement.
Travaux dirigés
TD 1 — Lecture d’un diagramme
À partir d’un diagramme fourni par l’enseignant, dresser la table de transition, identifier l’état initial, préciser si le modèle est Moore ou Mealy et déterminer la sortie pour plusieurs suites d’entrées.
TD 2 — Détecteur de 110
Concevoir un détecteur de la séquence 110 avec chevauchement selon le modèle de Moore. Définir les états, construire le diagramme et établir les tables.
TD 3 — Version Mealy
Reprendre le détecteur de 110 selon le modèle de Mealy. Comparer le nombre d’états et le moment d’activation de la sortie.
TD 4 — Feu tricolore
Concevoir une machine à trois états VERT, JAUNE et ROUGE. Les entrées TV, TJ et TR signalent la fin des temporisations. Déterminer les sorties et les transitions.
TD 5 — Contrôle d’accès
Un code 1011 doit être reçu successivement. Toute erreur ramène à l’état initial. Concevoir le diagramme et proposer un codage.
TD 6 — Distributeur
Un produit coûte 3 unités et la machine accepte des pièces de 1 et 2 unités. Concevoir un modèle de Mealy avec délivrance et rendu de monnaie.
TD 7 — Commande moteur
Définir une machine comprenant ARRÊT, AVANT, ARRIÈRE et DÉFAUT. Interdire le passage direct AVANT↔ARRIÈRE et donner la priorité au défaut.
TD 8 — Codage des états
Pour une machine à cinq états, comparer le nombre de bascules nécessaire en codage binaire, one-hot et Gray. Discuter les avantages.
TD 9 — Équations d’excitation
À partir d’une table codée sur deux bits, déterminer D1 et D0, puis les simplifier avec Karnaugh.
TD 10 — États inutilisés
Une machine utilise cinq états codés sur trois bits. Définir une stratégie de retour sécurisé pour les trois états non utilisés.
Activité pratique proposée
Simulation d’une machine à états dans Logisim Evolution, Proteus ou un outil HDL
- Choisir une application : détecteur 101, feu tricolore ou contrôle d’accès simplifié.
- Créer le registre d’état avec des bascules D.
- Implémenter la logique de transition et la logique de sortie.
- Ajouter une horloge manuelle ou lente et un Reset.
- Afficher l’état sur des LED ou un afficheur.
- Appliquer des suites d’entrées normales et des cas limites.
- Comparer le chronogramme obtenu à la table de transition.
- Tester le comportement après forçage d’un état non utilisé.
Compte rendu attendu
1. Cahier des charges reformulé.
2. Diagramme et tables.
3. Codage des états.
4. Équations simplifiées.
5. Schéma réalisé.
6. Chronogrammes de validation.
7. Analyse des erreurs et conclusion.
Synthèse du chapitre
- Une machine à états mémorise une information abstraite appelée état interne.
- L’état futur dépend de l’état présent et des entrées : Q⁺=f(Q,X).
- Les modèles de Moore et de Mealy diffèrent par la dépendance des sorties.
- Le diagramme, les tables et les équations sont des représentations complémentaires.
- Le codage des états influence le nombre de bascules et la complexité logique.
- La conception suit une démarche systématique depuis le cahier des charges jusqu’à la validation.
- Les états non utilisés, le Reset et les contraintes temporelles doivent être traités explicitement.
Glossaire
Terme | Définition |
État présent | Information mémorisée actuellement par le registre d’état. |
État futur | État chargé au prochain front actif. |
Transition | Passage d’un état à un autre sous une condition donnée. |
FSM | Finite State Machine, machine à états finis. |
Moore | Machine dont les sorties dépendent uniquement de l’état. |
Mealy | Machine dont les sorties dépendent de l’état et des entrées. |
Codage one-hot | Codage utilisant une bascule par état. |
État inaccessible | État qui ne peut être atteint depuis l’état initial. |
État non utilisé | Combinaison binaire non affectée à un état fonctionnel. |
Auto-correction | Capacité à revenir d’un état interdit vers un état valide. |
Auto-évaluation
1. Quelle différence existe entre l’état présent et l’état futur ?
2. Pourquoi une machine à états possède-t-elle une mémoire ?
3. Où place-t-on les sorties dans un diagramme de Moore ?
4. Où place-t-on les couples entrée/sortie dans un diagramme de Mealy ?
5. Combien de bascules faut-il au minimum pour six états ?
6. Quel est l’avantage principal du codage one-hot ?
7. Avec des bascules D, quelle relation lie D et l’état futur ?
8. Pourquoi faut-il traiter les états non utilisés ?
9. Quel modèle convient généralement mieux à une commande stable d’actionneur ?
10. Quelle est la dernière étape avant de valider définitivement une machine ?
Éléments de correction
Correction de l’auto-évaluation
Question | Réponse |
1 | L’état présent est mémorisé maintenant ; l’état futur est celui qui sera chargé au prochain front actif. |
2 | Parce que le comportement futur doit dépendre de l’histoire résumée par l’état interne. |
3 | Dans les cercles représentant les états. |
4 | Sur les transitions, généralement sous la forme X/Y. |
5 | Trois bascules, car 2²<6≤2³. |
6 | Des équations de transition souvent très simples et une grande rapidité. |
7 | D = Q⁺. |
8 | Pour éviter un blocage ou un comportement dangereux après une perturbation. |
9 | Le modèle de Moore. |
10 | La simulation et la vérification complète par rapport au cahier des charges, y compris les cas limites. |
Pistes de correction des TD
TD 1. La table doit contenir une ligne pour chaque couple état–entrée et aucune transition ne doit être ambiguë.
TD 2. Pour 110 en Moore, les états mémorisent généralement : aucun préfixe, «1», «11» et détection complète.
TD 3. En Mealy, la sortie peut être placée sur la transition qui complète 110, ce qui réduit souvent d’un état.
TD 4. Le feu tricolore est naturellement une machine de Moore à trois états, avec une sortie active par état.
TD 5. Le contrôle d’accès possède un état par préfixe correct ; une erreur ramène à l’état initial.
TD 6. Le distributeur utilise les crédits 0, 1 et 2 ; les transitions dépassant 3 produisent délivrance et éventuellement rendu.
TD 7. Le défaut doit conduire depuis tout état vers DÉFAUT. Le changement de sens passe obligatoirement par ARRÊT.
TD 8. Pour cinq états : 3 bascules en binaire, 5 en one-hot. Le Gray demande également au moins 3 bits mais dépend du graphe.
TD 9. Avec des D, chaque équation Dᵢ est obtenue directement depuis la colonne Qᵢ⁺ de la table.
TD 10. Les états non utilisés peuvent tous être dirigés vers l’état initial au cycle suivant pour assurer l’auto-correction.
Fiche méthode récapitulative
1. Reformuler le cahier des charges en règles non ambiguës.
2. Lister entrées, sorties, horloge et Reset.
3. Identifier l’information historique à mémoriser.
4. Définir un ensemble minimal d’états.
5. Tracer un diagramme complet et déterministe.
6. Établir les tables de transition et de sortie.
7. Choisir un codage et traiter les états non utilisés.
8. Choisir les bascules.
9. Déterminer et simplifier les équations.
10. Réaliser, simuler et vérifier tous les scénarios.
| Conclusion — La machine à états constitue une méthode universelle pour transformer un comportement séquentiel complexe en une architecture matérielle claire, vérifiable et réalisable. |