Logique séquentielle

Simulation des circuits en logique séquentielle

Il est possible de simuler l'essentiel des montages de logique séquentielle avec le logiciel libre Logisim. Les tables de vérités, fournies par la simulation, peuvent être visualisées par gtkwave après création du fichier vcd, ou encore par gnuplot après écriture du fichier de commandes plt. On peut aussi utiliser le logiciel logisim-evolution qui intègre les chronogrammes

Définition

Dans un système séquentiel, on injecte une ou plusieurs sorties en entrée et éventuellement des signaux intermédiaires (Y_k) qui ne correspondent pas aux sorties. Ce qui fait que chaque sortie S_k ou signal intermédiaire Y_k est utilisé en entrée en prenant en compte le temps de propagation dans le circuit Δt.
A chaque instant t, on exprime chaque sortie S_k(t) en fonction des entrées e_m(t), des valeurs précédentes des sorties S_i(t-Δt) et des valeurs précédentes des signaux intermédiaires Y_j(t-Δt).

On peut donc remarquer qu'un système séquentiel ne fonctionne que si le temps de propagation n'est pas nul.

L'analyse des systèmes séquentiels se fait donc en fonction du temps. Pour cela on intègre le temps dans la table de vérité, on utilise également la repésentation temporelle : le diagramme des temps ou chronogramme, ou encore un diagramme d'états.

Les bascules

Les bascules sont des circuits séquentiels qui ne changent d'état que sous certaines conditions.

La bascule RS ou mémoire

Cette bascule comprend une entrée R (reset) de mise à 0 de la sortie et une entrée S (set) de mise à 1 de la sortie.

Principe de fonctionnement avec des portes ET-NON

Table de vérité de la fonction ET-NON (NAND)

a	b	S
0	X	1
X	0	1
1	1	0

Un état 0 sur une des deux entrées donne un 1 en sortie.

Ici on utilise les notations S̅ et R̅ pour indiquer que les entrées sont actives à 0.

Retour au départ précédent suivant

Au démarrage, R̅=0 et S̅=1.

D'après la table de vérité de la fonction NAND, on obtient Q̅=1 que l'on reporte sur l'autre porte NAND qui donne Q=0. La valeur de Q=0 est reportée sur la première NAND, l'autre entrée étant à 0, la sortie reste inchangée. Le système est stable.

R̅=1 et S̅=1

Porte NAND du haut

• Aucun changement en entrée, donc la sortie ne change pas d'état

Porte NAND du bas

• l'autre entrée est à 0, la sortie reste inchangée.

Le système reste dans l'état précédent.

R̅=1 et S̅=0

Porte NAND du haut

• La sortie Q ne change pas immédiatement d'état.
• Q=0 pendant le temps ΔT.

Porte NAND du bas

• La sortie Q̅ ne change pas d'état.

R̅=1 et S̅=0

porte NAND du haut

• Le temps ΔT est écoulé la sortie Q change d'état : Q=1.

Porte NAND du bas

• La sortie Q̅ ne change pas immédiatement d'état.
• Q̅=1 pendant un nouveau temps ΔT.

R̅=1 et S̅=0

porte NAND du haut

• La nouvelle valeur de Q̅ ne change pas l'état de la sortie car S̅=0.

Porte NAND du bas

• Le nouveau temps ΔT est écoulé la sortie Q̅ change d'état : Q̅=0.

R̅=1 et S̅=1

porte NAND du haut

• La sortie ne change pas d'état car l'autre entrée est à 0.

Porte NAND du bas

• La sortie ne change pas d'état car les deux entrées sont toujours à 1.

Le système reste dans l'état précédent.

R̅=0 et S̅=1

porte NAND du haut

• La sortie ne change pas d'état car Q̅ reste à l'état 0.

Porte NAND du bas

• Q̅=0 pendant le temps ΔT.

R̅=0 et S̅=1

porte NAND du haut

