# TD4 VHDL Logique Sequentielle

Dans ce chapitre nous présentons toute la logique séquentielle appelée non régulière.
* Définition
* On appelle logique séquentielle non régulière toute logique séquentielle pour laquelle le calcul de l'état futur en fonction de l'état présent ne peut pas se faire avec des opérateurs simples (sur plusieurs bits).
Le lecteur de ce chapitre devra essayer d'appréhender les techniques communes avec tout ce qui a été présenté au chapitre précédent, surtout en ce qui concerne le problème des initialisations.
L'objectif de ce chapitre est d'introduire dans l'ordre :
* les graphes d'évolution
* les graphes d'états
* les GRAFCETs
Il s'agit de trois formalismes différents pour spécifier le séquentiel.

## Programmation des graphes d'évolutions

Nous allons nous intéresser dans cette section à la programmation des graphes d'évolutions en VHDL. C'est un sujet que nous avons abordé en TD 1 mais qu'il est important d'approfondir maintenant.
Pour illustrer cette partie, nous allons prendre un exemple particulier : le réveil.
Dans la partie droite de la figure ci-dessus, vous pouvez apercevoir le diagramme d'évolution du réveil qui sera utilisé comme exemple par la suite.
Principe de fonctionnement du réveil : à partir de "Off", "key"=1 arme le réveil. Si "trip" passe à 1 (c'est à dire que l'heure courante devient égale à l'heure de réveil) le réveil passe en "ringing" et sonne. "trip" ne reste pas très longtemps à un (1 seconde). Son retour à 0 ne suffit pas à arrêter la sonnerie. Seul le passage de "key" à 0 peut l'arrêter.

### Les équations de récurrences

Il est possible d'obtenir à partir d'un graphe d'évolution une table état présent / état futur. Cet exemple traite le cas où il n'y a aucune entrée. Dans le cas où les transitions sont conditionnées par des entrées il faut ajouter celles-ci dans la partie gauche du tableau... ce qui rend très vite le travail fastidieux. C'est pour cela que l'on va commencer par montrer comment éviter ce travail en déportant cette étude plus loin. Une autre façon de dire les choses : nous vous conseillons fortement de commencer votre étude par le style « case when » ci-après.

### Les graphes d'évolutions et le style « case when »

On rappelle encore une fois que le style « case when » permet de ne pas chercher les équations de récurrences. Mais comme nos diagrammes d'évolutions se sont compliqués (par l'ajout d'étiquettes sur les transitions), il nous faudra ajouter des "if then". Cela est tellement intuitif que nous passons directement aux exemples. Présentons

#### Programmation sans initialisation

Le principe consiste à déclarer d'abord un type énuméré avec une définition symbolique de chacun des états (ici Armed, Off, Ringing) :
Ensuite dans un « case when » on détaillera toutes les transitions possibles comme montré ci-dessous dans le cas où l'on ne s'intéresse pas à une initialisation :
L'idée générale est donc d'utiliser un « case » sur les états avec des « if » pour gérer l'ensemble des transitions.
Voici le programme complet du réveil en utilisant le type BIT :
Intéressez-vous à la seule partie séquentielle pour le moment.
Le même programme complet du réveil en utilisant le type STD_LOGIC est donné plus loin.

#### Version du réveil avec deux process

Avant de changer de sujet, rappelons qu'il est possible d'utiliser un style comportant deux process pour décrire un graphe d'états (seuls les process de la partie séquentielle sont comptés). Voici donc la version du réveil avec deux process :
Le process de la partie combinatoire n'est pas compté car il n'est pas obligatoire comme cela est montré plus loin.

### Ajout d'une initialisation
#### Initialisation synchrone

L'ajout d'une initialisation synchrone se fait dans le "if clk'event" comme indiqué ci-dessous :

#### Initialisation asynchrone

Comme pour les compteurs, l'initialisation asynchrone se fait elle, avant le "if clk'event" sans oublier d'ajouter l'entrée d'initialisation (ici reset) dans la liste des sensibilités du « process » correspondant.
Notez en ligne 5 l'utilisation d'un "elsif" en lieu et place d'un "else if" dont l'intérêt est d'économiser un "end if".

### Autre façon de gérer le combinatoire

Gérer le combinatoire avec un "IF" est coûteux (en nombre de lignes) : cela nécessite absolument l'utilisation d'un process. Cela alourdit donc le programme avec le "PROCESS" et sa liste de sensibilité ainsi que le "END PROCESS" correspondant. Une autre manière de faire est d'utiliser la structure "WHEN ELSE" :
sera très avantageusement remplacé par :

### Un automatisme de sonnerie de réveil complet avec des std_logic et une entrée de validation

L'utilisation du type bit dans les exemples précédents limite largement son utilisation car il est ipossible de câbler ensemble des bit et des std_logic. Nous allons donc utiliser des std_logic dans le code ci-dessous.
Nous lui avons ajouté une entrée de validation "ena". Si vous n'en n'avez pas besoin, vous pouvez la relier à '1'. Elle est utile lorsqu'on désire utiliser cet automatisme de sonnerie de réveil dans les règles de l'art, c'est à dire avec l'horloge du FPGA. Si vous voulez vous affranchir des rebonds des boutons il vous faut ralentir l'horloge. les meilleures pratiques dans FPGA pour réaliser cela consistent à réaliser un tick, c'est à dire un signal qui vaut un pendant une seule période d'horloge.
Voici donc le code complet de l'automatisme de sonnerie de réveil :

### Le codage des états

La programmation des états nécessite une déclaration symbolique comme on peut voir ci-dessous :
Quand la synthèse sera demandée plusieurs solutions peuvent se présenter suivant le codage des états. Une telle déclaration débouchera sur un codage Armed=00, Off=01 et Ringing=10.
On peut modifier ce codage à l'aide de deux attributs différents : enum_encoding et state_encoding. Enum_encoding est normalisé par le standard IEEE 1076.6.
La directive state_encoding spécifie la nature du code interne pour les valeurs d'un type énuméré.
Les valeurs légales de la directive state_encoding sont sequential, one_hot_zero, one_hot_one, and gray.
* sequential : on code en binaire au fur et à mesure de l'énumération avec autant de bits que nécessaire.
* one_hot_zero : on code la première valeur par zéro, puis le reste en utilisant à chaque fois un seul un : N états nécessiteront donc N-1 bits.
* one_hot_one : idem à one_hot_zero sauf que l'on n'utilise pas le code zéro. N états nécessiteront donc N bits.
* Gray : les états suivent un code de GRAY.
Exemples :
* avec codage one hot zeo
* avec codage de type Gray

### Exercice 1

Concevez une machine d'état capable de détecter la présence de la sequence « 1111010 ».
1°) Dessiner le graphe d'évolution.
2°) Quel code des états sur combien de bits proposez vous
3°) Réaliser le programme VHDL correspondant.
1°)
Certains aspects de cet automate demandent réflexion.
2°) Les méthodes d'optimisation du codage d'états ne sont pas enseignées (Huffman). Mais il existe une méthode heuristique pour coder les états qui consiste à mettre le plus de zéros possible sur les états qui ont beaucoup de flèches de transitions qui s'y terminent. On peut constater qu'un codage en binaire naturel à partir de l'état de gauche sur la figure ci-dessus convient très bien (c'est un pur hasard). L'état s0 de gauche est codé "000" et cela tombe bien c'est celui qui a plus de flèches qui y arrivent (6 en tout)

