FONCTIONS NUMÉRIQUES CHAPITRE 5: MACHINE À ÉTATS Delaram HAGHIGHI-TALAB 2025-2026

LES RÈGLES DE JEU

Rôle d’enseignant

• Présenter les définitions et la méthodologie.

Rôle d’étudiant

• Noter.
• A l’écoute active en s’évaluant par les quizz.
• Chercher des questions et des erreurs !

TRAVAUX DIRIGÉS (TD)

Rôle d’étudiant

• Réviser les définitions et exercer la méthodologie.

Rôle d’enseignant

• Contrôler les réponses.
• Donner les références conformes aux erreurs.

TRAVAUX PRATIQUES (TP)

Rôle d’étudiant

• Pratiquer les acquis en réalisant un système numérique.

Rôle d’enseignant

• Diriger.
• Évaluer.

SOMMAIRE CHAPITRE 5 : MACHINE À ÉTATS

Introduction

• Pourquoi machine à états ? Ces machines sont fondamentales pour la conception de systèmes numériques séquentiels en modélisant leur comportement dynamique.
• Définition : états, événement, transition. Comprendre comment un système évolue d'un état défini à l'autre en réponse à des événements externes ou internes spécifiques.
• Graphes d’états. Une représentation visuelle claire du comportement du système, facilitant l'analyse et la conception.
• Machine à états de Moore et de Mealy. Deux modèles distincts pour la détermination des sorties, l'un basé uniquement sur l'état, l'autre sur l'état et les entrées combinées.

Méthodologie de conception d’une machine à états

POURQUOI MACHINE À ÉTATS ?

Gestion de la complexité

• Les machines à états simplifient la gestion des systèmes complexes en décomposant leur comportement en états et transitions distincts. Cela facilite la compréhension et la gestion du flux du système, ainsi que son débogage et sa maintenance.

Interface Utilisateur

• Les machines à états sont couramment utilisées lors de la programmation d'interfaces utilisateur (UI). Lors de la création d'une interface utilisateur, différentes actions d’utilisateur (comme un clic de bouton, une saisie de texte, ou un passage de souris) dirigent l'interface vers différents segments de traitement ou affichages. Chacun de ces segments agit comme un état dans la machine à états, permettant une gestion structurée et prévisible des interactions utilisateur et des réponses du système.

MACHINE À ÉTATS – VIE QUOTIDIENNE

• Une machine à états est un moyen de modéliser le fonctionnement d’un système, en utilisant des états et des transitions pour montrer comment le système réagit au fil du temps en réponse aux événements, offrant une abstraction puissante du comportement.

Exemple

• Un portillon (Wikipedia). Considérez un portillon d'accès. Il peut être dans l'état "Fermé". Lorsqu'un utilisateur insère un ticket valide (un événement), le portillon passe à l'état "Ouvert". Une fois que la personne a traversé (un autre événement), il retourne à l'état "Fermé", attendant la prochaine interaction.

ÉTATS (STATES)

Élément constitutifs

• Les états, événements et transitions constituent un outil puissant pour modéliser et comprendre les systèmes, définissant leur comportement dynamique de manière formelle.

Définition d'un État

• Un état représente une situation ou un mode particulier dans lequel un système peut se trouver à un moment donné, caractérisant son comportement actuel et les actions qu'il peut entreprendre. Par exemple, une commande en ligne peut être dans les états suivants : en attente, expédiée, livrée ou retournée.
• Chacun de ces états est un état fini, contribuant au cycle de vie complet d'une commande et définissant les actions et réponses possibles du système tant qu'il s'y trouve.

Finite State Machine (FSM)

• Une machine avec un nombre fini d'états signifie qu'un objet ne peut être que dans un seul état à la fois. C'est le principe du mutualisme exclusif des états. Par exemple, une commande ne peut pas être simultanément dans les états "En attente" et "Livrée", garantissant la clarté et la non-ambiguïté du comportement du système à tout instant.

ÉVÉNEMENT ET TRANSITION

Événements