• Q=1 pendant un nouveau temps ΔT.

Porte NAND du bas

• Le temps ΔT est écoulé la sortie Q̅ change d'état : Q̅=1.

R̅=0 et S̅=1

porte NAND du haut

• Le nouveau temps ΔT est écoulé la sortie Q change d'état : Q=0.

Porte NAND du bas

• La sortie ne change pas d'état car R̅=0.

R̅=1 et S̅=1

Porte NAND du haut

• Aucun changement en entrée, donc la sortie ne change pas d'état

Porte NAND du bas

• l'autre entrée est à 0, la sortie reste inchangée.

Le système reste dans l'état précédent.

Remarques

• On a positionné R̅ à 0 pour forcer Q à 0. En effet si on avait démarrer la bascule avec S̅=1 et R̅=1, on n'aurait pas pu déterminer l'état des sorties de la bascule RS. Cet état aurait été aléatoire. Ceci signifie qu'il faut toujours initialiser les systèmes séquentiels de façon à déterminer l'état du système au démarage. Cela peut se faire manuellement à l'aide d'un bouton poussoir ou , mieux encore, automatiquement à l'aide d'un circuit RC. La charge du condensateur maintient un état 0 au démarrage pendant un temps suffisant pour forcer l'état du système. Ce qui justifie que les entrées d'initialisation (R ou reset) des systèmes séquentiels sont la plupart du temps actives à 0.
• Il faut remarquer que la combinaison R̅=0 et S̅=0 n'est pas utilisée. En effet, dans ce cas les sorties Q et Q̅ valent toutes les deux 1, ce qui ne correspond pas au fonctionnement standard de la bascule RS. Si ce cas n'apparaît jamais, il n'y a pas de problèmes. Dans le cas contraire, il faut modifier le schéma pour affecter soit un état Q=1 et Q̅=0 ou bien une état Q=0 et Q̅=1. Cette combinaison qui ne doit pas être utilisée est quelque fois identifiée "interdit" dans les tables de vérité.

Définitions et représentations

S	R	Qn
0	0	Qn-1
0	1	0
1	0	1
1	1	X

La table de vérité fait apparaître la notion de temps en exprimant Q_n à l'instant t en fonction de Q_n-1 à l'instant t-ΔT.

X représente l'état inutilisé ou état interdit.

On ne fait plus apparaître la valeur de ΔT sur le diagramme, mais on le prend en compte pour l'analyse du fonctionnement.

Le diagramme d'état est une autre de méthode de représentation des systèmes séquentiels. Chaque cercle représente un état du système, les flèches entre les états représentent les conditions de passage d'une état à un autre. Les flèches qui bouclent sur un état représentent les conditions qui permettent de rester dans le même état.

La bascule RST

C'est une bascule RS avec une entrée de validation T. Ce qui signifie que les valeurs des entrées S et R ne seront prises en comptes uniquement sur l'état actif de T qui est généralement 1.

H actif à 1 H actif à 0

H	S	R	Qn
0	X	X	Qn-1
1	0	0	Qn-1
1	0	1	0
1	1	0	1
1	1	1	X

H	S	R	Qn
1	X	X	Qn-1
0	0	0	Qn-1
0	0	1	0
0	1	0	1
0	1	1	X

Schéma avec des portes NAND

Au démarrage, en l'absence d'initialisation de la bascule à 0, on ne peut pas connaître l'état de la sortie. Cet état est représenté par la partie hachurée qui signifie que l'état de la sortie peut être 0 ou 1. La valeur de la sortie se positionne dès que T est actif et R ou S actif (1).

La bascule D latch

C'est une bascule avec une entrée D qui est tansmise en sortie Q lorsque l'entrée de validation H est active. Elle possède en plus une entrée de mise à 0 (R̅) active à l'état 0 pour répondre au problème d'initialisation des systèmes séquentiels décrit dans les paragraphes précédents.

