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

Début de la boite de navigation du chapitre

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.

fin de la boite de navigation du chapitre

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

Définition

Un diagramme d'évolution est composé d’un ensemble d'états dessinés par des cercles. On peut étiqueter ces états en code binaire ou avec des noms de notre choix. Ces états sont reliés par des flèches qui représentent des transitions. Ces flèches pourront elles aussi avoir des conditions comme étiquettes. On pourra passer d’un état à un autre que si une flèche de transition le permet : cette transition aura lieu seulement si le bon front d'horloge arrive.

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.

Remarque

Le dernier diagramme d'évolution (à droite) avec un état isolé est à éviter (Hang-Up State). Même si ce genre d'état ne peut pas être atteint, en principe, un évènement extérieur (parasite) peut l'y conduire. On restera alors bloqué dans cet état !

Que représente un diagramme d'évolution ?

Arrivé à ce point vous voyez ce que décrit un diagramme d'évolution mais il reste à comprendre quand a 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.

Propriété

Regardez chaque état d’un diagramme d'évolution comme un état présent. La transition vous indique alors quel sera l'état futur. Un diagramme d'évolution exprime donc une relation entre les états présents et les états futurs et répond à la question : si je suis dans tel état, vers quel état vais-je aller si un front d'horloge arrive ?

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.

Début d’un principe

Principe

Pour trouver un diagramme d'évolution à partir d’un schéma utilisant des bascules D, il faut commencer par donner une valeur aux sorties des bascules D. Cela définit l'état présent. Puis chercher les valeurs des entrées de ces bascules : l’ensemble de ces valeurs constitue l'état futur. En répétant ce travail pour chacune des possibilités sur l'état présent, on trouve le diagramme d'évolution complet.

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

Principe

• L'ensemble des sorties des bascules D correspondent toujours à l'état présent.
• L'ensemble des entrées des bascules D correspondent toujours à l'état futur.

Fin du principe

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

Remarque

La réponse à la question sur la position de l'état présent et de l'état futur pour une bascule est contre-intuitif. Nous insistons un peu. Ceci est probablement lié au fait que l’on est conditionné à un axe des temps qui va de la gauche vers la droite... qui nous laisse mettre le présent à gauche, ce qui est ABSOLUMENT faux.

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 !

Définition

On appelle une équation de récurrence une équation pour laquelle la sortie (il n'y en a qu'une seule dans une équation) se retrouve aussi dans la partie droite de l'équation.

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.

Définition

On appelle table état présent état futur, une table de vérité qui, dans sa partie SI (à gauche) liste tous les états présents possibles, et dans sa partie alors liste tous les états futurs correspondants.

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

Remarque

Prenez le temps de digérer la notion de présent et de futur. N'oubliez pas non plus qu'un jour ou l'autre le futur deviendra présent : c’est ce qui se passera au prochain front d'horloge.

Exercice 2

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

Solution

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:

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

Pourquoi INOUT ?

Les propriétés ci-dessous sont toujours vraies :

• 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.

Vous voyez bien que dans cette histoire, q0 joue à la fois le rôle d'entrée et le rôle d'une sortie ! C’est vrai aussi pour q1.

Exercice 3

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

Solution

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 :

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 <= NOT q0 XOR q1;
  END IF;
  END PROCESS;
END acmpt;