Carte de Karnaugh

Une carte de Karnaugh ( KM ou K-map ) est un diagramme qui peut être utilisé pour simplifier une expression d'algèbre booléenne . Maurice Karnaugh l'a introduit en 1953 comme un raffinement du diagramme de Veitch de 1952 d' Edward W. Veitch [ qui était lui-même une redécouverte du diagramme logique d' Allan Marquand de 1881 (alias diagramme de Marquand ). Il est également utile pour comprendre les circuits logiques. Les cartes de Karnaugh sont également connues sous le nom de diagrammes de Marquand–Veitch , diagrammes de Svoboda -(quoique rarement)- et cartes de Karnaugh–Veitch ( cartes KV ).

Définition

Une carte de Karnaugh réduit le besoin de calculs approfondis en tirant parti de la capacité de reconnaissance des modèles des humains. Elle permet également l'identification et l'élimination rapides des conditions de course potentielles .

Les résultats booléens requis sont transférés d'une table de vérité vers une grille bidimensionnelle 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é d'origine. 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 implémentées en utilisant le nombre minimal de portes logiques . Une expression de somme de produits (SOP) peut toujours être implémentée en utilisant des 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, 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'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 sommes peuvent être implémentées directement en utilisant les opérateurs logiques AND et OR.

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 .

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.

