# Logique séquentielle/Description par graphe d'états
## Graphe d'états

Un graphe d'états est une suite d'états et de transitions réceptives. Pour ceux qui auraient une connaissance du GRAFCET on parle ici d'état et non d'étape. Les évolutions seront représentées par un jeton (et un seul) qui se déplace d'état en état.

### États

Même si nous avons déjà rencontré la notion d'état, il est important de se rappeler :
Voici des exemples d'états à droite.
Cette figure représente respectivement un état normal inactif, un état normal actif (on y ajoute un jeton), un état initial inactif (double cercle). Dire qu'on se trouve dans un état se représente donc par un jeton (comme pour les GRAFCETs).

### Transitions

Une transition a toujours été décrite, jusqu'ici, au moyen d'une flèche et d'une éventuelle condition le passage d’un état à un autre : on parle de transition conditionnelle. Une telle transition ne spécifie pas ce qui se passe si la condition est fausse.
Voici une transition réceptive (à droite)
La réceptivité est l'équation booléenne : c’est une valeur booléenne. La signification de cette transition peut être présentée par le dessin ci-contre.
On aperçoit dans cette figure l’intérêt d'une transition réceptive : on retire les transitions d’un état sur lui-même. C’est tout mais c’est le genre de simplification qui peut simplifier grandement un dessin si l’on a plusieurs dizaines d'états.

### Graphe d'états

Un graphe d'états est un graphe pour lequel les états sont reliés les uns aux autres par des transitions. Ce graphe ne possède qu'un seul état initial. Si l’on s'intéresse à l'évolution d’un tel graphe on obtient un seul jeton qui se déplace à travers les états.

## Équations de récurrence

Du point de vue du codage des états, ce que l’on présente maintenant est souvent appelé Code One-shot. Cela signifie, en clair, qu'on utilise une équation de récurrence par état. Le graphe d'états présenté en figure plus loin possède quatre états, il sera donc décrit par quatre équations de récurrence. Comment trouver ces équations de récurrence ?
On cherche pour chacun des états i les conditions d'activation que l’on notera $AC_{i}$ et les désactivations que l’on notera $D_{i}$ puis on écrit une des deux équations ci-dessous suivant le type d'état que l’on a :
${{x_{i}}^{+}}=AC_{i}+{\overline {D_{i}}}\cdot x_{i}+Init$
pour un état initial et
${{x_{i}}^{+}}=(AC_{i}+{\overline {D_{i}}}\cdot x_{i})\cdot {\overline {Init}}$
pour un état normal. Init est une entrée ajoutée destinée à l'initialisation (synchrone ici).
$AC_{i}$
* On appellera condition de désactivation de l'état i et l’on notera $D_{i}$ l'équation combinatoire qui décrit les conditions qui vont faire qu'on va quitter l'état i au prochain front d'horloge en considérant qu'on est dans cet état.
Un exemple sera plus parlant qu'un long discours. Soit le graphe d'états ci-dessous :
Cherchons les conditions d'activation $AC_{i}$ de chacun des états :
* $AC_{1}=x_{3}\cdot e_{4}+x_{4}\cdot e_{3}$
* $AC_{2}=x_{1}\cdot e_{1}$
* $AC_{3}=x_{2}\cdot e_{2}$
* $AC_{4}=x_{1}\cdot {\overline {e_{1}}}$
puis les conditions de désactivation
* $D_{1}=e_{1}+{\overline {e_{1}}}=1$
* $D_{2}=e_{2}$
* $D_{3}=e_{4}$
* $D_{4}=e_{3}$
Les équations de récurrence sont alors :
* ${{x_{1}}^{+}}=AC_{1}+{\overline {D_{1}}}\cdot x_{1}+Init=x_{3}\cdot e_{4}+x_{4}\cdot e_{3}+Init$
* ${{x_{2}}^{+}}=(AC_{2}+{\overline {D_{2}}}\cdot x_{2})\cdot {\overline {Init}}=(x_{1}\cdot e_{1}+{\overline {e_{2}}}\cdot x_{2})\cdot {\overline {Init}}$
* ${{x_{3}}^{+}}=(AC_{3}+{\overline {D_{3}}}\cdot x_{3})\cdot {\overline {Init}}=(x_{2}\cdot e_{2}+{\overline {e_{4}}}\cdot x_{3})\cdot {\overline {Init}}$
* ${{x_{4}}^{+}}=(AC_{4}+{\overline {D_{4}}}\cdot x_{4})\cdot {\overline {Init}}=(x_{1}\cdot {\overline {e_{1}}}+{\overline {e_{3}}}\cdot x_{4})\cdot {\overline {Init}}$

## Équations de sortie

Nous n'avons encore jamais rencontré ce type d'équation.
Les équations de sortie de l'exemple ci-dessus sont donc :
* $a_{1}=x_{1}$
* $a_{2}=x_{1}$
* $a_{3}=x_{3}+x_{4}$
* $a_{4}=x_{2}$

## Implantation

On implante ces équations de récurrence facilement avec des bascules D (voir TD 3). Le schéma comporte deux parties : les équations de récurrence se retrouvent en partie gauche et les équations de sortie se retrouvent en partie droite.
En suivant toutes ces règles, on trouve pour l'exemple ci-dessus le schéma donné maintenant :
Essayez de retrouver les équations de récurrence sur ce schéma ainsi que les équations de sortie : ce travail n’est pas complètement inutile.
Posons-nous la question de savoir comment pourrait-on programmer une PAL à partir des équations.

## Implantation en VHDL

Le programme VHDL est trouvé très facilement quand on a les équations : il suffit de les traduire en VHDL. Les équations de récurrence seront alors dans un "if clk'event …" et du coup dans un process. Le process en question a une liste de sensibilité toute simple : l'horloge. Les équations de sortie ne seront pas dans ce process mes concourantes (à lui). Regardez tout cela das le programme ci-dessous :

## Exercices

* Les technologies