MINISTERE DE

MINISTRY OF HIGHER
L’ENSEIGNEMENT SUPERIEUR
EDUCATION
UNIVERSITE DE DOUALA
UNIVERSITY OF DOUALA

EXPOSE DE VLSI ET SYSTEME

THEME : MACHINES A ETATS FINIS

Sous l’encadrement de : M. DJANDE

GROUPE 5
NOMS ET PRENOMS DES MATRICULES
PARTICIPANTS
NGOKI GOUETH MARCELIA 23G01090
NDOKAYO MAHOUNDE BRICE 21G00065
MANGA NGOLONG HAIDANE 21G00070
NGOH TONG AUGUSTE 21G00162
NGOUANA DASSE JORDAN 21G00256
M’PESSA NTAMACK MANUEL 21G00100
NGONO JONATHAN ARTHUR 21G00457
NGALLE JOEL HENRI 21G0
NGANKEM DONGMO EDWINE 21G00320
NEMAGA NGALEU ARMANDA 21G00209
NGAMBOU ADAM JEANNOT 21G00374
NGANSOP LYDIE ARCHANGE 21G00242
NGUIMBOCK DANIEL 23G0

GESI 4

2024-2025
1
Table des matières
INTRODUCTION......................................................................................................................3
I- CONCEPTS FONDAMENTAUX DES MACHINES À ETAT FINIS...............................4
1- États et Mémoire..............................................................................................................4
2- Transitions et Signaux d’Horloge................................................................................................4
3- Types de Machines à États Finis en VLSI.....................................................................................4
4- Les entrées et sorties d’une machine à états finis......................................................................5
a- Entrées d’une FSM..................................................................................................................5
b- Sorties d’une FSM...................................................................................................................5
5- Diagramme d’état.......................................................................................................................5
II- MODELISATION ET REPRESENTATION DES MACHINES A ÉTATS FINIS..............................................6
1- Structure de Mealy.....................................................................................................................6
2- Structure de Moore....................................................................................................................7
3- Représentation d’une machine à états finis (FSM)......................................................................7
4- Diagramme d'états - transitions..................................................................................................7
5- Tableau de transitions...............................................................................................................10
6- Diagramme de transition d'états (STD) :...................................................................................10
7- Graphes de Petri.......................................................................................................................10
III- SYNTHÈSE DES MACHINES A ÉTATS FINIS DANS LES SYSTÈMES VLSI................................................10
III- APPLICATIONS DES MACHINES À ÉTAT FINIS EN VLSI................................................................11
IV- AVANTAGES ET LIMITES DES MACHINES A ÉTAT FINIS DANS LES SYSTEMES VLSI......................12
1- Avantages des machines à état fini...........................................................................................12
2- Limites des machines à état fini................................................................................................13
CONCLUSION........................................................................................................................................14

2
 INTRODUCTION

Une machine à états finis (MEF) est un modèle mathématique utilisé pour représenter
le comportement séquentiel des systèmes. Elles sont largement utilisées en conception de
circuits numériques, en informatique et dans divers domaines de l’ingénierie pour modéliser
les systèmes séquentiels. Les MEF jouent un rôle crucial en informatique et en électronique
en permettant de modéliser et de contrôler des systèmes complexes. Elles sont utilisées dans
de nombreux domaines, notamment :
 La conception de circuits logiques séquentiels
 Le traitement du langage naturel en abrégé TAL
 Les réseaux de communication
 Le contrôle d’applications embarqués.
La MEF est intégrée dans le circuit VLSI (Very Large Scale Integration) à l’aide de portes
logiques et de registres, qui travaillent ensemble pour contrôler le comportement temporel du
circuit en fonction des entrées reçues. Dans notre exposé, il sera question pour nous de vous
expliquer tour à tour les concepts fondamentaux des MEF, de sa modélisation, de sa
représentation et de ses applications en VLSI.

3
 I- CONCEPTS FONDAMENTAUX DES MACHINES À ETAT
FINIS

Dans le domaine des circuits intégrés à très grande échelle (VLSI, ou Very Large Scale
Integration), les machines à états finis (FSM, pour Finite State Machines) jouent un rôle
crucial dans la conception et la gestion des circuits numériques complexes. Voici les concepts
fondamentaux des FSM appliquées aux VLSI :