R̅	H	D	Qn
0	X	X	0
1	0	X	Qn-1
1	1	0	0
1	1	1	1

Au démarrage R̅=0 impose Q=0 quelque soient les valeurs des autres entrées H et D. Ce qui est représenté par la zone hachurée. On représente ici un exemple de démarrage d'un système séquentiel.

Ensuite on a les fonctionnements suivants :

• Lorsque H=1, la sortie Q prend la valeur de D
• Lorsque H=0, la sortie Q garde en mémoire la dernière valeur transmmise.

Il existe une version avec une entrée d'horloge active à 0. On peut s'inspirer du paragraphe précédent (bascule RST) pour comprendre le fonctionnement de la bascule Dlatch dans ce cas.

Le fait que ce soit l'état actif de H qui valide la transmission de l'entrée en sortie, ne permet pas encore de parler de système synchrone. Ce qui fait que ce système est très vivement déconseillé dans les solutions numériques synchrones.

La bascule RST maître-esclave

Il s'agit de la mise en cascade de deux bascules RST, où la première est active sur un état 0 de H et la seconde active sur un état 1 de H.

La première bascule RST est activée lorsque H=0, la deuxième bascule RST est activée lorsque H1=0, c'est à dire H=1.

1. H=0 : les signaux S et R sont transmis respectivement à S₁ et R₁. Comme H1=1, les sorties Q et Q̅ restent inchangées.
2. H=1 : les signaux S₁ et R₁ restent inchangés (mémoire). Comme H1=0, les signaux S₁ et R₁ sont transmis respectivement à Q et Q̅.

Tout se passe comme si les signaux S et R étaient transmis sur une transition 0 vers 1 de H, que l'on nomme front montant de H.

On a réalisé une bascule qui valisent les signaux d'entrée sur un front montant, cette fois-ci, il s'agit d'une technologie synchrone.

La bascule D

La sortie Q prend la valeur de D sur un front montant ou descendant de l'entrée C. L'entrée R, active à 0, est une entrée de mise à 0 asynchrone, c'est à dire que la mise à 0 ne dépend pas de l'horloge.

C actif à 1 C actif à 0

R̅	C	D	Qn
0	X	X	0
1	0	X	Qn-1
1	1	X	Qn-1
1	↑	0	0
1	↑	1	1

R̅	C	D	Qn
0	X	X	0
1	0	X	Qn-1
1	1	X	Qn-1
1	↓	0	0
1	↓	1	1

Dans ce cas on a un front montant

Lorsque l'entrée R̅ est à 1 :
à chaque front montant de C, la sortie Q prend la valeur de D située avant le front d'horloge, comme cela est présenté sur le diagramme avec les flèches qui montrent quelle est la valeur de D qui est transmise à la sortie Q. Ces flèches peuvent être traduites par l'équation : Q(t)=D(t - ΔT) avec 0 < ΔT < T_Clk où T_Clk est la période de l'horloge Clk.

Dans ce cas on a un front descendant

Lorsque l'entrée R̅ est à 1 :
à chaque front descendant de C, la sortie Q prend la valeur de D située avant le front d'horloge, comme cela est présenté sur le diagramme avec les flèches qui montrent quelle est la valeur de D qui est transmise à la sortie Q. Ces flèches peuvent être traduites par l'équation : Q(t)=D(t - ΔT) avec 0 < ΔT < T_Clk où T_Clk est la période de l'horloge Clk.

Le temps pendant lequel la valeur de l'entrée D doit être stable avant le front d'horloge s'appelle le temps de setup (en Anglais set-up time) qui est défini dans la documentation constructeur comme dans le cas du circuit HEF4013.

C'est la bascule la plus utilisée dans les systèmes séquentiels synchrones avec un initialisation (remise à 0) asynchrone.

Exercice

Soit le schéma suivant :

Enoncé Solution

Compléter le diagramme des temps