• Les événements sont des occurrences externes ou internes qui peuvent causer une transition entre les états d'une machine RÉSULTS. Ils peuvent inclure des entrées utilisateur (comme un clic de bouton), des signaux de capteurs (porte ouverte ou fermée), des conditions internes (minuterie écoulée), ou des messages provenant d'autres systèmes. Dans l'exemple précédent de la commande, un événement tel qu'un "article expédié" peut faire passer une commande de l'état « En attente » à l'état « Expédiée ».

Transition d'état

• Une transition d'état décrit la manière dont un système passe d'un état à un autre en réponse à un ou plusieurs événements satisfaits et/ou de conditions remplies. Cela se décrit par les flèches reliant les états dans un graphe, étiquetées selon l'événement qui déclenche la transition et, potentiellement, les conditions supplémentaires qui doivent être vraies à ce moment.
• Dans ce cours, les transitions se produisent généralement au front montant de l’horloge (systèmes synchrones), sous réserve des événements nécessaires et de la satisfaction des conditions booléennes associées. Cela assure un comportement temporel prévisible.

GRAPHE D’ÉTATS

Représentation

• Un graphe d’états est une représentation graphique et structurée des états que peut prendre un système et des transitions possibles entre ces états, offrant ainsi une vue d'ensemble claire et intuitive du comportement dynamique du système.

Structure

• **Nom de l’état :** En haut de l’ellipse. Doit être unique et descriptif du mode de fonctionnement ou de la situation actuelle du système (par exemple, "Attente", "Veille").
• **Actions à effectuer dans cet état :** En bas de l’ellipse. Représentent les sorties actives ou les opérations / fonctions effectuées tant que le système est dans cet état. Ces actions sont généralement liées à la sortie de la machine à états.
• **Conditions/Action :** À côté de la flèche indiquant la transition. Décrivent les critères booléens qui doivent être remplis pour que la transition se produise, ainsi que les actions (éventuelles) effectuées pendant le processus de transition lui-même.
• Un état est représenté par une ellipse et doit inclure le nom de l'état et les éventuelles actions. Les actions correspondent souvent à l’activation ou la désactivation de sorties booléennes (par exemple, allumer une LED, activer un moteur, désactiver un signal de chauffage).
• Une transition est une flèche entre un état d’origine (état source) et un état destination (état cible), indiquant les conditions logiques et/ou les événements qui sont nécessaires pour passer d'un état à l'autre. Ces conditions sont évaluées à chaque cycle d'horloge.
• Les conditions sont des expressions booléennes; si aucune condition n’est précisée, cela signifie que la transition doit toujours être franchie (condition toujours vraie) dès l'occurrence d'un événement implicite ou après un certain délai.

MACHINE À ÉTATS DE MOORE ET DE MEALY

Machine de Moore

• La sortie de la machine de Moore est basée uniquement sur l'état actuel dans lequel la machine se trouve. Les sorties sont stables et ne changent qu'au changement d'état, ce qui simplifie leur synchronisation et les rend moins sujettes aux "glitchs" ou "aléas".

Machine de Mealy

• La machine Mealy détermine ses sorties à partir de l'état actuel et des entrées. Cela permet des réponses plus rapides aux changements d'entrées, mais peut induire des "glitchs" ou des "aléas" sur les sorties si les entrées changent avant que l'état ne soit mis à jour, rendant sa conception et son analyse plus délicates.

Utilisation

• Utiliser Mealy uniquement si Moore ne suffit pas pour répondre aux exigences fonctionnelles du système (par exemple, si une sortie doit réagir instantanément et de manière combinatoire à une entrée sans attendre le prochain cycle d'horloge pour changer d'état). Évitez d'utiliser Mealy en E1 sauf en question bonus, car sa conception et son analyse peuvent être plus complexes et prone aux erreurs.

RÉSUMÉ DES RÈGLES

États

• À tout instant, un état et un seul est actif; tous les autres étant inactifs. Ceci garantit le déterminisme du comportement du système et évite les situations ambiguës.
• L’un des états doit être défini comme « initial », activé au démarrage ou en cas de réinitialisation du système, établissant le point de départ de son fonctionnement régulier.

