1

CHAPITRE II

FFoonnccttiioonnss LLooggiiqquueess eett

CCiirrccuuiittss

ddeess 00 eett ddeess 11

2

Les ordinateurs actuels s’appuient sur des technologies basées sur un système binaire en utilisant dans les systèmes physiques deux états stables : allumé – éteint, ouvert – fermé, trou – bosse, etc. Suivant les progrès de la technologie, on peut imaginer que l’on puisse travaillera dans l’avenir sur des systèmes à plus de 2 états (dans certaines circonstances c’est d’ailleurs déjà le cas). Un ordinateur est une machine pour traiter et stocker des informations préalables codées sous forme

binaire. L’objectif de ce chapitre est de montrer d’une part, que le traitement des données et leur stockage

peut être entièrement décrit par des fonctions logiques très simples et d’autre part, que ces fonctions peuvent être réalisées par des circuits tout aussi simples.

Dans un premier nous décrirons comment ces fonctions peuvent être implémentées avec la technologie des semi-conducteurs (les transistors), mais rapidement nous nous dégagerons de cet aspect technologique pour décrire les circuits de manière indépendante d’une technologie donnée. Si les premières traces d’un système binaire datent d’environ 300 av JC (trigrammes et hexagrammes de Yi-King, sans d’ailleurs de preuves qui s’agissait d’un système de comptage ou codage), les développements se font réellement à partir du milieu du 19ième siècle avec les travaux sur l’algèbre binaire de George Boole permettant de construire l’algèbre de Boole.

George Boole a donné une base algébrique à la logique des propositions, une proposition étant un énoncé qui peut être vrai (V) ou faux (F). Ces propositions peuvent être reliées par des connecteurs pour élaborer de nouvelles propositions. Les connecteurs usuels sont le ¬(non logique), le ∧ (et logique) et le ∨ (ou logique). Par exemple, le connecteur ¬ appliqué à une proposition vrai la rendra fausse. Le « robinet est ouvert » est une proposition p qui peut prendre les deux valeurs V et F. La proposition q « l’eau coule » est une

proposition qui peut être vrai ou fausse. S’il y a deux robinets, alors la proposition « l’eau coule » est à vrai si l’un ou l’autre des robinets est à vrai. Les variables associées aux propositions pour manipuler celles-ci de manière plus abstraites sont appelées des variables booléennes. Nous avons ainsi la formalisation q=V lorsque p1=V ou p2=V et q=F dans tous les autres cas. La représentation algébrique donne q= p1 ∨ p2 à condition de définir totalement (pour toutes les valeurs possibles des variables p1 et p2) l’opérateur ∨ . A l’instar des opérations arithmétiques qui sont définies à l’aide de tables (d’addition, de multiplication, ..), un opérateur (connecteur) logique est défini par une table dite de vérité. Pour des propositions p et q quelconques la table de vérité de l’opérateur logique ou est : Claude Shannon a fait le lien avec les nombres binaires 0 et 1. Les principaux résultats de l’algèbre vont être rappelés avec la notation de Shannon. La même table de vérité devient alors, en prenant la convention V=0 et F=1, les variables sont dénommées a et b. Intéressons nous plus particulièrement, l’ensemble étant dénombrable, à l’ensemble de toutes les fonctions à deux variables. Il y a 16 fonctions de ce type, mais qui ne sont évidemment pas toutes indépendantes les unes des autres.

