FR

Machines à états (Moore et Mealy)

Du diagramme d'états à la table et aux équations des bascules, avec un détecteur de séquence

Concepteur de détecteur de séquence

Machine

Diagramme d'états

Chaque flèche porte la valeur de l'entrée x qui la provoque ; en Mealy, aussi la sortie produite (« entrée/sortie »). En Moore la sortie est inscrite dans l'état, et les états à double cercle sont ceux qui donnent z = 1.

Table d'états

Équations avec des bascules D

Simulation

Entrée

Qu'est-ce qu'une machine à états

Une machine à états finis est un circuit séquentiel qui se trouve à chaque instant dans l'un d'un nombre limité d'états. L'état résume tout ce qui compte du passé. À chaque front d'horloge, elle passe dans un nouvel état qui dépend de l'état actuel et des entrées. Elle se construit avec un registre de bascules, qui mémorise l'état, et deux blocs de logique combinatoire : l'un calcule l'état suivant et l'autre les sorties.

C'est la façon ordonnée de concevoir tout automatisme séquentiel : un feu tricolore, la commande d'une porte automatique, un distributeur, le protocole d'un port série ou les étapes d'un cycle de lavage. Dans un automate, on la programme de la même manière en GRAFCET ou par étapes en ladder, et dans un microcontrôleur avec un switch sur une variable d'état.

Moore et Mealy

MooreMealy
La sortie dépendDe l'état seulementDe l'état et des entrées
Où l'on dessine la sortieDans chaque étatSur chaque flèche, « entrée/sortie »
Nombre d'étatsIl en faut souvent un peu plusIl en faut souvent moins
RéponseLa sortie change au front d'horloge suivantLa sortie change dès que l'entrée change
SortieStable pendant tout le cycle, sans parasitesPeut présenter des parasites si l'entrée en a

Comparez les deux types dans le simulateur avec la même séquence : le détecteur de Mealy donne z = 1 dans le même cycle que l'arrivée du dernier bit, et celui de Moore un cycle plus tard, une fois entré dans l'état final. Si la sortie d'une machine de Mealy alimente un autre circuit synchrone, ce retard apparaît de toute façon lorsqu'elle est mémorisée.

Étapes de la conception

  1. Diagramme d'états. On décrit le comportement : quels états existent, vers lequel on passe avec chaque entrée et quelle sortie est produite. Dans un détecteur de séquence, chaque état signifie « j'ai reçu les k premiers bits de la séquence ».
  2. Table d'états. La même chose que le diagramme, sous forme de tableau : état actuel et entrée à gauche, état suivant et sortie à droite.
  3. Codage. On attribue un code binaire à chaque état. Avec S états, il faut ⌈log₂ S⌉ bascules. Le codage binaire utilise le minimum de bascules ; le codage « one-hot » (une bascule par état) en utilise davantage mais simplifie beaucoup les équations, et il est courant dans les FPGA.
  4. Équations. Avec des bascules D, l'entrée D de chacune est directement le bit correspondant de l'état suivant. Les codes inutilisés sont indifférents et aident à simplifier dans le tableau de Karnaugh. Avec des bascules JK, on utilise la table d'excitation au lieu de recopier l'état suivant.
  5. États inutilisés. Il faut vérifier où va la machine si elle démarre sur un code inutilisé, à cause d'un parasite ou à la mise sous tension, et prévoir une remise à zéro qui la ramène à l'état initial.

Recouvrement

Avec recouvrement, les derniers bits d'une séquence détectée peuvent être le début de la suivante : en cherchant 1011 dans 1011011, on la détecte deux fois. Sans recouvrement, après chaque détection la machine recommence et n'en trouve qu'une. Pour décider vers quel état revenir quand arrive un bit qui ne convient pas, on cherche la plus longue partie de ce qui a été reçu qui coïncide avec le début de la séquence ; c'est la même idée que celle de l'algorithme de recherche de texte KMP.

Exemple : un feu tricolore

Un feu pour voitures avec bouton pour piétons est une machine de Moore : les feux ne dépendent que de l'état. Une temporisation donne le signal « temps écoulé » et l'appui sur le bouton est mémorisé jusqu'à ce qu'il soit pris en compte.

ÉtatFeux voituresFeux piétonsPasse au suivant quand
S0 VertVertRougeUn piéton a appuyé et le temps minimal de vert est écoulé
S1 OrangeOrangeRougeTemps d'orange écoulé
S2 RougeRougeVertTemps de traversée écoulé
S3 DégagementRougeVert clignotantTemps de dégagement écoulé ; retour à S0

Quatre états se codent avec deux bascules. Les sorties sont des fonctions de Q1 et Q0, par exemple vert voitures = Q1'·Q0' et rouge piétons = Q1'.

Voir aussi : bascules, tableau de Karnaugh, simulateur de portes logiques et simulateur ladder.