Transitions

• Une transition doit être dessinée entre 2 états : un état source et un état cible. Elle indique un changement de comportement du système.
• Il doit exister une et une seule transition de vraie partant de l’état (et éventuellement rebouclant dessus), quelles que soient les valeurs des entrées. Cette règle fondamentale (complétude et exclusivité des conditions de transition) assure qu'il n'y a jamais d'ambiguïté sur le prochain état et que le système ne reste jamais bloqué dans un état sans transition définie.

Conditions

• Une condition s’exprime sous la forme d’une opération booléenne avec un résultat « vrai » ou « faux ». Elle peut dépendre d'une ou plusieurs entrées logiques du système.
• Les conditions associées à plusieurs transitions ayant le même état source doivent être mutuellement exclusives pour éviter toute ambiguïté sur quelle transition doit être prise. De plus, la somme logique de toutes les conditions de transition sortantes d'un état doit être toujours vraie pour assurer la complétude (une transition est toujours possible).

Actions

• Une action se présente sous la forme d’une affectation de sortie. Ces actions sont exécutées lorsque le système est dans un état particulier ou lors d'une transition.
• Dans le cas de Moore, les sorties dépendent de l’état, elles sont donc générées uniquement par le fait d'être dans un certain état, ce qui les rend stables.

EXEMPLE: CONTRÔLE DU FOUR À MICRO-ONDES

• Le four est équipé d'un bouton de mise en marche et d'une minuterie qui détermine la durée de cuisson.
• La cuisson peut être interrompue en ouvrant la porte du four ; après fermeture de la porte, la cuisson reprend.
• La cuisson est terminée une fois la minuterie écoulée.

Entrées du système

• **Clk et resetn :** nécessaires car le système doit stocker un état et donc utilise des bascules. clk est le signal d'horloge synchronisant les transitions, resetn est un signal de réinitialisation asynchrone (actif à l'état bas).
• **Bouton de mise en marche :** son activation par l'utilisateur démarre la cuisson (signal à l'état haut B=1).
• **Minuterie :** indique si la durée de cuisson est écoulée (la minuterie est remise à zéro au début du cycle de cuisson). M=1 si écoulée, M=0 sinon.
• **Capteur de porte :** indique l'état de la porte (ouverte avec un signal à l'état bas P=0 ou fermée avec un signal à l'état haut P=1).

Sortie

• **Alimentation :** active la cuisson (signal à l'état haut Alim=1) ou stoppe la cuisson (signal à l'état bas Alim=0).

EXEMPLE: CONTRÔLE DU FOUR À MICRO-ONDES

Éléments de l'entrée

• **Entrées :** clk, reset (n’apparaissent pas dans le graphe d'état car ils sont implicites pour la synchronisation et l'initialisation du circuit, mais seront présents dans le circuit physique).
• **B : bouton start :** démarre si B=1.
• **M : minuterie écoulée :** M=1 si écoulée ou pas (M=0).
• **P : Capteur de porte :** ouvert (P=0)/fermé (P=1).

Éléments de la sortie

