Les Machines à États Finis (FSM)
Modéliser et concevoir des systèmes séquentiels complexes
Qu’est-ce qu’une Machine à États Finis ?
Une Machine à États Finis (FSM – Finite State Machine) est un modèle mathématique de calcul qui se trouve toujours dans l’un d’un nombre fini d’états. Elle passe d’un état à un autre selon les entrées et des règles de transition définies.
Une FSM est définie par :
- S : Ensemble fini d’états
- I : Ensemble fini d’entrées
- O : Ensemble fini de sorties
- δ : Fonction de transition (état suivant = δ(état actuel, entrée))
- λ : Fonction de sortie
- s₀ : État initial
Exemple simple : Feu tricolore
- États : {VERT, ORANGE, ROUGE}
- Entrée : Signal d’horloge (temporisation)
- Transitions : VERT → ORANGE → ROUGE → VERT → …
Les Deux Types de FSM
Machine de Moore
Dans une machine de Moore, les sorties dépendent uniquement de l’état actuel.
✅ Avantages
- Sorties synchronisées avec l’horloge
- Pas de glitches de sortie
- Plus simple à concevoir
- Plus prévisible
❌ Inconvénients
- Peut nécessiter plus d’états
- Réponse retardée d’un cycle
Machine de Mealy
Dans une machine de Mealy, les sorties dépendent de l’état actuel ET des entrées.
✅ Avantages
- Réponse plus rapide
- Moins d’états nécessaires
- Plus compact
❌ Inconvénients
- Risque de glitches sur les sorties
- Plus complexe à concevoir
- Sorties asynchrones
- Moore : Quand la stabilité des sorties est cruciale
- Mealy : Quand la vitesse de réaction est prioritaire
Diagramme d’États
Le diagramme d’états est une représentation graphique de la FSM. C’est l’outil principal pour concevoir et documenter une machine à états.
- Cercle : Représente un état
- Flèche : Transition entre états
- Double cercle : État initial (optionnel)
- Étiquette de flèche : Condition / Sortie
Exemple : Détecteur de séquence « 101 »
Objectif
Détecter la séquence « 101 » dans un flux binaire série. La sortie passe à 1 quand la séquence est détectée.
Diagramme d’états (Moore)
S0 (Initial) : Rien détecté
→ Si entrée=1 : aller en S1
→ Si entrée=0 : rester en S0
S1 : « 1 » détecté
→ Si entrée=0 : aller en S2
→ Si entrée=1 : rester en S1
S2 : « 10 » détecté
→ Si entrée=1 : aller en S3 (séquence complète !)
→ Si entrée=0 : retour en S0
S3 : « 101 » détecté → Sortie = 1
→ Si entrée=0 : aller en S2 (pour détecter « 1010… »)
→ Si entrée=1 : rester en S1
Table de transition
| État actuel | Entrée = 0 | Entrée = 1 | Sortie |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 |
Implémentation Matérielle
Pour implémenter une FSM en matériel, on utilise :
Bascules D pour mémoriser l’état actuel (N bascules pour 2ᴺ états)
Calcule l’état suivant = f(état actuel, entrées)
Moore : f(état) | Mealy : f(état, entrées)
Encodage des états
Chaque état doit être représenté par un code binaire unique.
Encodage binaire
États numérotés séquentiellement
S2=10, S3=11
Simple mais pas optimal
Encodage Gray
Un seul bit change entre états adjacents
S2=11, S3=10
Réduit les glitches
One-Hot
Un bit par état (1 seul à 1)
S2=0100, S3=1000
Plus rapide, plus de bascules
- Binaire : Minimise le nombre de bascules
- Gray : Réduit les transitions multiples
- One-Hot : Simplifie la logique de décodage, plus rapide
Conception avec Karnaugh
💡 Méthode
Exemple Complet : Contrôleur de Feu Tricolore
Cahier des charges
Feu tricolore simple avec temporisations :
- VERT : 30 secondes
- ORANGE : 5 secondes
- ROUGE : 30 secondes
Entrée : Signal d’horloge (1 Hz) + compteur interne
États et transitions
| État | Durée | Sorties (R,O,V) | État suivant |
|---|---|---|---|
| S_VERT | 30s | 0,0,1 | S_ORANGE |
| S_ORANGE | 5s | 0,1,0 | S_ROUGE |
| S_ROUGE | 30s | 1,0,0 | S_VERT |
Implémentation
Utiliser :
- 2 bascules D pour encoder 3 états (encodage binaire : 00, 01, 10)
- Compteur 6 bits pour compter jusqu’à 30
- Comparateurs pour détecter les fins de temporisation
- Logique combinatoire pour les transitions
Application : Décodeur de Protocole Série
Problème
Décoder un protocole série simple :
- START bit : 0
- 8 bits de données
- STOP bit : 1
États nécessaires
| État | Description | Action |
|---|---|---|
| IDLE | Attente de START | Surveiller ligne série |
| START | START détecté | Initialiser compteur |
| DATA | Réception données | Décaler les bits (×8) |
| STOP | Vérification STOP | Valider trame |
| ERROR | Erreur détectée | Signal d’erreur |
Ligne : ___╲___╱───╲___╱───╲___╱───...___╱‾‾‾╲___
États : IDLE START D0 D1 D2 D3...D7 STOP IDLE
Application concrète
Ce type de FSM est utilisé dans :
- Interface CAT des transceivers
- Réception RTTY (radioteletype)
- Décodage APRS
- Communication avec GPS
Implémentation en VHDL/Verilog
Les FSM sont souvent décrites en langages HDL (Hardware Description Language) pour implémentation sur FPGA.
Exemple en pseudo-code VHDL
-- Machine à états pour détecteur de séquence
PROCESS(clk, reset)
BEGIN
IF reset = '1' THEN
state <= S0;
ELSIF rising_edge(clk) THEN
CASE state IS
WHEN S0 =>
IF input = '1' THEN
state <= S1;
ELSE
state <= S0;
END IF;
WHEN S1 =>
IF input = '0' THEN
state <= S2;
ELSE
state <= S1;
END IF;
WHEN S2 =>
IF input = '1' THEN
state <= S3;
ELSE
state <= S0;
END IF;
WHEN S3 =>
IF input = '0' THEN
state <= S2;
ELSE
state <= S1;
END IF;
END CASE;
END IF;
END PROCESS;
-- Logique de sortie (Moore)
output <= '1' WHEN state = S3 ELSE '0';
- Description de haut niveau
- Simulation possible avant fabrication
- Synthèse automatique en portes logiques
- Facile à modifier et maintenir
Méthodologie de Conception
Définir clairement le comportement souhaité et les entrées/sorties
Dessiner le diagramme avec tous les états et transitions
Décider entre Moore et Mealy selon les contraintes
Choisir binaire, Gray ou One-Hot
Créer la table complète état actuel → état suivant
Utiliser Karnaugh pour minimiser la logique
Réaliser avec bascules + portes OU HDL + FPGA
Tester tous les cas, y compris les cas limites
Pièges à Éviter
Vérifier que tous les états peuvent être atteints depuis l'état initial.
S'assurer qu'il n'existe pas d'état sans sortie possible.
Avec encodage binaire, certains codes peuvent ne correspondre à aucun état défini. Prévoir un état de récupération.
Deux transitions depuis un même état ne doivent jamais être vraies simultanément.
Synchroniser les signaux asynchrones avec des bascules en cascade (double-flop).
Autres Applications Radio
Encodeur CTCSS
FSM générant la séquence de tonalité sous-audio
Temporisateur TOT
Time-Out Timer : FSM surveillant la durée d'émission
Séquenceur TX/RX
Gestion de la commutation émission/réception
Décodeur DTMF
FSM détectant les tonalités duales
Contrôle de squelch
FSM avec hystérésis pour éviter le "battement"
Analyseur de protocole
Décodage de trames AX.25, APRS, etc.
Projet : Décodeur DTMF Simple
Objectif
Créer une FSM qui détecte une séquence de 4 chiffres DTMF pour déverrouiller un système.
Code secret : 1234
États de la FSM
| État | Description | Sortie |
|---|---|---|
| IDLE | Attente touche 1 | Verrouillé |
| DIGIT1 | 1 reçu, attente 2 | Verrouillé |
| DIGIT2 | 12 reçu, attente 3 | Verrouillé |
| DIGIT3 | 123 reçu, attente 4 | Verrouillé |
| UNLOCK | 1234 complet | Déverrouillé |
| ERROR | Mauvaise touche | Verrouillé |
Extensions possibles
- Ajouter un timeout (retour IDLE après 5 secondes d'inactivité)
- Compteur de tentatives (blocage après 3 erreurs)
- Code programmable en mémoire
- Indicateur LED de progression
Points à Retenir
- Les FSM modélisent des systèmes séquentiels complexes
- Moore : sorties = f(état) - plus stable
- Mealy : sorties = f(état, entrées) - plus rapide
- Le diagramme d'états est l'outil de conception principal
- Encodage des états : binaire, Gray ou One-Hot
- Implémentation : bascules + logique combinatoire
- Les FSM sont essentielles dans les protocoles de communication
- HDL (VHDL/Verilog) facilite la conception sur FPGA
- Toujours prévoir la gestion des états d'erreur
73 de F4HXN - Prochaine fiche : Applications radio amateur ! 📡