1- États et Mémoire
Dans une FSM pour VLSI, chaque état représente une configuration ou un comportement
spécifique du circuit numérique. Ces états sont stockés dans des éléments de mémoire, comme
des bascules ou des registres, permettant au circuit de « se souvenir » de son état actuel.
La gestion de la mémoire est essentielle en VLSI pour assurer que les circuits répondent
correctement aux entrées en fonction de l’état actuel et non uniquement des signaux d’entrée.

2- Transitions et Signaux d’Horloge

Les transitions sont définies en fonction des signaux d’entrée et de l’état courant, souvent
synchronisés par un signal d’horloge (clock) pour assurer la cohérence du circuit.
Dans les VLSI, les signaux d’horloge permettent de synchroniser les changements d’état à des
intervalles précis, ce qui est essentiel pour éviter les comportements erratiques et gérer la
synchronisation entre différents sous-circuits.

3- Types de Machines à États Finis en VLSI

 FSM de type Mealy : Dans une FSM de type Mealy, la sortie dépend à la fois de l’état
actuel et des entrées. Ce type de FSM est utile dans les circuits qui nécessitent des
réponses rapides aux changements d’entrée, car la sortie peut changer sans attendre le
prochain cycle d’horloge.
Avantage : Le fonctionnement est plus stable et plus facile à prévoir.
Exemple : Un feu de circulation où chaque état représente une couleur (rouge, vert, jaune) et
la sortie correspond simplement à l’état actuel.
 FSM de type Moore : Dans une FSM de type Moore, la sortie dépend uniquement de
l’état actuel, ce qui garantit une stabilité de la sortie jusqu’au prochain changement
d’état. Ces FSM sont souvent préférées pour leur simplicité en VLSI, car elles tendent
à réduire la complexité des circuits logiques de sortie.
Avantage : Le fonctionnement est plus stable et plus facile à prévoir.
Exemple : Un feu de circulation où chaque état représente une couleur (rouge, vert, jaune) et
la sortie correspond simplement à l’état actuel.

4
 4- Les entrées et sorties d’une machine à états finis
Elles jouent un rôle central dans le fonctionnement d’une FSM (Finite State Machine). Elles
déterminent comment la machine passe d’un état à un autre et comment elle produit des
résultats. Voici comment elles fonctionnent et s’articulent :
a- Entrées d’une FSM
Les entrées sont des signaux ou des données externes reçues par la machine, qui influencent
ses transitions entre les états.
Une FSM lit les entrées pour déterminer la prochaine transition d’état en fonction de l’état
actuel. Ces entrées peuvent être des signaux binaires (0 ou 1) ou des combinaisons plus
complexes, comme des codes spécifiques dans des applications plus avancées.
Dans un circuit de commande de moteur, par exemple, une entrée pourrait indiquer la
direction souhaitée (avant/arrière) ou la vitesse.
b- Sorties d’une FSM
Les sorties sont les signaux ou actions produites par la machine en fonction de son état actuel
et, dans certains cas, de ses entrées.
Les sorties permettent de contrôler d’autres parties du système ou de fournir une réponse aux
entrées reçues. Elles sont essentielles dans les applications de contrôle où la FSM doit réagir à
des événements ou signaux de manière prédéterminée.
Dans une FSM de contrôle d’accès, une sortie pourrait être un signal pour ouvrir une porte
une fois que l’identification est validée.

5- Diagramme d’état
Les machines à états finis sont souvent représentées sous forme de diagrammes d’états, où les
cercles représentent les états et les flèches montrent les transitions en fonction des entrées. Un
tel diagramme permet de visualiser facilement le comportement d’un automate et ses
réactions face à différentes entrées.
Pour créer un diagramme de machine à états finis (FSM), on utilise des symboles spécifiques
qui représentent les états et les transitions entre eux en fonction des entrées et des sorties.
Voici les principaux éléments d’un tel diagramme :
1. États : Les états sont représentés par des cercles. Chaque cercle correspond à une
configuration ou un comportement spécifique de la machine.
2. Transition : Les transitions entre les états sont représentées par des flèches. Chaque
flèche indique le passage d’un état à un autre en fonction d’une condition d’entrée.
3. État initial : Cet état est souvent marqué par une flèche sans origine (ou avec un
symbole d’origine) pointant vers le premier état de la machine.
4. États finaux : Les états finaux, où la machine peut s’arrêter, sont parfois représentés
par un cercle double.