• **Alim :** active le chauffage (Alim=1) (tous les signaux d'E/S sont sur 1 bit).

Diagramme d'état

• État - Attente : Alim=0 (four inactif, prêt à démarrer)
• Cuisson : Alim=1 (four en train de chauffer)
• Arrêt : Alim=0 (cuisson suspendue suite à l'ouverture de la porte)
• Fini : Alim=0 (cuisson terminée, signal de fin)

Du texte au graphe d’états

1. Déterminer et nommer les états pertinents du système.
2. Définir les sorties en fonction de l’état actuel, conformément au modèle de Moore si possible.
3. Définir les transitions entre les états en spécifiant les conditions (événements et entrées) qui les déclenchent.

ASTUCE: LES CONDITIONS DE TRANSITION

• Comment déterminer les conditions de transitions non triviales ?
• Utiliser un tableau de Karnaugh ou un tableau de vérité qui montre toutes les combinaisons possibles des entrées prises en compte lorsque l’on est dans cet état, afin de définir de manière exhaustive les conditions de sortie de chaque état.

CHRONOGRAMME

• **clk, resetn, B, P, M :** États d'attente, cuisson, arrêt, fini -- Visualisation de l'évolution des signaux d'entrée, des états internes et des sorties au cours du temps, synchronisée par l'horloge.
• Alimentation et états

QUIZZ

• À propos du graphe ci-dessous :
• ( A ) il n'y a pas d'erreurs ni d'optimisation possible
• ( B ) on peut simplifier le graphe
• ( C ) il y a une erreur
• ( D ) on peut simplifier et il y a une erreur

RAPPEL: PRINCIPE DE CONCEPTION DU CIRCUIT SÉQUENTIEL

• Une fois le nombre de bascules nécessaires établit, il faut définir :
  • Fonction de transition (circuit combinatoire) : détermine le prochain état du système en fonction de son état actuel et de ses entrées.
    $Q^+ = T(entrée, Q)$
  • Fonction de génération (circuit combinatoire) : détermine les sorties de la machine à états.
  • Moore : $sorties = G_{état}$ (les sorties dépendent uniquement de l'état présent)
  • Mealy : $sorties = G_{état, entrées}$ (les sorties dépendent de l'état présent et des entrées combinatoires)

CONCEPTION D’UNE MACHINE À ÉTATS

Étape 1 - Construction du graphe d’états

• Chaque état est représenté par un cercle ou une ellipse.
• Définir et nommer l’état initial, représenté par un double cercle ou une flèche entrante sans source. C'est l'état dans lequel la machine se trouve au démarrage ou après une réinitialisation (resetn).
• Donner un nom significatif à chaque état qui reflète sa fonction ou le mode de fonctionnement du système (ex: "Attente", "Veille", "Actif", "Erreur").
• Pour chaque état, définir les valeurs des sorties qui sont actives ou inactives lorsque la machine est dans cet état. Ces sorties doivent rester stables tant que la machine est dans cet état.
• La transition d’un état à un autre dépend des entrées et de l’état actuel. Ces flèches définissent les chemins possibles entre les états en réponse à des événements.
• Représenter les transitions par des flèches marquées avec des conditions. Ces conditions sont les critères booléens qui déclenchent le passage d'un état à l'autre.
• Attention aux transitions implicites, où l’on ne change pas d’état (représentées par une flèche avec les conditions correspondantes et qui reboucle sur l'état source), elles sont essentielles pour assurer qu'une transition est toujours définie pour toutes les combinaisons d'entrées non utilisées par d'autres transitions sortantes.

Étape 2 – Codage des états (méthode « one-hot »)

• Choisir un codage : attribuer à chaque état une combinaison unique de valeurs de bascules (bits d'état). Le nombre de bascules nécessaires dépendra du nombre total d'états et de la méthode de codage choisie.
• Méthode « one-hot »: une seule bascule est à 1 à la fois, chaque état étant associé à une bascule spécifique. Par exemple, si l'état A est actif, seule la bascule $_A$ est à 1 et toutes les autres sont à 0.

Avantages du codage « one-hot »

• Permet d’obtenir les équations de la fonction de transition directement sans table de vérité complexe, car chaque terme de l'équation correspond à l'activation d'une bascule d'état (exemple: $Q<em>B^+$ si $Q</em>A$ et conditions A -> B). Cela simplifie grandement la logique combinatoire du prochain état.
• Simplifie intérieurement la table de vérité de la fonction de génération, car les sorties sont souvent directement liées à l'état actif (bascule à 1), réduisant les portes logiques nécessaires pour les décoder.

Inconvénient

• Imposition d’un circuit de décodage pour générer les sorties à partir de l’état, ce qui peut augmenter la complexité matérielle si le nombre d'états est élevé, car chaque bascule représente un état unique nécessitant son propre bit, ce qui peut consommer plus de ressources (bascules) qu'un codage binaire minimum.

EXEMPLE: CONTRÔLE DU FOUR À MICRO-ONDES CODAGE « ONE – HOT »

• **Noms des bascules :** Correspondent aux états. Chaque bascule est active 1 lorsque son état correspondant est valide.
  | État | $Q<em>A$ | $Q</em>B$ | $Q<em>{Ar}$ | $Q</em>F$ |
  | -------- | -------- | -------- | -------- | -------- |
  | Attente | 1 | 0 | 0 | 0 |
  | Cuisson | 0 | 1 | 0 | 0 |
  | Arrêt | 0 | 0 | 1 | 0 |
  | Fini | 0 | 0 | 0 | 1 |

Étape 3 – Équation de la fonction de transition (méthode « one - hot »)

• Équations logiques décrivant la valeur du prochain état ($Q^+$) pour chaque bascule en fonction de l'état actuel et des entrées. Ces équations définissent le comportement séquentiel de la machine.
• $Q_B^+$ (Cuisson) vaudra 1 au prochain cycle si :
  • On est dans l’état Attente ($Q_A$) et B et P vaut 1.
  • On est dans l’état Arrêt ($Q_{Ar}$) et P vaut 1.
  • On est dans l’état Cuisson ($Q_B$) et M vaut 0 et P vaut 1 (pour rester en cuisson).
    Formules :
• $Q<em>B^+ = (Q</em>A \cdot B \cdot P) + (Q<em>{Ar} \cdot P) + (Q</em>B \cdot \overline{M} \cdot P)$
• $Q<em>A^+ = (Q</em>A \cdot (\overline{B} + \overline{P})) + Q_F$
• $Q<em>{Ar}^+ = (Q</em>{Ar} \cdot \overline{P}) + (Q_B \cdot \overline{M} \cdot \overline{P})$
• $Q<em>F^+ = Q</em>B \cdot M$

CONCEPTION D’UNE MACHINE À ÉTATS

Étape 4 – Équations de la fonction de génération (méthode « one - hot »)

• Les valeurs des sorties ne sont pas celles des bascules directement; il faut un circuit combinatoire pour les générer à partir des états (et éventuellement des entrées pour Mealy).
• En « one-hot », une seule bascule est à 1 à la fois, ce qui simplifie la logique de sortie.
• Équations de sortie générées :
  | $Q<em>A$ | $Q</em>B$ | $Q<em>{Ar}$ | $Q</em>F$ | Alim |
  | ------------------- | ------------------- | ------------------- | ------------------- | ------------------- |
  | 1 | 0 | 0 | 0 | 0 |
  | 0 | 0 | 1 | 0 | 0 |
  | 0 | 1 | 0 | 0 | 1 |
  | 0 | 0 | 0 | 1 | 0 |
  | Autres combinaisons | 0 |
• $Alim = Q<em>B$ (L'alimentation est active uniquement lorsque la machine est dans l'état Cuisson, représenté par la bascule $Q</em>B$).

Étape 5 – Schématique

• Commencer par dessiner les bascules, en connectant le resetn pour n’activer qu’une seule bascule (celle correspondant à l’état initial) au démarrage.
• Ajouter la fonction de transition (schémas des $Q^+$), qui correspond à la logique combinatoire déterminant le prochain état des bascules.
• Compléter par la fonction de génération (schéma des sorties), qui correspond à la logique combinatoire produisant les sorties finales du système.
• Nommer les fils pour une meilleure lisibilité et faciliter le débogage du circuit !

EXEMPLE: CONTRÔLE DU FOUR À MICRO-ONDES SCHÉMATIQUE

Fonctions de transition

• $Q<em>B^+ = (Q</em>A \cdot B \cdot P) + (Q<em>{Ar} \cdot P) + (Q</em>B \cdot \overline{M} \cdot P)$
• $Q<em>A^+ = (Q</em>A \cdot (\overline{B} + \overline{P})) + Q_F$
• $Q<em>{Ar}^+ = (Q</em>{Ar} \cdot \overline{P}) + (Q_B \cdot \overline{M} \cdot \overline{P})$
• $$