Parmi ces fonctions certaines sont plus intéressantes que d’autres : f1 ne présente pas un intérêt majeur (elle produit la valeur 0 quelque soient les valeurs de a et b. Par contre celles qui sont

p q p∨q V V V V F V F V V F F F

a b a∨b 0 0 0 0 1 0 1 0 0 1 1 1

a b f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

3

surlignées sont plus utiles et certaines mêmes fondamentales. Avec les notations en chiffre binaire, les opérateurs ∧ et ∨ sont remplacés par les signes . et +.

and a +b or a.b xor a ⊕ b nor (a+b) nand (a.b) De fait on peut montrer que toutes les fonctions logiques, quelles qu’elles soient, peuvent être construites à partir de deux opérateurs (¬ et +) ou (¬ et .). Ce résultat peut paraître curieux, mais effectivement toute opération faite par l’ordinateur, que ce soit le calcul d’un logarithme ou un classement par ordre alphabétique, sera traduite in fine en fonctions élémentaires de ce type. Le complément d’une variable peut s’écrire de différentes manières : ¬a, ...,a*,a,a c que l’on lit non a, a barre, a étoile, a complémenté (et à tort a inversé) Les principaux résultats de l’algèbre de Boole sont résumés dans les lignes qui suivent Le théorème fondamental est celui de De Morgan : il dit que le complément d’un OU donne un ET des compléments, et inversement. Lorsque l’on passe à une réalisation pratique à l’aide de circuits électronique on utilise parfois le symbolisme suivant que l’on appelle des portes logiques (gates). Un ensemble de portes connectées constitue un circuit logique. a.b a +b non a ⊕ b Le circuit suivant donne la réalisation d’un ou exclusif à l’aide de portes and et or. Ce circuit correspond à la matérialisation de la relation : bababa +=⊕ et est appelé un logigramme . Ce type de réalisation est un circuit combinatoire : les sortie évoluent « simultanément » avec les entrées au temps de propagations près. Ces circuits se distinguent des circuits séquentiels par le fait que ces derniers ont une capacité de mémorisation. Les circuits combinatoires vont nous permettre d’aboutir à la construction d’une unité arithmétique et logique (UAL) qui le composant qui dans un processeur effectue les calculs sur les données. Les

a b f9 0 0 0 0 1 0 1 0 0 1 1 1

a b f15 0 0 0 0 1 1 1 0 1 1 1 1

a b f7 0 0 0 0 1 1 1 0 1 1 1 0

a b f2 0 0 1 0 1 0 1 0 0 1 1 0

a b f8 0 0 1 0 1 1 1 0 1 1 1 0

Théorème des constantes a + 0 = a a . 0 = 0

a + 1 = 1 a . 1 = a Idempotence a + a = a a . a = a

Complémentation a + a = 1 a . a = 0 Commutativité a + b= b + a a . b= b . a Distributivité sur OU a + (bc) = (a + b) . (a + c)

sur ET a . (b + c)= (a.b) + (a.c) Associativité sur OU a + (b + c) = (a + b) + c = a + b + c

sur ET a .(b.c) = (a. b). c = a.b.c Théorème de De Morgan baab += et baba =+ On notera aussi la relation définissant le ou exclusif.

bababa +=⊕

Logigramme du XOR

4

circuits séquentiels vont être à la base des circuits de mémorisation et donc de la mémoire tout court. Les circuits combinatoires. Relation avec les circuits électroniques et le transistor en particulier.

Un transistor est fondamentalement un circuit électronique permettant de réaliser une amplification de courant. En injection un courant ib dans la base le transistor fait passer un courant iec = β ib entre l’émetteur et le collecteur (approximation). β est le gain du transistor . Ce gain peut être de l’ordre de 100 mais peut aussi prendre des valeurs très importantes. Le transistor utilisé en mode amplificateur sert essentiellement dans tout ce qui relève du traitement analogique du signal : amplification, filtrage, modulation , …

Lorsque le gain du transistor est très grand, un courant très faible génère un courant très important dans le collecteur et le transistor arrive très rapodiment à une situation de saturation. On exploite cette propriété pour faire fonctionner un transistor en mode commutation : soit le courant base est nul, soit le courant base est suffisamment important pour saturé le transistor. Ces deux situations sont représentées dans les figures ci-contre. Pour avo ir un courant de base nul, la base est connectée à la masse, c'est-à-dire au potentiel 0V. Le collecteur du transistor est relié à l’alimentation +5V

par d’une résistance qui limite le courant susceptible de traverser le transistor. Si le courant de base est nul, le transistor est dit bloqué : il ne laisse passer aucun courant dans le collecteur et par là même, il n’y a pas de chute de tension aux bornes de la résistance. La tension au niveau de collecteur est donc égale à 5V. Si le courant de base est suffisamment grand, pour ce faire la base est reliée à la tension d’alimentation +5V, alors un courant important traverse la résistance, y provoque une chute de tension telle que la tension du collecteur devienne proche de 0V. Un transistor en commutation fonctionne à la manière d’un interrupteur et il est essentiellement caractérisé par sa vitesse de commutation. Faisons maintenant le lien avec nos portes logiques. Avec quelles conventions un transistor peut-il devenir opérateur logique de base ? Dans le circuit ci-dessus, l’émetteur ne varie jamais en tension. On peut considérer le transistor comme un circuit à une entré (la base) et une sortie (le collecteur). S’il est un opérateur alors c’est un opérateur unaire. Associons d’abord une valeur logique à une tension électrique. Il n’est pas possible d’affecter une valeur précise de tension à une valeur logique 0 ou 1, car une tension est soumise à des aléas de variations. On dira que la valeur logique binaire 0 est associée à une valeur de tension suffisamment proche de 0V et que la valeur logique 1 est associée à une tension suffisamment proche de la tension d’alimentation, 5V. Dans le courant où le courant ne passe pas, l’entrée est à 0 logique (en bleu souligné sur la figure) et la sortie est à 1. Ce circuit réalise dans cet état le complément à 0. Dans le cas où le courant passe, l’entrée du circuit vaut 1 logique (5V) et la sortie est à 0 (~0V, à la tension 0,6Vde jonction près) si la résistance est calculée en conséquence. Le circuit réalise donc aussi le complément à 1. Nous avons ainsi vérifié que le circuit correspond aux deux lignes de la table de vérité de l’opérateur NON. Dans la pratique de l’électronique, un circuit qui fait basculer les tensions d’un extrême à l’autre est appelé un inverseur, d’où le nom un peu abusif de ce circuit (la fonction d’inversion n’existe pas en algèbre de Boole ).

E S 0 1 1 0

a b x 0 0 1 0 1 0 1 0 0 1 1 0

0v

0v

5v

5v

pas de courant

0 1

0v

5v ~ 0v

5v

le courant passe

0 1

collecteur

base

émetteur

bax +=

5

Comment passer maintenant aux opérateurs binaires ? Le circuit ci-contre correspond à un montage en parallèle de deux transistors (équivalent à deux interrupteurs montés en parallèle). On peut appliquer le même raisonnement que précédemment pour dire que le courant passe si l’une ou l’autre (voire les deux) des bases est alimentée. Ce circuit vérifie donc la table de vérité du NOR (non_OU) qui est la fonction f2 de la liste initiale. De manière analogue au montage parallèle des deux transistors, il est possible de faire un montage en série (deux interrupteurs en série). Le collecteur de l’un est relié à l’émetteur de l’autre. Il est facile de vérifier que le circuit correspond vérifie la table de vérité du NAND, soit la fonction f8 de la table des fonctions. Il est à remarquer qu’avec deux transistors on réaliser un AND à deux entrées (ou précédemment un NOR). Il peut donc être plus économique en nombre de transistors de réaliser des circuits à base de NAND ou de NOR plutôt que de AND et de OR. Il y a un tiers de composants en moins et quand il s’agit d’une intégration à grande échelle (des millions de transistors), gagner un tiers en composants de base n’est pas un facteur négligeable. A partir de maintenant, nous ne nous attarderons plus sur les transistors, en en restant sur les portes logiques, ce qui nous amène à être indépendant de la technologie. A ce stade, il faut introduire une autre opérateur, qui même s’il n’est pas de base, est souvent utilisé tel que, par exemple dans les circuits où il y a des additions à faire (addition binaire, calcul d’un CRC, …). Cet opérateur est le OU exclusif que nous noterons désormais XOR est symbolisé par x = a ⊕ b. La table de vérité montre que la sortie est à vrai que si l’une ou l’autre exclusivement des entrées est à vrai. Les principales propriétés du XOR qui peuvent être utiles sont données ci-dessous. Sa définition est : bababa +=⊕ , mais nous avons aussi : b.aabba +=⊕ a ⊕ 0 = a et a ⊕ a = 0 a ⊕ 1 = a et a ⊕ a = 1 a ⊕ b = b ⊕ a et (a ⊕ b) ⊕ c = a ⊕ ( b⊕ c)

a b x 0 0 1 0 1 1 1 0 1 1 1 0

a b x 0 0 0 0 1 1 1 0 1 1 1 0

b.ax =

6

Les circuits intégrés standard du marché . Il s’est écoulé une quinzaine d’années entre l’invention du transistor en 1947 (qui consomme 1000 fois moins qu'un tube et est 1000 fois plus petit invention due à William Schokley, John Bardeen et Walter Brattain des laboratoire Bell, prix Nobel en 1956) et la généralisation de l’utilisation des semi-conducteurs. Le vrai démarrage est provoqué par l’invention en 1959 du circuit intégré (Jack Kilby, Texas Instruments, Nobel en 2000) avec la mise au point d’un circuit de résistances, condensateurs et transistor par gravure d’une plaque de silicium par attaque chimique. Les développements se sont fait suivants d’une part des technologies différentes (TTL, CMOS) qui correspondent à des vitesses et des consommation de courant différentes et d’autre part suivant différents niveaux d’intégration (du SSI (Small Scale Integration) avec moins de 100 portes logiques au VLSI entre 105 et 107 portes et l’ULSI à plus de 107 portes). Ces progrès ont essentiellement dus au progrès de la finesse de gravure sur le silicium (6 µ pour le 8080 en 1974 pour 6000 transistors sur une puce à 0.13 µ pour le Pentium IV avec plus de 6 000 000 de transistors). La finesse de gravure a des conséquences directes sur la « vitesse de calcul » d’un circuit avec des portes logiques : plus la gravure est fine, plus les connexions entre composants sont rapprochés et moins il y aura de temps de propagation. Si la vitesse de propagation d’un signal électrique est de 200 000 Km/s dans un métal, elle est seulement de 2km/s dans un semi conducteur (100 000 fois moins). Il y a donc un temps d’établissement d’un résultat sur un porte simple (= 1 couche) qui est de l’ordre de quelques nanosecondes et il est utile d’avoir le même nombre de portes pour différents « chemins » possibles des variables ; sinon les temps de propagation sont différent s et les données ne sont pas présentes au même moment. Exemple de circuit intégré à fonctions logiques. Voici un exemple de circuit de type LSI de la série 74 de portes logiques.

7

Synthèse d’un circuit combinatoire. Notre premier objectif était de montrer comment tous les traitements de données pouvaient être effectués à partir de ces opérateurs de base. Le problème à traiter est donc le suivant : étant donné une fonction logique, aussi compliquée soit-elle, comment construire, synthétiser le circuit réalisant cette fonction.

Cette synthèse se fait en 3 étapes : la première est la spécification de la table de vérité, c'est-à-dire donner la description d’une fonction sous la forme d’une table de vérité, la seconde est la synthèse du circuit (avec une méthode du type minterm), la dernière concerne la réduction ou

simplification du circuit obtenu (avec la méthode du diagramme de Karnaugh). Table de vérité : La table de vérité comporte un nombre de lignes égal au nombre de combinaisons possibles sur les n variables d’entrées de la fonction à synthétiser. A coté des n colonnes des variables d’entrées il y aura autant de colonnes supplémentaires que de variables de sorties. Chacune de ces colonnes comporte la valeur d’une sortie pour la combinaison d’entrée correspondante. Dans la pratique on raisonnera variable de sortie par variable de sortie. Les minterms. Lorsque la table de vérité est totalement spécifiée, il faut transformer cette table en équation logique donnant la variable de sortie en fonction des variables d’entrées. L’idéal consiste à pouvoir exprimer cette équation avec uniquement les trois opérateurs de base que sont le OU (somme), le ET (produit) et le NON. Deux méthodes existent : décrire la fonction sous la forme d’un » OU de ET », ou autrement dit sous la forme du somme de produits, ou alors la décrire sous la forme d’un produit de sommes. On parle de somme canonique de produits ‘minterm’ et de produit canonique de sommes ‘maxterms’. Nous développerons la méthode des minterms sur la base d’une fonction à 3 variables d’entrées a, b et c. Il y a donc 8 combinaisons Ci de valeurs possibles pour les variables d’entrées et pour ces trois variables on peut définir un ensemble de 8 produits logiques (les minterms) Pj qui ne prennent la valeur 1 que pour l’une des combinaisons possibles (lorsque i =j ) et la valeur 0 pour toutes les autres combinaisons.

P0 P1 P2 P3 P4 P5 P6 P7 Ci a b c cba cba cba cba cba cba cab abc 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 2 0 1 0 0 0 1 0 0 0 0 0 3 0 1 1 0 0 v 1 0 0 0 0 4 1 0 0 0 0 0 1 0 0 0 5 1 0 1 0 0 0 0 0 1 0 0 6 1 1 0 0 0 0 0 0 1 0 7 1 1 1 0 0 0 0 0 0 0 1

Pour une table de vérité à mettre en équation le principe consiste à lister toutes les combinaisons de la table pour lesquelles la sortie est à 1. Par exemple, si la fonction vaut 1 pour la combinaison C1 alors la fonction se comporte pour cette combinaison comme le produit P1. On procède ainsi pour toutes les lignes où la sortie est à 1. Comme un produit n’est à 1 que pour une combinaison, la description complète de la fonction peut se faire simplement en faisant la somme des produits Pj pour toutes les lignes j pour lesquelles la sortie est à 1. De plus le fonction prend la valeur 0 pour toutes les autres combinaisons, exactement comme les produits Pj retenus.

Ci a b c S P0+ P2+ P7 0 0 0 0 1 1 1 0 0 1 0 0 2 0 1 0 1 1 3 0 1 1 0 0 4 1 0 0 0 0 5 1 0 1 0 0 6 1 1 0 0 0 7 1 1 1 1 1

8

Exemple : soit la table de vérité suivante : On peut exprimer la fonction par S = P0 + P2 + P7 , c'est-à-dire : S = cba + cba + abc La traduction sous forme de logigramme est alors immédiate : il s’agit d’un OR à 3 entrées, chacune des entrées étant un le résultat d’un AND également à 3 entrées. De manière générale, pour ne pas passer systématique par le tableau des produits, on construit l’équation en faisant la somme des produits dans les lignes où le résultat est à 1 et chaque produit est construit directement en faisant le produit avec les variables lorsqu’elles sont à 1 et avec leur complément lorsqu’elles sont à 0. Par exemple la ligne 2 donne la configuration : Ce qui donne comme produit cba La méthode des minterms permet donc d’obtenir, avec le passage par la somme canonique des produits, un premier schéma de conception. Le schéma obtenu n’est en général pas très optimal car la méthode ne tient pas compte des éventuellement redondances. Pour s’en convaincre, il suffit d’appliquer la méthode à une table de vérité bien connue. Soit la fonction à deux variables définie par la table de vérité suivante

L’application des minterms donne l’équation suivante : S = ba + ba + ab Ce qui donne le circuit ci-contre (1 OR et 3 AND) alors la fonction est tout

simple un OR Cette redondance est due au fait que l’équation n’est pas réduite : avec les théorèmes de l’algèbre de Boole, il est facile de ramener la sortie à sa forme minimale qui est S = a + b. La méthode du diagramme de Karnaugh permet de réaliser cette minimisation de manière systématique pour des fonctions jusqu’à 5 variables. Au-delà de ce nombre de variables les concepteurs s’orientent vers les méthodes formelles de calcul automatique. Diagramme de Karnaugh. La méthode de simplification de Karnaugh est construite sur les relations suivantes : Comme b + b = 1 (complémentation) alors a = a ( b + b ) soit finalement :

a = a ( b + b ) = a b + ab La méthode consiste à mettre la table de vérité sous la forme d’un tableau mettant en évidence de manière visuelle les regroupements de la forme ( b + b ). La construction du tableau de Karnaugh est faite en positionnant les cellules représentant l’état des variables d’entrées de manière à ce qu’elles soient adjacentes, c'est-à-dire en veillant à ce qu’une seule variable change d’état d’une case à l’autre. La disposition des lignes et des colonnes est donc faite suivant le code de Gray. Une cellule contient la valeur de la fonction.

La méthode de Karnaugh de simplification consiste à regrouper tout ensemble de cases à 1 adjacentes sur une ligne (ou une colonne) dont le nombre d’éléments est une puissance de 2 (dans

l’ordre 2, 4, 8). Les plus grands regroupements donnent les équations les plus simples. Les recouvrements sont autorisés. Les cases ont toujours quatre cases voisines : les bords du tableau se

rejoignent comme si le tableau était enroulé sur un cylindre vertical ou horizontal et les cases extrêmes d’une même colonne (resp. ligne) sont considérées comme adjacentes si elles sont à 1.

Les cases isolées restent telles que.

2 0 1 0 1

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

a b c

9

Si nous reprenons l’exemple de la fonction à deux variables, la retranscription de la table de vérité donne le tableau de Karnaugh ci-contre. Nous retrouvons bien sûr les cases à 1. La simplification consiste à procéder à des regroupements verticaux ou horizontaux d’ensemble de 1 en nombre d’éléments en puissances de 2. Les seuls regroupements possibles sont ici ceux visualisés par l’ellipse verticale et l’ellipse horizontale. Le cas {a=1 ; b=1} est un recouvrement, il correspond à l’union des deux ensembles. Le regroupement horizontal correspond au cas a=1, alors que le regroupement vertical correspond au cas b=1. La fonction est à 1 pour l’un ou l’autre des cas d’où le résultat final escompté S = a + b. Application à la fonction des trois variables. La table vérité avait mené à l’équation : S = cba + cba + abc Le tableau de Karnaugh construit à partir de la table de vérité fait apparaître un regroupement possible : les cases extrêmes de la première ligne sont à 1 et adjacentes. Le terme de la seconde ligne reste isolé et constitue un groupe à lui seul. Le résultat simplifié est maintenant : S = ca + abc . Remarque : on notera la disposition de l’énumération des valeurs de bc {00, 01, 11, 10} qui correspond à un code de Gray. Les lignes horizontales et verticales au dessus et sur le coté gauche du tableau permettent de repérer visualiser plus rapidement la variable (a) de son complément (a ). Autres exemples de tableaux à 3 et 4 variables.

S = ca + bc S = db

111

100

10

111

100

10ab

01001

10010

10110100

01001

10010

10110100

a

cb

abc

01001

11010

10110100

01001

11010

10110100

a

cb

abc

100100

000001

100110

000011

10110100

100100

000001

100110

000011

10110100

a

abcd

b

c

d

10

Quelques exemples de synthèse de circuit. Le voteur. On désire réaliser un circuit capable de décrire sur un ensemble n impair de bits s’il y a une majorité de 1 ou une majorité de 0. Soit M la variable majorité : on va la définir par M=1 s’il y a une majorité de 1 et M=0 s’il y a une majorité de 0. La synthèse est faite dans le cas n=3. La table de vérité est donnée ci-dessous.

Trois regroupements ont été effectués, chaque groupe ayant 2 éléments. Il n’est pas possible de faire un groupe de 4 et le groupe de 3 de la ligne inférieure n’est pas autorisé, le nombre d’éléments n’étant pas une puissance de 2. Cas des conditions impossibles, cases à valeurs indifférentes. Il arrive dans certains cas que la table de vérité comporte des cases qui soient indifférentes du point de vue de leur contenu. Jusqu’à présent la spécification d’une fonction booléenne comporte une partie « gauche de la table qui consiste à décrire systématiquement toutes les combinaisons d’entrées. Les entrées de la fonction étant la plupart du temps les sortie d’autres fonctions, il se peut que certaines configurations d’entrées soient impossibles (elles n’arriveront jamais). Dans ce cas on peut mettre n’importe quelle valeur dans la case correspondante et pour marquer cette indifférence on mettra X comme contenu de la case. Les cases indifférentes (« don’t care cells » en anglais) peuvent aussi survenir de par la spécification de la fonction. Par exemple dans le cas d’un voteur à 4 entrées : il y 3 cas de sortie (majorité de 1, majorité de 0 et égalité) donc 2 variables binaires de sortie avec des cas non utilisés. Lors des regroupements dans le tableau de Karnaugh, il peut alors être intéressant de regarder si en affectant à certains X la valeur 1 cela n’aurait pas pour effet de simplifier la fonction. Exemple :

Il y a avantage à remplacer le X de la première ligne par un 1 et celui de la seconde ligne par un 0. Ce choix permet de réaliser le plus grand regroupement possible et donne donc la meilleure simplification.

a b c M 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

11101

01000

10110100

11101

01000

10110100

a

c

abc

b

a

M

b c

11X01

X1000

10110100

11X01

X1000

10110100

a

c

abc

b

11001

11000

10110100

11001

11000

10110100

a

c

abc

b

111 11000 000000000000000111 11000 000000000000000

11

Quelques fonctions bien utiles. Le premier objectif, qui consistait à montrer que l’on peut synthétiser n’importe quelle fonction booléenne, étant atteint, décrivons maintenant quelques fonctions de calcul binaire fréquemment dans un processeur et qui devront être intégrées dans son unité de calcul appelée UAL (Unité Arithmétique et Logique). L’additionneur binaire. La première fonction qu’il peut paraître nécessaire d’avoir est l’additionneur, car une fois défini celui-ci, il sera possible de réaliser les autres opérations arithmétiques. La cellule élémentaire à concevoir est l’additionneur 2 bits : il comporte 2 sorties (la somme et la retenue de sortie) et 3 entrées (les 2 variables a et b ainsi qu’une retenue d’entrée). Pour réaliser un additionneur 8 bits,par exemple sur ds nombres codés en complément à deux sur 8 bits, il faudra

chaîner 8 de ces cellules élémentaires en connectant la retenue de sortie d’une cellule à la retenue d’entrée de sa voisine de gauche. La spécification de l’additionneur donne la table de vérité ci-contre. Le circuit résultant n’est pas donné sous la forme réduite au sens du diagramme de Karnaugh, mais avec des portes XOR. Cela est souvent le cas dans la représentation des circuits pour lesquelles la fonction fait intervenir une somme (comme par exemple un calcule de parité). Le schéma ci-dessous donne le circuit d’un additionneur pour des mots de 4 bits. Il faut chaîner 4 cellules

d’additionneur 1 bit. La retenue d’entrée de la cellule la plus à droite (poids faible) doit être fixée à 0 et la retenue de sortie de la cellule la plus à gauche (poids fort) devient un indicateur de débordement de l’addition.

Rs

a ba ReS

Rs

a ba ReS

Rs

a ba ReS

Rs

a ba ReS

2 1 03

S0S1S2S3

b0a0b1a1b2a2b3a3

0

Over

Rs

a ba ReS

Rs

a ba ReS

Rs

a ba ReS

Rs

a ba ReS

2 1 03

S0S1S2S3

b0a0b1a1b2a2b3a3

0

Over Ce circuit additionneur n’effectue pas réellement toutes les additions de bits en parallèle. Chaque additionneur élémentaire demande un certain temps pour faire l’addition (temps de propagation à travers toutes les portes) et l’addition sur le deuxième bit ne donne un résultat juste qu’après l’obtention de la première retenue. C’est un additionneur à propagation de retenue et le résultat un temps non négligeable pour se stabiliser et il existe d’autres manières de réaliser une additionneur pour pallier ce problème. Le générateur de parité impaire . Le générateur de parité impaire est un dispositif qui ajoute à une suite de bits un bit qui sert de clé de protection vis-à-vis des erreurs (de transmission par exemple). Dans le cas d’une parité impaire, ce bit supplémentaire est calculé de manière à ce que le nombre total de bits à 1 (y compris le bit de parité) soit impair. L’exemple traité concerne un ensemble de trois bits {a, b, c} pour lequel on calcule le bit de parité impair P. La table de vérité est donnée ci-contre. Les minterms appliqués à la table de vérité donne :

a b Re S Rs 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1

a b c P 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0

a b

Rs

SRea b

Rs

SRe

12

P = cba + bca + cba + cab = cb(a + )bc + cb(a + )cb

= )cb(a ⊕ + )cb(a ⊕

= cba ⊕⊕ La réduction de l’expression a été faite algébriquement par rapport à un résultat à exprimer sous la forme de portes XOR. Le comparateur. Un comparateur de deux bits délivre trois sorties à partir de deux entrées. En fonctions des deux entrées a et b, les sorties donne les indications suivantes : une variable pour signifier l’égalité, une pour signifier que a>b, une pour indiquer que a<b. On pourrait bien sûr diminuer le nombre de variables de sortie à cause de la redondance ou des impossibilités, en particulier entre les deux dernières variables. L’objectif est ici de « visualiser » à l’aide de trois indicateurs ou drapeaux (en anglais flag) les différents résultats de la comparaison. Cette technique des indicateurs est très utilisée dans le processeur : de tels indicateurs sont positionnés lors de chaque opération arithmétique et logique et permet donc au programmeur de tester les résultats d’une manière synthétique, en particulier pour les instructions de branchements conditionnels. Le multiplexeur. Une autre fonction importante consiste à opérer des choix en fonction des valeurs de variables d’entrée. Le multiplexeur est un circuit qui fait un aiguillage d’une des variables d’entrées vers la sortie. La variable d’entrée est sélectionnée à l’aide de variables de commande. Une commande à n bits permet de faire la sélection parmi 2n entrées. La table de vérité prend cette fois une forme légèrement différente : la sortie de s’exprime pas directement sous la forme d’un 0 ou d’un 1, mais elle correspond à la valeur de la variable d’entrée. Par exemple si a vaut 1 et b vaut 0 alors la sortie S reproduira la valeur de la variable D2. La fonction de sortie s’écrit comme pour une table de vérité classique, mais en considérant que la combinaison d’entrée d’une ligne doit générer une sortie à 1 pour sélectionner l’entrée D correspondante et valoir 0 dans tous les autres cas. On obtient alors la fonction définissant le multiplexeur : S = ba D0 + ba D1 + ba D2+ ab D3 Ce circuit est très souvent utilisé, en particulier dans une unité arithmétique et logique. On lui assigne maintenant le symbole de porte logique ci-contre.

a b E Sup Inf 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0

a b S 0 0 D0

0 1 D1 1 0 D2 1 1 D3

a

b

cP

a

b

cP

a

bP

Sup

Inf

a

bP

Sup

Inf

D0 00

D1 01

D2 10

D3 11

a b

S

D0 00

D1 01

D2 10

D3 11

D0 00

D1 01

D2 10

D3 11

a b

S

D0

D1

D2

D3

D0

D1

D2

D3

a b

S

C

R

01

2n

C

R

01

2n

13

Le démultiplexeur. Le multiplexeur joue un rôle important dans toute la circuiterie liée à la communication des données. La principale utilisation du multiplexage est l’utilisation d’une voie unique de communication pour faire passer « simultanément » plusieurs communications : le support est alloué successivement aux différentes communications. Le support voit donc passer un « mélange » de communications qu’il faudra démultiplexer à l’arrivée. Le démultiplexeur est un circuit à une entrée et 2n sorties : l’entrée est aiguillée vers la sortie adéquate en fonction des n variables de commande du circuit. Unité Arithmétique et Logique UAL Une UAL est l’entité qui dans un processeur effectue tous les traitements des données. On peut imaginer une UAL comme un ensemble de circuits comme ceux vus précédemment et capable de faire la plupart de opérations de base nécessaire à l’exécution du programme sur un ordinateur. Ces opérations de bases sont néanmoins relativement élémentaires comme les quatre opérations arithmétiques sur les entiers, des opérations logiques, des décalages, des opérations de lecture et d’écriture avec la mémoire centrale. Leur nombre dépend d’un processeur à l’autre, mais l’ordre de grandeur est la centaine d’opérations qui pour ne pas simplement les assimiler à du calcul, sont appelées instructions . En première approximation, les données à l’entrée sont traitées par tous les circuits qui font parallèlement les opérateurs et le choix du résultat est fait à l’aide d’un circuit multiplexeur. Les entrées de commande du multiplexeur sont alors des bits qui servent à coder les instructions. Le code d’une instruction est appelé le code opératoire . Le code opératoire d’une instruction du processeur Z80 est décrit sur 8 bits, celui du 68000 l’est sur 16 bits, ce qui ne signifie d’ailleurs pas que le Z80 a 256 instructions et 68000 en aurait 65536 ! Nous verrons ultérieurement que le code opératoire est structuré. Le symbolisme utilisé pour représenter une UAL est décrit dans le figure ci-contre.. L’instruction d’un processeur est constitué du code opératoire suivi d’un plusieurs paramètres qui sont les opérantes. Les opérations se font en général sur deux opérantes (Données A et B) et produisent un résultat F(A,B). L’UAL est ainsi le passage obligé sur le chemin des données. Les instructions purement arithmétiques et logiques positionnent des indicateurs associés à des états sur le résultat obtenu (résultat positif avec le drapeau P, nul avec Z, négatif avec N, débordement, …). Ces indicateurs sont accessibles au programmeur et peuvent être ré-utilisés par l’UAL pour l’exécution d’instructions conditionnelles (instructions du type SI condition ALORS …). L’UAL est le matériel de base pour l’exécution d’une instruction. Pour obtenir un processeur il faudra compléter cette UAL par une unité capable d’enchaîner les instructions d’un programme. Cette unité est appelée un séquenceur (automate), ou aussi unité de contrôle (contrôle au sens anglais de pilotage et non de vérification).

a b D0 D1 D2 D3

0 0 E 0 0 0 0 1 0 E 0 0 1 0 0 0 E 0 1 1 0 0 0 E

D0

D1

D2

D3

D0

D1

D2

D3

a b

E

00 D0

01 D1

10 D2

11 D3

a b

E

00 D0

01 D1

10 D2

11 D3

a b

E

a b

EE

U A L Code

OpératoireIn

dica

teur

s

Données A Données B

Résultats F(A,B)

U A L Code

OpératoireIn

dica

teur

s

Données A Données B

Résultats F(A,B)

14

Nous avons également noté que les résultats ne sont pas obtenus instantanément. Cela signifie que les données à traiter doivent être maintenues à leur valeur pendant toute la durée du traitement. Un processeur devra donc comporter un minimum de capacité de mémorisation : ces mémoiresq sont appelées des registres.

Les circuits de mémorisation et les automates relèvent de la logique séquentielle. La logique séquentielle. Un circuit combinatoire prend en compte les signaux d’entrées au fur et à mesure de leur changement et les sortie varient évidemment en conséquence : les résultats du circuit peuvent donc être sensibles soit au fait que toutes données d’entrées ne sont pas forcément présentes au même instant, soit au bruit pouvant se superposer momentanément au signal (parasite). Les opérations de synchronisation temporelle sont alors indispensables : il sera alors possible de définir la simultanéité (pendant quel intervalle de temps on considère que deux événements sont simultanés) et les relations de causalité du type événement-action (un événement provoque une action et il s’écoule un temps entre les deux) Le point commun entre le séquencement et la mémorisation est le temps. Comment introduire cette notion dans les circuits ? La mémorisation implique que l’on puisse exploiter la durée d’un phénomène physique. Prenons un exemple. Au début des calculatrices de bureaux, les mémoires à semi-conducteur étaient très onéreuses (ou n’existaient pas !) et tous les moyens étaient bons pour réaliser un circuit de mémoire. Ainsi des calculatrices de bureau utilisaient des circuits mémoire basés sur la propagation des ondes acoustiques dans des fils métalliques pour obtenir une capacité de l’ordre du Kilooctet. Pour créer des circuits de mémorisation, il faut créer un effet de rétroaction qui réinjecte une sortie sur l’entrée de manière à « entretenir » la mémoire. Prenons le circuit le plus simple : l’inverseur. Peut- il servir de mémoire ? Directement non, car il n’a qu’une seule sortie et qu’une seule entrée. Si on relie la sortie à l’entrée, l’inverseur ne pourra plus inverser longtemps et choisira de manière définitive la sortie ou l’entrée… ! Par contre, si l’on associe deux inverseurs l’on obtient deux sorties et deux entrées. Une sortie d’un inverseur ne pourrait-elle pas être connectée à l’entrée de l’autre ? Relions la sortie de l’inverseur du haut à l’entrée de l’inverseur du bas. Supposons que cette sortie est à 0. En injectant cette sortie sur l’entrée du circuit inférieur, la sorte de cet inverseur passe à 1. Pouvons-nous relier cette sortie à l’entrée du circuit supérieur ? Oui, car si la sortie de l’inverseur est à 0, son entrée est donc à 1. On peut donc sans dommage établir ce lien. Le circuit est dans un état stable : il mémorise indéfiniment le 1 de l’entrée de l’inverseur du haut sur la sortie de l’inverseur du bas. Le même raisonnement se répète si l’on part de la sortie de l’inverseur du haut à 1. Le circuit a donc un deuxième état stable. Dans le second état, le circuit mémorise un 0 de la même manière qu’il avait mémorisé un 1. On notera que ce circuit mémorise une valeur, mais aussi son complément sur l’autre sortie. Ce circuit, appelé bistable (ou flip-flop), est celui qui est à la base des fonctions de mémorisation et de séquencement (automates). Il ne reste à pouvoir le commander pour le mettre dans un état ou l’autre à la demande et l’on aura réalisé une mémoire à 1 bit. Ce pilotage peut être obtenu en remplaçant l’inverseur par un circuit équivalent du point de vue de l’inversion, mais avec une entrée supplémentaire comme le NOR (on peut procéder de la même manière avec des portes NAND). Ainsi naît le bistable RS.

0

10

0

1

1

0

1

0

0

1

15

Le bistable RS. Le bistable RS est la première évolution du circuit mémoire à base d’inverseurs. Il a deux entrées de commandes qui permettent de mettre le bistable dans l’un ou l’autre des états : la commande R (Reset) met le bistable à 0, c'est-à-dire Q=0, alors que la commande S (Set) met le bistable à 1 (Q=1). La valeur mémorisée est accessible sur la sortie Q. Comme pour les fonctions logiques, ce bistable est représentable par sa table de vérité. C’est un circuit à mémoire, c'est-à-dire qu’il mémorise un état. Dans ce cas l’état du circuit est également sa sortie, Q en l’occurrence. Q est l’état à l’instant t courant, au moment où l’on applique les commandes R ou S et Q+ sera le futur état, à l’instant t+1. L’équation caractéristique du bistable RS est Q+ = SR + RS . Q Tant que R et S restent à 0, le circuit continue de mémoriser la valeur précédente. La commande Set met la mémoire à 1 et la commande R met la mémoire à 0. Le fait de lancer les deux commandes simultanément donne lieu à une mémorisation indéterminée. Il faut proscrire cette possibilité. Les systèmes d’appels de service en hôpital sont souvent basés sur ce principe : l’appel et la réinitialisation ne se font pas dans le même lieu (impossibilité des deux commandes simultanées). Le circuit est dit asynchrone car il n’est piloté par aucun signal d’horloge. En effet les commandes R et S sont prises en compte à tout moment et l’on peut donc avoir les mêmes problèmes de sensibilité au bruit que les circuits de la logique combinatoire classique. Le bistable RSC Par rapport au bistable RS, le bistable RSC (C = Clock, horloge) introduit une validation des commandes par un signal supplémentaire C. Les commandes R et S ne sont prises en compte que lorsque C est à 1. Le bistable JK. Le bistable JK est une variante du bistable RS en gérant le cas R=S=1. Les entrées sont J et K, sans la moindre signification pour les lettres, elles jouent le même rôle que R et S, mais dans le cas où J=K=1 alors la sortie Q est complémentée (Q+ devient le complément de Q). Le bistable D. Par rapport au bistable RS, le bistable D (Data) répond aux deux besoins : éviter d’une part le cas d’indétermination et d’autre part de permettre la mémorisation d’une donnée D quelque soit sa valeur (et non plus seulement forcer un 1 ou 0 dans la mémoire). On veut donc trouver, à la validation près, une relation de la forme Q+ = D. Le bistable D est une évolution du bistable RSC en effectuant une complémentation entre les entrées R et S avec un inverseur. Les lignes surlignées sont celles qui correspondent à la fonction de mise en mémoire (C=1). L’équation caractéristique est Q+ = DC + C . Q

R S Q Q+ 0 0 0 0 Q+ = Q 0 0 1 1 Q+ = Q 0 1 0 1 mise à 1 0 1 1 1 mise à 1 1 0 0 0 mise à 0 1 0 1 0 mise à 0 1 1 0 X indéterminé 1 1 1 X indéterminé

D C Q Q+

0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

R

S

Q

Q

R

S

Q

Q

R

S

Q

QC

R

S

Q

QC

Q

QC

D

16

Comme pour le bistable RS, l’équation caractéristique du bistable D exprime que l’état futur Q+ (qui est aussi la sortie) est une fonction de l’état présent et des entrées. Le bistable D est l’unité élémentaire de mémorisation d’un bit et est largement utilisé dans les registres (mémoires internes aux processeurs) et dans certaines mémoires comme les mémoires cache. Tel que représenté avec sa réalisation en portes logiques il y a trois couches de circuit avec au total environ une dizaine de transistors. La mémorisation prendra un temps qui dépendra du cycle d’horloge (le circuit est synchrone et il faut attendre le prochain niveau « haut » de C pour valider la donnée D, plus le temps de propagation à travers les couches du circuit. Le bistable D est représenté par les symboles ci-dessous suivant la manière dont l’entrée horloge valide la mémorisation. Dans l’ordre, la mémorisation est faite sur le niveau haut de C, le niveau bas, un front de montée de C et enfin un front de descente. Les opérations qui peuvent faites sur cette mémoire sont l’écriture (la mémorisation) et la lecture (sans effet sur le contenu de la mémoire).

Pour un processeur 8 bits qui travaille de manière privilégiée sur des mots de 8 bits (l’octet), la structure ci-dessus représente l’entité standard de mémorisation interne : le registre. Le registre décrit permet de ranger les données sur les entrées D, les valeurs peuvent être lues sur les sortie O. Ce registre présente aussi la particularité de pouvoir être mis directement à 1 et à 0. L’opération de re-initialisation à 0 d’une variable étant une chose courante, il peut être intéressant de prévoir directement cette opération (instruction CLEAR d’un processeur) au niveau d’un registre plutôt que sur l’UAL. Synthèse d’un automate.

Dans cette partie nous allons décrire la manière dont on peut faire la synthèse d’un automate à l’aide de la logique combinatoire et de la logique séquentielle.

Un automate est un dispositif qui reproduit des séquences d’actions entièrement prédéterminé par rapport à son environnement. Dans notre contexte, l’automate est pris au sens de son modèle mathématique qui permet de décrire son comportement, c'est-à-dire la manière dont l’automate effectue la transition d’un état à l’état suivant. Un état de l’automate est l’ensemble des valeurs des paramètres permettant de décrire c que fait l’automate à un instant déterminé. L’état de l’automate, caractérisé par un nom, a une durée, alors que la transition, caractérisée plutôt par un verbe, d’un état à un autre se fait en temps nul. La modélisation dépend donc en fait de la granularité du temps d’observation. Par exemple, si on caractérise une personne par sa position assise ou debout, il n’ y aura que deux états si on considère que le temps mis pour se lever ou s’asseoir est faible par rapport à la durée de la position assise ou debout. Si l’on change d’échelle de temps et que la personne change fréquemment de position, alors le temps consacré à se lever et à s’asseoir n’est plus négligeable. La transition « se lever » ou « s’asseoir » devient alors un état « en train de se lever », entrain de s’asseoir : la modélisation comporte maintenant quatre états au lieu de deux. Une transition prenant un temps nul (dans le modèle), il est impossible de l’arrêter. Prenons un autre exemple : une barrière d’entrée de parking. La barrière a à priori deux états « levée » et abaissée et cela suppose que le temps de montée et de descente est nul. Dans la réalité ce n’est pas le cas et si

D

C

Q D

C

Q D

C

Q D

C

QD

C

QD

C

Q D

C

QD

C

Q D

C

QD

C

Q D

C

QD

C

Q

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D7 D6 D3 D2D5 D4 D1 D0

O7 O6 O3 O2O5 O4 O1 O0

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D

C

QR

S

D7 D6 D3 D2D5 D4 D1 D0

O7 O6 O3 O2O5 O4 O1 O0

17

l’on ne veut pas que la barrière continue à se baisser alors qu’une voiture passe et ainsi passer dans l’état « barrière détruite », il faut bien affecter un état « en train de se lever » et « en train de s’abaisser » pour pouvoir arrêter le mouvement de la barrière. On ne peut sortir que d’un état, pas d’une transition.

La réalisation d’un automate pose plus de problèmes au niveau de sa spécification que de sa conception.

Les automates développés dans ce cadre sont les automates finis, ou plus précisément les automates à nombre d’états fini. Comme l’algèbre de Boole est la base de la logique combinatoire, la logique séquentielle s’appuie sur la théorie des automates finis (FSM, Finite State Machines). Un automate fini est un être mathématique à nombre fini d’éléments pour mémoriser les paramètres associés à un état particulier. La quantité de mémoire permettra de définir le nombre d’états : ainsi pour une mémoire de n bits, l’automate pourra avoir 2n états. Au sens des circuits, l’automate comporte une entrée E (ou un ensemble d’entrées), une sortie S (ou un ensemble de sorties) et un état Q (ou un ensemble d’états). L’automate est une machine séquentielle qui fait intervenir le temps : le temps s’écoule en temps discret {t-1, t, t+1}. Le comportement de l’automate est décrit par les relations qui lient entrées, états et sorties. Il y a différentes manières de l’exprimer : fonctions, diagrammes et tables :

• Fonctions de transfert : S(t+1) = f [Q(t), E(t)] et Q(t+1)=g[Q(t), E(t)] dans la suite on remplacera Q(t+1) par Q+ et S(t+1) par S+

• Diagramme Etats-Transitions : c’est une représentation graphique où les états sont représentés par des cercles et les transitions par des arcs orientés. Ce symbolisme visuel est très intéressant pour la spécification.

• Les tables d’états et de transitions : c’est un symbolisme proche des tables de vérités et qui

permettront de faire de la même manière la synthèse et la simplification pour la partie combinatoire du circuit.

Pour la modélisation des automates, deux approches sont possibles : l’automate de Moore et l’automate de Mealy. Nous resterons sur des principes très généraux concernant ces modèles pour en signifier les principales différences dans l’approche de modélisation qu’ils proposent. Une comparaison plus fine relève de la théorie des automates. Nous donnerons un exemple de synthèse d’automate dans chacun des cas. L’automate de Moore. Dans l’automate de Moore, la sortie est une image immédiate des états : les variables de sorties s’obtiennent par une logique combinatoire, donc sans délai, de l’état du système. L’état actuel est combiné avec les entrées pour définir l’état futur Q+. Le bistable D vu précédemment est un exemple d’automate de Moore avec le cas particulier où la sortie est égale à l’état. Synthèse d’un automate de Moore La première étape pour la réalisation d’un automate est sa spécification. Il s’agit de décrire dans un premier temps le comportement de l’automate avec des phrases (ou des dessins, schémas)

Logique

Combinatoire

Etats

Mémoire

Logique

Combinatoire

Q+ = g[Q(t), E(t)] S+ = f[Q+]

ES

Q

Logique

Combinatoire

Etats

Mémoire

Logique

Combinatoire

Q+ = g[Q(t), E(t)] S+ = f[Q+]

Logique

Combinatoire

Etats

Mémoire

Logique

Combinatoire

Q+ = g[Q(t), E(t)] S+ = f[Q+]

ES

Q

18

suffisamment non ambiguës ou le moins ambiguë possible, et dans un deuxième temps de donner une représentation formelle, un formalisme mathématique par exemple sur lequel il est possible de s’appuyer pour faire une réalisation aussi conforme que possible à la description initiale. Illustrons la synthèse sur l’exemple du testeur de parité impaire. 1) Spécification informelle. C’est le sujet de l’exercice : il s’agit de réaliser un circuit qui vérifie si la parité calculée au fil de l’eau sur une suite de bits est impaire. Cette spécification est semi-formelle, elle n’est pas très précise et l’on peut envisager plusieurs interprétations. 2) Spécification formelle. Pour cet exemple, nous allons utiliser le formalisme graphique du diagramme états-transitions. L’état est représenté par un cercle. La représentation des états est une phase primordiale dans la synthèse : il faut énumérer l’ensemble des états, sans en oublier. Le testeur doit analyser les bits qui arrivent et au fur à mesure de leur arrivée évaluer la parité. Le testeur doit donc mémoriser la dernière parité pour calculer la nouvelle. Les deux états du testeur sont donc « pair » et « impair ». Un tel diagramme met en avant les états et les transitions plutôt qu’une description classique d’un système avec les entrées d’un coté et les sorties de l’autre. Les entrées sont les événements qui font passer l’automate d’un état vers un autre : elles sont représentées en association avec une transition et sont considérées comme une condition d’activation de cette transition. Dans le cas du testeur, la donnée en entrée fait réagir le testeur de la manière suivante : Si le nombre précédent de 1 est pair (état pair), alors un 1 en entrée fait passer le testeur dans l’état impair ; Si le nombre précédent de 1 est pair (état pair), alors un 0 en ent rée fait rester le testeur dans l’état pair (boucle de l’état sur lui-même); Si le nombre précédent de 1 est impair (état impair), alors un 1 en entrée fait passer le testeur dans l’état pair ; Si le nombre précédent de 1 est impair (état impair), alors un 0 en entrée fait rester le testeur dans l’état impair (boucle de l’état sur lui-même); Relations définissant la sortie à partir de l’entrée et de la sortie. La valeur de sortie qui nous intéresse doit nous permettre de savoir si les bits à 1 sont en nombre impair : cette valeur correspond à la lecture directe de l’état. Nous avons donc affaire avec un automate de Moore. Les valeurs de sortie sont alors indiquées au niveau des états, sous la forme S=X. Cette spécification formelle doit permettre de vérifier que le problème que nous allons résoudre est bien celui qui a été posé. On remarque q’il n’y a pas de début et de fin : les testeur travaille au fil de l’eau et donne à tout instant la parité de tous les bits déjà passés. Le testeur ne fonctionne pas sur une analyse d’un mot de n bits, mais sur une suite continue. On constate d’autre part qu’il n’y a pas moyen de réinitialiser le système. 3) Codage des états et des sorties. Si l’on admet que cette spécification est bonne, on peut passer à l’étape suivante qui consiste à passer d’une représentation symbolique des états sous forme de nom à une représentation codée sous forme binaire des états permettant leur manipulation par des tables de vérités. Pour le testeur, le codage est immédiat l’état pair est codé par un 0, l’état impair par un 1. Il en est de même pour la sortie (S=0 si le résultat est pair et S=1 si le résultat est impair). L’étape suivante est la transcription du diagramme des états vers une table de transition d’états. 4) Table des transitions d’état. La table des transitions d’état donne dans notre exemple la fonction Q(t+1)=g[Q(t), E(t)] ; la sortie étant identique étant identique à l’état actuel. L’état est l’élément qui doit être mémorisé sous forme binaire et le

