# Logique séquentielle/Diagrammes d'évolution équations de récurrence

Dans ce chapitre, nous allons nous intéresser à la spécification de la logique séquentielle puis à l'établissement des équations correspondantes. Si la spécification de la logique combinatoire est réalisée essentiellement par des tables de vérité, nous utiliserons ici des diagrammes d'évolution.

## Diagrammes d'évolution

Les montages séquentiels simples sont en général spécifiés par un diagramme d'évolution. Il s'agit d’un ensemble d'états (cercles) reliés entre eux par des flèches (transitions).

### Définitions

Pour le moment on va s'intéresser aux diagrammes d'évolution avec transitions sans étiquette (sans condition). Ces diagrammes d'évolution décrivent un automate fini simple.

### Que représente un diagramme d'évolution ?

Arrivé à ce point vous voyez ce que décrit un diagramme d'évolution mais il reste à comprendre quant à lieu la transition si elle n'a pas d'étiquette (même si la réponse a déjà été donnée plus haut) ? Le fait qu'elle n'ait pas d'étiquette veut dire qu'elle n'attend pas une condition spécifique. Pourtant pour se réaliser une transition attend toujours un évènement particulier. Il s'agit d’un front d'horloge. Cette propriété des transitions n'est jamais représentée dans le dessin (du diagramme d'évolution). Il y a toujours des sous-entendus dans un dessin, eh bien en voilà un.
Les diagrammes d'évolution peuvent être aussi variés que ceux présentés ci-dessus. Ils peuvent avoir un ou plusieurs cycles. La suite des états n’est pas forcément dans l’ordre naturel (du comptage). Le nombre d'états N est relié au nombre n de bits (ou de bascules D) : $N=2^{n}$ : eh bien oui, un jour ou l'autre il faudra introduire des bascules D (ou JK) pour réaliser ces diagrammes d'évolution. Pour trouver ce nombre de bits n, étiquetez vos états en binaire : n est alors le nombre de bits nécessaire.
Puisque l’on parle de bascules, nous allons nous intéresser à l'analyse de schémas séquentiels.

### Analyse de schéma séquentiel

On rappelle que la sortie des bascules D s’appelle Q tandis que son entrée s’appelle D.
Il nous faut commenter ce principe tellement il est important. On y définit des notions d'états présents et futurs ainsi que leurs rapports avec les entrées et sorties des bascules D. J'insiste donc avec ce principe :
* L'ensemble des entrées des bascules D correspondent toujours à l'état futur.
Nous assurons le lecteur que s'il garde toujours ce principe en tête il comprendra l'essence du séquentiel.

### Exercice 1

Trouver les diagrammes d'évolution correspondant aux schémas ci-dessous :

## Des diagrammes d'évolution aux équations de récurrence
### La notion d'équation de récurrence

Nous avons déjà eu l’occasion dans un autre projet de présenter la notion d'équation booléenne. Revenons un peu sur cette notion.
Prenons comme exemple $y=a.b+{\bar {c}}$.
Rappelons-nous que le signe "=" n’est pas commutatif contrairement aux mathématiques. C’est d'ailleurs pour cela qu’il est écrit "<=" en VHDL. Ce qui est à gauche du signe "=" est toujours une sortie tandis que tout ce qui est à droite correspond toujours à des entrées. Pour une équation de récurrence, une même variable peut se trouver à la fois à gauche et à droite du signe "=" ! Cela veut dire que cette variable jouera à la fois le rôle de sortie et à la fois le rôle d'entrée… autrement dit qu’il existe un fil reliant une sortie à une entrée… autrement dit qu’il y a des boucles mais tout ceci est une autre histoire.
Vous voulez un exemple : $y=a.b+{\bar {y}}$ que l’on préfère noter $Y=a.b+{\bar {y}}$. Vous ne savez pas ce qu'elle représente. Oui, mais rien qu'en la regardant vous pouvez affirmer que c’est une équation de récurrence !
Il est temps de donner une interprétation à l'équation $Y=a.b+{\bar {y}}$. Il y a une différence entre la variable y et la variable Y : la première représente la valeur présente de la variable booléenne tandis que la deuxième représente la valeur future. Notre équation peut donc se lire : dans le futur la variable y sera soit a.b soit le complément logique de la valeur présente de y. Si c’est trop compliqué, lâchez prise, cette notion de présent et futur sera reprise sous une autre forme.

### Obtention d'une table état présent état futur

Il est facile de construire une table des transitions (état présent ; état futur) à partir d’un diagramme d'évolution. Cela constitue tout simplement la table de vérité de l'équation de récurrence cherchée.
Par exemple pour le premier diagramme d'évolution donné en haut de cette page (celui de gauche que l’on a reproduit ici pour plus de clarté), on trouve :

#### Tableau État présent/État futur

    État présentÉtat futur q1q0Q1Q0 0001 0110 1011 1100

### Obtention des équations de récurrence

Si on veut une forme simplifiée il faudra utiliser un ou plusieurs tableaux de Karnaugh. On peut déduire des tableaux de Karnaugh les équations simplifiées. Ici on obtient :
$Q1=q1\oplus q0$
et
$Q0={\overline {q0}}$
Ces deux équations sont des équations de récurrence.

### Exercice 2

Trouver les équations de récurrence de chacun des diagrammes d'évolution présentés au début de ce TD.
Le deuxième diagramme d'évolution donne les équations :
$q_{0}^{+}={\bar {q}}_{0}$
et
$q_{1}^{+}={\bar {q}}_{0}\oplus q_{1}$
On a utilisé la propriété : au lieu d'inverser la sortie d'un OU exclusif, on inverse une de ses entrées (voir propriétés mathématiques du OU exclusif).

### Encore plus d'entrainement

Si vous voulez être à l'aise avec tous les concepts introduit dans cette section il faut vous entrainer à faire ce que l’on a fait dans l'exercice 2 à l’envers. Partez des équations de récurrence et retrouvez les graphes d'évolution et les tableaux états présents états futurs. Quand vous passerez facilement de l'un à l'autre vous étendrez les notions de présent et futur à ces trois représentations et ce sera le début de la compréhension.

## Des équations de récurrence aux programmes VHDL

Nous allons maintenant apprendre à passer des équations de récurrence aux programmes VHDL. Le compteur ci-dessus s'écrit par exemple en VHDL:
Notez que q0 et q1 sont déclarées en INOUT, ce qui est obligatoire pour des équations de récurrence (en fait il existe d'autres façons de faire).
La variable $q_{0}^{+}$ n'existe pas en VHDL ! Une autre manière de dire les choses, c’est que VHDL ne distingue pas entre l'état présent et l'état futur.
* Lorsque vous écrivez "q0 <= …" en VHDL, q0 est obligatoirement une sortie.
* Lorsque vous écrivez "… <= … q0 …" en VHDL, q0 est obligatoirement une entrée.
* Se trouver à gauche du signe "<=" fait de nous une sortie, tandis que se trouver à droite fait de nous une entrée.

### Exercice 3

Pour chacune des équations de récurrence trouvées à l'exercice 2, trouver le programme VHDL correspondant.
Il vous faut repérer les deux équations de récurrence dans le programme VHDL donné en exemple. Chaque diagramme d'évolution donne une paire d'équations de récurrence que vous traduisez en VHDL. Le deuxième diagramme d'évolution donne le programme :
| Mémoires et bascules | Implantation matérielle avec bascules D et bascules JK |