Cours architecture de base d’un ordinateur

Cours architecture de base d’un ordinateur, tutoriel & guide de travaux pratiques en pdf.

Synthèse d’un circuit séquentiel synchrone

Graphes d’états
Considérons le fonctionnement du circuit séquentiel synchrone de la Figure 1. 33, détecteur de la séquence ’1,0,1’ :
Une suite de chiffres binaires arrive sur E, et les instants d’échantillonnage (moments où la valeur de E est prise en compte) sont les fronts montants de CLK. On souhaite que la sortie S vaille 1 si et seulement si les deux dernières valeurs de E sont : 1,0,1.
Cette spécification est en fait imprécise, car elle ne dit pas exactement à quel moment par rapport à l’horloge CLK la sortie doit prendre sa valeur. Il y a deux possibilités :
1. la sortie ne dépend que de l’état interne du circuit, et ne peut changer que juste après chaque front d’horloge. Elle ne pourra changer ensuite qu’au prochain front d’horloge, même si les entrées changent entre temps. On appelle schéma de MOORE une telle conception, et elle conduit au graphe de MOORE de la Figure 1. 34.
Figure 1. 34 Détecteur de séquence 1,0,1 de type Moore, non simplifié. Chaque état est associé à la réception d’une certaine séquence des 3 derniers bits. Seul l’état g provoque la sortie S =1.
La valeur de la sortie S est clairement associée aux états, et ne peut donc changer qu’avec eux. Les changements d’état se produisent à chaque front de l’horloge CLK, qui n’est pas représentée sur la graphe, mais dont la présence est implicite. Un arc libellé ’0’ par exemple indique un changement d’état lorsque E = 0.
2. la sortie dépend de l’état interne du circuit et de ses entrées, et on dit alors qu’il s’agit d’un schéma de MEALY. Pour le détecteur de séquence par exemple, la sortie S pourrait valoir 1 dès que E passe à 1 pour la deuxième fois, avant même que sa valeur ne soit ’officiellement’ échantillonnée au prochain front d’horloge. Cela conduit au graphe de MEALY de la Figure 1. 35.
L’arc libellé ’1/0’de a vers b par exemple indique un changement d’état de a vers b lorsque E = 1, avec une valeur de la sortie S=0. Mais attention : le changement d’état ne se produira qu’au prochain front d’horloge, alors que le changement de sortie se produit immédiatement après le changement des entrées.
Figure 1. 35 Détecteur de séquence 1,0,1 de type Mealy, non simplifié

Transformation d’un graphe de Moore en graphe de Mealy
On voit sur la Figure 1. 36 comment un arc dans un graphe de MOORE se transforme en un arc dans un graphe de MEALY équivalent.
Figure 1. 36 Un arc d’un graphe de MOORE transformé en un arc équivalent d’un graphe de
MEALY. Si avec l’entrée e on va en a associé à une sortie S, alors cette sortie peut être directement attachée à l’arc : e/S.
On a donc une méthode automatique pour transformer les graphes de MOORE en graphes de MEALY, très utile car les graphes de MOORE sont souvent plus faciles à concevoir. C’est elle qu’on a utilisée par exemple pour transformer le graphe de MOORE de la Figure 1. 34 en graphe de MEALY de la Figure 1. 35.

Tables de transitions
Les tables de transitions, encore appelées tables de Huffman ne sont rien d’autre qu’une version tabulaire des graphes de transitions. Par exemple, les tables associées aux graphes de MOORE et de MEALY du détecteur de séquence sont représentées Figure 1. 37.
Figure 1. 37 Table de transitions du graphe de MOORE pour le détecteur de séquence 1,0,1. À chaque arc du graphe correspond une ligne dans la table. On notera la table complémentaire, qui donne les sorties associées à chaque état.

Simplification des tables de transition
Une table de transitions permet notamment de repérer facilement des états équivalents. Un groupe G d’états sont dits équivalents si, pour chaque combinaison possible des entrées, ils conduisent à des états du groupe G avec les mêmes sorties. On peut alors diminuer le nombre d’états en remplaçant tous les états du groupe G par un seul, puis tenter de rappliquer cette procédure de réduction sur l’ensemble d’états réduit.
Par exemple, sur la table de transitions précédente associée au diagramme de MOORE, on constate que a et e sont équivalents, que c et g sont équivalents, que d et h sont équivalents.
Attention : b et f ne sont pas équivalents car, bien qu’ils aient mêmes états suivants, ils sont associés à des sorties différentes. On peut réécrire la table de transitions en supprimant les lignes associées à e, g et h, et en remplaçant partout e par a, g par c, h par d (Figure 1. 38).
Figure 1. 38 Table de transitions du détecteur de séquence 1,0,1après une première phase de simplification.
Sur cette table, on constate que b et d sont équivalents, ce qui ne pouvait pas être déterminé à l’étape précédente. La Figure 1. 39 montre la table encore simplifiée.
Figure 1. 39 Table de transitions du détecteur de séquence 1,0,1 après une deuxième phase de simplification.
Le processus de simplification s’arrête ici. Finalement, 4 états suffisent pour ce détecteur de séquence. Ceux- ci ont perdu la signification qu’ils avaient initialement dans le graphe à 8 états. Le graphe simplifié est représenté Figure 1. 40.
Figure 1. 40 Graphe de MOORE simplifié du détecteur de séquence 1,0,1.

