Tables de Karnaugh : simplification booléenne visuelle

TL;DR : une table de Karnaugh (K-map) dispose une table de vérité dans une grille 2D en code Gray où les cases adjacentes diffèrent d’une seule variable. Regrouper les 1 adjacents en rectangles de taille puissance de deux produit directement des expressions Somme-de-Produits minimales — sans algèbre. Les K-maps minimisent de façon fiable les fonctions jusqu’à 4 variables ; pour 5 ou 6, on utilise Quine-McCluskey, et au-delà, des synthèses algorithmiques de type ESPRESSO.

La simplification algébrique à l’aide des lois booléennes fonctionne, mais elle repose sur la capacité à repérer la bonne factorisation au bon moment. Si vous manquez une occasion, vous obtenez un résultat sous-optimal. Pour les expressions à quatre variables ou plus, le nombre de manipulations possibles explose.

La table de Karnaugh (K-map) résout ce problème en convertissant la simplification algébrique en reconnaissance visuelle de motifs. Mise au point en 1953 par le physicien des Bell Labs Maurice Karnaugh, elle dispose une table de vérité dans une grille bidimensionnelle où les cases adjacentes diffèrent d’exactement une variable. Regrouper les 1 adjacents sur la grille produit directement des expressions Somme-de-Produits minimales — sans aucune manipulation algébrique.

Diagramme du composant porte ET

La table de vérité visuelle : qu’est-ce qu’une K-map ?

À la base, une table de Karnaugh est une table de vérité déguisée. Alors qu’une table de vérité liste entrées et sorties de manière linéaire et verticale, la K-map les réarrange en une grille bidimensionnelle. Ce n’est pas qu’un effet d’esthétique. Le génie de la K-map réside dans la disposition spécifique de ses cases.

Dans une table de vérité standard, les lignes suivent un comptage binaire (00, 01, 10, 11). Dans une K-map, lignes et colonnes suivent une séquence appelée code Gray. Dans une séquence en code Gray, chaque nombre adjacent — qu’on se déplace horizontalement ou verticalement — diffère d’un seul bit. Cette propriété, appelée adjacence logique, est le moteur de la simplification. Lorsque vous regroupez des cases adjacentes contenant des « 1 », vous identifiez visuellement les variables qui changent (et qui n’affectent donc pas le résultat) et vous les éliminez, ne laissant qu’un terme booléen minimal.

Avant de plonger dans les K-maps complexes à 4 variables utilisées dans la conception d’UAL moderne, examinons la K-map fondamentale à 2 variables pour les entrées $A$ et $B$ . Elle se compose de $2^2 = 4$ cases représentant les quatre mintermes possibles.

	$B=0$ ( $\overline{B}$ )	$B=1$ ( $B$ )
$A=0$ ( $\overline{A}$ )	$m_0$ ( $\overline{A}\overline{B}$ )	$m_1$ ( $\overline{A}B$ )
$A=1$ ( $A$ )	$m_2$ ( $A\overline{B}$ )	$m_3$ ( $AB$ )

Remarquez l’adjacence : en passant de $m_0$ à $m_1$ , seule la variable $B$ change. En passant de $m_1$ à $m_3$ , seule la variable $A$ change. Cette proximité physique sur la grille représente une relation logique que nous pouvons exploiter pour réduire le nombre de portes.

Voir la logique de base en action

L’art du regroupement : des tables à la logique minimale

L’objectif d’une K-map est de couvrir tous les « 1 » de la table en utilisant les groupes rectangulaires les plus grands possible. Il y a toutefois une contrainte : le nombre de cases dans chaque groupe doit être une puissance de deux (1, 2, 4, 8, 16, et ainsi de suite). Chaque groupe que vous dessinez correspond à un terme produit simplifié. Votre expression finale optimisée n’est rien d’autre que la « Somme de Produits » (réunion par OU des résultats de ces groupes).

Les règles de regroupement sont strictes mais simples. Les suivre mécaniquement garantit un résultat minimal.

Couvrir chaque « 1 » : chaque « 1 » de la table doit appartenir à au moins un groupe. Aucun « 1 » ne peut rester non regroupé.
Puissances de deux uniquement : les groupes doivent contenir exactement $2^k$ cases : 1, 2, 4, 8 ou 16. On ne peut pas former de groupe de 3, 5 ou 6. Une zone de six « 1 » doit être couverte par des groupes superposés de 4 et 2.
Maximiser la taille des groupes : les plus grands groupes éliminent plus de variables. Un groupe de 2 élimine 1 variable ; un groupe de 4 en élimine 2 ; un groupe de 8 en élimine 3. Cherchez toujours le plus grand groupe possible en premier.
Le chevauchement est autorisé : un même « 1 » peut appartenir à plusieurs groupes. Utilisez le chevauchement de façon agressive pour créer de plus grands groupes.
Forme rectangulaire uniquement : les groupes doivent former des rectangles (carrés compris). Les formes en L, en T et les diagonales ne sont pas valides.
La table se replie : la colonne la plus à gauche est adjacente à celle la plus à droite. La ligne du haut est adjacente à celle du bas. Imaginez la table comme un tore — les quatre coins sont mutuellement adjacents.