### Utilisation du tableau des états pour obtenir les équations de récurrences

Une fois le choix du codage des états réalisé, il n'est pas difficile de réaliser le tableau état présent/état futur pour en déduire les équations de récurrences.
Pour l'exemple du réveil, déjà présenté, et rappelé ci-dessus, on choisit le code :
Il n'est pas très difficile d'en déduire la table de transition :

#### Table de transitions du réveil

| Entrées | Entrées | Sortie |
| Etat Présent | Conditions | Etat futur |
| q1 q0 | key trip | q1+ q0+ |
| 0 0 | 0 X | 0 0 |
| 0 0 | 1 X | 0 1 |
| 0 1 | 1 0 | 0 1 |
| 0 1 | 0 X | 0 0 |
| 0 1 | X 1 | 1 0 |
| 1 0 | 0 X | 1 0 |
| 1 0 | 1 X | 0 0 |
| 1 1 | X X | 0 0 |
Remarque : Cette table est ambiguë : cette ambiguité était déjà présente dans le graphe d'évolution qui ne dit pas ce qui se passe si on est dans l'état "armed" et que key=0 avec aussi trip=1 ! Il faut choisir une priorité pour la coder !

#### Table de transitions du réveil avec priorité

| Entrées | Entrées | Sortie |
| Etat Présent | Conditions | Etat futur |
| q1 q0 | key trip | q1+ q0+ |
| 0 0 | 0 X | 0 0 |
| 0 0 | 1 X | 0 1 |
| 0 1 | 1 0 | 0 1 |
| 0 1 | 0 X | 0 0 |
| 0 1 | 1 1 | 1 0 |
| 1 0 | 0 X | 1 0 |
| 1 0 | 1 X | 0 0 |
| 1 1 | X X | 0 0 |
Les deux équations de récurrences s'en déduisent immédiatement.

