Le tableau de Karnaugh

Avec l'algèbre, tu cherches des factorisations sans savoir si tu as trouvé la plus courte. Le tableau de Karnaugh règle ce problème pour trois ou quatre variables. C'est une autre façon de dessiner la table de vérité, rangée de telle sorte que les simplifications sautent aux yeux : au lieu de calculer, tu entoures des paquets de 1. Maurice Karnaugh l'a proposé en 1953, en améliorant un diagramme présenté un an plus tôt par Edward Veitch. Tu vas construire des tableaux de trois et quatre variables, faire les bons regroupements et utiliser les cases indifférentes, jusqu'à un cas réel : la commande d'un segment d'afficheur.

Pour trois variables, le tableau a deux lignes pour A et quatre colonnes pour B et C. Pour quatre variables, quatre lignes pour A et B, quatre colonnes pour C et D. Le point essentiel est l'ordre des lignes et des colonnes : 00, 01, 11, 10. C'est le code de Gray du module 1. Grâce à lui, deux cases voisines ne diffèrent que par une seule variable. Chaque case correspond à une ligne de la table de vérité : tu y recopies simplement la valeur de la sortie. Attention à ne pas mettre 10 avant 11 : c'est l'erreur la plus fréquente.

Ensuite, tu entoures les 1 par paquets rectangulaires. Un paquet contient une, deux, quatre, huit ou seize cases, jamais trois ou six. Fais des paquets les plus grands possible, et le moins de paquets possible. Chaque 1 doit être couvert au moins une fois, et un 1 peut appartenir à plusieurs paquets si cela agrandit un regroupement. Aucun 0 ne doit être entouré. Enfin, le tableau se replie sur lui-même : la colonne de gauche touche celle de droite, la ligne du haut touche celle du bas, et les quatre coins forment un paquet possible.

Comment lire un paquet ? Regarde chaque variable. Si elle change de valeur à l'intérieur du paquet, elle disparaît. Si elle garde la même valeur, elle reste : telle quelle si elle vaut 1, barrée si elle vaut 0. Un paquet de deux cases fait disparaître une variable, un paquet de quatre en fait disparaître deux, un paquet de huit en fait disparaître trois. Chaque paquet donne un produit, et l'équation simplifiée est la somme de ces produits. Pour le vote majoritaire, tu trouves trois paquets de deux cases, et donc directement A et B, ou B et C, ou A et C.

Les cases indifférentes, notées X, sont celles des combinaisons impossibles ou sans importance. Dans le tableau, tu as le droit de les compter comme des 1 quand cela agrandit un paquet, et de les ignorer sinon. Tu n'es jamais obligé de les couvrir. Un exemple classique : un circuit qui reçoit un chiffre en BCD sur quatre bits. Les codes de 1010 à 1111 n'arrivent jamais, ce qui fait six cases X sur seize. Bien utilisées, elles réduisent souvent beaucoup le nombre de portes. Note quand même, dans ton dossier, ce que fera le circuit si l'une de ces combinaisons arrive par erreur.

Voici un cas réel : l'afficheur à sept segments d'un compteur, qui reçoit un chiffre en BCD sur quatre bits, D étant le poids fort et A le poids faible. Le segment a, la barre du haut, doit s'allumer pour les chiffres 0, 2, 3, 5, 6, 7, 8 et 9, et rester éteint pour 1 et 4. Les codes 10 à 15 sont des X. Grâce aux X, le tableau donne quatre paquets : huit cases pour D, huit pour B, quatre pour C et A, et les quatre coins pour non C et non A. L'équation tient en une ligne : a égale D ou B ou C et A, ou non C et non A.

Une simplification se vérifie toujours avant de câbler. Reprends ta table de vérité et, pour chaque ligne, calcule la sortie avec l'équation simplifiée. Elle doit donner la même valeur partout, sauf sur les X, où elle peut donner ce qu'elle veut. Le simulateur Digital sait générer un circuit à partir d'une table de vérité, en la minimisant, et lancer des cas de test automatiques. Mais fais au moins une fois la vérification à la main : c'est là que tu repères une colonne rangée dans le mauvais ordre ou un paquet de trois cases.

La méthode se déroule toujours de la même façon. Range les lignes et les colonnes dans l'ordre 00, 01, 11, 10. Entoure les 1 par paquets de une, deux, quatre ou huit cases, les plus grands possible, en pensant aux bords et aux coins. Utilise les X quand ils agrandissent un paquet. Lis chaque paquet en gardant les variables qui ne changent pas. Au-delà de quatre variables, le tableau devient vite difficile à lire, et on passe à des méthodes automatiques comme celle de Quine-McCluskey. Dans le lab de ce module, tu vas appliquer toute la chaîne à l'alarme d'un local technique.