Plongée : la K-map à 4 variables

Attaquons-nous à un scénario réel. Supposons que nous concevions une logique spécifique pour une CONTROL_UNIT qui doit émettre un signal lorsqu’une entrée de 4 bits correspond à certaines conditions. Notre fonction est $F(A,B,C,D) = \Sigma m(0, 2, 5, 7, 8, 10, 13, 15)$ .

La notation $\Sigma m$ est simplement un raccourci pour « la sortie est HAUTE quand l’entrée binaire vaut ces valeurs décimales ». Commençons par remplir notre grille de 16 cases.

	$CD=00$	$CD=01$	$CD=11$	$CD=10$
$AB=00$	1 ( $m_0$ )	0	0	1 ( $m_2$ )
$AB=01$	0	1 ( $m_5$ )	1 ( $m_7$ )	0
$AB=11$	0	1 ( $m_{13}$ )	1 ( $m_{15}$ )	0
$AB=10$	1 ( $m_8$ )	0	0	1 ( $m_{10}$ )

Maintenant, cherchons les motifs.

Groupe 1 : les quatre coins

Regardez les « 1 » en $m_0, m_2, m_8$ et $m_{10}$ . Comme la table se replie horizontalement et verticalement, ces quatre coins sont en fait adjacents ! Ils forment un seul groupe de quatre.

Variable A : passe de 0 à 1. (Élimination)
Variable B : reste 0. (On garde $\overline{B}$ )
Variable C : passe de 0 à 1. (Élimination)
Variable D : reste 0. (On garde $\overline{D}$ )
Résultat : $\overline{B}\overline{D}$

Groupe 2 : le bloc central

Nous avons un carré 2x2 parfait au centre, en $m_5, m_7, m_{13}$ et $m_{15}$ .

Variable A : passe de 0 à 1. (Élimination)
Variable B : reste 1. (On garde $B$ )
Variable C : passe de 0 à 1. (Élimination)
Variable D : reste 1. (On garde $D$ )
Résultat : $BD$

Tous les « 1 » sont couverts. Notre expression simplifiée finale est :

F = \overline{B}\overline{D} + BD

C’est la définition booléenne d’une porte XNOR — un fouillis de huit portes ET à 4 entrées s’effondre en un seul composant.

Diagramme du composant porte XNOR

Explorer le circuit XNOR simplifié

Piège courant : pourquoi le code Gray est non négociable

Une erreur fréquente consiste à dessiner les K-maps en ordre binaire standard — 00, 01, 10, 11. Ne le faites pas.

Si vous utilisez l’ordre binaire standard, vous brisez le principe d’adjacence. Regardez le saut de 01 à 10 : les deux bits changent ( $0 \to 1$ et $1 \to 0$ ). Si vous avez des « 1 » dans ces deux cases adjacentes, vous ne pouvez pas les simplifier parce que plus d’une variable change. La séquence en code Gray (00, 01, 11, 10) garantit que chaque pas sur la table correspond au changement d’exactement une variable. C’est cette « magie » qui permet aux mathématiques de fonctionner visuellement. Sans le code Gray, la K-map n’est qu’un tableau déroutant ; avec lui, c’est une calculatrice.

Vérification avec l’OSCILLOSCOPE_8CH

L’un des moments les plus satisfaisants en ingénierie numérique est de prouver que votre « petit » circuit fait exactement la même chose que le « gros ». Sur digisim.io, vous pouvez le faire en temps réel.

Construisez la version brute : utilisez huit portes ET et une grande porte OU pour représenter les mintermes originaux.
Construisez la version optimisée : placez en dessous une unique porte XNOR (ou son équivalent à deux ET et un OU).
Synchronisez les entrées : connectez les quatre mêmes composants INPUT_SWITCH aux deux circuits.
Analysez : connectez la sortie du circuit brut au canal 1 d’un OSCILLOSCOPE_8CH et la sortie optimisée au canal 2.