### Exercice 2

Active-FSM est un outil ancien présent avec le compilateur warp. Il permet de faire un dessin d'un graphe d'évolution et de générer la programme VHDL entier correspondant.
Un étudiant a utilisé active-FSM et généré un programme VHDL correspondant au dessin ci-contre. Puis il a réalisé un projet pour compiler et obtenu le fichier de rapport ci-dessous.
1°) Remplir le tableau état présent état futur ci-contre en choisissant comme état futur de $(11)_{2}$ l'état 00.
2°) Trouver les équations de récurrences correspondantes.
3°) Comparer au fichier rapport. Pourquoi n'y a-t-il pas d'équation combinatoire de sortie ? Où est la sortie ?
Pour remplir le tableau, vous utiliserez naturellement les équations de récurrence du fichier rapport. Dans ce fichier, la notation truc.D signifie ${truc}^{+}$ et truc.Q signifie truc (état présent). On notera sregSBV_0 tout simplement s0.

#### Table de transitions

| Entrées | Entrées | Sortie |
| Etat Présent | Conditions | Etat futur |
| s s0 | e0 e1 Init | s+ s0+ |
| 0 0 | 0 X 0 | |
| 0 0 | 1 X 0 | |
| 0 1 | 0 X 0 | |
| 0 1 | 1 X 0 | |
| 1 0 | 0 X 0 | |
| 1 0 | 1 X 0 | |
| 1 1 | 1 X 0 | |
Fichier rapport
1°) Table de transitions remplie tout simplement à partir de notre diagramme d'évolution. Rien de compliqué en somme !
2°) ${{s_{0}}^{+}}={\bar {s}}\cdot {\bar {s}}_{0}\cdot e_{0}\cdot {\overline {Init}}+{\bar {s}}\cdot s_{0}\cdot e_{1}\cdot {\overline {Init}}$
${{s_{1}}^{+}}=s\cdot {\bar {s}}_{0}\cdot {\bar {e}}_{0}\cdot {\overline {Init}}+{\bar {s}}\cdot s_{0}\cdot e_{1}\cdot {\overline {Init}}$
3°) La sortie s n'est pas réalisée avec une sortie combinatoire mais directement avec le poids fort des états Cela est visible sur le brochage du composant qui montre deux sorties en broche 15 pour s justement et en broche 16 pour l'autre bit servant au code des états.
Le fichier rapport donne exactement les mêmes équations de récurrences avec des variables aux noms bizarres. Rappelez-vous que la notation truc.D signifie entrée de la bascule D, ce que l'on appelle état futur et notons ${truc}^{+}$
Un ensemble d'exemples utilisant des graphes d'évolutions est présenté en TD5 :VHDL et CAO.

## Programmation de graphes d'états

Nous avons déjà eu l'occasion d'introduire ce problème en logique, dans le cours Logique séquentielle.
Ce qui est traité dans cette section est très ressemblant à ce qui est traité dans la section précédente... mais les graphes d'états sont un pas de plus vers les GRAFCETs qui sont tout simplement l'objectif de ce chapitre.
Une transition barrée est dite réceptive (comme avec les GRAFCETs) et, comme l'indique l'équivalence du dessin ci-dessus, elle sous entend que si la réceptivité est fausse on reste dans le même état.
Remarque : Il est présenté dans le cours WIKIVERSITE logique séquentielle, particulièrement dans le chapitre Description par graphe d'états une méthode qui permet de passer d'un graphe d'état à des équations de récurrences.

### Utilisation du style "case when"

Il est très facile de transformer le graphe d'évolution du réveil en graphe d'états. En comparant avec le programme donné en VHDL pour ce même réveil il n'est pas difficile de tirer quelques règles de codage.
Pour ne pas donner deux fois le même programme, nous donnons le programme du réveil légèrement modifié pour remplacer les "bit" par des "std_logic".
On vous laisse comparer la partie graphe d'évolution de la figure avec le programme pour en déduire quelques règles pour réaliser votre code.

### Les forçages synchrones et asynchrones

Il existe deux façons pour initialiser en utilisant les fronts d'horloge (synchrone) ou non (asynchrone). La technique de programmation est très similaire à celle des compteurs du TD précédent.

#### Forçage asynchrone