L'entrée D est relié à la sortie Q̅. Ce qui a pour effet d'inverser la valeur de Q à chaque front montant de l'horloge

Il ne faut pas oublier qu'à chaque impulsion d'horloge, D prend la valeur de Q qui précède le front montant. On applique la relation Q(t)=D(t-ΔT)

La période du signal Q est le double de la période du signal d'horloge. Du point de vue de la fréquence, on a un diviseur de fréquence par 2.

Jeu de bascules

Soit le schéma suivant :

Enoncé Solution

Compléter le diagramme des temps

Il ne faut pas oublier qu'à chaque impulsion d'horloge, D prend la valeur de Q qui précède le front descendant. On applique la relation Q(t)=D(t-ΔT)

On a les équations $S_1=\overline{Q_1}$ et $S_2=Q_2$

Ce qui donne les équations des entrées D des bascules

• $D_1=\overline{Q_1}+Q_2=S_1+S_2$
• $D_2=\overline{Q_1}.\overline{Q_2}=S_1.\overline{S_2}$

1. Au démarrage : Q₁=Q₂=0⇒D₁=D₂=1
2. Clk=↓ : Q₁=1⇒S₁=0 et S₂=1 ⇒ D₁=1 et D₂=0
3. Clk=↓ : S₁=0 et S₂=0 ⇒ D₁=0 et D₂=0
4. Clk=↓ : S₁=0 et S₂=2 : états de démarrage

La bascule JK

La valeur de la sortie Q, dépend de deux entrées J et K, avec J qui positionne la sortie Q à 1 lorsqu'il est à 1 et K qui positionne la sortie Q à 0 lorsqu'il est à 1. Lorsque les deux entrées J et K sont à 1 la sortie Q change d'état à chaque front d'horloge.

H	J	K	Qn
0	X	X	Qn-1
1	X	X	Qn-1
↑	0	0	Qn-1
↑	0	1	0
↑	1	0	1
↑	1	1	Q̅n-1

On a un front montant

Au démarrage la bascule n'est pas initialisée, l'état est aléatoire jusqu'au premier front d'horloge.

• H=↑ : J=0 et K=1 donne Q=0
• H=↑ : J=0 et K=0 donne Q=Q_n-1
• H=↑ : J=1 et K=0 donne Q=1
• H=↑ : J=1 et K=1 donne Q=Q̅_n-1

Cette bascule n'est plus utilisée dans les systèmes séquentiels, elle est remplacée par la bascule D, plus facile à mettre en oeuvre.

Les registres

Un registre est un ensemble de n bascules D qui permet de mémoriser une valeur sur n bits pendant un cycle d'horloge.

A chaque front montant d'horloge, les valeurs des bits du mot d'entrée est transmis en sortie. Cette structure est l'élément de mémorisation des systèmes séquentiels synchrones.

Les registres à décalage

Un registre à décalage est un ensemble de n bascules D qui permet de décaler les bits d'une valeur exprimée sur n bits. Si on affecte un poids binaire aux bits, on réalise un décalage à droite du bit de poids fort vers le bit de poids faible, ou un décalage à gauche du bit de poids faible vers le bit de poids fort. Un décalage à droite de n bits réalise une division par 2ⁿ, un décalage à gauche de n bits réalise une multiplication par 2ⁿ.

Avec remise à 0 Sans remise à 0

On peut observer que la donnée transmise en série apparaît sur les 4 sorties à la quatrième impulsion de l'horloge. On a ainsi réalisé une conversion d'une donnée transmise en série sur des sorties en parallèle. Pour la transmission série, il faut lire la transmission 1101 sur l'entrée D₀ ce qui fait que c'est le bit de poids fort qui est transmis en premier, d'où le résultat 1101 en sortie.

Au démarrage l'entrée R̅ est à 0, ce qui initialise toutes les sorties des bascules à 0.

Au démarrage l'entrée R̅ est à 1, ce qui fait que la valeur des sorties est aléatoire, cet état incertain est représenté par une zone hachurée.