5
 II- MODELISATION ET REPRESENTATION DES MACHINES
A ÉTATS FINIS

Il existe comme mentionné plus haut deux structures de FSM

1- Structure de Mealy
La structure de Mealy est l'une des deux structures principales utilisées pour concevoir des
FSM. Dans une machine de Mealy, les sorties dépendent non seulement de l'état actuel du
système, mais aussi de l'entrée actuelle.

Les principaux éléments d'une machine de Mealy :

États : Une machine de Mealy a un ensemble d'états discrets qui représentent les différents
modes de fonctionnement du système. Chaque état peut être associé à des actions spécifiques
Ou à des transitions vers d'autres états en fonction des entrées et de l'état actuel.

Transitions : Les transitions définissent comment là

Machine passe d'un état à un autre en fonction des
Entrées. Chaque transition est associée à une condition qui, si elle est remplie par l'entrée
actuelle et l'état actuel, déclenche le passage à un nouvel état.

Entrées : Les entrées sont les signaux qui influencent les

Transitions et les sorties de la machine de Mealy. Chaque transition est conditionnée par une
combinaison d'entrées et d'états.
Sorties : Contrairement à une machine de Moore, où les sorties dépendent uniquement de
l'état actuel, dans une machine de Mealy, les sorties dépendent à la fois de l'état actuel et de
l'entrée actuelle. Cela signifie que les sorties peuvent changer à chaque cycle d'horloge en
fonction de l'entrée.

Fig.1 : Schéma d’une machine de Mealy

6
 2- Structure de Moore
La structure de Moore est l'autre structure principale utilisée pour concevoir des FSM. Dans
une machine de Moore, les sorties dépendent uniquement de l’état actuel du système
indépendamment de l'entrée actuelle.

Les points clés d'une machine de Moore sont :

États : Comme pour une machine de Mealy, une machine de Moore a un ensemble d'états
discrets qui représentent les différents modes de fonctionnement du système.

Transitions : Les transitions spécifient comment la machine passe d'un état à un autre en
fonction des entrées. Chaque transition est déclenchée par une condition sur les entrées et
l'état actuel.

Entrées : Les entrées sont des signaux qui influencent les transitions entre les états de la
machine de Moore.

Sorties : Les sorties d'une machine de Moore dépendent uniquement de l'état actuel. Cela
signifie que la sortie reste constante pendant toute la durée de l'état et ne dépend pas de
l'entrée actuelle

Fig.2 : Schéma d’une machine de Moore

3- Représentation d’une machine à états finis (FSM)

Une machine à états finis peut être représentée de différentes manières, en fonction de
l'objectif de la représentation et du niveau de détail requis.

4- Diagramme d'états - transitions

C'est la méthode la plus courante et la plus intuitive pour représenter une machine à états
finis. Chaque état est représenté par un cercle ou une boîte avec son nom à l'intérieur. Les
transitions entre les états sont représentées par des flèches dirigées, indiquant la direction du
changement d’état. Les conditions déclenchent les transitions sont généralement indiquées à
côté des flèches.

 Machine de Mealy

• Mémorisation synchrone des états (c.à.d. sur un front d’horloge).

7
 (clk ) ⇒ Sortie asynchrone .
• La sortie dépend directement de l’entrée et ceci indépendamment de l’horloge

• L’état futur est calculé à partir des entrées et de l’état présent.

• Les sorties d’une machine de Mealy dépendent de l’état présent et des entrées.

Exemple : Machine de Mealy reconnaissant la séquence 1 0 Diagramme de transitions

8
  Machine de Moore

• Les sorties d’une machine de Moore dépendent de l’état présent (synchrones, elles changent
sur un front d’horloge).

• L’état futur est calculé à partir des entrées et de l’état présent.

Exemple : Machine de Moore reconnaissant la séquence 10 Diagramme de transitions