1

1

00

Pair (0)

[S=0]

Impair(1)

[S=1]

1

1

00

Pair (0)

[S=0]

Impair(1)

[S=1]

011

100

10Q,SE

Etat actuel Etat futur Q+

011

100

10Q,SE

Etat actuel Etat futur Q+

19

dispositif retenu de mémorisation peut être un bistable D : il y a deux valeurs d’états, donc 1 bit de quantité d’information. L’état futur Q+ devient l’entrée du bistable D de telle manière qu’au prochain top sur l’entrée Clock du bistable cet état soit mémorisé pour devenir le nouvel état actuel. 5) Synthèse de la logique combinatoire. Pour cette synthèse, il est préférable de transformer la table des transitions d’état en une table de vérité pour application de la méthode des minterms et le cas échéant pour effectuer des simplifications. Le passage à la table de vérité est immédiat et l’on trouve la table ci-contre qui montre que l’état futur est le XOR entre l’entrée et l’état actuel. 6) Schéma final Il suffit maintenant de faire le lien entre la logique combinatoire qui définit l’état futur en fonction de l’état actuel et de l’entrée, le bistable de la mémorisation de l’état et la logique combinatoire définissant la sortie en fonction de l’état actuel (ici c’est l’identité). On pourra remarquer que ce circuit intervient sous forme de vriante dans le circuits CRC correspondant à la détection d’erreurs par les codes cycliques. Nous avons choisi de corriger la spécification initiale en rendant possible la réinitialisation du testeur. Cette réinitialisation peut être simplement faite en prenant un bistable D avec une commande R(eset). Le diagramme états-transitions est corrigé en conséquence : le symbole utilisé pour la ré- initialisation indique que la transition peut venir de n’importe quel état. L’automate de Mealy. Dans l’automate de Mealy, Les nouveaux états et les sorties sont calculés parallèlement. Cela signifie qu’à la différence de l’automate de Moore où les sorties sont associées aux états, les sorties sont associées aux transitions. Dans le diagramme état transition, les arcs de transitions sont alors annotés par les nouvelles valeurs des sorties. Synthèse d’un automate de Mealy Nous allons procéder de la même manière que pour la synthèse d’un automate de Moore, en précisant lorsque cela est nécessaire quelles sont les différences. Un problème d’automate peut être modélisé par un automate de Moore ou un automate de Mealy. Comment choisir entre les deux ? Disons qu’en première approximation il est plus aisé de travailler avec un automate de Moore lorsque les états sont immédiatement visibles (sorties), et plus facile d’utiliser l’automate de Mealy lorsque l’état est une variable interne dont la visibilité n’est pas nécessaire. Nous allons prendre comme exemple de synthèse avec l’automate de Mealy un additionneur série. 1) Spécification semi-formelle.

