Table de Karnaugh

Une table de Karnaugh (prononcé [k a ʁ .n o]) est une méthode graphique et simple pour trouver ou simplifier une fonction logique à partir de sa table de vérité. Elle utilise le code de Gray (aussi appelé binaire réfléchi), qui a comme propriété principale de ne faire varier qu'un seul bit entre deux mots successifs (la distance de Hamming de deux mots successifs du code de Gray est égale à 1).

Cette méthode a été développée par Maurice Karnaugh en 1953, en perfectionnant un diagramme similaire introduit en 1952 par Edward Veitch (en).

Principe[modifier | modifier le code]

Un tableau de Karnaugh peut être vu comme une table de vérité particulière, à deux dimensions, destinées à faire apparaître visuellement les simplifications possibles.

Supposons $2n$ ou $2n+1$ variables : on assignera par exemple $n$ ou $n+1$ variables au repérage des lignes, les $n$ autres variables au repérage des colonnes. Chaque case élémentaire correspond alors à une seule ligne et à une seule colonne, donc à une seule combinaison des variables.

Examinons le cas d'une fonction $S$ des quatre variables A, B, C, D, les variables A et B étant assignées aux lignes, C et D aux colonnes de la table ci-dessous.

Table de Karnaugh
S	00	01	11	10
AB
00	0	1	1	0
01	0	1	1	1
11	0	1	1	1
10	0	1	1	0

Cette table est proche du diagramme de Veitch antérieur. Pour rendre plus évidentes les simplifications cherchées, Karnaugh propose, pour la succession des valeurs données à C et D, ainsi qu'à A et B, d'employer un code de Gray, de sorte que les valeurs de deux repères consécutifs ne diffèrent que par la modification d'une seule variable, et fasse apparaître des symétries utiles. Ainsi :

La colonne 1 correspond aux valeurs de S pour $C=0$ et $D=0$ , ou ${\overline {CD}}=1$
La colonne 2 correspond aux valeurs de S pour $C=0$ et $D=1$ , ou ${\overline {C}}D=1$
La colonne 3 correspond aux valeurs de S pour $C=1$ et $D=1$ , ou $CD=1$
La colonne 4 correspond aux valeurs de S pour $C=1$ et $D=0$ , ou $C{\overline {D}}=1$

La ligne 1 correspond aux valeurs de S pour $A=0$ et $B=0$ , ou ${\overline {AB}}=1$
La ligne 2 correspond aux valeurs de S pour $A=0$ et $B=1$ , ou ${\overline {A}}B=1$
La ligne 3 correspond aux valeurs de S pour $A=1$ et $B=1$ , ou $AB=1$
La ligne 4 correspond aux valeurs de S pour $A=1$ et $B=0$ , ou $A{\overline {B}}=1$ .

Alors, on assigne à la case de la ligne 4, colonne 2 la valeur de $S$ quand $A=1,B=0,C=0$ et $D=1$ . Cette valeur peut être trouvée dans la table de vérité ou par une équation à simplifier.

Les valeurs du tableau de Karnaugh considéré correspondent aux valeurs de la table de vérité suivante :

*Table de vérité*
A	B	C	D	S
0	0	0	0	0
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

Méthode de recherche de l'équation[modifier | modifier le code]

Pour trouver l'équation de S, c'est simple. Il y a deux méthodes :

former une somme ;
former un produit.

La somme[modifier | modifier le code]

Pour trouver une somme, il faut regrouper les valeurs de S égales à 1. Le nombre de 1 dans chaque groupe doit être égal à une puissance de 2. Les groupes formés doivent être les moins nombreux possibles, mais ils doivent englober tous les 1. Un 1 peut être inclus dans plus d'un groupe, par contre aucun 0 ne doit être inclus. Les groupes sont composés d'une ou plusieurs colonnes et d'une ou plusieurs lignes. Si possible, assemblez-les par valeurs d'entrées communes. Par exemple, la colonne 2 et la colonne 3 ont pour valeur commune D=1. La ligne 1 et la ligne 4 ont la valeur B=0 en commun..

Pour les tables à 4 variables, de préférence procéder dans l'ordre suivant :

Le rectangle 16 cases puis,
les rectangles 8 cases puis,

les rectangles 4 cases puis,
les rectangles 2 cases et,
enfin les cases uniques.

