Architecture des Ordinateurs
Chapitre 2 - Fonctions Logiques et Circuits
Copyright 2013 - Michaël Mrissa
Objectifs
Ordinateur
traitement de l'information
Mémorisation de l'information
Moyens
Fonctions logiques réalisées par des circuits électroniques
Algèbre de Boole & Logique
Logique des propositions
Proposition
C'est un énoncé qui peut être vrai (V) ou faux (F).Connecteurs (ou opérations)
Relient des propositions pour en élaborer une nouvelle
Connecteurs usuels : ¬ (non logique), ∧ (et logique) ∨ (ou logique)
Une opération est définie par une 'Table de Vérité'
Variable Booléenne
V et F deviennent 1 et 0
∧ et ∨ deviennent . et + (produit et somme)
On parle de fonction logique
Fonctions Logiques
Fonctions logiques à 2 variables
Les fonctions 'utiles'
Algèbre (Boole)
Résultats fondamentaux
Théorème des constantes : a + 0 = a et a . 0 = 0 et a + 1 = 1 et a . 1 = a
Idempotence : a + a = a et a . a = a
Complémentation : a + ¬a = 1 et a . ¬a = 0
Commutativité : a + b = b + a et a . b = b . a
Distributivité sur OU : a + (b.c) = (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.cThéorème de De Morgan : ¬(a.b) = ¬a + ¬b et ¬(a+b) = ¬a . ¬b
Définition du Ou Exclusif : a ⊕ b = ¬a . b + a . ¬b
Traitement de l'information
Logique Combinatoire
Circuits combinatoires
Des circuits physiques aux fonctions logiques
Des notations alternatives existent...
Traitement de l'information
Logigramme :
Schéma de fonctions composées
Exemple OU Exclusif : XOR
Les sorties évoluent simultanément avec les entrées (au temps de propagation près)
Circuits élémentaires
Circuits électroniques et transistors
Circuit qui réalise la fonction ¬ (non) (inverseur)
Transistor en 'Tout Ou Rien' (TOR)
Circuits et fonctions NOR
Circuits élémentaires
Circuits et fonctions NAND
Intégration
SSI (Small Scale Integration) 102 portes logiques
VLSI (Very Large Scale Integration) entre 105 et 107 portes
ULSI (Ultra Large Scale Integration) > 107 portes
Synthèse de Circuits
Objectif :
D'une table de vérité, à un circuit réalisant la fonction (en logique combinatoire)
Synthèse en trois étapes
1 - Spécification de la fonction sous la forme d'une table de vérité
2 - Synthèse du circuit avec une méthode du type 'minterms'
3 - Réduction ou simplification du circuit avec, par exemple, le diagramme de Karnaugh
Synthèse de Circuits
Transformation de la fonction logique
Mise en forme 'canonique'
Se ramener aux 3 opérateurs de base : OU, ET et NON.
Deux méthodes équivalentes:
minterms : décrire la fonction sous la forme d'un « OU de ETs » (somme de produits)
maxterms : décrire la fonction sous la forme d'un « ET de OUs » (produit de sommes)
Les minterms
Transformation avec les équations logiques (calcul automatique)
Exemple : Z = a ⊕ b = ¬a b + a ¬bTransformation graphique (visuelle) uniquement valable pour les exemples simples
Synthèse de Circuits
Les Minterms (par l'exemple)
Fonctions à 3 variables (a, b, c) : 8 combinaisons possibles Ci
Définir 8 produits logiques, les minterms Pj avec
valeur à 1 lorsque i=j
valeur à 0 pour toutes les autres combinaisons
Synthèse de Circuits
Principe de la transformation
Lister toutes les combinaisons de la table où la sortie est à 1
Pour chaque combinaison (ligne) donner le produit Pj équivalent
Description complète de la fonction
somme des produits Pj de toutes les lignes j pour lesquelles la sortie est à 1
de plus, la fonction prend la valeur 0 pour toutes les autres combinaisons, exactement comme les produits Pj retenus
Synthèse de Circuits
Application pratique
Lister toutes les combinaisons avec la sortie S à 1.
Somme logique des termes pour chaque S=1 en prenant :
chaque variable d'entrée telle quelle si sa valeur est 1 (a=1 => a )
sinon elle est complémentée (a=0 => ¬a )
Exemple : Trois variables a, b et c, 8 sorties de P0 à P7
S = P0 + P2 + P7 donnez la formule mathématique
S = ?? + ?? + ??
Synthèse de Circuits
Forme normale (canonique)
Objectif : décrire la fonction définie par une table de vérité à l'aide de circuits de base (ET, OU, NON)
Moyen : méthode des minterms :
somme logique des termes pour chaque sortie valant 1
chaque variable d'entrée est prise telle quelle si sa valeur est 1 sinon elle est complémentée.
Application au XOR
Z = a ⊕ b = ¬a.b + a.¬b
Diagramme de Karnaugh
Réduction de la forme canonique (redondance)
Principe : de la table de vérité vers le diagramme (de Karnaugh) :
chaque case du diagramme représente une ligne de la table de vérité;
on met 1 dans les cases où la fonction est vraie
simplification (uniquement applicable avec un nombre faible de variables) :
on regroupe tout ensemble de cases à 1 adjacentes sur une ligne (ou une colonne) de cardinal égal à une puissance de 2 (dans l'ordre 2, 4, 8). Les bords sont adjacents et les recouvrements sont autorisés. Les cases isolées restent telles quelles.
Exemple de dimension 2
S = ¬ab + a¬b + ab se simplifie en S = a + b
car ¬ab + a¬b + ab = ¬ab + a¬b + ab + ab = (¬a + a)b + a(¬b + b) = b + a = a + b
Diagramme de Karnaugh
Justification
La simplification de Karnaugh repose sur les relations suivantes:
Comme b + ¬b = 1 , alors a = a ( b + ¬b) = ab + a¬b
Méthode : mettre en évidence les regroupements de la forme ( b + ¬b).
Construction du diagramme (code de Gray)
Le tableau est construit en positionnant les cellules
D'une case à une autre, une seule variable doit changer de valeur
Disposition des lignes et des colonnes suivant le code de Gray.
Une cellule contient la valeur de la fonction pour la combinaison ligne-colonne.
Diagramme de Karnaugh
Cas de la fonction à 3 variables
Table de vérité : S = ¬a¬b¬c + ¬ab¬c + abc
Donnez le logigramme
Réduction
S = ¬a¬c + abc
Donnez le logigramme
Cas des cases indifférentes (don't care cells)
'Marquer' les cases indifférentes par X
Remplacer les X par 0 ou 1 pour optimiser la réduction
Exemple 1 ~ voteur
Système de vote à n entrées binaires
la sortie M vaut 0 ou 1 suivant une majorité de 0 ou de 1 en entrées
Traitons le cas n=3
Exemples de fonctions utiles
Générateur de parité impaire
Utilisation du XOR comme porte de base
z = ¬a ¬b ¬c + ¬a b c + a ¬b c + a b ¬c
= ¬a [¬b¬c + bc] + a [¬bc + b¬c]
= ¬a ¬[ b ⊕ c ] + a [ b ⊕ c]
= ¬[a ⊕ [ b ⊕ c ]] = ¬[a ⊕ b ⊕ c]
Exemples de fonctions utiles
Comparateur (bit à bit)
2 entrées (à comparer)
3 sorties (Egalité, Supérieur, Inférieur)
Utilisation du XOR
Exemples de fonctions utiles
Multiplexeur : exemple 4 vers 1
S = ¬a¬bD0 + ¬abD1 + a¬bD2 + abD3
a, b sont des variables de commandes
D0 à D3 sont les données d'entrées
Exemples de fonctions utiles
Démultiplexeur : exemple 1 vers 4
4 tables de vérités :
D0 = abE D1 = abE D2 = abE D3 = abE
a, b sont des variables de commandes
E est l'entrée et D0 à D3 sont les sorties.
Exemples de fonctions utiles
Additionneur
Cellule addition 1 bit
Exemples de fonctions utiles
Additionneur 4 bits
Unité Arithmétique et Logique 1 bit
UAL (très simplifiée) 8, 16, 32, 64 bits
Généralisation de l'UAL 1 bits
opérations arithmétique sur les entiers
opérations logiques sur ensemble de bits
procure une partie du jeu d'instructions du processeur
symbolisme graphique parfois utilisé "grand V"
Unité Arithmétique et Logique 1 bit
Source : Tanenbaum
Mémorisation de l'information
Circuits Combinatoires
pas de rétroaction : pas de retour des sorties sur les entrées
les sorties ne dépendent que des entrées au même instant
s'appuient sur l'algèbre de Boole
Circuits séquentiels
Introduction du temps, notion de mémoire
Temps modélisé par une variable Q
Discrétisation du temps Qt, Qt+1
Rétroaction : sortie dépend de la séquence précédente
Effet de mémoire
S'appuient sur la théorie des automates finis (FSM: Finite State Machine)
Circuits séquentiels
Mémoire élémentaire et bistable
Mémoire 1 bit avec un circuit combinatoire
Faire une rétroaction (Q+ = Qt+1)
Notion de bistable (bistable RS ou SR latch)
Mémorisation d'une valeur voulue (1 bit)
Circuits séquentiels
Principe de fonctionnement
Q+ est déterminé à partir de Q, R et S : Q+ = ¬R.S + ¬R.¬S.Q
On envoie 1 sur Reset puis on relâche : mise à 0 de Q
On envoie 1 sur S puis on relâche : mise à 1 de Q
Table de vérité (en entrée : R, S et état précédent Q)
Circuits séquentiels
Bistable D
Mémorisation d'une variable d'un bit :
Transfert l'entrée D <=>Q
D=0 <=> (R=1, S=0) <=> Q+ = 0
D=1 <=> (R=0, S=1) <=> Q+ = 1
Problème : maintient du signal
Solution : ajout d'une horloge
Circuits séquentiels
Bistable D avec horloge (gated D latch)
Entrées
D entrée de données
C entrée de commande
Horloge à 1
Donnée envoyée par D stockée en mémoire
Horloge à 0
Donnée mémorisée gardée en mémoire
Circuits séquentiels
Validation par Horloge
Octet : 8 bistables D
Où la trouve-t-on ? Mémoire processeur, caches
Circuits à mémoire
Registre 8 bits
RAM Random Access Memory
SRAM statique : rapide, chère
Équivalent à un bistable D
Circuits à mémoire
DRAM dynamique : bon marché, moins rapide
1 transistor et condensateur
- Remplissage du condensateur, qui se vide rapidement
- Nécessite un rafraîchissement, "cadence" de la DRAM, problèmes de chauffe
Où la trouve-t-on ? Mémoire centrale de l'ordinateur les "barrettes" de RAM
Circuits à mémoire
Mémoire « vive » vs mémoire « morte »
RAM appelée aussi mémoire « vive »
- Volatile, pas de courant = perte de données
- Contenu indéterminé à la mise sous tension
- Destinée à la manipulation des variables
ROM appelée mémoire « morte »
- Contenu a priori non modifiable (démarrage du dispositif)
- Chargement système d'exploitation, redirection vers support
- Téléphone, machine à laver, four micro ondes, etc...
- BIOS, EFI, UEFI => démarrage PC
Tous sont inscrits sur de la mémoire morte
Circuits à mémoire
ROM Read Only Memory
PROM, EPROM, ...Flash
amorce de démarrage (boot), BIOS
Erasable PROM (EPROM)
Extraire du support et reprogrammer avec des ultraviolets + tensions électriques
Electronically Erasable PROM (EEPROM)
Durée de conservation de l'information : 10 ans
Programmation directe sur le support, changement partiel possible
Utilisé comme mémoire secondaire moins rapide que de la RAM
recopie vers RAM si appelé plusieurs fois
Circuits à mémoire
Mémoire Flash
Flash NAND 1989 Toshiba, évolution EEPROM
- Lecture écriture assez rapides
- Cycle de vie limité en nombre d'écritures (100 000 à 1 million)
Écriture par blocs (512 octets, 1 secteur disque)
- Utilisée dans les SSD (solid state drive)
- Problème d'usure : solution => wear levelling (fonction trim)
- Importance du contrôleur de disque
SLC (single level cell) ou MLC (multi level cell)
- 2 ou plusieurs niveaux de charge par cellule
- Compromis compacité/efficacité
Le futur... FRAM (Ferro-électrique) ?
Avantages
Consomme moins d'énergie
Plus de cycles de lecture/écriture (100 billions?)
Plus rapide (100x plus que la mémoire flash?)
Inconvénients
Coût de production
Difficilement intégrable
Moins de capacité de stockage
Formats de mémoire
Formats les plus courants
SIMM : Single in-line memory module
DIMM : dual in-line memory module
SoDIMM : small outline dual in-line memory module
Mémoires grand public connues
DDR2 SDRAM
Double Data Rate 2-Synchronous Dynamic Random Access Memory
DDR = transferts sur fronts montant et descendant des impulsions d'horloge
DDR3 SDRAM
Double Data Rate 3rd generation Synchronous Dynamic Random Access Memory
Idem mais largeur de bus 8 bits, consommation électrique plus faible
Mémoire Centrale
'Contrôleur' de mémoire
Opérations lecture/écriture
Mémoire Centrale
'Contrôleur' de mémoire
Sélection de 'case mémoire'
