Tableau de Karnaugh — Guide de simplification K-map

Un tableau de Karnaugh, ou K-map, est une grille utilisée pour simplifier une expression booléenne sans faire autant d’algèbre à la main. On place les valeurs de sortie d’une table de vérité sur la grille, on regroupe les $1$ adjacents, puis on écrit un terme plus simple pour chaque groupe.

La condition est importante : les K-maps sont surtout pratiques pour de petites fonctions, généralement avec deux, trois ou quatre variables. Quand le nombre de variables augmente, la carte devient plus difficile à lire et d’autres méthodes sont généralement préférables.

Ce que montre un tableau de Karnaugh

Une K-map contient les mêmes informations qu’une table de vérité, mais elle organise les cases selon l’ordre du code Gray au lieu de l’ordre binaire ordinaire. Cette disposition fait que deux cases voisines ne diffèrent que par une seule variable.

Cette différence d’une seule variable est précisément l’idée clé. Si deux cases adjacentes valent toutes deux $1$, la variable qui change peut disparaître du terme simplifié.

Comment les regroupements éliminent des variables

La règle visuelle vient d’identités booléennes telles que

$$XY + X\overline{Y} = X$$

Les deux termes ne diffèrent que par $Y$, donc $Y$ s’élimine et la partie commune $X$ reste. Une K-map permet de repérer directement ce schéma de simplification sur la grille.

Exemple de tableau de Karnaugh

Supposons

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

Cela signifie que $F=1$ pour les mintermes $1$, $3$, $4$, $5$ et $7$.

Pour une K-map à $3$ variables, utilisez $A$ pour les lignes et $BC$ pour les colonnes dans l’ordre du code Gray $00$, $01$, $11$, $10$ :

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

Commencez par le plus grand groupe valide. Les quatre $1$ des deux colonnes centrales forment un groupe. Dans ces quatre cases, $C=1$ reste fixe tandis que $A$ et $B$ changent, donc ce groupe se simplifie en

$$C$$

Il reste encore un $1$ non couvert : le minterme $4$, qui est $(A,B,C)=(1,0,0)$. Associez-le au minterme adjacent $5$, qui est $(1,0,1)$.

Dans cette paire, $A=1$ et $B=0$ restent fixes tandis que $C$ change, donc la paire se simplifie en

$$A\overline{B}$$

L’expression simplifiée est donc

$$F(A,B,C) = C + A\overline{B}$$

Cette expression plus courte est équivalente à la liste originale de mintermes.

Règles pour former des groupes valides dans une K-map

Utilisez des groupes dont la taille est une puissance de deux : $1$, $2$, $4$, $8$, etc.

Utilisez les plus grands groupes valides possibles. Les groupes plus grands éliminent généralement davantage de variables.

N’oubliez pas que la carte se referme sur elle-même. Les bords gauche et droit sont adjacents, et les bords haut et bas le sont aussi.

Les cases en diagonale ne sont pas adjacentes.

Le chevauchement est autorisé si cela aide à créer un groupe plus grand ou plus simple.

Erreurs fréquentes avec les tableaux de Karnaugh

Utiliser l’ordre binaire ordinaire

Si vous étiquetez les lignes ou les colonnes $00$, $01$, $10$, $11$, l’adjacence est incorrecte. Les K-maps doivent utiliser l’ordre du code Gray pour que deux cases voisines ne diffèrent que d’un seul bit.

Former des groupes de trois

Un groupe de trois cases n’est jamais valide. La taille doit être une puissance de deux.

Oublier l’adjacence par raccordement des bords

Certaines des meilleures simplifications utilisent des cases situées sur des bords opposés de la carte. Si vous oubliez cette règle, votre réponse est souvent plus longue que nécessaire.

Forcer chaque $1$ à appartenir à un seul groupe

Ce n’est pas une règle. Réutiliser une case peut être la meilleure façon de créer un groupe plus grand et une expression finale plus courte.

Quand utilise-t-on un tableau de Karnaugh ?

Les K-maps sont courants en logique numérique et dans les cours d’introduction au génie informatique, car ils transforment la simplification booléenne en un processus visuel. Ils sont particulièrement utiles quand on veut obtenir une expression somme de produits plus simple avant de dessiner ou d’implémenter un circuit logique.

Ils sont aussi utiles pour développer l’intuition. Même si un logiciel prend en charge les conceptions plus grandes, apprendre les K-maps aide à comprendre pourquoi certains termes booléens se combinent et d’autres non.

Essayez un problème similaire

Essayez de simplifier $F(A,B,C)=\sum m(0,2,4,6,7)$ par vous-même. Dessinez la carte, formez d’abord les plus grands groupes valides, puis ne gardez que les variables qui restent constantes dans chaque groupe.

Si vous voulez aller un peu plus loin, essayez une version avec des valeurs don't-care et utilisez-les seulement lorsqu’elles vous aident à former un groupe valide plus grand.