Machines À Etats [PDF]

Zitiervorschau

Machines à Etats

1

Définition  Les

sorties d’un système séquentiel dépendent de l’évolution de ses entrées au cours du temps  Afin de mémoriser cet évolution des entrées, une mémoire est nécessaire. Il s’agit de l’état du système, constitué des bits d’état. 2

Définition

Etat d’un système séquentiel

 L’état

du système est stocké dans les variables d’état du système. Ces variables, à un instant donné, contiennent toutes les informations nécessaires au calcul du comportement futur du système.

3

Définition

Etat d’un système séquentiel

 On

définit l’état futur du système en fonction de son état courant et des

entrées : état futur = F(état présent, entrées) 4

Définition

Etat d’un système séquentiel

 Un

système séquentiel synchrone voit son état synchronisé par un signal d’horloge  Le nombre d’états d’un système synchrone est borné par 2 n , où n est le nombre d’éléments de mémorisation 5

Définition

Machine à états

 Une

machine à états (M.A.E.) est un système dynamique, qui peut se trouver, à chaque instant, dans une position parmi un nombre fini de positions possibles. Elle parcourt des cycles, en changeant éventuellement d’état lors des transitions actives de l’horloge. 6

Types de machines d’états  Suivant

la façon dont les sorties dépendent des états et des commandes, on distingue deux types de machines à états: les machines de Moore et les machines de Mealy.

7

Types de machines d’états Posons : X : le vecteur d’entrée S : le vecteur d’état Y : le vecteur de sortie  On définit les types de machines suivants :  machines de Moore: les sorties ne dépendent que de l’état actuel : Y = f(S)  machines de Mealy les sorties dépendent de l’état actuel et des entrées Y = f(S, X) 

8

Machine de Moore: Y = f(S) Dans une machine de Moore, la sortie ne dépend que de l’état de la machine : elle ne change que lors d’un changement d’état.  Les sorties sont synchrones avec les transitions d’état et les fronts d’horloge. 

9

Machine de Moore: Y = f(S) X S futur

S

Y État futur = F (état présent, entrées) Sortie = G (état présent) Y= G(s) 10

Machine de Mealy Mealy:: Y = f(S,X)  Dans

une machine de Mealy, la sortie est calculée en fonction de l’état présent et de la valeur présente des entrées : les sorties peuvent changer immédiatement après un changement des entrées, indépendamment de l’horloge. 11

Machine de Mealy Mealy:: Y = f(S,X) X S futur

S

Y État futur = F (état présent, entrées) Sortie = G (état présent, entrées) Y= G(S,X) 12

Moore: exemple

13

Moore: équations

14

Moore :

Mode de représentation: Table des états Table des états de la machine de Moore :  Chaque case indique l’état futur  Une colonne supplémentaire indique la sortie en fonction de l’état courant  Pour notre exemple : 

15

Moore : Mode de représentation : Graphe des états

• Chaque état est représenté par un noeud • Chaque changement d’état est représenté par une flèche reliant l’état courant à l’état futur • Les conditions associées aux changements d’états sont indiquées sur les flèches • La valeur de la sortie est indiquée dans l’état

Structure du graphe d'état de Moore 16

Moore : Mode de représentation : Graphe des états Exemple :

17

Moore : Mode de représentation : Chronogramme

• Les états changent sur les fronts montants de l’horloge • La sortie change également sur les fronts montants

18

Mealy:: exemple Mealy

19

Mealy:: équations Mealy

20

Mealy :

Mode de représentation: Table des états  Une

table à 2 dimensions  Chaque ligne représente un état présent  Chaque colonne représente une combinaison des entrées  Chaque case indique l’état futur et la sortie, séparés par un / 21

Mealy :

Mode de représentation: Table des états 

Dans notre exemple :

22

Mealy : Mode de représentation : Graphe des états

• Chaque état est représenté par un noeud • Chaque changement d’état est représenté par une flèche reliant l’état courant à l’état futur • Les conditions associées aux changements d’états sont indiquées sur les flèches, suivies de la valeur de la sortie

Structure du graphe d'état de Mealy 23

Mealy : Mode de représentation : Graphe des états

Exemple :

24

Mealy : Mode de représentation : Chronogramme

• Les états changent sur les fronts montants de l’horloge • La sortie peut changer n’importe quand

25