Lorsque vous basculez les interrupteurs à travers les 16 combinaisons, les chronogrammes sur l’OSCILLOSCOPE_8CH seront identiques. Cependant, en observant le retard de propagation ( $t_{pd}$ ), vous remarquerez que le circuit optimisé répond significativement plus vite. Dans un projet CPU à haute vitesse, ces nanosecondes font la différence entre une horloge à 1 MHz et une horloge à 10 MHz.

Applications concrètes : au-delà de la salle de classe

Les K-maps ne servent pas qu’à passer des examens ; elles sont le pain quotidien de la description matérielle.

1. Logique de contrôle de l’UAL

Dans un CPU 8 bits typique, l’UAL (Arithmetic Logic Unit) doit savoir s’il faut additionner, soustraire ou effectuer un ET bit à bit selon un « opcode ». Cet opcode peut faire 4 bits de large. Les ingénieurs utilisent des K-maps pour concevoir la logique du décodeur qui prend cet opcode 4 bits et active les lignes de commande spécifiques de l’ADDER_8BIT ou du COMPARATOR_8BIT. En minimisant cette logique, ils réduisent le temps de « décodage d’instruction », qui est un goulot d’étranglement critique des performances du CPU.

2. Machines à états finis (FSM)

Qu’il s’agisse d’un contrôleur de feu de circulation ou d’un gestionnaire de protocole complexe, les FSM reposent sur la « logique d’état suivant ». Cette logique examine l’état courant (stocké dans un REGISTER) et les entrées courantes pour décider de l’état suivant. Ces tables de vérité deviennent rapidement énormes. Les K-maps permettent aux concepteurs de trouver la manière la plus efficace de router ces signaux, économisant souvent des dizaines de portes dans l’implémentation finale.

Diagramme du composant ALU

Pièges courants

Erreurs courantes à éviter :

Entrées flottantes : chaque entrée de chaque porte ET doit être reliée à quelque chose. Une entrée flottante peut se comporter de façon prévisible dans un simulateur, mais dans le matériel réel, elle capte du bruit.
Oublier le repliement : vérifiez les coins et les bords. Certaines des simplifications les plus élégantes proviennent du regroupement des quatre coins ou des lignes du haut et du bas.
Groupes redondants : une fois tous les 1 couverts, arrêtez-vous. Ajouter un groupe supplémentaire « parce que ça fait joli » introduit des portes inutiles dans le circuit et va à l’encontre de l’objectif de la K-map.

La puissance des conditions « don’t care »

Dans de nombreuses conceptions réelles, certaines combinaisons d’entrée ne peuvent jamais survenir. Par exemple, un système BCD (Binary-Coded Decimal) utilise 4 bits pour représenter les chiffres 0-9, si bien que les combinaisons 1010 à 1111 n’apparaissent jamais. Dans une K-map, on marque ces entrées impossibles par un $X$ (don’t care) au lieu de 0 ou 1.

L’essentiel : vous pouvez traiter chaque $X$ comme un 0 ou un 1 — celui qui vous aide à former un plus grand groupe. Puisque ces entrées ne se produisent jamais en pratique, peu importe ce que le circuit produit en sortie pour elles.

Exemple : supposons qu’une fonction à 4 variables ait des 1 aux cases 0, 2, 8, 10 et des don’t cares aux cases 1 et 3. Sans les don’t cares, les quatre 1 (coins) se regroupent en $\overline{B}\overline{D}$ . Mais en traitant les cases 1 et 3 comme des 1, vous pouvez former un plus grand groupe de 4 sur la ligne du haut ( $\overline{A}\overline{B}$ ) en plus du groupe coin original, ce qui peut donner une expression totale plus simple. Les conditions don’t care réduisent fréquemment le nombre final de portes de 20 à 30 % dans les conceptions réelles.

Passez à l’étape suivante

Cet article fait partie de la série « Fondements de l’algèbre booléenne ». Lectures liées :

Maîtriser l’algèbre booléenne — les identités algébriques derrière le regroupement K-map.
Maîtriser la somme de produits (SOP) — la forme canonique produite par les K-maps.
Au-delà de la somme de produits : le produit de sommes — la minimisation duale.
Lois de De Morgan — les règles de transformation utilisées pour convertir entre formes.

La table de Karnaugh transforme une tâche algébrique complexe en puzzle visuel. Pour les fonctions jusqu’à 4 variables, elle produit de façon fiable des expressions SOP (ou POS) minimales. Pour 5 à 6 variables, les K-maps restent utilisables mais peu pratiques ; les méthodes algorithmiques comme Quine-McCluskey prennent le relais.

Construisez les circuits brut et optimisé de l’exemple traité, et observez l’alignement des chronogrammes sur l’oscilloscope. Démarrez un nouveau circuit pour vérifier.