Rappel : Un forçage asynchrone est un forçage pris en compte même si aucun front d'horloge est envoyé.
La partie commentée avec par "--ici le synchrone" désigne aussi bien un "case when" que des équations de récurrences.

#### Forçage synchrone

L'obtention des équations de récurrences par les techniques classiques décrites dans le cours de logique séquentielle donne automatiquement les forçages synchrones à l'aide de l'entrée que l'on a appelée Init.

##### Première façon

On résume ici ce qui a été obtenu dans le cours de logique séquentielle.
Mais ce n'est pas la seule et unique façon de procéder.

##### Deuxième façon

On peut retirer tout ce qui est lié à l'entrée "Init" des équations et transformer le programme ainsi :
Cette technique nécessite de connaître le code de l'état initial (ici "0000") ou au moins son nom symbolique.

## Programmation des GRAFCETs en VHDL

Vous pouvez lire le WIKI GRAFCET ou les livres GRAFCET (niveau 8) et Automatisme : norme 1131-3 et GRAFCET (niveau 13) de la Wikiversité avant d'aborder ce chapitre.
Les GRAFCET se décrivent en VHDL relativement facilement en utilisant la même technique que la section précédente sur les graphes d'états. On rappelle que la différence entre les deux est simplement qu'en aucun cas il ne peut y avoir deux jetons dans un graphe d'évolution alors que cela est parfaitement autorisé pour un GRAFCET. C'est pour cela que l'on parle d'étape dans un GRAFCET et d'état dans le graphe d'évolution. Lorsque plusieurs jetons se trouvent dans un GRAFCET, on parle de parallélisme. En voici un exemple simple :
Dans le GRAFCET de la figure, quitter l'étape 10 active les deux étapes 21 et 30.

### Obtenir les équations de récurrences

La méthode simple consiste à écrire pour chacune des étapes les conditions d'activations (notées $AC_{i}$) et les conditions de désactivations (notées $D_{i}$).
* Définition
* La condition d'activation $AC_{i}$ s'obtient en se posant la question : comment activer l'étape i si elle n'est pas active ?
* La condition de désactivation s'obtient quant à elle en se posant la question : quelles sont les conditions nécessaires pour que le jeton quitte l'étape i s'il est dedans ?
Avec ces conditions on va pouvoir former les équations de récurrences :
* Pour la ou les étapes initiales : $x_{i}^{+}=AC_{i}+{\overline {D_{i}}}\cdot x_{i}+Init$
* Pour les étapes non initiales : $x_{i}^{+}=(AC_{i}+{\overline {D_{i}}}\cdot x_{i})\cdot {\overline {Init}}$
L'indice i parcourant toutes les étapes, il y a autant d'équations de récurrences que d'étapes. En terme matériel, cela signifie que l'on utilisera une bascule D par étape. Bien sûr, un codage des états permet de faire des économies de ce côté là mais rappelez-vous qu'à ce point on a que des étapes et pas encore des états.
Nous allons partir d'un GRAFCET assez général pour réaliser un exemple complet.
Prenez un peu de temps pour relire l'équation de AC1 et celle de D3 qui prennent en compte le parallélisme. C'est le seul type de situation qui diffère du graphe d'état.
Voici le programme VHDL correspondant :
pour lequel on a utilisé parfois, les lois de De Morgan sur les équations de récurrences présentées en commentaires.

### Codage des états pour un GRAFCET

Transformer un GRAFCET en graphe d'états est toujours possible. L'intérêt de la chose est qu'une fois le graphe d'états obtenu, il est possible de compter ses états. L'exemple de la section précédente nous semble être un bon point de départ :
Cette figure transforme un GRAFCET à gauche en un graphe d'état à droite. La notation {2,4} dans un état indique que l'état correspond à l'étape 2 et l'étape 4 actives (chacune avec son jeton) dans le GRAFCET.
* Définition
* On dit que l'état {2,4} correspond au marquage de l'étape 2 et de l'étape 4. Tout marquage doit être accessible pour être compté comme un état. Par exemple le marquage symbolisé par {1,2,4} n'est pas accessible, c'est à dire qu'il n'existe aucune séquence sur les entrées qui amène le GRAFCET de son état initial vers ce marquage.
Dans cet exemple vous obtenez un graphe d'états qui comporte 5 états pour un GRAFCET qui comporte 5 étapes. En principe, le graphe d'états comporte plus d'états que le GRAFCET comporte d'étapes. Ceci n'est pas une règle absolue et tous les cas peuvent se rencontrer. Il n'empêche que d'une certaine manière, c'est à cause de cette propriété que l'on a inventé le GRAFCET : décrire le plus simplement possible un système qui peut être complexe du point de vue de sa description par graphe d'états.
Pour coder les états vous devez utiliser la relation $2^{M-1}$ < N (états) $<=2^{M}$ qui vous donne le nombre de bits M nécessaire au code.
Par exemple, nos 5 états nécessitent trois bits de code.

