Solveur de Tableau de Karnaugh (K-Map)

Le Solveur de Tableau de Karnaugh (K-Map) minimise toute fonction logique booléenne de 2 à 5 variables et visualise la simplification sous forme de tableau de Karnaugh classique avec des regroupements codés par couleur. Saisissez vos mintermes, maxtermes ou utilisez la table de vérité interactive — le solveur exécute l'algorithme de Quine-McCluskey en arrière-plan, identifie chaque implicant premier, marque les essentiels et produit l'expression minimale en Somme de Produits (SOP) ou Produit de Sommes (POS) avec une explication détaillée. Cliquez sur n'importe quel jeton d'implicant premier pour faire pulser les cellules qu'il couvre et comprendre comment le regroupement simplifie la logique.

Qu'est-ce qu'un Tableau de Karnaugh ?

Un tableau de Karnaugh (inventé par Maurice Karnaugh en 1953) est une représentation graphique d'une table de vérité, disposée de sorte que les cellules qui ne diffèrent que par une seule variable d'entrée soient physiquement adjacentes. L'astuce réside dans le codage en code Gray des lignes et colonnes : les étiquettes consécutives comme 00, 01, 11, 10 ne diffèrent que d'un seul bit. Cette adjacence permet de repérer visuellement des groupes de 1 (ou de 0) pouvant être combinés en un terme simplifié unique.

Pour n variables d'entrée, le tableau possède 2^n cellules. Un tableau à 4 variables est une grille 4×4 de 16 cellules ; un tableau à 5 variables est dessiné sous forme de deux grilles 4×4 adjacentes.

SOP vs POS : Quelle forme choisir ?

Somme de Produits (SOP)

La SOP regroupe les cellules à 1. Chaque groupe devient un produit (ET) de littéraux, et tous les groupes sont reliés par un OU. Exemple : AB'C + BD. La SOP est généralement le choix par défaut car elle correspond directement aux réseaux de portes ET–OU.

Produit de Sommes (POS)

Le POS regroupe les cellules à 0. Chaque groupe devient une somme (OU) de littéraux complémentés, et toutes les sommes sont reliées par un ET. Exemple : (A + B')(C + D'). Le POS est souvent plus compact lorsque la fonction contient plus de 1 que de 0.

L'outil calcule les deux formes indépendamment — changez de mode pour comparer le nombre de littéraux et choisir la solution la plus simple pour votre implémentation.

Règles de regroupement pour les tableaux de Karnaugh

• Groupes de puissances de deux uniquement : les groupes doivent contenir 1, 2, 4, 8 ou 16 cellules. Un groupe de 3 ou 5 est interdit.
• Forme rectangulaire : les cellules d'un groupe forment un rectangle (horizontalement, verticalement ou par repliement sur les bords).
• Adjacence circulaire (Wrap-around) : la ligne du haut est adjacente à celle du bas ; la colonne la plus à gauche est adjacente à celle de droite. C'est pourquoi l'ordre du code Gray est crucial.
• Privilégier les plus grands groupes : les groupes plus grands éliminent plus de variables, créant des termes plus courts. Un groupe de 8 cellules supprime 3 variables ; un groupe de 4 en supprime 2 ; un groupe de 2 en supprime 1.
• Chaque 1 doit être couvert : au moins un groupe doit couvrir chaque cellule à 1 (pour SOP) ou à 0 (pour POS).
• Le chevauchement est autorisé : un même 1 peut être couvert par plusieurs groupes si cela permet de former des groupes plus grands.
• Les don't-cares sont flexibles : ils peuvent être inclus si cela agrandit les groupes, mais ils n'ont pas l'obligation d'être couverts.

Implicants premiers et Implicants premiers essentiels

Un implicant premier est un groupe qui ne peut pas être agrandi davantage sans inclure un 0 (pour SOP). Le solveur liste tous les implicants premiers trouvés. Il sélectionne ensuite une couverture minimale : l'ensemble le plus réduit d'implicants premiers couvrant tous les mintermes requis.

Un implicant premier essentiel est marqué ESSENTIEL lorsqu'il est le seul à couvrir au moins un minterme spécifique. Toute expression minimale doit inclure tous les implicants premiers essentiels. Après les avoir sélectionnés, les mintermes restants sont couverts par les implicants premiers additionnels les moins coûteux.

Conditions Don't-Care (Indifférentes)

Un don't-care (noté X sur le tableau) est une combinaison d'entrée dont la sortie est non pertinente — soit elle n'apparaît jamais dans le circuit réel, soit sa valeur importe peu. L'algorithme est libre de traiter chaque X comme un 0 ou un 1 pour obtenir l'expression la plus simple. En pratique, les don't-cares réduisent souvent le nombre de littéraux de 30 à 60 %. Un exemple courant : les décodeurs de chiffres décimaux qui n'utilisent que 10 des 16 combinaisons d'entrée sur 4 bits, laissant les combinaisons 10 à 15 en don't-cares.

L'algorithme de Quine-McCluskey

Le tableau de Karnaugh est visuel, mais devient complexe au-delà de 4 ou 5 variables. L'algorithme de Quine-McCluskey (QM) est son équivalent tabulaire — rigoureux et évolutif. Ce solveur utilise QM en interne :

