Carte de Karnaugh - Karnaugh map

Un exemple de carte de Karnaugh. Cette image montre en fait deux cartes de Karnaugh : pour la fonction ƒ , en utilisant des minterms (rectangles colorés) et pour son complément, en utilisant des maxterms (rectangles gris). Dans l'image, E () signifie une somme de minterms, notée dans l'article par .

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 .

Table de vérité d'une fonction
  UNE B C
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é).
K-map dessinée sur un tore, et dans un avion. Les cellules en pointillés sont adjacentes.
Construction de K-map. Au lieu des valeurs de sortie (les valeurs les plus à droite dans la table de vérité), ce diagramme montre une représentation décimale de l'entrée ABCD (les valeurs les plus à gauche dans la table de vérité), donc ce n'est pas une carte de Karnaugh.
En trois dimensions, on peut plier un rectangle en un tore.

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

Diagramme montrant deux K-maps. La K-map pour la fonction f(A, B, C, D) est représentée par des rectangles colorés qui correspondent aux minterms. La région brune est un chevauchement du carré rouge 2×2 et du rectangle vert 4×1. La K-map pour l'inverse de f est représentée par des rectangles gris, qui correspondent aux maxterms.

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

La valeur de pour ABCD = 1111 est remplacée par un "ne s'en soucie pas". Cela supprime complètement le terme vert et permet au terme rouge d'être plus grand. Il permet également au terme inverse bleu de se déplacer et de devenir plus grand

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.
Les aléas de course sont présents sur ce schéma.
Diagramme ci-dessus avec des termes de consensus ajoutés pour éviter les risques de course.

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

Remarques

Les références

Lectures complémentaires

Liens externes