Chapitre 3 : Conception avancée de
logique séquentielle
Électronique numérique avancée
I. Introduction à la logique séquentielle
La logique séquentielle repose sur des éléments de mémoire
comme des bascule D (flip-flops), bascule JK, bascule SR, et les
registres. Ces éléments permettent au circuit de mémoriser des
états ou de fonctionner en fonction d'un signal d'horloge.
Logique séquentielle synchrone : Les changements d'état se
produisent en synchronisation avec un signal d'horloge.
Logique séquentielle asynchrone : Les changements d'état se
produisent immédiatement en fonction des transitions des entrées,
sans horloge.
Ces éléments de mémoire sont principalement :
Bascule SR : Gère des états de "Set" (mise à 1) et "Reset" (mise à
0).
Le bascule RS Asynchrone à base des portes NOR :
Table de vérité :
Tableau de Karnaugh : Equation logique de sortie :
Le bascule RS Asynchrone à base des portes NAND :
Table de Vérité :
Tableau de Karnaugh : Equation logique de sortie :
Table de vérité :
Bascule RSH :
La bascule RSH est une bascule
synchronisée par un signal
d’horloge H. Les entées et de la
bascule ne sont prises en compte
que lorsque l’horloge est active :
Symbole : Logigramme avec des NAND :
Base de toutes les bascules
Bascule D :
- Flip-Flop D : Stocke un bit de donnée en fonction d'une entrée et
d'un signal d'horloge.
-La D-latch : est une bascule RSH pour laquelle on n’a conservé que
les deux combinaisons ( 1) et (1 ). La D-latch a une seule entrée,
nommée D.
La donnée D est copiée dans la bascule lorsque l’horloge passe de 1 à
0. Elle y est mémorisée jusqu’à ce que l’horloge redevienne active.
Symbole :
Table de vérité :
Bascules J-K :
Les bascules JK sont plus polyvalentes que les basculent RS, puisque
l’état indéterminé est remplacé par un état complémenté, elles n’ont
pas donc d’état ambigu
La bascule JK synchrone est obtenue à partir d'une bascule RSH dont
les sorties sont rebouclées sur les entrées. Ceci permet d'éliminer
l'état indéterminé.
Logigramme avec des NAND : Table de vérité :
D’après cette table de vérité, nous remarquons que les 3 premières
lignes correspondent bien à une bascule RS mais la dernière ligne
introduit un mode supplémentaire qui sera très utilisé pour réaliser les
compteurs synchrones que nous verrons plus loin.
Symbole :
bascule JK synchronisée sur front montant :
bascule JK synchronisée sur front descend :
II. SYSTEMES SEQUENTIELS
1. Définition : Les systèmes séquentiels peuvent être différenciés en
fonction de leur mode de fonctionnement qui peut être
synchrone ou asynchrone:
Dans le mode synchrone, les éléments de mémorisation sont des
bascules. Les modifications d'état du système ne peuvent donc
intervenir qu'à des instants très précis déterminés par des
signaux d'horloge.
Dans le mode asynchrone, la fonction de mémorisation est réalisée
par de simples boucles de rétroaction. L'évolution des états ne
dépend donc que des modifications intervenant sur les entrées Ei
de la machine.
Comme illustré sur les Figures ci-dessous , ces systèmes séquentiels
peuvent donc être représentés par deux modèles différents :
système séquentiel synchrone système séquentiel asynchrone
Ei : les entrées de la machine
Si : les sorties de la machine
Qi : les états
2. Les machines à nombres finis d’états :
2.1. Définition
Une machine à états (M.A.E.) en anglais Finite State Machine (F.S.M.)
est un système dynamique, qui peut se trouver, à chaque instant, dans
une position parmi un nombre fini de positions possibles. Elle parcourt
des cycles, en changeant éventuellement d’état lors des transitions
actives de l’horloge. L’architecture générale d’une machine à état est
présentée ci-dessous.
2.2. Architectures des machines
Suivant la façon dont les sorties dépendent des états et des commandes,
on distingue deux types de machines à états: les machines de Moore et
les machines de Mealy. Dans les premières les sorties ne dépendent que
de l’état actuel, pour les secondes les sorties dépendent de l’état actuel
et des entrées.
a. Les machines de Moore
Dans une machine de Moore, la sortie ne dépend que de l’état de la
machine : elle ne change que lors d’un changement d’état. Les
sorties sont synchrones avec les transitions d’état et les fronts
d’horloge. Prochain état = F (état présent, entrées)
Sortie = G (état présent)
Représentation de la machine de Moore
b. Les machines de Mealy
Dans une machine de Mealy, la sortie est calculée en fonction de
l’état présent et de la valeur présente des entrées : les sorties peuvent
changer immédiatement après un changement des entrées,
indépendamment de l’horloge. Prochain état = F (état présent, entrées)
Sortie = G (état présent, entrées)
Représentation de la machine de Mealy
III. Diagrammes d'états et tables d'états
1. Graphe d’état
Le modèle généralement utilisé pour représenter le cahier des charges
d'un système est un graphe appelé graphe d'état ou graphe de fluence.
Les nœuds de ce graphe représentent les états, un nom symbolique
étant affecté à chacun des états. Les arcs du graphe sont orientés. Ils
représentent les possibilités de passage entre états. Ces changements
d’états se font sur un front d’horloge en fonction des valeurs d’entrée.
La structure générale du graphe représentant l'évolution des états
d’une machine ayant une entrée E est représentée sur la Figure
suivante :
Structure générale du graphe d'état d'un système séquentiel synchrone
Les caractéristiques de ces graphes sont les suivantes :
Chaque état (Qi) est représenté par un cercle,
A chaque état est associé un nom symbolique
Le passage d'un état à un autre se fait au coup d'horloge,
L'état atteint dépend de l'état de départ et de la valeur des d'entrées
(Ei)
De chaque état part au plus 2n arcs, n étant le nombre d'entrées (Ei)
Ce graphe est connexe.
Si l'on considère maintenant la sortie, il faut différencier les deux
types de machines que sont machines de Moore et machines de
Mealy. En effet, dans une machine de Moore, les sorties ne dépendent
que des états et par conséquent peuvent être consignées à l'intérieur
des cercles. Dans une machine de Mealy, les sorties dépendent des
états mais également des entrées. Ces sorties doivent donc être
consignées sur les arcs du graphe. Ainsi, selon le type de machine, un
modèle différent de graphe d'état doit être considéré.
Machine de Moore Machine de Mealy
Structure des graphes d’état de Moore et de Mealy
Exemple :
Selon que le système sera réalisé sous forme de machine de Moore
ou sous forme de Machine de Mealy, le graphe d'état représentant le
cahier des charges précédent est représenté sur la Figure suivante :
Machine de Moore
Machine de Mealy
Remarque: La structure des deux graphes paraît identique. En fait, il
est toujours possible de passer d'un graphe de Moore à un graphe de
Mealy. Pour cela il, suffit de reporter les sorties associées à chaque état
(Moore) sur les arcs arrivant à chacun de ces états. Nous verrons par la
suite que l'inverse, c'est à dire passer d'un graphe de Mealy à un graphe
de Moore n'est pas toujours possible.
Ce modèle permet de représenter le cahier des charges sous une forme
exploitable, mais permet également de figer le fonctionnement du
circuit dans tous les cas particuliers non prévus dans le cahier des
charges initial.
A ce niveau de la synthèse, ce qui est important c'est de s'assurer que
le graphe correspond bien au cahier des charges. Le nombre d'état
utilisés pour représenter ce cahier des charges importe peu. Il sera
minimisé par la suite.
2. Table d’état
Le cahier des charges d'un système peut également être modélisé sous
une forme tabulaire qui est plus facile à manipuler qu'une
représentation sous forme de graphe. Cette représentation tabulaire,
appelée table d'état, est directement déductible du graphe d'état. Elle
représente les différentes possibilités d'états suivants de chacun des
états du système et ceci en fonction des entrées. Les sorties associées
à chaque état sont également représentées sur cette table. Elles
dépendent ou non des entrées selon qu'il s'agit d'une machine de
Mealy ou d'une machine de Moore.
Exemple : Les tables d'état correspondant au graphe de la figure ci-
dessous sont présentées sur le tableau.
Machine de Moore
Machine de Mealy
3. Minimisation du nombre d'états
Le nombre d'états de la machine influe directement sur le nombre de
bascules nécessaires pour réaliser ce système. Or, le nombre d'états
utilisés pour représenter le cahier des charges, que ce soit sur le graphe
d'état ou sur la table d'état, n'est pas nécessairement minimum.
a. Règles de minimisation
Deux règles permettent de déterminer les états équivalents et par
conséquent de minimiser le nombre d'états nécessaires à la réalisation
du circuit.
Règle R1 : Deux états sont équivalents si pour chaque
combinaison d'entrée, ils ont mêmes sorties et mêmes états
suivants.
Règle R2 : Les états sont regroupés en différentes classes selon les
valeurs de sorties associées. Ainsi, deux états ayant mêmes sorties
(pour chaque combinaison d'entrée) sont dans la même classe. Les
états appartenant à une même classe sont équivalents s’ils ne peuvent
être séparés. Or les états appartenant à une même classe doivent être
séparés si les états suivants associés à chacun d'eux sont dans des
classes différentes.
Lorsque plusieurs états sont équivalents, il suffit de garder qu'un seul
représentant par classe d'équivalence et de renommer les états
suivants en conséquence.
Exemple : Les règles de minimisation appliquées à la table d'état de
la machine de Mealy précédente donnent :
R1: A et D on mêmes sorties et mêmes états suivants, ils sont donc
équivalents. L'état D peut par exemple être éliminé. En renommant
les états suivants en conséquence, c'est à dire en remplaçant D par A,
la table d'état devient :
Table d’état réduite
Au sens de la règle R1 il n'y a pas d'autres états équivalents.
R2 : les états peuvent être regroupés en deux classes (classe 1 et
classe 2).
Les états A et B doivent être séparés. Il y a maintenant qu'un seul
état par classe. Il n'y a donc plus d'états équivalents. Cette machine
peut être réalisée avec 3 états.
b. Détermination du nombre de bascules minimum
Le nombre minimum d'états "q" étant déterminé, on peut en déduire
le nombre minimum "n" de variables d'état et par conséquent de
bascules nécessaires au codage de ces états à partir de la double
inéquation suivante :
Exemple : Pour la machine de Mealy précédente, le nombre
minimum d’état étant de 3, le nombre de variables d’état nécessaire au
codage de ces états est 2. Deux bascules sont donc nécessaires pour
réaliser ces systèmes.
IV. Analyse et synthèse de circuits séquentiels
1. Codage
a. Codage des états
Chaque état peut être codé par une combinaison de ces n variables
d'état. Chaque état doit avoir un code différent des autres mais le
codage des états peut être quelconque. Notons toutefois que le codage
influence la structure de la future machine et peut donc influencer sa
complexité. Le problème de l'optimisation de la machine résultante
passe donc par un choix judicieux du codage des états.
Une fois les états codés, la table d'état peut être exprimée en fonction
de ces codes.
Exemple: Nous appellerons les variables d'état (sorties des 2 bascules)
de la machine précédente, Q1 et Q2. En considérant un codage donné
(celui indiqué dans la colonne "Etats"), la table d'état codée de la
machine de Mealy correspondant à la table d'état du tableau realisé est
représentée sur le tableau ci-dessous.
Tables d'état codées de la machine de Mealy
b. Codage des entrées de bascules
Le code des états étant déterminé, les entrées de bascules peuvent
l'être. Pour chaque bascule i nous connaissons l'état suivant Qi(n+1)
(après le coup d'horloge) en fonction de l'état présent Qi (n) et des
entrées.
Pour réaliser ce système il reste à déterminer les entrées de chaque
bascule. Avec des bascules D, les entrées Di peuvent être déterminée
directement à partir de la relation : Di(n) = Qi(n+1)
Exemple:
Reprenons la machine de Mealy précédente. Les entrées D1et D2 des
bascules Q1 et Q2 sont représentées sur le tableau ci-dessous :
Détermination des entrées de bascules
2. Synthèse
a. Synthèse des entrées de bascules et des sorties de la machine
Sur la table précédente on dispose des sortie et entrées de bascules
exprimées en fonction des entrées et des variables d'état (sorties des
bascules). Il suffit donc maintenant d'exprimer les fonctions logiques
relatives aux sorties et entrées de bascules.
Exemple: Reprenons la machine de Mealy précédente et
déterminons les équations de la sortie S et des entrée de bascules
D1et D2
b. Implantation technologique
L’implantation technologique
de fonctions logiques est un
problème en soit qui sera
traité dans un chapitre
spécifique. Nous pouvons
nous contenter ici, d’une
implantation à portes obtenue
directement à partir de ces
équations déterminée
précédemment