E Qb Q+

0 0 0

0 1 1 1 0 1 1 1 0

D

C

QE S

RRe-Init

D

C

QE S

RRe-Init

1

1

00

Pair (0)

[S=0]

Impair(1)

[S=1]

Re-Init1

1

00

Pair (0)

[S=0]

Impair(1)

[S=1]

1

1

00

Pair (0)

[S=0]

Impair(1)

[S=1]

Re-Init

Logique

Combinatoire Etats

Mémoire

ES

Q

Q+ = g[Q(t), E(t)] ; S+ = f[Q(t), E(t)]

Logique

Combinatoire Etats

Mémoire

ES

Q

Q+ = g[Q(t), E(t)] ; S+ = f[Q(t), E(t)]

20

L’addition de deux nombres E1 et E2 est faite en série, c'est-à-dire que les bits des deux nombres arrivent un à un. Les bits sont additionnés, le résultat S est affiché et il faut mémorisé la retenue pour l’addition des 2 bits suivants. 2) Spécification formelle. Nous spécifions l’additionneur à l’aide d’un diagramme état-transition : les sorties sont annotées sur les arcs de transitions et non plus sur les états. Les transitions sont annotés par trois valeurs : les deux premières représentent le nouvel ensemble de bits {E1i, E2i} des nombres à additionner et la troisième est la valeur correspondante prise par la sortie Si. D’un ensemble de bits à l’autre, l’additionneur 1 bit que nous concevons produit une sortie correspondant à la somme et garde éventuellement une retenue pour l’addition suivante. Il y a deux états, donc il suffit d’un bit (bistable D) pour les mémoriser. 3) Codage des états et des sorties. Les sorties sont directement représentées par leur valeur résultat de la somme sous forme de 0 et 1, et l’état de retenue peut directement être codée sous sa forme utilisable dans l’addition. 4) Table des transitions d’états. L’on exprime l’état futur (la retenue suivante) et la sortie (somme) en fonction des deux variables d’entrées et de la retenue actuelle. Le passage à cette table sert de tremplin pour passer à la table de vérité. 5) Table de vérité. La table de vérité comporte trois colonnes d’entrées (E1, E2 et Q) et 2 colonnes de résultat correspondant aux deux fonctions à définir l’état suivant et la sortie. La table étant un peu plus compliquée que dans le cas précédent, regardons si l’application du diagramme de Karnaugh permet de réduire les fonctions logiques.