Cet état indéterminé se propage à chaque impulsion d'horloge. Cela montre la nécéssité de toujours initaliser les systèmes séquentiels.

Jeux de registres

Codage de suites binaires

On va utiliser des registres à décalage pour effectuer un codage convolutif qui fait parti de la famille des codes correcteurs. Ces méthodes font appel au corps de Galois à deux élements nommé GF2 (Galois Field 2) en référrence à Evariste Galois. Un autre exemple d'application est présenté dans le calcul du CRC.

Soit le schéma :

Au démarrage les deux bascules sont initialisées à 0, puis à chaque front d'horloge apparaît une nouvelle valeur de X nommée X(k).

X(k) correspond à la suite de valeurs de D₀ à chaque front d'horloge d'indice k (implicitement kT_Clk). Y₁(k) et Y₂(k) sont les valeurs des sorties Y₁ et Y₂ au même instant k.

Demander une suite binaire

Solution [ Voir ]

Générateur de valeurs binaires pseudo-aléatoires

Ce système utilise des registres à décalage avec une fonction logique en rétro-action sur l'entrée. La fonction de rétro-action détermine la suite des valeurs binaires. Le calcul de la fonction de rétro-action fait également appel à la théorie de Galois.

Les compteurs

Un compteur binaire est un système séquentiel qui totalise le nombre d'impulsions d'horloge. Ce total est exprimé en binaire sur les sorties du compteur.

Le compteur asynchrone

Ce compteur est composé de diviseurs par 2 en cascade. Chaque sortie d'un étage est relié à l'entrée d'horloge de l'étage suivant, ce qui a pour effet d'insérer des valeurs intermédiaires entre chaque valeur de comptage.

On obtient donc la suite de valeurs : 0,1,0,2,3,2,0,4,5,0,6,7,6,4,0.

Ce type de compteur n'est plus utilisé, car il propage le temps de propagation de chaque élement du compteur créant ainsi des valeurs intermédiaires erronées.

Le compteur synchrone

Pour faire la synthèse d'un compteur synchrone, on fait une table de vérité qui exprime les valeurs de D en fonction des valeurs de Q.

Q2	Q1	Q0	D2	D1	D0
0	0	0	0	0	1
0	0	1	0	1	0
0	1	0	0	1	1
0	1	1	1	0	0
1	0	0	1	0	1
1	0	1	1	1	0
1	1	0	1	1	1
1	1	1	0	0	0

$D_1=Q_0.\overline{Q_1}+\overline{Q_0}{Q}_1=Q_0\oplus Q_1$

$D_0=\overline{Q_0}$

A partir des équations obtenues, on réalise le schéma avec des bascules D.

Le choix du front descendant est arbitraire, on obtient le même compteur avec des bascules D qui sont activées avec un front montant.

1. A chaque front descendant on évalue Q(t)=D(t - ΔT).
2. On déduit les nouvelles valeurs de D après le front desendant qui reste constant jusqu'au prochain descendant.

Il n'y a aucun changement d'état entre deux fronts descendants.

On remarque que la mise à 0 reste asynchrone, afin de pouvoir initialiser le compteur sans l'horloge.

Un mise à 0 synchrone est utilisée pour remettre le compteur à 0 avant la fin de comptage ce qui est les cas lorsque l'on veut construire un compteur qui passe à 0 avant la fin de comptage. Cette mise à 0 synchrone se trouvait dans certains circuits logiques comme le CD40162, circuits qui ne sont plus utilisés aujourd'hui.

Les équations des entrées D contiennent des OU exclusifs, ce qui nous fait penser aux équations d'un additionneur sur n bits, c'est ce que nous allons vérifier maintenant.

On rappelle les équations d'un bit de poids i dans une addition sur n bits :

On choisit ∀ i, Q_i=a_i et b_i=0, puis R_e0=1; ce qui donne R_s0=Q₀ et R_s1=Q₁Q₀.