${\displaystyle f(A,B,C,D)=\sum _{}m_{i},i\in \{6,8,9,10,11,12,13,14\ <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> <mo>=</mo> <munder> <mo>∑</mo> <mrow> </mrow> </munder> <msub> <mi>m</mi> <mrow> <mi>i</mi> </mrow> </msub> <mo>,</mo> <mi>i</mi> <mo>∈</mo> <mo>{</mo> <mn>6</mn> <mo>,</mo> <mn>8</mn> <mo>,</mo> <mn>9</mn> <mo>,</mo> <mn>10</mn> <mo>,</mo> <mn>11</mn> <mo>,</mo> <mn>12</mn> <mo>,</mo> <mn>13</mn> <mo>,</mo> <mn>14</mn> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle f(A,B,C,D)=\sum _{}m_{i},i\in \{6,8,9,10,11,12,13,14\}}</annotation> </semantics> </math><img src=$ ${\displaystyle m_{i <semantics> <mrow> <mstyle> <msub> <mi>m</mi> <mrow> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle m_{i}}</annotation> </semantics> </math><img src=$
${\displaystyle f(A,B,C,D)=\prod _{}M_{i},i\in \{0,1,2,3,4,5,7,15\ <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> <mo>=</mo> <munder> <mo>∏</mo> <mrow> </mrow> </munder> <msub> <mi>M</mi> <mrow> <mi>i</mi> </mrow> </msub> <mo>,</mo> <mi>i</mi> <mo>∈</mo> <mo>{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>4</mn> <mo>,</mo> <mn>5</mn> <mo>,</mo> <mn>7</mn> <mo>,</mo> <mn>15</mn> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle f(A,B,C,D)=\prod _{}M_{i},i\in \{0,1,2,3,4,5,7,15\}}</annotation> </semantics> </math><img src=$ ${\displaystyle M_{i <semantics> <mrow> <mstyle> <msub> <mi>M</mi> <mrow> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle M_{i}}</annotation> </semantics> </math><img src=$

Construction

Dans l'exemple ci-dessus, les quatre variables d'entrée peuvent être combinées de 16 manières différentes, de sorte que la table de vérité comporte 16 lignes et la carte de Karnaugh comporte 16 positions. La carte de Karnaugh est donc organisée selon 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 selon le code Gray plutôt que selon l'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 dans la carte de Karnaugh représentent des possibilités de simplifier l'expression. Les minitermes (« termes minimaux ») de l'expression finale sont trouvés en encerclant des groupes de 1 dans la carte. Les groupes de minitermes doivent être rectangulaires et avoir une surface qui est une puissance de deux (c'est-à-dire 1, 2, 4, 8...). Les rectangles de minitermes doivent être aussi grands que possible sans contenir de 0. Les groupes peuvent se chevaucher afin d'agrandir chacun d'eux. Les groupements optimaux dans l'exemple ci-dessous sont indiqué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'autre part, 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 l'image). Les cellules à l'extrême droite sont en fait « adjacentes » à celles à l'extrême gauche, dans le sens où les valeurs d'entrée correspondantes ne diffèrent que d'un bit ; de même, celles tout en haut et celles tout en bas le sont également. Par conséquent, A D peut être un terme valide (il inclut les cellules 12 et 8 en haut, et s'enroule vers le bas pour inclure les cellules 10 et 14), tout comme B D , qui inclut les quatre coins.

Solution

Une fois la carte de Karnaugh construite et les 1 adjacents lié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 minterme rouge.
B ne maintient pas le même état (il passe de 1 à 0), et doit donc être exclu.
C ne change pas. Il est toujours 0, donc son complément, NOT-C, doit être inclus. Ainsi, C doit être inclus.
D change, il est donc exclu.

Ainsi, le premier minterme dans l’expression booléenne de somme de produits est A C .

Pour le groupement vert, A et B conservent le même état, tandis que C et D changent. B est 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 . ${\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D <semantics> <mrow> <mstyle> <mi>A</mi> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>A</mi> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>B</mi> <mi>C</mi> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation>{\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}}</annotation> </semantics> </math><img src=$

Ainsi, la carte de Karnaugh a guidé une simplification de

{\displaystyle {\begin{aligned}f(A,B,C,D)={}&{\overline {A}}BC{\overline {D}}+A{\overline {B}}\,{\overline {C}}\,{\overline {D}}+A{\overline {B}}\,{\overline {C}}D+A{\overline {B}}C{\overline {D}}+{}\\&A{\overline {B}}CD+AB{\overline {C}}\,{\overline {D}}+AB{\overline {C}}D+ABC{\overline {D}}\\={}&A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}\end{aligned <semantics> <mrow> <mstyle> <mrow> <mtable> <mtr> <mtd> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> <mo>=</mo> <mrow> </mrow> </mtd> <mtd> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mi>B</mi> <mi>C</mi> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>A</mi> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>A</mi> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mi>D</mi> <mo>+</mo> <mi>A</mi> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mi>C</mi> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> </mrow> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi>A</mi> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mi>C</mi> <mi>D</mi> <mo>+</mo> <mi>A</mi> <mi>B</mi> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>A</mi> <mi>B</mi> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mi>D</mi> <mo>+</mo> <mi>A</mi> <mi>B</mi> <mi>C</mi> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> </mtd> </mtr> <mtr> <mtd> <mo>=</mo> <mrow> </mrow> </mtd> <mtd> <mi>A</mi> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>A</mi> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>B</mi> <mi>C</mi> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{aligned}f(A,B,C,D)={}&{\overline {A}}BC{\overline {D}}+A{\overline {B}}\,{\overline {C}}\,{\overline {D}}+A{\overline {B}}\,{\overline {C}}D+A{\overline {B}}C{\overline {D}}+{}\\&A{\overline {B}}CD+AB{\overline {C}}\,{\overline {D}}+AB{\overline {C}}D+ABC{\overline {D}}\\={}&A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}\end{aligned}}}</annotation> </semantics> </math></span><img src=

Il aurait également été possible d’obtenir cette simplification en appliquant soigneusement les axiomes de l’algèbre booléenne , mais le temps nécessaire pour y parvenir augmente 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 couvrant l'inverse sont tous représentés par des cases grises avec des bordures de couleurs différentes :

marron : A B
or : A C
bleu : BCD

Cela donne l'inverse :

{\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD <semantics> <mrow> <mstyle> <mrow> <mover> <mrow> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> </mrow> <mo>¯</mo> </mover> </mrow> <mo>=</mo> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>B</mi> <mi>C</mi> <mi>D</mi> </mstyle> </mrow> <annotation>{\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}</annotation> </semantics> </math></span><img src=

Grâce à l'utilisation des lois de De Morgan , le produit des sommes peut être déterminé :

{\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}} ight)\left({\overline {{\overline {A}}\,{\overline {C}}}} ight)\left({\overline {BCD}} ight)\\&=\left(A+B ight)\left(A+C ight)\left({\overline {B}}+{\overline {C}}+{\overline {D}} ight)\end{aligned <semantics> <mrow> <mstyle> <mrow> <mtable> <mtr> <mtd> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow> <mover> <mover> <mrow> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> </mrow> <mo>¯</mo> </mover> <mo>¯</mo> </mover> </mrow> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mrow> <mover> <mrow> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mi>B</mi> <mi>C</mi> <mi>D</mi> </mrow> <mo>¯</mo> </mover> </mrow> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mover> <mrow> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> </mrow> <mo>¯</mo> </mover> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mover> <mrow> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> </mrow> <mo>¯</mo> </mover> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mover> <mrow> <mi>B</mi> <mi>C</mi> <mi>D</mi> </mrow> <mo>¯</mo> </mover> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>+</mo> <mi>B</mi> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>+</mo> <mi>C</mi> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}} ight)\left({\overline {{\overline {A}}\,{\overline {C}}}} ight)\left({\overline {BCD}} ight)\\&=\left(A+B ight)\left(A+C ight)\left({\overline {B}}+{\overline {C}}+{\overline {D}} ight)\end{aligned}}}</annotation> </semantics> </math></span><img src=