La forme canonique de Q+ peut être réduite et devient : Q+ = Q.E1 + Q.E2 + E1.E2

La forme canonique de la somme S ne peut pas être réduite et nous restons avec sa forme initiale de la table de vérité : S = Q.2E.1E + Q.2E.1E + Q.2E.1E + Q.2E.1E

E1 E2 Q Q+ Somme 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1

11/001/1

Pas deretenue

(0)

Retenue

(1)

00/0

10/1 11/1

10/0

01/0

00/1

Sortie Si

Entrées : E1iE2i

11/001/1

Pas deretenue

(0)

Retenue

(1)

00/0

10/1 11/1

10/0

01/0

00/1

Sortie Si

Entrées : E1iE2i

1/11/01/00/11

1/00/10/10/00

1 11 00 10 0Q

E1i E2i

retenue retenue future Q+ / Somme

1/11/01/00/11

1/00/10/10/00

1 11 00 10 0Q

E1i E2i

retenue retenue future Q+ / Somme

11101

01000

1 01 10 10 0

Q

E1i

QE1iE2i

E2i

Diagramme de Karnaugh de Q+

11101

01000

1 01 10 10 0

Q

E1i

QE1iE2i

E2i

Diagramme de Karnaugh de Q+

01011

10100

1 01 10 10 0