On obtient ainsi

• $i=0\Rightarrow D_0=Q_0\oplus R_{e_0}=Q_0\oplus 1=\overline{Q_0}$
• $i=1\Rightarrow D_1=Q_1\oplus R_{e_1}=Q_1\oplus R_{s_0}=Q_1\oplus Q_0$
• $i=2\Rightarrow D_2=Q_2\oplus R_{e_2}=Q_2\oplus R_{s_1}=Q_2\oplus Q_1{Q}_0$

Ces équations sont celles trouvées avec les tableaux de Karnaugh. On peut donc conclure d'un compteur n bits est un additionneur n bits avec Re=1 et B=0 suivi d'un registre n bits comme le montre le schéma.

Cette solution est toujours utilisée, car il n'y a plus de valeurs erronées. La généralisation de cette structure est la machine à états.

Les machines à états

Une machine à états ou automate à états finis (en anglais FSM : Finite State Machine) est la structure de base des tous les systèmes séquentiels syncrhones. Sa structure permet d'implémenter toutes les solutions de logique séquentielle. C'est un des éléments de base des systèmes microprocesseurs.

Il existe plusieurs types de machines à état

• Machine de Moore : les sorties sont définis à partir des valeurs des états à l'aide de fonctions combinatoires.
• Machine de Mealy : les sorties sont définis à partir des valeurs des états et aussi à partir directement à partir des valeurs des entrées (anticipation de certains signaux d'entrées).
• Machine de Medvedev : les sorties sont égales aux entrées (pas de bloc de sortie), c'est la cas du compteur synchrone précédent.

Exemple

On propose de faire la synthèse d'une machine à état à partir du diagramme d'état de la machine avec 3 entrées (m=3), 3 états (n=3) et 4 sorties (k=4).

Entrées			Etat actuel			Etat suivant			Sortie
e2	e1	e0	Q1	Q0	état	D1	D0	état	S3	S2	S1	S0
X	0	X	0	0	S1	0	0	S1	0	0	0	1
X	1	X	0	0	S1	0	1	S2	0	0	0	1
0	X	X	0	1	S2	0	1	S2	1	0	1	0
1	X	X	0	1	S2	1	0	S3	1	0	1	0
X	X	0	1	0	S3	1	0	S3	1	1	0	0
X	X	1	1	0	S3	0	0	S1	1	1	0	0

Les X sont des états indeterminés, qui peuvent prendre 0 ou 1. On pourra les utiliser dans les tableaux de Karnaugh comme des 1 afin de minimiser les groupements

L'objectif est d'exprimer les valeurs de D en fonction des entrées et des sorties Q pour donner les équations d'états, puis les valeurs des sorties S en fonctions des valeurs Q pour donner les équations des sorties.

Le reset, qui n'est pas représenté, a pour fonction de déterminer l'état initial de la machine à état. L'état initial est représenté sur le graphe par un point dans cet exemple.

Tableaux de Karnaugh des états

L'équation de D₁ est :

$D_1=Q_0{e}_2+Q_1\overline{e_0}$

L'équation de D₀ est :

$D_0=\overline{Q_1}.\overline{Q_0}.e_1+Q_0.\overline{e_2}$

Tableaux de Karnaugh des sorties

L'équation de S₃ est

$S_3=Q_1+Q_0$

L'équation de S₂ est

$S_2=Q_1$

L'équation de S₁ est

$S_1=Q_0$

L'équation de S₀ est

$S_0=\overline{Q_1}.\overline{Q_0}$

On a donc défini une machine à états en exprimant les équations d'états qui permettent de calculer l'état suivant ainsi que les équations de sorties en fonctions des valeurs des états

Aujourd'hui la synthèse des systèmes séquentiels est réalisée par des logiciels de conception pour réaliser des circuits numériques en utilisant un langage de haut niveau comme VHDL.