Apprendre › Chapitre 4

Tableaux de Karnaugh à 2, 3 et 4 variables et cas indifférents (X)

7 min de lecture · Équipe bitGateLab

Simplifier avec l'algèbre de Boole fonctionne, à condition de « voir » quelle loi appliquer. Le tableau de Karnaugh transforme cette recherche en exercice visuel : il dispose la table de vérité dans une grille où deux cases voisines ne diffèrent que par une seule variable, et simplifier revient alors à entourer des groupes de uns. Vous allez apprendre ici à construire des tableaux à 2, 3 et 4 variables, à regrouper correctement (y compris par les bords, qui « se rejoignent ») et à tirer parti des cas indifférents.

L'idée : des cases voisines, une seule variable de différence

La loi d'adjacence dit que AB + AB = A : deux termes qui ne diffèrent que par une seule variable fusionnent, et cette variable disparaît. Le tableau de Karnaugh dispose les mintermes de sorte que deux cases partageant un côté remplissent toujours cette condition. Pour y parvenir, les en-têtes des lignes et des colonnes ne suivent pas l'ordre binaire 00, 01, 10, 11, mais le code Gray : 00, 01, 11, 10. Entre deux valeurs consécutives, un seul bit change, et il en va de même entre la dernière et la première (10 et 00). C'est pourquoi le tableau se comporte comme si ses bords opposés étaient collés l'un à l'autre.

Tableaux à 2 et 3 variables

Le tableau à deux variables comporte 4 cases : A sur les lignes et B sur les colonnes. Celui à trois variables comporte 8 cases : A sur les lignes et BC sur les colonnes, dans l'ordre Gray. Le numéro inscrit dans chaque case indique le minterme qui lui correspond :

Remarquez que m3 et m2 se trouvent dans cet ordre : c'est l'effet du code Gray, et la cause de nombreuses erreurs lorsqu'on remplit le tableau à la main.

Règles de regroupement

• Les groupes ne peuvent contenir que des uns (ou des X, comme vous le verrez plus loin), jamais de zéros.
• La taille de chaque groupe doit être une puissance de 2 : 1, 2, 4, 8 ou 16 cases.
• Les groupes sont des rectangles de cases adjacentes, adjacence par les bords comprise. Les diagonales ne comptent pas.
• Faites chaque groupe aussi grand que possible : un groupe de 2^k cases élimine k variables.
• Utilisez le plus petit nombre de groupes qui couvre tous les uns. Les groupes peuvent se chevaucher.

Pour lire un groupe, examinez chaque variable : si elle garde la même valeur dans toutes les cases du groupe, elle apparaît dans le terme (sans barre si elle vaut 1, avec une barre si elle vaut 0) ; si elle change, elle est éliminée.

Tableau à 4 variables et adjacence par les bords

Avec quatre variables, le tableau comporte 16 cases : AB sur les lignes et CD sur les colonnes, toutes deux dans l'ordre Gray.

La colonne de gauche est voisine de celle de droite, et la ligne du haut est voisine de celle du bas. Par conséquent, les quatre coins (m0, m2, m8, m10) forment un groupe valide de 4 cases : dans toutes, B = 0 et D = 0, ce qui se lit BD.

Cas indifférents (X)

Il arrive que certaines combinaisons d'entrée ne se produisent jamais, ou que leur sortie soit sans conséquence. Par exemple, dans un chiffre BCD, les codes 1010 à 1111 n'existent pas. Sur ces lignes, on écrit un X (appelé aussi don't care) et on le note à part sous la forme d(...). Au moment de regrouper, chaque X peut être pris comme un 1 s'il vous aide à former un groupe plus grand, ou ignoré dans le cas contraire. Il n'est jamais nécessaire de couvrir un X.

Erreurs fréquentes

• Ordonner les en-têtes en binaire (00, 01, 10, 11) au lieu du code Gray. Les cases voisines ne diffèrent plus d'une seule variable et les groupes sont faux.
• Former des groupes de 3 ou 6 cases. Seules les puissances de 2 sont permises.
• Oublier l'adjacence par les bords et celle des quatre coins, ce qui laisse des groupes plus petits que nécessaire.
• Ajouter un groupe dont toutes les cases sont déjà couvertes par d'autres. Il est superflu et ajoute des portes.
• Se croire obligé de couvrir les X. On ne les utilise que lorsqu'ils agrandissent un groupe.

Essayez dans le simulateur

Le module Karnaugh dispose la fonction dans l'ordre Gray, marque les groupes et écrit l'expression minimale ; vous pouvez ainsi comparer votre regroupement à celui que propose l'outil.

1. Créez une fonction de quatre variables et saisissez les uns de l'exemple 2.
2. Regroupez d'abord vous-même sur papier et écrivez votre résultat.
3. Observez les groupes que marque le tableau et l'expression obtenue ; si elle diffère de la vôtre, cherchez quel groupe n'était pas maximal.
4. Saisissez l'exemple 3 en marquant comme X les cases 0, 2 et 5, puis observez comment la simplification change lorsque vous retirez ces X.
5. Convertissez le résultat en circuit et changez les entrées pour confirmer qu'il coïncide avec la table.

Exercices

1. Simplifiez F(A, B, C) = Σm(0, 2, 4, 6).
   Réponse

   Les colonnes BC = 00 et BC = 10 sont voisines par le bord et elles sont pleines. Dans les quatre cases, C = 0 : F = C.

2. Simplifiez F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
   Réponse

   Coins : BD. Bloc central m5, m7, m13, m15 : BD. F = BD + BD, c'est-à-dire la XNOR de B et D.

3. Simplifiez F(A, B, C, D) = Σm(4, 5, 6, 7, 12, 13, 14, 15).
   Réponse

   Les lignes AB = 01 et AB = 11 forment un groupe de 8 ; seule B reste à 1. F = B.

4. Un chiffre BCD (A est le bit de poids fort) doit activer une sortie lorsqu'il vaut 5 ou plus. Simplifiez F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15).
   Réponse

   Avec les X, les lignes AB = 11 et AB = 10 forment un groupe de 8 : A. Le bloc m5, m7, m13, m15 donne BD et le bloc m6, m7, m14, m15 donne BC. F = A + BD + BC = A + B(C + D).

Au-delà de quatre ou cinq variables, le tableau devient difficile à lire ; pour ces cas, il existe une procédure tabulaire, la méthode de Quine-McCluskey.