Q

E1i

QE1iE2i

E2i

Diagramme de Karnaugh de S

01011

10100

1 01 10 10 0

Q

E1i

QE1iE2i

E2i

Diagramme de Karnaugh de S

21

6) Schéma final. Il faut faire le lien entre la logique combinatoire obtenue à partir de la table de vérité et de la mémorisation de la retenue avec un bistable D (par exemple). Circuit à vérifier : Mémoires et automates. Nous avons vu que le bistable D peut être un composant idéal pour la fabrication de mémoires à semi-conducteurs. Ces circuits, lorsqu’ils sont optimisés, donnent effectivement de bonnes performances en temps d’accès. Malheureusement, ils sont très gourmands en transistor et à surface égale, ils sont relativement onéreux. Ce type de mémoire, appelée SRAM, est donc réservé aux mémoires les plus proches du processeur (les mémoires cache) et aux mémoires internes du processeur (les registres). A cause de leur coût, elles n’ont en général pas une très grande capacité. La mémoire centrale de l’ordinateur, c'est-à-dire la mémoire qui va contenir le programme et les données au moment de l’exécution de celui-ci, requiert maintenant une grande capacité, de quelques centaines de mégaoctets à quelques gigaoctets. Il a donc fallu trouver une solution moins onéreuse pour arriver à ces tailles de mémoires. RAM, SRAM et DRAM. La mémoire centrale est souvent appelée RAM (Random Access Memory). Le terme aléatoire (random) est ici à prendre au sens de direct : la mémoire RAM est à accès direct par opposition à accès séquentiel. La plupart des mémoires utilisées au début de l’informatique était des mémoires de type ruban ou bande (papier, magnétique) : cela signifie que l’on ne peut pas accéder directement à n’importe quelle « case mémoire », mais qu’il faut partir du début de la bande (opération de rembobinage – rewind –) et compter toutes les cases jusqu’à arriver à la bonne. On parle alors d’un accès séquentiel. Les mémoires RAM sont à adressage direct, c'est-à-dire que le décodage de l’adressage permet immédiatement de viser la bonne case mémoire. Lorsque la moire est construite à partir de bistable de type D, on parle de SRAM avec S comme Statique. Le terme de statique signifie que le circuit mémoire reste dans un état stable dès lors que la mémorisation est faite (ce qui normal pour un bistable D). Le qualificatif statique est à opposer à celui de dynamique pour les DRAM. Dans les DRAM, c'est-à-dire les RAM dynamiques, les très grandes capacités mémoires sont obtenues en minimisant au plus le nombre de composants électroniques à utiliser pour la mémorisation d’un bit, en particulier au niveau des transistors. Or ce résultat a été obtenu, non pas avec des bistables ou des bascules comme nous venons de les voir, mais en utilisant un seul transistor et un condensateur comme circuit mémoire. Le condensateur chargé représente un 1 par exemple et représente un 0 lorsqu’il est déchargé. Si le principe est bon, la réalité des condensateurs fait qu’ils ont toujours des courants de fuites et un condensateur chargé fini toujours par se décharger.

D

C

Q

Q Q+

Somme

E1 E2

22

