Leçons de niveau 14

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

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Diagrammes d'évolution équations de récurrence
Icône de la faculté
Chapitre no 2
Leçon : Logique séquentielle
Chap. préc. :Mémoires et bascules
Chap. suiv. :Implantation matérielle avec bascules D et bascules JK
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Logique séquentielle : Diagrammes d'évolution équations de récurrence
Logique séquentielle/Diagrammes d'évolution équations de récurrence
 », n'a pu être restituée correctement ci-dessus.

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'évolutions.

Diagrammes d'évolutions[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]


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

Td2bfig1.png


Que représente un diagramme d'évolution ?[modifier | modifier le wikicode]

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'évolutions 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) :  : 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[modifier | modifier le wikicode]

On rappelle que la sortie des bascules D s’appelle Q tandis que son entrée s’appelle D.

Début d’un principe
Fin du principe

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 :

Début d’un principe
Fin du principe

Nous assurons le lecteur que s'il garde toujours ce principe en tête il comprendra l'essence du séquentiel.


Exercice 1[modifier | modifier le wikicode]

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

Td2bfig2.png

Des diagrammes d'évolutions aux équations de récurrences[modifier | modifier le wikicode]

La notion d'équation de récurrence[modifier | modifier le wikicode]

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 .

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 : que l’on préfère noter . 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 . 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[modifier | modifier le wikicode]

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.


Diagramme d'évolution de départ

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
q1 q0 Q1 Q0
0 0 0 1
0 1 1 0
1 0 1 1
1 1 0 0

Obtention des équations de récurrences[modifier | modifier le wikicode]

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 :

et

Ces deux équations sont des équations de récurrences.


Exercice 2[modifier | modifier le wikicode]

Trouver les équations de récurrence de chacun des diagrammes d'évolution présentés au début de ce TD.

Encore plus d'entrainement[modifier | modifier le wikicode]

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écurrences 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[modifier | modifier le wikicode]

Nous allons maintenant apprendre à passer des équations de récurrence aux programmes VHDL. Le compteur ci-dessus s'écrit par exemple en VHDL:

ENTITY cmpt IS PORT (
clk: IN BIT;
q0,q1: INOUT BIT);
END cmpt;
ARCHITECTURE acmpt OF cmpt IS
BEGIN
  PROCESS (clk) BEGIN -- ou cmpt:PROCESS (clk) BEGIN
  IF (clk'EVENT AND clk='1') THEN
      q0 <= NOT q0;
      q1 <= q0 XOR q1;
  END IF;
  END PROCESS;
END acmpt;

Notez que q0 et q1 sont déclarées en INOUT, ce qui est obligatoire pour des équations de récurrences (en fait il existe d'autres façons de faire).

La variable 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.

Exercice 3[modifier | modifier le wikicode]

Pour chacune des équations de récurrence trouvées à l'exercice 2, trouver le programme VHDL correspondant.