Machines Moore et Mealy

Les automates finis peuvent avoir des sorties correspondant à chaque transition. Il existe deux types de machines à états finis qui génèrent une sortie -

  • Machine farineuse
  • Machine de Moore

Machine farineuse

Une machine Mealy est un FSM dont la sortie dépend de l'état actuel ainsi que de l'entrée actuelle.

Il peut être décrit par un 6 tuple (Q, ∑, O, δ, X, q 0 ) où -

  • Q est un ensemble fini d'états.

  • est un ensemble fini de symboles appelé alphabet d'entrée.

  • O est un ensemble fini de symboles appelé alphabet de sortie.

  • δ est la fonction de transition d'entrée où δ: Q × ∑ → Q

  • X est la fonction de transition de sortie où X: Q × ∑ → O

  • q0est l'état initial à partir duquel toute entrée est traitée (q 0 ∈ Q).

Le tableau d'état d'une machine Mealy est illustré ci-dessous -

État actuel État suivant
entrée = 0 entrée = 1
Etat Production Etat Production
→ un b x 1 c x 1
b b x 2 x 3
c x 3 c x 1
x 3 x 2

Le diagramme d'état de la machine Mealy ci-dessus est -

Machine de Moore

La machine de Moore est un FSM dont les sorties dépendent uniquement de l'état actuel.

Une machine de Moore peut être décrite par un 6 tuple (Q, ∑, O, δ, X, q 0 ) où -

  • Q est un ensemble fini d'états.

  • est un ensemble fini de symboles appelé alphabet d'entrée.

  • O est un ensemble fini de symboles appelé alphabet de sortie.

  • δ est la fonction de transition d'entrée où δ: Q × ∑ → Q

  • X est la fonction de transition de sortie où X: Q → O

  • q0est l'état initial à partir duquel toute entrée est traitée (q 0 ∈ Q).

La table d'état d'une machine Moore est présentée ci-dessous -

État actuel État suivant Production
Entrée = 0 Entrée = 1
→ un b c x 2
b b x 1
c c x 2
x 3

Le diagramme d'état de la machine Moore ci-dessus est -

Mealy Machine contre Moore Machine

Le tableau suivant met en évidence les points qui différencient une machine farineuse d'une machine Moore.

Machine farineuse Machine de Moore
La sortie dépend à la fois de l'état actuel et de l'entrée actuelle La sortie dépend uniquement de l'état actuel.
Généralement, il a moins d'états que Moore Machine. Généralement, il a plus d'états que Mealy Machine.
La valeur de la fonction de sortie est fonction des transitions et des changements, lorsque la logique d'entrée sur l'état actuel est effectuée. La valeur de la fonction de sortie est fonction de l'état actuel et des changements aux fronts d'horloge, chaque fois que des changements d'état se produisent.
Les machines farineuses réagissent plus rapidement aux entrées. Ils réagissent généralement dans le même cycle d'horloge. Dans les machines Moore, plus de logique est nécessaire pour décoder les sorties, ce qui entraîne plus de retards de circuit. Ils réagissent généralement un cycle d'horloge plus tard.

Moore Machine à Mealy Machine

Algorithme 4

Input - Machine Moore

Output - Machine farineuse

Step 1 - Prenez un format de table de transition Mealy Machine vierge.

Step 2 - Copiez tous les états de transition de Moore Machine dans ce format de tableau.

Step 3- Vérifiez les états actuels et leurs sorties correspondantes dans la table d'état de Moore Machine; si pour un état Q i la sortie est m, copiez-la dans les colonnes de sortie de la table d'état de la machine Mealy où Q i apparaît dans l'état suivant.

Exemple

Considérons la machine de Moore suivante -

État actuel État suivant Production
a = 0 a = 1
→ un b 1
b une 0
c c c 0
b une 1

Nous appliquons maintenant l'algorithme 4 pour le convertir en machine Mealy.

Step 1 & 2 -

État actuel État suivant
a = 0 a = 1
Etat Production Etat Production
→ un b
b une
c c c
b une

Step 3 -

État actuel État suivant
a = 0 a = 1
Etat Production Etat Production
=> a 1 b 0
b une 1 1
c c 0 c 0
b 0 une 1

Mealy Machine à Moore Machine

Algorithme 5

Input - Machine farineuse

Output - Machine Moore

Step 1- Calculer le nombre de sorties différentes pour chaque état (Q i ) qui sont disponibles dans la table d'état de la machine Mealy.

Step 2- Si toutes les sorties de Qi sont identiques, copier l'état Q i . S'il a n sorties distinctes, divisez Q i en n états comme Q dansn = 0, 1, 2 .......

Step 3 - Si la sortie de l'état initial est 1, insérez un nouvel état initial au début qui donne 0 sortie.

Exemple

Considérons la machine farineuse suivante -

État actuel État suivant
a = 0 a = 1
État suivant Production État suivant Production
→ un 0 b 1
b une 1 0
c c 1 c 0
b 0 une 1

Ici, les états «a» et «d» ne donnent respectivement que 1 et 0 sorties, nous conservons donc les états «a» et «d». Mais les états «b» et «c» produisent des sorties différentes (1 et 0). Alors on se diviseb dans b0, b1 et c dans c0, c1.

État actuel État suivant Production
a = 0 a = 1
→ un b 1 1
b 0 une 0
b 1 une 1
c 0 c 1 C 0 0
c 1 c 1 C 0 1
b 0 une 0