Dans l'exemple pris ci-dessus : on peut former un rectangle de 8 cases, puis un carré de 4 (le rectangle des colonnes 2 et 3 et le carré au croisement des lignes 2-3 et des colonnes 3-4). Le rectangle correspond à l'équation « D » car dans ces deux colonnes et dans ces deux colonnes seulement, D est toujours égal à 1. Le carré correspond à l'équation « B·C » car dans ces cases et dans ces cases seulement B=1 et C=1. S est représenté par l'union des 2 figures, et on obtient pour équation de S : « S = D + B·C ».

Cette méthode, une fois assimilée, permet de trouver une équation au premier coup d'œil, et propose une alternative simple à la simplification d'équation, qui peut rapidement devenir fastidieuse.

Le produit[modifier | modifier le code]

Cette méthode ne regroupe pas les « 1 » mais les « 0 », pour trouver non pas une somme de produits mais un produit de sommes.

En regroupant les 0, on trouve S' sous forme d'une somme, et par complémentation, on obtient S sous forme de produit.

Ici, en regroupant les 0 de S (ou 1 de S') on obtient S' = C'D'+ B'D', le premier terme regroupant la 1^re colonne, et le second les 4 coins. Donc, par la règle de De Morgan, S = (C+D)·(B+D) : S est maintenant vu comme l'intersection de C+D, qui représente les colonnes 1 à 3, et de B+D, qui représente le carré total hormis les 4 coins ^[1].

Utilisation[modifier | modifier le code]

Les tables/tableaux de Karnaugh sont surtout utilisé(e)s en électronique. En effet, la simplification de l'expression algébrique booléenne permet d'économiser des opérateurs logiques (portes logiques) et donc des circuits. Elle engendre aussi une économie de temps de conception et de fonds, tout en augmentant la fiabilité de l'ensemble.

En programmation, l'utilisation des tables de Karnaugh permet de réduire les séquences de conditions de test complexes en les regroupant en des conditions non intuitives au premier abord, mais qui réduisent la complexité effective du code (volume du source), ainsi que son temps d'exécution en réduisant le nombre des évaluations nécessaires.

Extension aux fonctions partiellement définies[modifier | modifier le code]

Parfois la fonction à réaliser n'est que partiellement définie. Par exemple, si une fonction dépend de 4 variables représentant le codage binaire d'un chiffre décimal, seuls 10 cas sont définis sur 16. Alors, les cases non définies reçoivent une marque spéciale différente de 0 et de 1 (par exemple x ou Φ), et deviennent annexables aux points employés sans l'être aux points à réaliser. On peut donc trouver des solutions plus simples, moins coûteuses, car les cas indéfinis font partie des possibilités sans faire partie des points nécessaires. Si, dans notre exemple, 10 cas sont définis sur 16, alors 2^6 = 64 fonctions complètement déterminées sont compatibles avec notre fonction, et toute réalisation d'une fonction compatible pourra être employée comme réalisation de la fonction incomplète visée.

Notes et références[modifier | modifier le code]

↑ Les 4 coins forment un carré si on pense que les bords parallèles se touchent, comme si le diagramme était dessiné sur un tore

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Table de Karnaugh, sur Wikimedia Commons
Table de Karnaugh, sur Wikiversity
Algèbre de Boole, chapitre « Simplification des expressions booléennes », section « Table de Karnaugh », sur Wikibooks

Articles connexes[modifier | modifier le code]

Les logiciels[modifier | modifier le code]

Bmin, Qt ouvrez l'application Source - les cartes de Karnaugh et la 3^e visualisation de n-cube Booléenne, Quine-McCluskey et la minimisation d'Express, "PoS" et la représentation "SoP" de fonctions et plus.
Karma, un ensemble d'outils de synthèse logiques en incluant des cartes de Karnaugh, une minimisation de Quine-McCluskey, un module enseignant et plus. Laboratoires de Synthèse de Circuit logiques.
GKMap, application de logiciel gratuit à SourceForge.net.
Karnaugh Map Minimizer, libre (mais souvent incorrect^{[réf. nécessaire]}, essayez avec cette équation : 0,1,5,8,10,13) l'application de logiciel à SourceForge.net.

[1] Les 4 coins forment un carré si on pense que les bords parallèles se touchent, comme si le diagramme était dessiné sur un tore

[1]