5- Tableau de transitions
Cette représentation est plus formelle et est souvent utilisée pour une spécification détaillée
de la machine à états finis. Les états sont listés dans les lignes du tableau, et les colonnes
représentent les entrées et les sorties. Chaque cellule du tableau spécifie l'état suivant et la
sortie correspondante en fonction de l'entrée actuelle et de l'état actuel.

9
 6- Diagramme de transition d'états (STD)
C’est une représentation graphique similaire au diagramme d'états - transitions, mais avec une
structure plus formelle. Il utilise des symboles normalisés pour représenter les états, les
transitions, les entrées et les sorties. Les STD sont souvent utilisés dans la conception de
systèmes électriques et électroniques.

7- Graphes de Petri
Cette représentation est particulièrement utile pour modéliser des systèmes concurrents ou
parallèles. Les états sont représentés par des places, et les transitions entre les états sont
représentées par des arcs. Les graphes de Petri peuvent être utilisés pour analyser la
concurrence, les blocages et d'autres comportements complexes.

III- SYNTHÈSE DES MACHINES A ÉTATS FINIS DANS LES

SYSTÈMES VLSI

a. Processus de Conception
Les Machines à États Finis (MEF) jouent un rôle fondamental dans la conception des circuits
intégrés VLSI (Very Large Scale Integration). Elles permettent de modéliser et de contrôler le
comportement séquentiel des systèmes électroniques. Le processus de conception commence
par la définition des états et des transitions de la MEF pour capturer le comportement souhaité
du circuit. Ensuite, ces définitions sont traduites en diagrammes d'état et de transition, qui
sont ensuite convertis en équations logiques. Ces équations sont ensuite implémentées dans du
matériel physique à l'aide de techniques de synthèse logique, permettant de créer des circuits
optimisés pour des tâches spécifiques.

b. Optimisation des Circuits

Les MEF permettent d'optimiser la conception des circuits VLSI de plusieurs façons. En
représentant les comportements complexes par des états finis bien définis, elles facilitent
l'analyse et la minimisation des chemins critiques, ce qui améliore les performances globales
du circuit. De plus, en optimisant la gestion des états et des transitions, les concepteurs
peuvent réduire la taille du circuit et sa consommation d'énergie, ce qui est crucial pour les
applications à grande échelle. La synthèse des MEF aide également à simplifier la vérification
et la validation des circuits, assurant ainsi une haute fiabilité.

c. Langages de Description de Matériel (HDL)

Les langages de description de matériel (HDL) tels que Verilog et VHDL sont essentiels pour
la description et la synthèse des MEF. Ces langages permettent aux concepteurs de décrire le
comportement et la structure des circuits électroniques à un haut niveau d'abstraction. Verilog
et VHDL offrent des constructions spécifiques pour définir les états et les transitions des
MEF, ce qui facilite leur implémentation. Une fois la description HDL écrite, des outils de
synthèse logique transforment cette description en un réseau de portes logiques et d'autres

10
éléments matériels, prêts pour la fabrication sur silicium. Ces langages et outils sont
incontournables pour la conception efficace des circuits VLSI, car ils permettent de gérer la
complexité croissante des systèmes électroniques modernes tout en assurant des performances
optimales et une consommation d'énergie réduite.

IV- APPLICATIONS DES MACHINES À ÉTAT FINIS EN VLSI

Les Machines à États Finis (MEF) offrent une polyvalence remarquable dans la conception de
circuits VLSI. Elles trouvent leur place dans de nombreux domaines illustrés par quelques
exemples :
 Contrôleurs de Protocoles de Communication
Ethernet : Les contrôleurs Ethernet utilisent des MEF pour gérer l'état de la liaison, la
détection de collisions, la retransmission des trames, etc.
USB : Les contrôleurs USB utilisent des MEF pour gérer les différents états de la liaison, les
transferts de données, et les requêtes.
SPI, I2C : Ces protocoles de communication série utilisent également des MEF pour gérer les
séquences de communication.
 Unités de Contrôle de Processeurs