Je m'en fiche

Les cartes de Karnaugh permettent également de minimiser plus facilement les fonctions dont les tables de vérité incluent des conditions « sans importance ». Une condition « sans importance » est une combinaison d'entrées pour lesquelles le concepteur ne se soucie pas de la sortie. Par conséquent, les conditions « sans importance » peuvent être incluses ou exclues de tout groupe rectangulaire, selon ce qui le rend plus grand. Elles sont généralement indiquées 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 « don't care ». Cela permet au terme rouge de s'étendre jusqu'en bas et, par conséquent, de supprimer complètement le terme vert.

Cela donne la nouvelle équation minimale :

{\displaystyle f(A,B,C,D)=A+BC{\overline {D <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> <mo>=</mo> <mi>A</mi> <mo>+</mo> <mi>B</mi> <mi>C</mi> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation>{\displaystyle f(A,B,C,D)=A+BC{\overline {D}}}</annotation> </semantics> </math></span><img src=

Notez que le premier terme est simplement A , et non A C . Dans ce cas, le terme « don't care » a supprimé un terme (le rectangle vert) ; en a simplifié un autre (le rouge) ; et a supprimé le risque racial (en supprimant le terme jaune comme indiqué dans la section suivante sur les risques raciaux).

Le cas inverse est simplifié comme suit :

{\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}D <semantics> <mrow> <mstyle> <mrow> <mover> <mrow> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> </mrow> <mo>¯</mo> </mover> </mrow> <mo>=</mo> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mi>D</mi> </mstyle> </mrow> <annotation>{\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}D}</annotation> </semantics> </math></span><img src=

Grâce à l'utilisation des lois de De Morgan , le produit des sommes peut être déterminé :

{\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}\,D}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}} ight)\left({\overline {{\overline {A}}\,{\overline {C}}}} ight)\left({\overline {{\overline {A}}\,D}} ight)\\&=\left(A+B ight)\left(A+C ight)\left(A+{\overline {D}} ight)\end{aligned <semantics> <mrow> <mstyle> <mrow> <mtable> <mtr> <mtd> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow> <mover> <mover> <mrow> <mi>f</mi> <mo>(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo>,</mo> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>)</mo> </mrow> <mo>¯</mo> </mover> <mo>¯</mo> </mover> </mrow> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mrow> <mover> <mrow> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> <mo>+</mo> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mi>D</mi> </mrow> <mo>¯</mo> </mover> </mrow> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mover> <mrow> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>B</mi> <mo>¯</mo> </mover> </mrow> </mrow> <mo>¯</mo> </mover> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mover> <mrow> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mrow> <mover> <mi>C</mi> <mo>¯</mo> </mover> </mrow> </mrow> <mo>¯</mo> </mover> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mover> <mrow> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mspace></mspace> <mi>D</mi> </mrow> <mo>¯</mo> </mover> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>+</mo> <mi>B</mi> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>+</mo> <mi>C</mi> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>+</mo> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}\,D}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}} ight)\left({\overline {{\overline {A}}\,{\overline {C}}}} ight)\left({\overline {{\overline {A}}\,D}} ight)\\&=\left(A+B ight)\left(A+C ight)\left(A+{\overline {D}} ight)\end{aligned}}}</annotation> </semantics> </math></span><img src=

Les dangers de la course

Élimination

Les cartes de Karnaugh sont utiles pour détecter et éliminer les conditions de course . Les risques 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, enveloppant le haut, le bas et les côtés.

