Carte de Karnaugh - Karnaugh map
La carte de Karnaugh ( KM ou K-map ) est une méthode de simplification des expressions algébriques booléennes . Maurice Karnaugh l'a introduit en 1953 comme un raffinement du diagramme de Veitch 1952 d' Edward W. Veitch , qui était une redécouverte du diagramme logique de 1881 d' Allan Marquand , alias diagramme de Marquand, mais avec un accent désormais mis sur son utilité pour les circuits de commutation. Les cartes de Veitch sont donc également connues sous le nom de diagrammes de Marquand-Veitch et les cartes de Karnaugh sous le nom de cartes de Karnaugh-Veitch ( cartes KV ).
La carte de Karnaugh réduit le besoin de calculs approfondis en tirant parti de la capacité de reconnaissance de formes des humains. Il permet également d'identifier et d'éliminer rapidement les conditions de concurrence potentielles .
Les résultats booléens requis sont transférés d'une table de vérité sur une grille à deux dimensions où, dans les cartes de Karnaugh, les cellules sont ordonnées en code Gray et chaque position de cellule représente une combinaison de conditions d'entrée. Les cellules sont également appelées minterms, tandis que chaque valeur de cellule représente la valeur de sortie correspondante de la fonction booléenne. Des groupes optimaux de 1 ou de 0 sont identifiés, qui représentent les termes d'une forme canonique de la logique dans la table de vérité originale. Ces termes peuvent être utilisés pour écrire une expression booléenne minimale représentant la logique requise.
Les cartes de Karnaugh sont utilisées pour simplifier les exigences logiques du monde réel afin qu'elles puissent être mises en œuvre en utilisant un nombre minimum de portes logiques. Une expression de somme de produits (SOP) peut toujours être implémentée à l'aide de portes ET alimentant une porte OU , et une expression de produit de sommes (POS) conduit à des portes OU alimentant une porte ET. L'expression POS donne un complément de la fonction (si F est la fonction alors son complément sera F'). Les cartes de Karnaugh peuvent également être utilisées pour simplifier les expressions logiques dans la conception de logiciels. Les conditions booléennes, telles qu'elles sont utilisées par exemple dans les instructions conditionnelles , peuvent devenir très compliquées, ce qui rend le code difficile à lire et à maintenir. Une fois minimisées, les expressions canoniques de somme de produits et de produit de somme peuvent être implémentées directement à l'aide des opérateurs logiques ET et OU.
Exemple
Les cartes de Karnaugh sont utilisées pour faciliter la simplification des fonctions d' algèbre booléenne . Par exemple, considérons la fonction booléenne décrite par la table de vérité suivante .
UNE | B | C | ré | ||
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 0 |
2 | 0 | 0 | 1 | 0 | 0 |
3 | 0 | 0 | 1 | 1 | 0 |
4 | 0 | 1 | 0 | 0 | 0 |
5 | 0 | 1 | 0 | 1 | 0 |
6 | 0 | 1 | 1 | 0 | 1 |
7 | 0 | 1 | 1 | 1 | 0 |
8 | 1 | 0 | 0 | 0 | 1 |
9 | 1 | 0 | 0 | 1 | 1 |
dix | 1 | 0 | 1 | 0 | 1 |
11 | 1 | 0 | 1 | 1 | 1 |
12 | 1 | 1 | 0 | 0 | 1 |
13 | 1 | 1 | 0 | 1 | 1 |
14 | 1 | 1 | 1 | 0 | 1 |
15 | 1 | 1 | 1 | 1 | 0 |
Voici deux notations différentes décrivant la même fonction en algèbre booléenne non simplifiée, en utilisant les variables booléennes A , B , C , D et leurs inverses.
- où sont les minterms à mapper (c'est-à-dire les lignes qui ont la sortie 1 dans la table de vérité).
- où sont les maxterms à mapper (c'est-à-dire les lignes qui ont une sortie 0 dans la table de vérité).
Construction
Dans l'exemple ci-dessus, les quatre variables d'entrée peuvent être combinées de 16 manières différentes, donc la table de vérité a 16 lignes et la carte de Karnaugh a 16 positions. La carte de Karnaugh est donc disposée dans une grille 4 × 4.
Les indices de ligne et de colonne (affichés en haut et en bas à gauche de la carte de Karnaugh) sont classés en code Gray plutôt qu'en ordre numérique binaire. Le code Gray garantit qu'une seule variable change entre chaque paire de cellules adjacentes. Chaque cellule de la carte de Karnaugh complétée contient un chiffre binaire représentant la sortie de la fonction pour cette combinaison d'entrées.
Regroupement
Une fois la carte de Karnaugh construite, elle est utilisée pour trouver l'une des formes les plus simples possibles - une forme canonique - pour les informations de la table de vérité. Les 1 adjacents sur la carte de Karnaugh représentent des opportunités pour simplifier l'expression. Les minterms (« termes minimaux ») pour l'expression finale sont trouvés en encerclant des groupes de 1 dans la carte. Les groupes Minterm doivent être rectangulaires et avoir une aire qui est une puissance de deux (c'est-à-dire 1, 2, 4, 8...). Les rectangles Minterm doivent être aussi grands que possible sans contenir de 0. Les groupes peuvent se chevaucher afin d'agrandir chacun. Les regroupements optimaux dans l'exemple ci-dessous sont marqués par les lignes vertes, rouges et bleues, et les groupes rouges et verts se chevauchent. Le groupe rouge est un carré 2 × 2, le groupe vert est un rectangle 4 × 1 et la zone de chevauchement est indiquée en marron.
Les cellules sont souvent désignées par un raccourci qui décrit la valeur logique des entrées que la cellule couvre. Par exemple, AD signifierait une cellule qui couvre la zone 2x2 où A et D sont vrais, c'est-à-dire les cellules numérotées 13, 9, 15, 11 dans le diagramme ci-dessus. D'un autre côté, A D signifierait les cellules où A est vrai et D est faux (c'est-à-dire que D est vrai).
La grille est connectée de manière toroïdale , ce qui signifie que des groupes rectangulaires peuvent s'enrouler sur les bords (voir photo). Les cellules situées à l'extrême droite sont en fait « adjacentes » à celles situées à l'extrême gauche, en ce sens que les valeurs d'entrée correspondantes ne diffèrent que d'un bit ; de même, ceux du haut et ceux du bas le sont aussi. Par conséquent, A D peut être un terme valide - il comprend les cellules 12 et 8 en haut et se termine en bas pour inclure les cellules 10 et 14 - tout comme B D , qui comprend les quatre coins.
Solution
Une fois la carte de Karnaugh construite et les 1 adjacents reliés par des cases rectangulaires et carrées, les mintermes algébriques peuvent être trouvés en examinant quelles variables restent les mêmes dans chaque case.
Pour le groupement rouge :
- A est le même et est égal à 1 dans toute la boîte, il doit donc être inclus dans la représentation algébrique du minterm rouge.
- B ne conserve pas le même état (il passe de 1 à 0) et doit donc être exclu.
- C ne change pas. C'est toujours 0, donc son complément, NOT-C, doit être inclus. Ainsi, C devrait être inclus.
- D change, il est donc exclu.
Ainsi, le premier minterm de l'expression booléenne de la somme des produits est A C .
Pour le groupement vert, A et B conservent le même état, tandis que C et D changent. B vaut 0 et doit être nié avant de pouvoir être inclus. Le deuxième terme est donc A B . Notez qu'il est acceptable que le groupement vert chevauche le groupement rouge.
De la même manière, le groupement bleu donne le terme BC D .
Les solutions de chaque groupement sont combinées : la forme normale du circuit est .
Ainsi, la carte de Karnaugh a guidé une simplification de
Il aurait également été possible de dériver cette simplification en appliquant soigneusement les axiomes de l'algèbre de Boole , mais le temps nécessaire pour le faire croît de manière exponentielle avec le nombre de termes.
Inverse
L'inverse d'une fonction est résolu de la même manière en regroupant les 0 à la place.
Les trois termes pour couvrir l'inverse sont tous affichés avec des cases grises avec des bordures de couleurs différentes :
- marron : A B
- or : A C
- bleu : BCD
Cela donne l'inverse :
Grâce à l'utilisation des lois de De Morgan , le produit des sommes peut être déterminé :
Ne s'en soucie pas
Les cartes de Karnaugh permettent également de minimiser plus facilement les fonctions dont les tables de vérité incluent des conditions « indifférent ». Une condition "ne se soucie pas" est une combinaison d'entrées pour laquelle le concepteur ne se soucie pas de la sortie. Par conséquent, les conditions « indifférent » peuvent être incluses ou exclues de tout groupe rectangulaire, selon ce qui le rend plus grand. Ils sont généralement indiqués sur la carte par un tiret ou un X.
L'exemple de droite est le même que l'exemple ci-dessus mais avec la valeur de f (1,1,1,1) remplacée par un "ne s'en soucie pas". Cela permet au terme rouge de s'étendre jusqu'en bas et, ainsi, supprime complètement le terme vert.
Cela donne la nouvelle équation minimale :
Notez que le premier terme est juste A , pas A C . Dans ce cas, l'indifférent a laissé tomber un terme (le rectangle vert) ; simplifié un autre (le rouge); et supprimé le risque de course (en supprimant le terme jaune comme indiqué dans la section suivante sur les risques de course).
Le cas inverse se simplifie comme suit :
Grâce à l'utilisation des lois de De Morgan , le produit des sommes peut être déterminé :
Risques de course
Élimination
Les cartes de Karnaugh sont utiles pour détecter et éliminer les conditions de course . Les dangers de course sont très faciles à repérer à l'aide d'une carte de Karnaugh, car une condition de course peut exister lors du déplacement entre n'importe quelle paire de régions adjacentes, mais disjointes, circonscrites sur la carte. Cependant, en raison de la nature du codage Gray, adjacent a une définition spéciale expliquée ci-dessus - nous nous déplaçons en fait sur un tore, plutôt que sur un rectangle, enroulant autour du haut, du bas et des côtés.
- Dans l'exemple ci - dessus , une condition de concurrence potentielle existe lorsque C vaut 1 et D vaut 0, A vaut 1 et B passe de 1 à 0 (passage de l'état bleu à l'état vert). Dans ce cas, la sortie est définie pour rester inchangée à 1, mais comme cette transition n'est pas couverte par un terme spécifique dans l'équation, il existe un potentiel de pépin (une transition momentanée de la sortie vers 0).
- Il existe un deuxième problème potentiel dans le même exemple qui est plus difficile à repérer : lorsque D est égal à 0 et que A et B valent tous les deux à 1, avec C passant de 1 à 0 (passage de l'état bleu à l'état rouge). Dans ce cas, le glitch s'enroule du haut vers le bas de la carte.
Que des problèmes se produisent réellement dépend de la nature physique de l'implémentation, et si nous devons nous en préoccuper dépend de l'application. En logique cadencée, il suffit que la logique s'installe sur la valeur souhaitée dans le temps pour respecter l'échéance de temporisation. Dans notre exemple, nous ne considérons pas la logique cadencée.
Dans notre cas, un terme supplémentaire de éliminerait le risque potentiel de course, faisant le pont entre les états de sortie vert et bleu ou les états de sortie bleu et rouge : ceci est représenté par la région jaune (qui s'enroule du bas vers le haut à droite moitié) dans le diagramme ci-contre.
Le terme est redondant en termes de logique statique du système, mais de tels termes redondants ou consensuels sont souvent nécessaires pour assurer des performances dynamiques sans course.
De même, un terme supplémentaire de doit être ajouté à l'inverse pour éliminer un autre danger potentiel de course. L'application des lois de De Morgan crée un autre produit d'expression de sommes pour f , mais avec un nouveau facteur de .
Exemples de cartes à 2 variables
Voici toutes les cartes de Karnaugh à 2 variables et 2 × 2 possibles. Les mintermes en fonction de l' équation minimale sans danger de course ( voir la section précédente ) sont listés avec chacun . Un minterm est défini comme une expression qui donne la forme d'expression la plus minimale des variables mappées. Tous les blocs interconnectés horizontaux et verticaux possibles peuvent être formés. Ces blocs doivent être de la taille des puissances de 2 (1, 2, 4, 8, 16, 32, ...). Ces expressions créent un mappage logique minimal des expressions de variables logiques minimales pour les expressions binaires à mapper. Voici tous les blocs avec un seul champ.
Un bloc peut se poursuivre en bas, en haut, à gauche ou à droite du graphique. Cela peut même dépasser le bord du graphique pour une minimisation des variables. En effet, chaque variable logique correspond à chaque colonne verticale et ligne horizontale. Une visualisation de la k-map peut être considérée comme cylindrique. Les champs sur les bords à gauche et à droite sont adjacents, et le haut et le bas sont adjacents. Les K-Maps pour quatre variables doivent être représentées sous la forme d'un beignet ou d'un tore. Les quatre coins du carré dessiné par la k-map sont adjacents. Des cartes encore plus complexes sont nécessaires pour 5 variables et plus.
Méthodes graphiques associées
Les méthodes de minimisation graphique associées incluent :
- Diagramme de Marquand (1881) par Allan Marquand (1853-1924)
- Carte de Veitch (1952) par Edward W. Veitch (1924-2013)
- Carte de Mahoney ( M-map , désignation numéros , 1963) par Matthew V. Mahoney (une extension symétrique par réflexion des cartes de Karnaugh pour un plus grand nombre d'entrées)
- Réduction de Karnaugh techniques (de RKM) (de 1969) comme des variables peu fréquentes , variables entrées sur carte (MEV), carte variable entrée (VEM) ou variable entré Karnaugh (de VEKM) par GW Schultz, Thomas E. Osborne , Christopher R Clare, J. Robert Burgoon, Larry L. Dornhoff, William I. Fletcher, Ali M. Rushdi et autres (plusieurs extensions successives de cartes de Karnaugh basées sur des entrées variables pour un plus grand nombre d'entrées)
- Minterm-ring map (MRM, 1990) par Thomas R. McCalla (une extension tridimensionnelle des cartes de Karnaugh pour un plus grand nombre d'entrées)
Voir également
- Forme normale algébrique (ANF)
- Diagramme de décision binaire (BDD), une structure de données qui est une représentation compressée d'une fonction booléenne
- Minimiseur logique heuristique expresso
- Liste des sujets d'algèbre booléenne
- Optimisation logique
- Place Punnett (1905), un diagramme similaire en biologie
- Algorithme de Quine-McCluskey
- Extension Reed-Muller
- Diagramme de Venn (1880)
- polynôme de Zhegalkin
Remarques
Les références
Lectures complémentaires
- Katz, Randy Howard (1998) [1994]. Conception logique contemporaine . La maison d'édition Benjamin/Cummings . p. 70-85 . doi : 10.1016/0026-2692 (95) 90052-7 . ISBN 0-8053-2703-7.
- Vingron, Shimon Peter (2004) [2003-11-05]. « Cartes de Karnaugh ». Théorie de la commutation : aperçu grâce à la logique des prédicats . Berlin, Heidelberg, New York : Springer-Verlag . p. 57-76. ISBN 3-540-40343-4.
-
Wickes, William E. (1968). "3.5. Diagrammes de Veitch". Conception logique avec circuits intégrés . New York, États-Unis : John Wiley & Sons . p. 36-49 . LCCN 68-21185 . p. 36 :
[…] un raffinement du diagramme de Venn en ce que les cercles sont remplacés par des carrés et disposés sous forme de matrice. Le diagramme de Veitch étiquette les carrés avec les minterms . Karnaugh a attribué des 1 et des 0 aux carrés et à leurs étiquettes et en a déduit le schéma de numérotation d'usage courant.
- Maxfield, Clive "Max" (2006-11-29). "Logique de Reed-Muller" . Logique 101 . EE Times . Partie 3. Archivé de l'original le 2017-04-19 . Récupéré le 2017-04-19 .
- Lind, Larry Frédéric ; Nelson, John Christopher Cunliffe (1977). "Article 2.3". Analyse et conception de systèmes numériques séquentiels . Presse Macmillan . ISBN 0-33319266-4. (146 pages)
- Holder, Michel Elizabeth (mars 2005) [2005-02-14]. "Une technique de carte de Karnaugh modifiée" . Transactions IEEE sur l'éducation . IEEE . 48 (1) : 206-207. doi : 10.1109/TE.2004.832879 . eISSN 1557-9638 . ISSN 0018-9359 . S2CID 25576523 . [2]
- Cavanagh, Joseph (2008). Arithmétique informatique et Verilog HDL Fundamentals (1 éd.). CRC Appuyez sur .
- Kohavi, Zvi ; Jha, Niraj K. (2009). Théorie de la commutation et des automates finis (3 éd.). Presse de l'Université de Cambridge . ISBN 978-0-521-85748-2.
Liens externes
- Détecter les Rectangles qui se chevauchent , par Herbert Glarner.
- Utilisation des cartes de Karnaugh dans des applications pratiques , projet de conception de circuits pour contrôler les feux de circulation.
- Tutoriel K-Map pour 2, 3, 4 et 5 variables
- Exemple de carte de Karnaugh
- SIMPLIFICATION DE LA FONCTION BOOLEENNE POCKET–PC, Ledion Bitincka — George E. Antoniou
- Dépannage de K-Map