Microprogrammation : Les microprogrammes, qui définissent le fonctionnement d'un
processeur au niveau micro-opération, sont souvent implémentés à l'aide de MEF.
Unités de contrôle d'exécution : Elles gèrent le décodage des instructions, la sélection des
registres et des unités fonctionnelles, et le contrôle du flux d'exécution.
 Circuits de Traitement du Signal Numérique (DSP)
Filtres numériques : Les filtres IIR et FIR peuvent être implémentés à l'aide de MEF pour
gérer les différents coefficients et les états du filtre.
Modulateurs et démodulateurs : Les opérations de modulation et de démodulation dans les
systèmes de communication utilisent des MEF pour gérer les différents états du modulateur
ou du démodulateur.
 Systèmes Embarqués
Gestion de l'alimentation : Les MEF sont utilisées pour gérer les différents modes
d'alimentation d'un système embarqué, en fonction des conditions de fonctionnement.
Interfaces utilisateur : Les MEF permettent de gérer les interactions avec l'utilisateur, comme
les boutons, les écrans tactiles, etc.
 Tests et Diagnostics
Générateurs de vecteurs de tests : Les MEF sont utilisées pour générer des séquences de tests
afin de vérifier le fonctionnement correct d'un circuit.

11
Unités de diagnostic : Elles permettent de détecter et d'isoler les pannes dans un circuit.

V- AVANTAGES ET LIMITES DES MACHINES A ÉTAT FINIS

DANS LES SYSTEMES VLSI

Développer un programme de contrôleur logique programmable (PLC) à partir de zéro peut

être une tache longue et ardue, l’utilisation de machines à états finies (MEF) permet non
seulement de simplifier la programmation, mais également de créer un système flexible et
robuste pour gérer tous les aspects du processus automatique.
EXEMPLE : machine à état fini

1- Avantages des machines à état fini

Les MEF ont plusieurs avantages parmi lesquels on a :
- La familiarité : lorsque l’on travaille sur un nouveau projet il peut être difficile de
comprendre son fonctionnement, l’utilisation d’un programme standard mis en place
avec la méthodologie permet une compréhension plus rapide en suivant une séquence
logique d’évènement
- Le développement plus rapide : il n’est plus nécessaire de partir de zéro, l’utilisation
d’une MEF comme modèle de départ pour un projet signifie que les conditions dans
lesquelles sont déjà prédéfinies
- La sécurité : il devient plus facile de gérer les sorties d’un système pour éviter les
accidents lors de la mise en service
- La prévisibilité : en utilisant les MEF l’Equipment ne peut passer que dans u nombre
limité d’états, par conséquent tout équipement qui utilise les MEF présenteront les
elles comportements que tous les autres systèmes
- La fiabilité : il n’a qu’un seul état actif à la fois, ce qui réduit considérable le risque
d’erreur imprévues ou de comportements inattendu du système
- Une MEF est facile à comprendre, facile à mettre en œuvre mais pourtant négligée

2- Limites des machines à état fini

Les MEF bien qu’elles soient utiles dans de nombreux domaines elles présentent certaines
limites comme :

12
 - La capacité de mémoire : elles ne peuvent pas stocker une grande quantité
d’informations. Elles peuvent se souvenir que de l’état courant et éventuellement d’un
nombre limité d’état précédente.
- Absence de logique de traitement : elles ne peuvent pas effectuer de calculs ou
d’Operations complexes comme le ferait les machines de TURING, par conséquent
elles ne pourront pas résoudre tous les problèmes computationnels
- Difficulté à modifier de systèmes asynchrones : elles sont souvent conçues pour les
systèmes synchrones.

CONCLUSION

En somme, nous dirons que les machines à état fini sont de outils conceptuels qui jouent un
rôle crucial dans la modélisation de systèmes ou les comportements sont déterminés par des

13
états successifs. Grâce à leur structure mathématique claire et leur simplicité, les machines à
état fini permettent de concevoir et d’analyser des systèmes complexes de manière organisée
et prévisible. Elles sont omniprésentes dans divers domaines, de la programmation et des
automates industriels à l’intelligence artificielle et aux jeux vidéo. En maitrisant leur logique,
on peut non seulement améliorer la fiabilité des systèmes interactifs, mais aussi optimiser les
processus de développement.

14