Support de cours d’Algèbre binaire et Circuits logiques
Université Mohammed V
Faculté des Sciences
Département de Mathématiques et Informatique
Filière : SMI
Algèbre binaire et Circuits logiques
(2007-2008)
Prof. Abdelhakim El Imrani
Plan
1.Algèbre de Boole 2.Circuits logiques 3.Circuits combinatoires 4.Circuits séquentiels
Algèbre de Boole George Boole (1815-1864) est un mathématicien autodidacte validité du raisonnement) et la représentation symbolique utilisée en mathématique.•Algèbre binaire anglais qui voulait faire un lien entre la logique (étude de la •Chapitre 1 Il a écrit deux ouvrages sur le sujet :•Écriture et simplification des fonctions • MathematicalAnalysisofLogiclogiques (1847) • An Investigation oftheLawsofThought(1854) Ces travaux n’ont pas connu d’intérêt particulier auprès de la communauté mathématique et scientifique de son époque, mis à part chez les logiciens |
Algèbre de Boole • C’est 70 ans plus tard que les travaux de Boole gagnent l’intérêt de tous, lorsque Claude Shannon fait le lien entre l’algèbre de Boole et la conception des circuits. • Claude Shannon montre que l’algèbre de Boole peut-être utilisée pour optimiser les circuits. Cette nouvelle avenue de recherche va ouvrir la voie à l’ère numérique. Æ « En utilisant l’algèbre de Boole avec le système binaire, on peut concevoir des circuits capables d’effectuer des opérations arithmétiques et logiques • Boole repose sur des axiomes, des postulats et des théorèmes qu’il faut connaître par coeur ! |
Algèbre de Boole Propositions vraie ou faussesAlgèbre de Boole et opérateurs sur ces préposition • Systèmes binaires: Vrai=1, Faux=0 • C’est le cas des systèmes numériques (circuits logiques) |
• L’ordinateur est constitué de circuits logiques • Élément de base est le transistor, deux états: Bloqué=0, Conducteur=1. Transistor Æ Porte logique Æ Circuit logique Æ Unité d’un système informatique |
Algèbre binaireDéfinitions: • États logiques: 0 et 1, Vrai et Faux • Variable logique: Symbole pouvant prendre comme valeur des états logiques (A, b, c, ...) • Opérateurs logiques: Or, And, Not, ... • Fonction logique: Expression de variables et d’opérateurs logiques. ( f = not(a) or (b OR c and d) |
Éléments de base • Variables d’entrée – Les variables d’entrée sont celles sur lesquelles on peut agir directement. Ce sont des variables logiques indépendantes. • Variable de sortie – Variable contenant l’état de la fonction après l’évaluation des opérateurs logiques sur les variables d’entrée. • Simplification d’une fonction logique – Trouver la représentation (l’écriture) la plus simple de la fonction réalisée: Algèbre de Boole |
Algèbre de Boole sur [0,1] = algèbre binaire Structure d’algèbre de boole • 2 lois de composition interne (Or, And) • 1 application unaire (Not) 2 Lois de Composition Interne : ET, OU Somme (OU, Réunion) s = a + b = a or b Produit (ET, intersection) s = a . b = ab = a and b Nb: a+b se lit « a OU b » pas « a PLUS b » Application unaire : Not (complémentation, inversion) s = a = not(a) NB: a se lit « a barre » ou « non a » |
Fonctions logiques Fonction logique à n variables f(a,b,c,d,...,n) [0,1]n [0,1] - Une fonction logique ne peut prendre que deux valeurs (0, 1) - Les cas possibles forment un ensemble fini (card = 2n) La table de fonction logique = table de vérité Définition : (a, b, c, ..., n) = vecteur d’entrée | |||||||||||||||||||||||||||||
Table de vérité • Table de vérité: Enumération ligne par ligne des valeurs prises par f en fonction des valeurs de ses paramètres. Or And Not s = a + b s = a . b s = a S est vrai si a OU b S est vrai si a ET b S est vrai est vrai. sont vrais. si a est faux
|
Notes sur les tables de vérité f (a, c, d, .., n) fonction logique à N entrées sera représentée par : • une table à 2N lignes
1 1 1 1 | ||||||||||||||||||||
Propriétés • Commutativité • a+b = b+a • a.b = b.a • Associativité • a+(b+c) = (a+b)+c • a.(b.c) = (a.b).c • Distributivité • a.(b+c) = a.b+a.c • a+(b.c) = (a+b).(a+c) | • • | Idempotence • a+a = a • a.a = a Absorption • a+a.b = a • a.(a+b) = a |
Démonstration distributivité
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Propriétés (2) • Élément neutre • a+0 = a • a.1 = a • Élément absorbant • a+1 =1 • a.0 = 0 • • Inverse • a+a = 1 • a.a = 0 | Théorème de DE Morgan • a+b = a . b • a.b = a + b |
Équations logiques On exprime f(a, b, c, ...) par une expression en a, b, c.. et des opérateurs logiques. Exemple: f = a+b.c.(d+e) Principe de dualité: Une expression reste vraie si on interverti les 1 par des 0 et les ET par des OU Exemple: si a+b=1 alors a.b=0 Je suis riche si je suis bien payé et que je ne dépense pas tout mon argent = Je suis pauvre si je ne suis pas bien payé ou que je dépense tout mon argent | ||||||||||||||||||||||
Les opérateurs NAND, NOR
s = a.b s = a+b S est vrai si a OU b S est vrai si ni a, ni b est faux. ne sont vrais. NAND (No-AND) NOR (No-OR ou NI) |
L’opérateur : XOR
s = a b = a.b + a.b S est vrai si a OU b est vrai mais pas les deux. XOR (Ou-Exclusif) vaut 1 si a est différent de b Opérateur de différence (disjonction) | ||||||||||
Propriétés du XOR XOR est associatif s = a b c ..... n vaut 1 si le nombre de variable à 1 est impaire. s=a b a b a b a? = ? = ? = XNOR b XNOR = XOR vaut 1 si a b= a 1 = a a 0 = a a c b c? = ? ? =a b Propriétés a x b? = ? = ?x a b |
Écriture des équations logiques Définitions: Apparition d’une variable = Lettre Produit de variables sous forme simple ou complémentées = Monôme Somme de monômes = Polynôme z = a + b.c.(d + e) Expression algébrique = a + b + c + (d + e) Développement = a + b + c + d . e Polynôme de 4 monômes de 1 et 2 lettres | ||
Fonctions logiques et formes canoniques f fonction logique de n variables | ||
• On appelle «minterme» de n variables, l’un des produits de ces variables ou de leurs complémentaires. • On appelle «maxterme» de n variables, l’une des sommes de ces variables ou de leurs complémentaires. | exemple n = 4 variables {a b c d, , , } m = a b c d? ? ? est un minterme m = a ?b c d? ? est un autre minterme m = a b c?? n'est pas un minterme M = + + +a b c d est un maxterme M = + + +ab c d est un autre maxterme M a b c= + + n'est pas un maxterme | |
Formes canoniques Une fonction est sous forme canonique (ou normale) si chaque terme contient toutes les variables. L’écriture sous forme canonique est unique. Exemples : f x y z( , , ) = x y z. . + x y z. . + x y z. . Minterme Première forme canonique ou forme normale disjonctive f x y z( , , ) = + +(x y z).(x + +y z) Maxterme Deuxième forme canonique ou forme normale conjonctive |
Formes canoniques Si la fonction n’est pas sous forme normale i.e. une des variables (au moins) ne figure pas dans un des termes La fonction est sous une forme simplifiée f x y z( , , ) = xyz + xyz + xyz Première forme canonique = xy z( + +z) xyz Forme simplifiée = y x( + xz) Forme simplifiée = y x( + z) Forme simplifiée |
Formes canoniques: Choix Première forme canonique = expression des 1 de la fonction Deuxième forme canonique = expression des 0 de la fonction Les deux formes canoniques sont équivalentes On choisit celle qui donne le résultat le plus simple peu de 0 => deuxième forme / peu de 1 => première forme |
Simplification des fonctions Objectif : Fabriquer un système • à moindre coûtMéthodes : Algébriques • rapide Graphiques • fiable Programmables • peu consommateur Résultat : on cherche la forme minimale d’une fonction nombre minimal de monômes/nombre minimal de lettre par monôme Possibilité de plusieurs formes minimales: formes équivalentes |
Simplification algébrique Applications des principes et propriétés de l’algèbre de Boole Identités remarquables : 1 a b. + a b. = b(a+b) (a+b)=b. 2 a + a.b = aa.(a+b) = a 3 a + a.b = a+ba.(a + =b) a b. Démonstrations : 1 et 2 trivial 3 : a ab+ . =aa ab.+. +aa. +ab a a a b a b. = +( ).( + = +) a 0 | |
Simplification algébrique Règles de simplification : (Mintermes adjacents = 1 seule variable qui change) 1 : Deux mintermes adjacents Il reste l’intersection commune 1’: Deux maxtermes adjacents Il reste la réunion commune a b c a b c a b c c. . + . . = . .( + =) a b. (a b c a b c+ + ).( + + = +) (a b c c)( + = +) a b 2: On peut ajouter un terme déjà existant à une expression logique. Æ pas de coefficient en algèbre de Boole. 3: On ne change pas le résultat en multipliant l'un des termes par 1 ou en ajoutant 0.
|
Exercice 2 Considérons la fonction F définie par la table de vérité suivante :
Mintermes F=x yz+x yz+x yz+x yz F = x y z+ x y z+ x y z+ x y z = (x y z+ x y z)+(x y z+ x y z)+(x y z+ x y z) = y z (x + x)+ x z (y+ y)+ x y (z+z) = x y+ y z+z x | ||||||||||||||||||||||||||||||||||||
Exercice 3 • On désire concevoir un circuit qui permet de gérer les notes des examens, on donne: Examen final (45 %), Examen Partiel (35 %), TPs (20 %). • Un étudiant est admis s’il dispose d’un pourcentage >= 55 %). – Exemple: Final=11, Partiel=8, Tps=10 Æ F=1, P=0, T=1 ? Pourcentage = 65 % Æ R=1 (étudiant admis). • Donner la table de vérité. • Donner la fonction logique correspondante. Simplifier le fonction obtenue. |
Simplification graphique: Karnaugh
• La méthode de Karnaugh permet de visualiser une fonction et d’en tirer naturellement une écriture simplifiée.
• L’élément de base de cette méthode est la table de Karnaughqui représente toutes les combinaisons d’états possibles pour un nombre de variables donné.
• La table de Karnaugh est un outil graphique qui permet de simplifier de manière méthodique des expressions booléennes.
• La construction des tables de Karnaugh exploite le codage de l’information et la notion d’adjacence
Karnaugh – simplification graphique Principe: Mettre en évidence sur un graphique les mintermes (ou maxtermes) adjacents. Transformer les adjacences logiques en adjacences «géométriques». Trois phases: Transcrire la fonction dans un tableau codé, recherche des adjacents pour simplification équations des groupements effectués Description: Table de vérité vs Tableau de Karnaugh 1 ligne 1 case n variables 2n cases |
Simplification graphique Règles de simplification 1 : Les groupements comportent une puissance de deux cases, 2 : Les 2k cases forment un rectangle, 3 : On élimine variable(s) qui change(nt) d’état Groupement de 2k cases Æ On élimine k variables 2 cases Æ on élimine 1 variable; 4 cases Æ on élimine 2 variables; 8 cases Æ on élimine 3 variables; 4 : Il faut utiliser au moins une fois chaque 1, le résultat est donnépar la réunion logique de chaque groupement, 5 : Expression minimale si : • les groupements les plus grands possibles • utiliser les 1 un minimum de fois |
Exemple 2
Premier groupement: On élimine B Deuxième groupement: On élimine A Æ S = A + B |
Conception d’un circuit logique
1. Identifier les entrées et les sorties de la fonction.
2. Construire la table de vérité.
3. Identifier la fonction à partir de la table devérité.
4. Simplifier la fonction.
5. Dessiner le schéma du circuit.