1. Lister les mintermes en binaire, les grouper par nombre de bits à 1.
2. Combiner les paires des groupes adjacents (différant d'un seul bit), en remplaçant ce bit par un tiret. Exemple : 0011 + 0111 → 0-11.
3. Répéter jusqu'à ce qu'aucune combinaison ne soit plus possible. Les termes restants sont les implicants premiers.
4. Construire un tableau d'implicants premiers — les lignes sont les implicants, les colonnes sont les mintermes. Identifier les essentiels (colonnes avec une seule coche).
5. Méthode de Petrick / recherche exhaustive : pour les mintermes non couverts, trouver le plus petit ensemble d'implicants supplémentaires.

Comment utiliser ce calculateur

1. Sélectionner le nombre de variables : 2, 3, 4 ou 5. Le tableau s'adapte automatiquement.
2. Choisir une méthode de saisie :
   • Mintermes : saisissez les indices où F = 1 (ex. 1, 3, 5, 7) et les éventuels don't-cares.
   • Maxtermes : saisissez les indices où F = 0. Le solveur déduit le reste.
   • Table de vérité : cliquez sur chaque ligne pour alterner entre 0, 1 et X.
3. Choisir SOP ou POS en sortie. Comparez les deux en basculant — l'une est souvent plus courte.
4. Cliquer sur Résoudre. Le tableau apparaît avec chaque implicant premier en couleur.
5. Inspecter les étapes : le détail Quine-McCluskey montre la dérivation de chaque implicant.

Exemple pratique : fonction à 4 variables avec Don't-Cares

Soit F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

Sans les don't-cares, la SOP minimale nécessiterait plusieurs termes. En traitant {0, 2} comme des 1, le solveur crée le groupe de 4 cellules A'B' (couvrant 0, 1, 2, 3). En traitant 5 comme un 1, il étend la couverture de CD. La simplification obtenue est :

Seulement 4 littéraux — contre plus de 10 sans l'astuce des don't-cares. Vous pouvez charger cet exemple précis via le bouton "4-var avec Don't-Cares" ci-dessus.

Pourquoi minimiser les fonctions booléennes ?

• Moins de portes = coût matériel réduit, surface de puce optimisée, consommation électrique moindre.
• Circuits plus rapides : moins de délais de commutation sur le chemin critique.
• Documentation plus claire : une expression concise est plus facile à vérifier et à maintenir.
• Base de la conception numérique : tout outil de synthèse FPGA utilise un descendant de Quine-McCluskey (Espresso-II, etc.).

Limitations et alternatives

• Plus de 5 variables : Les K-maps deviennent visuellement illisibles. Cet outil supporte jusqu'à 5 variables en scindant l'affichage. Au-delà, fiez-vous aux étapes de Quine-McCluskey ou à des outils comme ABC / Espresso.
• Aléas logiques (Hazards) : Une couverture minimale peut contenir des aléas statiques. Pour une conception sans aléas, incluez des implicants redondants.
• Minimisation multi-sorties : Si plusieurs fonctions partagent des variables, une minimisation conjointe est préférable. Cet outil traite une fonction à la fois.

Foire Aux Questions

Qu'est-ce qu'un tableau de Karnaugh ?

Un tableau de Karnaugh (K-map) est une méthode visuelle pour minimiser les expressions booléennes. Les cellules sont disposées de manière à ce que les cellules adjacentes ne diffèrent que par une seule variable (ordre du code Gray). Le regroupement des 1 dans des rectangles de taille 1, 2, 4, 8 ou 16 révèle l'expression minimale en Somme de Produits.

Quelle est la différence entre SOP et POS ?

La SOP (Sum of Products) regroupe les cellules à 1 et effectue un OU logique entre leurs termes produits, ex. A'B + CD. La POS (Product of Sums) regroupe les cellules à 0 et effectue un ET logique entre leurs termes sommes, ex. (A + B')(C' + D). Les deux décrivent la même fonction, mais une forme est généralement plus compacte.

Que sont les don't-cares et pourquoi les utiliser ?

Les termes don't-care (marqués X) sont des combinaisons d'entrées dont la valeur de sortie est non pertinente — soit elles ne se produisent jamais, soit leur valeur n'a pas d'importance. Le solveur peut les traiter comme 0 ou 1, selon ce qui donne l'expression la plus simple. Les don't-cares réduisent souvent considérablement le nombre de littéraux.

Qu'est-ce qu'un implicant premier ?

Un implicant premier est le plus grand groupe possible de cellules adjacentes à 1 (taille puissance de deux) qui ne peut pas être étendu davantage. Un implicant premier essentiel est celui qui couvre de manière unique au moins un minterme et doit être inclus dans chaque expression minimale.

Comment fonctionne l'algorithme de Quine-McCluskey ?

Quine-McCluskey est l'équivalent tabulaire d'un tableau de Karnaugh, adapté aux variables nombreuses. Il liste tous les mintermes en binaire, les regroupe par nombre de 1, et combine itérativement les paires qui diffèrent d'un seul bit. Les termes qui ne peuvent plus être combinés sont des implicants premiers. Un tableau d'implicants premiers permet ensuite de sélectionner la couverture minimale.

Combien de variables ce solveur de K-map supporte-t-il ?

Cet outil supporte de 2 à 5 variables. Un tableau de Karnaugh à 5 variables est affiché sous forme de deux tableaux 4x4 adjacents (un pour A=0, un pour A=1). Au-delà de 5 variables, les tableaux de Karnaugh deviennent peu pratiques ; utilisez les étapes de Quine-McCluskey pour les fonctions plus larges.

En savoir plus

• Tableau de Karnaugh — Wikipédia
• Algorithme de Quine-McCluskey — Wikipédia
• Méthode de Petrick — Wikipédia