- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Machines à états finis
(FSM : Finite State Machines)
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI !
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Catégories de machines séquentielles
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Modèle générale (machines synchrones)
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Les machines à états : machine de
Moore Les sorties dépendent des états présents
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Les machines à états : machine de
Moore
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Graphe d'états d'une machine de Moore
représentation du graphe d’état
• Description des sorties
sur les états
• Les sorties dépendent
seulement des états
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Les machines à états : Machine de Mealy
Les sorties dépendent des états présents et des entrées
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Les machines à états : Machine de Mealy
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Les machines à états : Machine de Mealy
• Description des sorties
sur les transitions
• la sortie dépend des
états et des entrées
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Moore vs Mealy
Machines de Moore et de Mealy peuvent être fonctionnellement
équivalentes
– Une machine de Moore équivalente peut être déduite d’une machine de
Mealy et vice-versa
Machine de Mealy permet une description plus complexe et
nécessite un nombre d’état
Machine de Mealy : prise en compte immédiate d’un changement en
entrée
– Une machine de Mealy a un temps de réponse réduit d’un cycle par
rapport à son équivalent de Moore.
Une machine de Moore n’a pas de chemin combinatoire liant
l’entrée et la sortie
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Les machines à états : Machine de Mealy
VS Moore
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Les machines à états
Identifiez le type de chacun des deux machines à états suivants
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Mise en oeuvre des automates
Les fonctions F et G peuvent être réalisées :
A l'aide d'opérateurs logiques élémentaires
A l'aide d'une PROM :
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Les étapes de synthèse des MEF
(Principe de la conception "à la main" d'un
automate à états finis )
1. Établir la spécification comportementale de l'automate sous la forme d'un
graphe d'états. Optimiser le graphe si nécessaire (réduction du nombre
d'états).
2. Coder les états du graphe.
3. Établir la table de transition (next-state table) à partir du graphe d’états.
4. Établir la table d’implémentation à partir de la table de transition après
avoir choisir la cible matériel de réalisation (types de bascules).
5. Déterminer l’équation d’excitation de chaque bascule à partir de la
table d’implémentation (Synthèse de la fonction G).
6. Établir la table de sortie à partir du graphe d’états
7. Déterminer les équations de sortie à partir de la table de sortie
(Synthèse de la fonction F).
8. Etablir le schéma logique de l’FSM à partir des équations d’excitation et
de sortie.
9. Réaliser et tester l'automate.
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Synthèse des MEF
(Principe de la conception d'un automate à
états finis à l'aide d'un environnement de CAO)
1. Etablir la spécification comportementale de l'automate sous la forme d'un
graphe d'états. Optimiser le graphe.
2. Transcrire le graphe d'états optimisé dans un langage accepté par
l'environnement de CAO (VHDL).
3. Vérifier la spécification par une simulation fonctionnelle de l'automate.
4. Choisir le support matériel de réalisation. Fixer les paramètres
d'optimisation (surface, vitesse,…). Faire la synthèse logique de l'automate.
Le synthétiseur fournit automatiquement la "netlist" (description au niveau
portes élémentaires) du circuit ou le contenu de la PROM.
5. Simuler le fonctionnement de l'automate après synthèse (simulation
fonctionnelle + temporelle).
6. Réaliser et tester l'automate.
À voir dans le cours architecture et conception des syst numériques
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple: Synthèse d’une FSM de Moore
1. Graphe d’états
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple: Synthèse d’une FSM de Moore
2. Table de transition
Pour les bascules D les tables de transition
et d’implémentation sont identique, juste on
remplace Qnext par D
3. Table d’implémentation
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple: Synthèse d’une FSM de Moore
4. Tableaux de karnaugh et équations d’excitation des bascules
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple: Synthèse d’une FSM de Moore
5. Table de sortie et équations
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple: Synthèse d’une FSM de Moore
6. Circuit de l’FSM
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple 2: Synthèse d’une FSM de Moore
In this example, we will synthesize a Moore FSM that is more typical
of what the control unit of a microprocessor is like.
1. Graphe d’états 2. Table de transition
4. équations d’excitation des bascules
Leçon 1
3. Table
Proposé par Pr. Abdessalem d’implémentation
BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple 2: Synthèse d’une FSM de Moore
5. Table de sortie et équations 6. Circuit
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple: Synthèse d’une FSM de Mealy
1. Graphe d’états
2. Table de transition
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple: Synthèse d’une FSM de Mealy
3. Table d’implémentation 4. équations d’excitation des bascules
5. Table de sortie et équations
6. équations de sortie
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Exemple: Synthèse d’une FSM de Mealy
7. Circuit
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
1.) Déterminer les équations d’excitation à partir du circuit logique
de l’état suivant (next-state logic circuit) la fonction G.
2.) Déterminer les équations d’évolution (équations des Qi_next
(état suivant) next-state equations) en remplaçant les équations
d’excitation dans les équations caractéristiques des bascules.
3.) Établir la table de transition (next-state table) à partir des
équations d’évolution (next-state equations).
4.) Déterminer les équations de sortie à partir du circuit logique de
sortie (the output logic circuit) la fonction F.
5.) Établir la table de sortie à partir des équations de sortie.
6.) Dessiner le graphe d’états à partir de la table d’évolution (next-
state table) et de la table de sortie (output table).
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Soit l’exemple
suivant :
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
1) Équations d’Excitation
D1 = Q1'Q0
D0 = Q1'Q0' + CQ1'
2) Équations d’évolution (Next-state)
l’ équation caractéristique de la bascule D est Qnext = D
en remplaçant les deux équations d’excitation dans l’équation
caractéristique de la bascule D nous obtenons les équations d’évolution
suivantes :
Q1next = D1 = Q1'Q0
Q0next = D0 = Q1'Q0' + CQ1'
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
3) Table de transition (Next-state Table)
La table d’évolution est tout simplement la table de vérité
correspondante à l’équation d’évolution (next-state equations)
Exemple de calcul de la valeur de
Q1next et Q0next pour Q1 = 0 and
Q0 = 0, et C = 0 (valeur de l’entrée
Q1next = Q1'Q0 Q1next = Q1'Q0' + CQ1'
= 0' • 0 = 0' • 0' + 0 • 0'
=1•0 =1+0
=0 =1
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
4) Équation de sortie
Y = Q1'Q0
5) Table de sortie
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Pour une machine 4) Équation de sortie
de mealy Y = CQ1'Q0
5) Table de sortie
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Exercice 1: FSM de Moor A et B : entrées ; X et Y : sorties
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Exercice 1
Output table:
Excitation / next-state equations:
Next-state table: State diagram:
Output equations:
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Exercice 2
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Exercice 2
Excitation / next-state equations:
State diagram:
Output equations:
Next-state and output tables:
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
différentes formats d’une machine à
états finis (sans sortie, avec sortie,
FSM à évolution conditionnel, FSM à
évolution parallèle)
Méthode de synthèse systématique
Leçon 1
!
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Exercice 3
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Exercice 3
Excitation equations: Next-state table:
Next-state equations:
Output equations:
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Analyse des Circuits Séquentiels
Exercice 3
State diagram
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
- Cours : Circuits de l’électronique numérique - >> ING1 en Electronique <<
Leçon 1
Proposé par Pr. Abdessalem BEN ABDELALI