Dans l'exemple ci-dessus, une condition de concurrence potentielle existe lorsque C est 1 et D est 0, A est 1 et B passe de 1 à 0 (passage de l'état bleu à l'état vert). Dans ce cas, la sortie est définie comme restant inchangée à 1, mais comme cette transition n'est pas couverte par un terme spécifique dans l'équation, il existe un risque de problème (une transition momentanée de la sortie à 0).
Il existe un deuxième problème potentiel dans le même exemple, plus difficile à repérer : lorsque D est 0 et que A et B sont tous les deux 1, avec C passant de 1 à 0 (passant de l'état bleu à l'état rouge). Dans ce cas, le problème s'étend du haut de la carte vers le bas.

La survenue de problèmes dépend de la nature physique de l'implémentation et de l'application. Dans une logique cadencée, il suffit que la logique se stabilise sur la valeur souhaitée à temps pour respecter le délai de temporisation. Dans notre exemple, nous ne prenons pas en compte la logique cadencée.

Dans notre cas, un terme supplémentaire éliminerait le risque de course potentiel, en 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 de la moitié droite) dans le diagramme adjacent. ${\displaystyle A{\overline {D <semantics> <mrow> <mstyle> <mi>A</mi> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation>{\displaystyle A{\overline {D}}}</annotation> </semantics> </math><img src=$

Le terme est redondant en termes de logique statique du système, mais de tels termes redondants ou consensuels sont souvent nécessaires pour garantir des performances dynamiques sans course.

De même, un terme supplémentaire de doit être ajouté à l'inverse pour éliminer un autre risque de course potentiel. L'application des lois de De Morgan crée une autre expression de produit de sommes pour f , mais avec un nouveau facteur de . ${\displaystyle {\overline {A}}D <semantics> <mrow> <mstyle> <mrow> <mover> <mi>A</mi> <mo>¯</mo> </mover> </mrow> <mi>D</mi> </mstyle> </mrow> <annotation>{\displaystyle {\overline {A}}D}</annotation> </semantics> </math><img src=$ ${\displaystyle \left(A+{\overline {D}} ight) <semantics> <mrow> <mstyle> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>+</mo> <mrow> <mover> <mi>D</mi> <mo>¯</mo> </mover> </mrow> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \left(A+{\overline {D}} ight)}</annotation> </semantics> </math><img src=$

Exemples de cartes à 2 variables

Voici toutes les cartes de Karnaugh possibles à 2 variables, 2 × 2. Chacune d'elles contient les minitermes en fonction de et de l'équation minimale sans risque de course ( voir la section précédente ). Un miniterme 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 avoir 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 champ. ${ extstyle \sum m() <semantics> <mrow> <mstyle> <mo>∑</mo> <mi>m</mi> <mo>(</mo> <mo>)</mo> </mstyle> </mrow> <annotation>{ extstyle \sum m()}</annotation> </semantics> </math><img src=$

Un bloc peut être continué en bas, en haut, à gauche ou à droite du graphique. Il peut même s'étendre au-delà du bord du graphique pour minimiser les variables. En effet, chaque variable logique correspond à chaque colonne verticale et à chaque ligne horizontale. Une visualisation de la k-map peut être considérée comme cylindrique. Les champs situés sur les bords gauche et droit 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 (0); K = 0
Σ m (1); K = A ′ B ′
Σ m (2); K = AB ′
Σ m (3); K = A ′ B
Σ m (4); K = AB
Σ m (1,2); K = B ′
Σ m (1,3); K = A ′
Σ m (1,4); K = A ′ B ′ + AB
Σ m (2,3); K = AB ′ + A ′ B
Σ m (2,4); K = A
Σ m (3,4); K = B
Σ m (1,2,3); K = A' + B ′
Σ m (1,2,4); K = A + B ′
Σ m (1,3,4); K = A ′ + B
Σ m (2,3,4); K = A + B
Σ m (1,2,3,4); K = 1

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 Svoboda (1956) par Antonín Svoboda (1907-1980)
Carte de Mahoney ( M-map , numéros de désignation , 1963) par Matthew V. Mahoney (une extension symétrique par réflexion des cartes de Karnaugh pour un plus grand nombre d'entrées)
Techniques de cartes de Karnaugh réduites (RKM) (à partir de 1969) telles que les variables peu fréquentes , les variables saisies dans la carte (MEV), les cartes saisies par variables (VEM) ou les cartes de Karnaugh saisies par variables (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)
Carte Minterm-ring (MRM, 1990) de Thomas R. McCalla (une extension tridimensionnelle des cartes de Karnaugh pour un plus grand nombre d'entrées)