### Programmation des GRAFCETs avec "case when"

La programmation de GRAFCETs avec le style "case when" de VHDL nécessite de coder les états. Cela signifie donc qu'il faut transformer le GRAFCET en graphe d'états. En effet, avec le style "case when", vous écrivez derrière le when une représentation (symbolique ou pas) d'un état, ainsi, le graphe d'états est inévitable.
Si vous avez votre graphe d'état, reportez vous à la section correspondante dans ce chapitre pour apprendre à coder avec le style correspondant.

#### Codage des états et équations de récurrences

Il est possible de partir d'un GRAFCET, de le transformer en graphe d'état comme déjà présenté. Une fois que l'on connait le nombre d'états, on peut choisir un code des états et transformer ensuite le tout en équations de récurrences. Voici un exemple :
Ce qui est nouveau est le tableau complètement à droite d'assignation des états à des codes. Ce tableau permet de remplir ensuite le tableau état présent état futur avec ces codes, pour en déduire finalement les équations de récurrences. Il est facile de tirer de cette figure :
* $Q_{0}^{+}={\overline {Q_{2}}}\cdot {\overline {Q_{1}}}\cdot {\overline {Q_{0}}}\cdot e_{1}+{\overline {Q_{2}}}\cdot {\overline {Q_{1}}}\cdot Q_{0}\cdot {\overline {e_{2}}}\cdot {\overline {e_{3}}}+{\overline {Q_{2}}}\cdot {\overline {Q_{1}}}\cdot Q_{0}\cdot e_{3}\cdot {\overline {e_{2}}}+{\overline {Q_{2}}}\cdot Q_{1}\cdot Q_{0}\cdot {\overline {e_{2}}}$
* $Q_{1}^{+}={\overline {Q_{2}}}\cdot {\overline {Q_{1}}}\cdot Q_{0}\cdot e_{2}\cdot {\overline {e_{3}}}+{\overline {Q_{2}}}\cdot Q_{1}\cdot {\overline {Q_{0}}}\cdot {\overline {e_{3}}}+{\overline {Q_{2}}}\cdot Q_{1}\cdot Q_{0}\cdot {\overline {e_{2}}}$
* $Q_{2}^{+}={\overline {Q_{2}}}\cdot {\overline {Q_{1}}}\cdot Q_{0}\cdot e_{3}\cdot e_{2}+{\overline {Q_{2}}}\cdot Q_{1}\cdot {\overline {Q_{0}}}\cdot e_{3}+{\overline {Q_{2}}}\cdot Q_{1}\cdot Q_{0}\cdot e_{2}+Q_{2}\cdot {\overline {Q_{1}}}\cdot {\overline {Q_{0}}}\cdot {\overline {e_{4}}}$
Remarque : la complexité des équations que l'on obtient est assez dépendante du code choisi pour les états. Il existe des méthodes pour minimiser le nombre d'états (Paull Unger) et choisir le code optimal (Huffman) mais on ne les présente pas ici. Une méthode heuristique pour coder les états, déjà présentée dans la correction de l'exercice 1, consiste à mettre le plus de zéros possible sur les états qui ont le plus de flèches de transitions qui y aboutissent. Ici, l'état {3,5} a trois transitions qui y aboutissent : il aurait donc été très judicieux de le coder "000" au lieu de "100" !!!

### Exercice 3

Si l'on intervertit dans l'exemple donné le code de {3,5} avec celui de {1}, quelles sont les équations de récurrences qui se simplifient ?
C'est Q2+ qui se simplifie : il comportera deux termes au lieu de quatre, comme quoi un bon code simplifie le matériel !

### Et pour finir, le problème des actions

Les actions des GRAFCETs ont été délaissées jusqu'à présent. Si vous savez les gérer avec les graphes d'états, il n'y a aucune différence pour le GRAFCET. Il s'agit d'équations combinatoires qui sont généralement très simples et se compliquent un peu si l'on code les états de manière compacte.
Nous avons présenté ce problème tout au long de ce chapitre, soit en utilisant un "IF" soit en utilisant une structure "WHEN ELSE". C'est la deuxième solution que nous préférons.

## Voir aussi

La conception autour de séquenceurs est largement repris dans le chapitre suivant.