Pour tenir compte de ces caractéristiques technologiques, un tel circuit n’est réellement utilisables comme un mémoire qu’en la « rafraîchissant » régulièrement, d’où le nom de RAM dynamique. La mémorisation n’est pas un état stable, il faut rajouter une circuiterie annexe qui a intervalle de temps régulier recharge les condensateurs qui le nécessite. Les DRAM sont peu onéreuses car un demandent un nombre minimal de composants par bit, par contre les temps d’accès sont d’un ordre de grandeur supérieur à ceux des SRAM. La mémoire centrale est aussi parfois appelée « mémoire vive », par opposition cette fois à « mémoire morte ». La mémoire RAM est une mémoire vive dans le sens où son contenu est modifiable à volonté et à tout moment, en particulier pour recevoir les modifications des variables des programmes, c'est-à-dire les résultats des calculs. La RAM est aussi dite volatile, c'est-à-dire que son contenu est perdu lorsque les circuits ne sont plus alimentés en courant électrique. A la mise sous tension d’une RAM, le contenu est à priori indéterminé. Une mémoire ROM (Read Only Memory, ce qui correspond à la bonne dénomination) est une mémoire morte au sens où son contenu a été constitué à la fabrication du composant et ce contenu ne peut ensuite plus être modifié. On ne peut lire que son contenu. A quoi peut servir une ROM ? Pour apporter des réponses, il faut penser à deux situations particulières : le démarrage d’un processeur et l’informatique embarquée. Le processeur est un automate d’exécution d’instruction, qui une fois son initialisation faite doit obligatoirement exécuter des instructions les unes après les autres sans jamais s’arrêter. Il faut donc qu’au démarrage il y ait dans la mémoire centrale un programme préexistant à la mise sous tension. Ce programme se trouve dans une partie de la mémoire centrale où l’on aura installé un bout de mémoire ROM. L’exécution du programme de cette ROM peut ensuite mener à aller chercher d’autres programmes (par exemple un système d’exploitation) sur un autre support (mémoire secondaire) comme un disque dur (dans le cas d’un PC on dit que la ROM contient un logiciel qui s’appelle le BIOS). L’informatique embarquée (ou enfouie, le terme anglais est embedded) est l’informatique que l’on trouve enfouie dans des équipements autonomes comme un téléphone, une machine à laver ou un appareil photo. Dans ces équipements il faut bien sûr une mémoire ROM pour assurer le démarrage du processeur, mais ce type de mémoire doit aussi jouer le rôle de mémoire secondaire lorsqu’il n’y en a pas : tous les programmes nécessaires au fonctionnement de l’appareil sont donc présent en mémoire centrale sous forme de ROM. La mémoire vive est alors principalement utilisée pour la manipulation des données. Les mémoires PROM (Programmable Read Only Memory) sont une variante des ROM. Alors que le contenu des ROM est défini à leur fabrication, les PROM sont des mémoires mortes qui sont reprogrammables avec un dispositif spécial appelé programmateur de PROM. C’est l’équivalent des CDROM réinscriptibles par rapport aux CDROM classiques. Une des techniques de reprogrammation consiste à procéder à un effacement de la mémoire en exposant le composant aux UV (via une petite fenêtre), puis à ré-écrire avec le programmateur. Le contrôleur de mémoire. Prenons le cas de mémoire élaborée à base de bistables D comme décrit précédemment. Depuis les processeurs huit bits, la mémoire est généralement organisée sur la base de l’octet, du moins en ce qui concerne l’expression de sa taille. Cela signifie que la granularité de mémorisation est l’octet : on lit ou on écrit un octet à la fois et non par bit. La « case mémoire » contient un octet et son adresse est donc une adresse d’octet : une adresse sur 10 bits permet un adressage sur 1024 adresses d’octets. Si la granularité de mémorisation était le bit alors il faut à capacité égale 13 bits (8192 adresses de bits). Il faut 8 bistables D pour mémoriser un octet et l’on pourrait penser que les huit bits d’un octet se trouvent dans le même circuit. En fait, ce n’est pas le cas car les opérations d’écriture et de lecture créent un échauffement sur les composants concernés et pour mieux répartir cette chaleur, les huit bits d’un octet sont mémorisés dans huit boîtiers différents. Ceci explique que quelle que soit la quantité de mémoire la mémoire est organisée en rangées de huit boîtiers (neuf s’il y a une gestion de bit de parité pour la détection d’erreur.

23

Dans cette perspective la mémoire centrale peut être vue comme un plan mémoire constituée avec la technologie actuelle avec un ensemble de « barrettes mémoire » connues sous le nom de SIMM ou DIMM (Single-Dual- Inline Mmemory Module). Dans le cas des barrettes DIMM les composants sont soudés des deux cotés de la barrette. Ce plan mémoire n’est qu’un ensemble de mémoire et ne peut rien faire de lui-même : ces cases doivent être gérées et cette gestion est assurée par un dispositif appelé contrôleur de mémoire. Pour faire une analogie en entreprise, la mémoire serait un stock (ou magasin) et le contrôleur serait le magasinier. Le travail le plus important est celui du contrôleur : lors d’une écriture en mémoire c’est à lui de réceptionner les données et les ranger dans l’ensemble des bistables correspondant à l’adresse mémoire qui lui aura été communiquée. Lors d’une lecture, c’est le contrôleur qui s’occupera de récupérer les données sur les sorties des bistables correspondant à l’adresse de lecture qui lui aura été communiquée. Les ordres d’écriture et de lecture viennent du processeur ce qui signifie que le contrôleur de mémoire est le partenaire privilégié du processeur : le principe de communication pour une écriture est de ranger le contenu d’un registre du processeur vers une adresse mémoire et pour la lecture, il s’agit pour le contrôleur de récupérer les données d’une adresse mémoire et de les transmettre au processeur afin de les ranger dans un registre interne. La communication entre le processeur et le contrôleur de mémoire est régie par un ensemble de règles que l’on appelle un protocole (de communication). (voir le chapitre Communication et Protocoles). Dans un version minimale le contrôleur de mémoire est une sorte d’unité (relevant de la logique combinatoire comme une UAL) spécialisée dans les opérations de lecture et d’écriture dans la mémoire centrale. Le circuit peut être relativement simple : il comporte essentiellement des circuits de décodage d’adresse pour sélectionner les bons bistables et une logique de pilotage des mémoires élémentaires pour l’opération de mémorisation. Dans le cas d’une RAM dynamique, le contrôleur comporte l’électronique de rafraîchissement de la mémoire. Dans d’autres cas, le contrôleur peut être très sophistiqué dans la mesure où l’on confère une certaine « intelligence » à ce magasinier. Vu les principes de localité (chapitre Gestion de la Mémoire) qui en première approximation indiquent qu’en cours d’exécution d’un programme on reste approximativement dans un même voisinage de mémoire, le contrôleur de mémoire peut essayer d’anticiper les demandes en provenance du processeur : sa complexité sera alors toute différente. Un contrôleur de mémoire cache est déjà un composant avec un bon niveau de complexité. Le schéma du contrôleur de mémoire présente ici de manière symbolique l’interface de communication avec le processeur : des bits pour décrire l’opération à faire (lecture ou écriture), des bits pour définir une adresse mémoire, des bits pour l’entrées des données (data in)lors d’une écriture, des bits (data out) pour la restitution des données lors d’une opération de lecture. Comme on ne fait pas de lecture et d’écriture simultanée, on utilise physiquement un même paquet de fils électriques pour les deux ensembles de bits. Organisation de la mémoire. Quand un processeur effectue une lecture ou une écriture, il donne l’adresse de l’octet en mémoire qu’il veut atteindre. Il adresse donc la mémoire avec toute la largeur du bus d’adresse (16, 32 bits). Du coté du contrôleur de mémoire il faut donc sélectionner l’octet correspondant dans tout l’espace adressable : il faut donc un système de décodage de l’adresse, qui à partir d’une adresse sur 32 bits, par exemple, sélectionne les bons circuits mémoire. La figure ci-dessous donne le schéma de principe du fonctionnement de l’accès en lecture et en écriture à un bit mémoire, l’accès à un octet étant similaire en regroupant 8 circuits. Pour qu’un

Plan mémoire

adresse

déco

deur

Data in

Data out

lecture /écriture

Contrôleur de Mémoire

Plan mémoire

adresse

déco

deur

Data in

Data out

lecture /écriture

Contrôleur de Mémoire

24

accès puisse se faire, il faut que le circuit soit validé du point de vue de son adresse. Ceci est fait par le décodeur d’adresse en positionnant AE (Address Enable) à vrai. La distinction entre une lecture et une écriture se fait au niveau de la commande W/R* (écriture si W est à vrai, c'est-à-dire le signal à 1 et lecture si R* est à vrai, c'est-à-dire le signal à 0). L’entrée et la sortie du bit de donnée (entrée sur D et sortie sur Q) se fait en utilisant le même fil du bus de données. L’utilisation du même fil pour transférer un bit dans un sens ou dans l’autre est faite à l’aide des deux circuits appelés buffer 3 états (tri-state Z buffer). La sortie du circuit est égale à l’entrée si le circuit est validé. Dans le cas contraire, le circuit est placé dans un état haute impédance dans lequel il ne transmet rien et se comporte sur le fil de sortie comme une très grande impédance (résistance) c'est-à-dire qu’il ne perturbe pas ce qui se passe sur ce fil. Toute la mémoire d’un ordinateur n’est pas constituée d’un seul bloc, mais comporte généralement plusieurs circuits (bancs). Le décodage d’une adresse serait théoriquement constitué d’un circuit décodeur à 32 entrées (bus d’adresse) avec 232 « fils » de sorties pour sélectionner le bon octet ! Concrètement, le décodage ne se fait pas en une étape, mais en plusieurs phases parallèles et hiérarchiques, chaque phase validant la suivante. Le décodeur est un circuit à n entrées et 2n sorties et une entrée de validation (Enable). Un décodeur simple 2 vers 4 est représenté ci-contre avec sa table de vérité. En général, le dernier étage de la suite de décodeur est interne au contrôleur de mémoire et porte sur 20 ou 24 bits (décodage par blocs de 1 Mo ou 16 Mo). Le proche avenir : les MRAM Mémoires RAM Magnétiques : mémoires non volatiles, ne perdent pas leur contenu à l’arrêt de la machine. A compléter …

E a b CS0 CS1 CS22 CS3

1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1

D

C

Q

W/R*

AE

Data In/OutD

C

Q

W/R*

AE

Data In/Out

N e

ntré

es

Enable

2NS

élec

tions

déc

od

eur

N e

ntré

es

Enable

2NS

élec

tions

déc

od

eur

A1

A2

En

CS0

CS1

CS2

CS3

A1

A2

En

CS0

CS1

CS2

CS3

25

Ebauche de séquenceur. Nous venons de voir comment la logique séquentielle et les automates nous ont amenés aux registres internes d’un processeur, à la mémoire centrale et son contrôleur. Il faut penser maintenant au cadencement (enchaînement automatique) de l’exécution des instructions dans l’UAL. Avant son exécution, une instruction se trouve en mémoire centrale et en première approche, le déroulement d’une instruction comporte 4 phases principales : la lecture du code opératoire de l’instruction et son décodage, les lectures des opérandes, l’exécution à proprement parlé et enfin l’écriture des résultats. Pour réaliser un séquenceur, il faut concrètement enchaîner les 4 phases d’une instruction par un circuit permettant de compter ces phases (compteur modulo 4) et un compteur d’instruction qui à la fin de l’exécution d’une instruction donne l’adresse de la suivante. Ce dernier compteur est appelé compteur de programme (Program Counter, PC) est réalisable simplement si l’on se place dans le cas où toutes les instructions ont la même taille en emplacement mémoire. Le cadencement initial (le temps qui progresse) est fourni par l’horloge externe. Une horloge est une variable logique qui prend alternativement les valeurs 0 et 1 pendant une durée finie. Cette succession de 0 et de 1 peut alors servir d’entrée à différents circuits compteurs ou autres. En théorie, il n’est pas indispensable que le processeur soit cadencé sur une base période (les premiers ordinateurs fonctionnait sans horloge, la fin d’une opération enclenchant la suivante), mais pour les besoins de communications et faciliter la synchronisation, l’horloge est un circuit électronique construit autour d’un oscillateur à quartz pour obtenir un signal périodique d’une grande précision et stabilité en fréquence. Pour faire la distinction entre l’horloge physique (le circuit à quartz) et l’horloge logique, les américains utilisent souvent le terme de « cristal ». Conclusion : le processeur L’objectif de ce chapitre qui était de montrer que le traitement des données d’une part et leur stockage d’autre part peut être entièrement décrit par des fonctions logiques est atteint, au moins dans les grandes lignes. Actuellement ce sont aussi les mêmes technologies (semiconducteurs) qui permettent de réaliser l’un et l’autre et éventuellement intégrer l’un dans l’autre (il est parfaitement courant d’intégrer une mémoire assez importante directement dans la microprocesseur). Nous sommes, à ce stade, en mesure de donner une première idée de l’architecture générale d’un ordinateur.

Compteur de phases

Séquenceur, Unité de Contrôle

Horloge

Compteur Ordinal

Commande mémoire

Commande UAL

P1

P2

P3

P4

adresse

Compteur de phases

Séquenceur, Unité de Contrôle

Horloge

Compteur Ordinal

Commande mémoire

Commande UAL

P1

P2

P3

P4

adresse

U A L

registre registre

registre

Unité de Contrôle

Plan mémoire

Contrôleur de Mémoire

Périphérique de

sortie

Contrôleur d’entrée

Périphérique d’entrée

Contrôleur de sortie

Unité Centrale

U A L

registre registre

registre

U A L

registre registre

registre

Unité de Contrôle

Plan mémoire

Contrôleur de Mémoire

Périphérique de

sortie

Contrôleur d’entrée

Périphérique d’entrée

Contrôleur de sortie

Unité Centrale

26

L’architecture générale fait apparaître un certain nombre d’unités qui ont déjà été présentées comme l’unité de contrôle et l’UAL (regroupées en un module appelé Unité Centrale, ou processeur), le contrôleur de mémoire (avec sa ROM et RAM). D’autres unités sont nouvelles : ce seront les contrôleurs d’entrées-sorties. Un ordinateur n’est utilisable que si nous pouvons lui communiquer des données à travailler et que s’il est en mesure de nous faire parvenir les résultats de ses traitements. Comme la mémoire RAM est nécessairement gérée par un dispositif appelé contrôleur de mémoire, il en est de même pour les équipements (les périphériques) qui nous permettent de communiquer (forme de lecture et d’écriture et donc une forte analogie avec la mémoire) avec le processeur en entrée et en sortie (par exemple un clavier et un écran) : ces équipements seront gérés par des contrôleurs d’entrées-sorties. Notion de bus. Les différents modules sont reliés par des liaisons (ensemble de fils) qui permettent le transfert de bits d’information d’un module à l’autre. A priori, l’on disposera ces liaisons bi-points (au sens où elles ne relient que deux modules) entre les modules qui le nécessitent. Ces liaisons bi-points sont efficaces car elles sont « privées » à deux modules et sont donc toujours disponibles. Elles ont aussi efficaces car des données peuvent circuler en parallèle sur plusieurs liaisons. Il y a cependant un inconvénient majeur à la mise en œuvre de ce type de liaisons : si le nombre de modules augmente, en particulier au niveau des périphériques le nombre de liaisons à établir peu devenir pharamineux et du coup utiliser toute la place disponible pour ne plus laisser de quoi mettre un module supplémentaire. Ce type de connexions constitue un handicap pour l’évolutivité de l’ordinateur. Toutes les liaisons sont remplacées par un moyen de communication unique, une sorte d’autoroute, sur lequel tous les modules viennent se brancher avec une connexion standard (une bretelle d’autoroute). Ce moyen de communication est le bus . Il est très général : il existe aussi bien à l’intérieur d’un processeur (non divulgué par le constructeur), d’un ordinateur (par exemple le bus PCI), de périphérique (bus SCSI) qu’au niveau d’un réseau d’ordinateur (le réseau Ethernet est un bus) Architecture d’un processeur : bloc-diagramme du processeur Intel 8080.

8

16

PC

SP

H L

D E

B C

A temp

F

Registre Instruction

Décodeur

Séquenceur Unité de Contrôle

Multiplex

Bus de Données

Bus d’Adresses

Bus de CommandeXtal

intel 8080 Bloc-Diagramme

UAL

8

16

PC

SP

H L

D E

B C

A temp

F

Registre Instruction

Décodeur

Séquenceur Unité de Contrôle

Multiplex

Bus de Données

Bus d’Adresses

Bus de CommandeXtal

intel 8080 Bloc-Diagramme

UAL

La figure ci-dessus donne un aperçu de l’architecture interne du processeur 8080 de la compagnie Intel. Le 8080 est un processeur 8 bits, c'est-à-dire qu’il travaille de manière privilégiée sur des mots de 8 bits : l’UAL manipule des octets, le bus de données a une largeur de 8 bits. Le bus

27

d’adresse a une largeur de 16 bits, ce qui signifie que la taille maximale du processeur est 216 octets, soit 65536 octets (64Ko). Toutes les opérations arithmétiques et logiques sont faites par le biais du registre A (Accumulateur) et un registre temporaire non accessible au programmeur. Le registre F (Flags, les drapeaux) héberge les indicateurs d’opérations comme le débordement, valeur nulle, positive, négative, … Certain registres sont des registres 8 bits mais peuvent être appairés pour constitué un registre de 16 bits, c’est le cas de BC, DE et HL. Enfin il y a deux registres de 16 bits directement liés aux adresses mémoire : PC (Program Counter ou compteur ordinal) et le pointeur de pile (Stack Pointer) indispensable pour la gestion des appels de procédures. Le processeur 8080 comportait 6000 transistors sur la puce (gravure 6 µ), fonctionnait avec une horloge de 2 Mhz et valait 150 $. Il est à l’origine de toutes les générations de processeur intel de la famille des x86, qui s’achève avec le processeur Pentium (environ 6 millions de transistors et une fréquence de 2 GigaHz). La première remarque qui s’impose est que le processeur ne comporte que très peu de registres (au nombre d’une dizaine). Toutes les données traitées par un programme devront passer par ces registres. D’autre part le processeur va chercher dans la même mémoire les instructions et les données : cette architecture est dite architecture de Von Neumann. Nous reviendrons plus en détail sur ce processeur, ou plutôt sur son successeur et compatible Z80 de la compagnie Zilog dans le cadre du chapitre « CPU et Modèle de Programmation ». Celui-ci est toujours encore l’un des microprocesseurs les plus vendus, la dernière version eZ80 intègre la pile protocolaire TCP/IP dans la puce. Carte Unité Centrale. La figure suivante donne les composants caractéristiques d’une carte unité centrale (par exemple appelée carte mère dans un PC) assurant les fonctionnalités de bases d’un ordinateur : l’unité de traitement, la mémorisation et la communication avec le mode extérieur.

Le bus interne du processeur définit le moyen de connexion du processeur avec ses contrôleurs compagnons (mémoire, E/S). Ce bus est relié via une interface au bus « machine », c'est-à-dire un

Bus de Données

Bus d’adresse

Bus de Commande

CPU Contrôleur de Mémoire

RAM

ROM Contrôleurs d’Entrées-Sorties

E/S

par

allè

les

E/S

séri

es E/S

inte

rru

ptio

ns

01001101

0100

1101

Inte

rfac

e B

US

« m

ach

ine

»

Bus de Données

Bus d’adresse

Bus de Commande

CPU Contrôleur de Mémoire

RAM

ROM Contrôleurs d’Entrées-Sorties

E/S

par

allè

les

E/S

séri

es E/S

inte

rru

ptio

ns

01001101

0100

1101

Inte

rfac

e B

US

« m

ach

ine

»

28

bus défini pour un ordinateur et non plus pour un processeur, par exemple le bus PCI, VME, …A l’aide de ce bus on pourra ensuite créer des extensions à l’ordinateur, extensions qui seront indépendantes du processeur de la carte unité centrale (par exemple une carte d’extension graphique avec un processeur de traitement de signal). Les contrôleurs d’entrées-sorties sont classés en trois catégories. Les entrées-sorties parallèles sont faites pour communiquer un ensemble de bits (8, 12, 16, 32) simultanément sur un canal de communication pour obtenir le transfert le plus rapide possible (interfaces disques, imprimantes, …). Par contre cette possibilité n’est offerte que sur des distances courtes (quelques dizaines de centimètres à quelques mètres suivant le débit). Les entrées-sorties séries servent à transmettre les données bit après bit sur une liaison à « un fil ». Les distances peuvent alors être plus grandes (de l’ordre du kilomètre pour le réseau Ethernet. Les entrées-sorties par interruption correspondent à la signalisation d’un événement dans le temps. Par exemple le passage d’un badge devant un lecteur signale l’événement « détection d’une carte » par l’intermédiaire d’une interruption, les informations de la carte pouvant ensuite être lues par une entrées-sorties parallèle. Et pour se changer les idées…

The Sex of the Computer (from Jeanie Ramsay) A language instructor was explaining to her class that in French, nouns unlike their English counterparts, are grammatically designated as masculine or feminine. "House," in French, is feminine-"la maison." "Pencil," in French, is masculine-"le crayon." One puzzled student asked, "What gender is computer ?" The teacher did not know, and the word wasn't in her French dictionary. So for fun she split the class into two groups appropriately enough, by gender and asked them to decide whether "computer" should be a masculine or feminine noun. Both groups were required to give four reasons for their recommendation. The men's group decided that computers should definitely be of the feminine gender ("la computer"), because:

1. No one but their creator understands their internal logic. 2. The native language they use to communicate with other computers is incomprehensible to everyone else. 3. Even the smallest mistakes are stored in long-term memory for possible later retrieval. 4. As soon as you make a commitment to one, you find yourself spending half your pay check on accessories for it.

The women's group, however, concluded that computers should be masculine ("le computer"), because: 1. In order to get their attention, you have to turn them on. 2. They have a lot of data but they are still clueless. 3. They are supposed to help you solve problems, but half the time they ARE the problem. 4. As soon as you commit to one, you realize that if you'd waited a little longer, you could have gotten a better model.

The women won L .

Intel 4004

Mémoire Circulante de la calculatrice programmable Monroe Epic 3000

29

Une mémoire pas comme les autres… on en pincerait pour elle ! Avant d’en arriver aux mémoires DRAM voisines du Gigaoctet dans les machines actuelles, la mémoire centrale de l’ordinateur a vu passer différentes technologies. L’une d’entre elles, peut-être l’une des plus ingénieuses, a été la ligne à retard. Le principe général consiste à considérer qu’une onde est capable de mémoriser une information, sous forme de signal, pendant tout le temps de sa propagation sur son support. Si, par un artifice, on arrive à rendre les extrémités du support suffisamment proches, alors on peut réinjecter le signal sortant du support sur son entrée en créant par là même une boucle de circulation. Ce phénomène existe dans la nature lorsque qu’un paysage de montagne renvoi l’écho qui lui-même est renvoyé et ainsi de suite, et ainsi de suite, et ainsi de suite … L’atténuation de tout signal fait que le phénomène s’estompe et le signal disparaît peu à peu. La mémoire circulante devient effective si à la sortie du support le signal est régénéré à sa valeur initiale. Ce principe a été utilisé assez tôt dans le développement des ordinateurs avec l’utilisation d’un long tube rempli de mercure (1950, EDVAC avec 128 tubes de mercure d’environ 1,5 m et une capacité de 384 bits) dans lequel se propageait des ondes sonores, mais le système s’est vraiment répandu, dans les années soixante, avec les lignes à retard métallique, sorte de corde à piano que l’on pince à l’une des extrémités pour coder une information. Une ligne à retard est un fil réalisé en alliance nickel-acier-titane d’environ 29 mètres enroulé en spires maintenues séparées et au centre desquelles on place les deux extrémités du fil avec leur électronique associée. A l’émission, l’extrémité du fil comporte une bande magnétostrictive qui permet de lui appliquer à l’aide d’une bobine d’électro-aimant une onde de torsion acoustique qui se propage sur le fil à la vitesse de 2950 m/s, soit un temps de propagation de 9,8 ms. En inversant le courant dans la bobine on crée une onde de torsion de sens opposé. La vitesse à laquelle on arrive à créer ces ondes de torsion, avec alternance de sens pour représenter les 1 et les 0, définit la capacité de mémorisation de la ligne. La fréquence maximum d’émission obtenue a été de 1 MHz, d’où une capacité maximale de 9800 bits, soit un peu plus de 1Ko. A l’extrémité de réception, la déformation de l’onde de torsion génère un signal électrique dans une bobine de détection (de sens opposé en fonction du sens de la torsion) retransformé en 1 et en 0. Les bits ainsi reconstitués entre dans un registre à décalage de 8 bits qui sert de « fenêtre » de lecture ou d’écriture. Lorsque les 8 bits de l’octet voulu sont dans le registre à décalage, ils peuvent être lus, ou remplacés par un nouvel octet pour la réécriture. La mémoire ainsi créée est une mémoire séquentielle gérée en FIFO (First In First Out) : il faut repérer l’octet d’adresse 0 comme début de mémoire et réaliser un comptage jusqu’à obtenir l’octet adressé. Cette mémoire est aussi considérée comme dynamique : il faut un circuit de rafraîchissement pour régénérer l’information mémorisée. Ce type de mémoire a été largement utilisé dans les calculatrices de bureau et il a aussi eu des applications mais en électronique analogique dans les « chambres de réverbération et d’écho » d’équipement HiFi.

Le premier microprocesseur, le 4004 d’Intel. En 1968, Gordon Moore, Robert Noyce (qui ont travaillé avec William Shockley un des inventeurs du transistor) et Andrew Grove, des « anciens » de Fairchild Semiconductor, fondent la société Intel avec pour but de fabriquer à moindre coût des mémoires à semi -conducteurs, technologie beaucoup plus coûteuse à l’époque que les mémoires à tores de ferrite alors en usage. La vente des mémoires démarrant difficilement, Intel acceptent de travailler sur des circuits à façon. Ainsi, en 1969, Busicom, un fabricant japonais commande à Intel une famille de calculateurs programmables à circuits intégrés. Ted Hoff, ingénieur fraîchement embauché, conçoit, avec l’aide de Federico Faggin, les quelques circuits multifonctions et y ajoute une mémoire programmable. Pour la réalisation, Ted Hoff a trouvé plus intéressant de concevoir un circuit à usage général programmable à partir d’informations mises en mémoire. Ainsi naquit le 4004, le premier microprocesseur, avec une mémoire de 640 octets, 45 instructions travaillant sur des mots de 4 bits, cadencé à 108 KHz, intégrant 2300 transistors sur 14 mm2 de silicium pour environ 60 000 opérations par seconde (le tout pour 200$). Pour l’anecdote, la société japonaise était propriétaire des droits du circuit, mais les physiciens d’Intel, qui étaient apparemment aussi déjà de bons gestionnaires rachetèrent les droits lorsque la société eut des difficultés financières… Aujourd’hui Intel est l’une des plus grosses sociétés au monde. Mais concrètement aucune application n’utilise réellement le 4004 comme étant une version miniaturisée d’un ordinateur. Fin 1971 Gary Kildall découvre, en lisant le magazine Electronic News, la publicité faite par Intel pour le 4004 et eut l’idée de franchir ce pas. Il achete un processeur, il contacte Intel et conçu pour eux les premiers développements logiciels (langage PL/M). En 1972, la société peut proposer son premier processeur 8 bits, le 8008 qui sera bientôt suivi du 8080 (1974). Un des concepteurs du 8080, Federico Faggin, quitta Intel pour fonder la société Zilog (1974) et réaliser un compatible amélioré du 8080 : le Z80 (registres d’index, transfert en bloc, …). Celui-ci supplanta rapidement le processeur d’Intel : le Z80 et le Z8 sont vendus à plus d’un milliard d’exemplaires (incorporés par exemple dans les télécommandes de télé). Une version, eZ80, intégrant la pile protocolaire TCP/IP est actuellement proposée pour les solutions embarquées internet.