Étapes de la synthèse d’un circuit séquentiel synchrone
Lors de la synthèse d’un circuit séquentiel synchrone à l’aide de bascules, qu’il soit de type MOORE ou de type MEALY, on obtiendra le circuit le plus simple en suivant les étapes suivantes :
1. dessin du graphe d’états : il permet une spécification claire du circuit.
2. table de transitions : forme plus lisible du graphe, qui permet de vérifier qu’aucune transition n’est oubliée, et prépare la phase de simplification.
3. simplification de la table de transitions : on applique la méthode vue précédemment, parfois en plusieurs étapes.
4. détermination du nombre de bascules : le nombre d’états du graphe simplifié permet d’établir un nombre minimum n de bascules à employer. On ne choisit pas encore le type des bascules à employer, car la phase d’assignation fournira de nouvelles informations.
5. assignation des états : pour chaque état, un vecteur unique de n bits est assigné, appelé vecteur d’état. Des règles heuristiques d’assignation permettent de trouver celle qui conduira à des calculs simples.
6. table de transitions instanciée : on réécrit la table de transitions, en remplaçant chaque symbole d’état par le vecteur associé.
7. choix des bascules : en observant la table de transitions instanciée, certains types de bascules peuvent être préférés. On emploiera une bascule D lorsqu’un état suivant est la recopie d’une valeur de l’état précédent, une bascule T lorsque l’état suivant est l’inverse d’un état précédent ; dans les autres cas, la bascule JK peut être employée.
8. calcul des entrées des bascules et calcul des sorties du circuit.

DÉTERMINATION DU NOMBRE DE BASCULES
Il y a quatre états à coder, donc 2 bascules seront employées, dont on appellera les sorties X et Y.

ASSIGNATION DES ÉTATS
La phase d’assignation consiste donc à affecter un vecteur d’état à chacun des états du circuit ; ici un couple (X,Y) pour chacun des 4 états. N’importe quelle assignation peut être employée. Néanmoins, on peut toujours affecter à l’état initial le vecteur d’état (0,0,…), qui sera forcé lors d’un RESET asynchrone du circuit. Par ailleurs, certaines assignations donnent lieu à des calculs plus simples que d’autres. On les trouve souvent en appliquant les règles heuristiques suivantes, par ordre de priorité décroissante :
1. rendre adjacents les états de départ qui ont même état d’arrivée dans le graphe.
2. rendre adjacents les états d’arrivée qui ont même état de départ dans le graphe.
3. rendre adjacents les états qui ont mêmes sorties.
L’idée est de minimiser le nombre de bits qui changent (état ou sorties) lors des changements d’états.
Appliqué à notre circuit, la première règle préconise d’associer a et c, a et f, b et f ; la deuxième règle préconise d’associer a et b, b et c, a et f ; la troisième règle préconise d’associer a, b et c. La Figure 1. 41 propose une assignation qui respecte au mieux ces règles.
Figure 1. 41 Assignation des états :
chaque état est associé à une
configuration binaire des bascules.

TABLE DE TRANSITIONS INSTANCIÉE
On recopie la table de transitions précédente, en remplaçant chaque symbole d’état par son vecteur d’état (Figure 1.
42).
Figure 1. 42 Table de transitions instantanée.

CHOIX DES BASCULES
En observant la table instanciée,on constate que X à l’état suivant reproduit l’entrée E :
une bascule D s’impose pour X. Dans le cas de Y, il reproduit presque la valeur de X de l’état précédent, sauf pour la deuxième ligne. A titre d’exemple, on va choisir une bascule JK.

CALCUL DES ENTRÉES DES BASCULES ET DE LA SORTIE DU CIRCUIT
Plusieurs méthodes sont possibles pour ces calculs. Celle qui sera employée ici est basée sur une réécriture de la table de transitions, à laquelle on rajoute les entrées des bascules, ici DX pour la bascule X et JY,KY pour la bascule Y (Figure 1. 43).
Figure 1. 43 Table de transitions instanciée avec les entrées des
bascules choisies.
En fait on connaissait déjà le résultat pour X : DX = E, qui est la raison pour laquelle on avait choisi une bascule D.
Pour Y, on trouve facilement que JY =E X et KY =X . Par ailleurs, on a S= X Y .
La synthèse est terminée, et notre séquenceur se réduit au schéma de la Figure 1. 44.

1 REPRÉSENTATION DES DONNÉES
1.1 INTRODUCTION
1.2 ÉLÉMENTS DE LOGIQUE COMBINATOIRE
1.3 MÉTHODES DE SIMPLIFICATION DES FONCTIONS COMBINATOIRES
1.4 MÉTHODE DE QUINE-MC CLUSKEY
1.5 ÉLÉMENTS DE LOGIQUE SÉQUENTIELLE
1.6 SYNTHÈSE D’UN CIRCUIT SÉQUENTIEL SYNCHRONE
2 INTRODUCTION À L’ARCHITECTURE
2.1 INTRODUCTION
2.2 ARCHITECTURE DE BASE D’UN ORDINATEUR
2.3 PRINCIPES DE FONCTIONNEMENT
2.4 ORGANISATION DE LA MÉMOIRE CENTRALE
2.5 CIRCULATION DE L’INFORMATION DANS UN CALCULATEUR
2.6 LE PROCESSEUR CENTRAL
2.7 LES MÉMOIRES
2.8 MICROPROCESSEUR INTEL 8086
2.9 LES INTERFACES D’ENTRÉES/SORTIES
3 ALGORITHMIQUE ET LANGAGE ÉVOLUÉS
3.1 ALGORITHMIQUE
3.2 ALGORITHMIQUE
3.3 PROGRAMMATION ET LANGAGE
3.4 DÉFINITIONS
3.4.1 ALGORITHME
3.4.2 ORGANIGRAMME
3.5 QUALITÉ D’UN ALGORITHME