Diagramme d’état
Un diagramme d’état préliminaire est un bon point de départ pour définir et étudier le comportement du système. On identifiera les différents états par des lettres pour les distinguer sans faire référence à des variables binaires associées à des éléments de mémoire. Il s’agit dans un premier temps d’un diagramme préliminaire, parce que le diagramme final qui sera implémenté sera potentiellement différent.
À partir du diagramme d’état, il est possible de vérifier quelle séquence de sortie correspond à une séquence d’entrée donnée, et ainsi de valider le comportement.
Tableau d’état
Un tableau d’état comporte une ligne par état présent et combinaison d’entrées. Selon les combinaisons d’entrées possibles, on donne le prochain état et les valeurs de sortie.
Réduction du nombre d’états
Deux états sont équivalents si, pour chaque combinaison d’entrées, ils produisent la même sortie et amènent le système dans le même état ou dans un état équivalent. Considérons le diagramme d’état de la figure suivante et le tableau d’état correspondant (tableau 52). On peut voir qu’il s’agit ici d’une machine de Mealy, car les valeurs de sortie sont associées aux transitions.
Diagramme d’état avant réduction
| État présent | x | État suivant | S | |
|---|---|---|---|---|
| a | 0 | b | 1 | |
| a | 1 | f | 1 | |
| b | 0 | d | 0 | |
| b | 1 | c | 1 | |
| c | 0 | d | 0 | |
| c | 1 | e | 0 | |
| d | 0 | b | 1 | |
| d | 1 | c | 1 | |
| e | 0 | e | 1 | |
| e | 1 | a | 1 | |
| f | 0 | d | 0 | |
| f | 1 | e | 0 |
En inspectant les différents états, on voit que les états c et f sont équivalents. En remplaçant l’état f par l’état c, on obtient le nouveau tableau d’état (tableau 52).
| État présent | x | État suivant | S | |
|---|---|---|---|---|
| a | 0 | b | 1 | |
| a | 1 | c | 1 | |
| b | 0 | d | 0 | |
| b | 1 | c | 1 | |
| c | 0 | d | 0 | |
| c | 1 | e | 0 | |
| d | 0 | b | 1 | |
| d | 1 | c | 1 | |
| e | 0 | e | 1 | |
| e | 1 | a | 1 |
On voit maintenant que les états a et d sont équivalents. En remplaçant l’état d par l’état a, on obtient le tableau d’état simplifié (tableau 53). Il n’y a plus de simplification possible. Nous sommes passés de six états à quatre.
| État présent | x | État suivant | S | |
|---|---|---|---|---|
| a | 0 | b | 1 | |
| a | 1 | c | 1 | |
| b | 0 | d | 0 | |
| b | 1 | c | 1 | |
| c | 0 | d | 0 | |
| c | 1 | e | 0 | |
| e | 0 | e | 1 | |
| e | 1 | a | 1 |
Il faut bien s’assurer que le tableau d’état simplifié produit les séquences de sortie désirées selon les séquences d’entrée appliquées.