qui devient en supprimant les termes inutiles :

3. 4. - MÉTHODE DE KARNAUGH        (Retour à la théorie 3)

La simplification algébrique des équations Booléennes n'est pas toujours évidente et demande de l'intuition. A l'inverse, la méthode de Karnaugh permet de mettre en évidence les monômes adjacents à l'aide d'un tableau sans difficulté.

Cette méthode fonctionne très bien de 2 à 5 variables, elle devient complexe au-delà.

3. 4. 1. - TABLEAUX DE KARNAUGH

a) - Le tableau

Le tableau de Karnaugh est une forme particulière de la table de vérité que nous avons utilisée jusqu'ici (table de vérité figure 53) :

Une table de vérité comprend autant de colonnes que de variables d'entrée. Elle comprend une ou plusieurs autres colonnes, celles de la ou des variables de sortie. Toutes les combinaisons de valeurs que peuvent prendre les variables d'entrée sont explorées en comptant dans un ordre binaire. La valeur de la ou des variables de sortie est indiquée en face de la combinaison correspondante.

Le tableau de Karnaugh comprend lui 2ⁿ cases, n étant le nombre de variables d'entrées de la fonction considérée.

b) - Cas de deux variables

Dans ce cas, le nombre de cases est 2ⁿ = 2² = 4   (figure 54).

L'ordre des variables en abscisse ou en ordonnée n'a pas d'importance, seul est très important le fait que lorsque l'on passe d'une case à la case adjacente, une seule variable change.

Exemple :

Représentons la fonction f = a . b "fonction ET"   (figure 55).

Nous voyons facilement que l'on a mis la valeur binaire que peut prendre la sortie à l'intérieur de la case pour laquelle les variables ont la valeur portée en abscisse et en ordonnée.

f vaut 1 uniquement pour a = 1 et b = 1

c) - Cas de trois variables   (figure 56).

Alors que pour deux variables, le tableau était carré, il est maintenant rectangulaire ; en effet, nous avons représenté les variables bc sur une même colonne.

On peut remarquer que l'ordre de la quatrième et de la troisième ligne paraît inversé. En réalité, il n'en est rien. On utilise seulement le code Gray ou binaire réfléchi afin de ne faire changer qu'une seule variable à la fois horizontalement ou verticalement.

d) - Cas de quatre variables   (figure 57)

On retrouve un carré qui comporte 2⁴ cases soit :

2⁴ = 16 cases

Nous voyons à nouveau, ce qui est absolument indispensable, que grâce au code Gray, en passant d'une case à l'autre horizontalement ou verticalement une seule variable change.

3. 4. 2. - SIMPLIFICATION GRAPHIQUE

a) - Il faut donc maintenant utiliser le tableau de Karnaugh pour rechercher les monômes adjacents au lieu de les rechercher algébriquement.

La table de Veitch (figure 58) comporte en abscisse et en ordonnée les expressions algébriques représentées pour chaque case. Par exemple : case ac.

La table de Karnaugh (figure 59) donne, elle, pour chaque case les valeurs que prennent les variables en abscisse et en ordonnée.

Dans les deux systèmes, on indique à l'intérieur de chaque case la valeur 1 ou 0 prise par le monôme considéré.

On peut voir facilement que deux monômes adjacents vont se trouver dans deux cases voisines puisque l'on a dit au départ que les tableaux de Karnaugh étaient faits de telle sorte qu'on ne change qu'une variable lorsqu'on change de case.

Il suffira donc pour chaque combinaison de variables de noter 1 ou 0 dans la case correspondante, selon le résultat trouvé pour la valeur de la fonction considérée, puis de regrouper les cases adjacentes dont le contenu est à 1 par groupe de 2, 4 ou 8 ou de 2ⁿ termes adjacents.

Exemple   (figure 60)

Les regroupements (ici de 2 termes) sont figurés en rouge, on notera que les cases ab et abc sont bien les cases représentant des monômes adjacents. On peut comparer la table représentée à la surface d'un tore si l'on essaie de rapprocher toutes les cases des monômes adjacents l'une de l'autre ; ainsi, si les cases des quatre coins du tableau étaient à 1, on pourrait constituer un groupement de 4 cases avec elles.

b) - Exemple pour un tableau à 3 variables :

Soit l'expression : S = ac + c + a liant la variable S aux variables a, b, c.

Établissons la table de vérité   (figure 61)

• Simplification par l'algèbre

• Simplification par les tableaux de Karnaugh

Reportons les valeurs de S dans le tableau de Karnaugh (figure 62) :

Réalisons les groupements a et c.

Nous pouvons écrire :

S = a + c

c) - Exemple pour un tableau à quatre variables :

Soit l'expression : S = abcd + abd + bc liant la variable S aux variables a, b, c, d.

Établissons la table de vérité   (figure 63) :

• Simplification algébrique

S = abcd + abd + bc

Mettons abd en facteur :

S = abd (c + 1) + bc

Utilisons l'identité remarquable (x + 1) = 1 d'où (c + 1) = 1 d'où l'on peut écrire :

S = abd + bc

• Simplification par les tableaux de Karnaugh

Reportons la valeur de S dans le tableau (figure 64).

Réalisons les groupements abd et bc.

Nous pouvons écrire :

S = abd + bc

d) - Cas de 5 variables

A partir de cinq variables, le problème se complique un peu. En effet, il n'est pas possible d'obtenir sur une surface plane un tableau dans lequel une case soit adjacente à 5 autres cases. Il est toutefois possible d'utiliser la méthode de Karnaugh en faisant deux tableaux (figure 65).

Nous voyons qu'en superposant les deux tableaux (figure 66), on peut obtenir une case donnée X, cinq cases adjacentes.

La figure 67 montre un cas ou l'on pourrait effectuer trois groupements :

      Groupement rouge : les quatre coins dans un même plan (tableau pour e = 0)

      Groupement vert : deux cases dans le même plan pour e = 1

      Groupement bleu : deux cases superposées.

NOTE :

Nous voyons dans cet exemple que le groupement bleu semble être superflu. Il est nécessaire lorsque l'on utilise une technologie électrique ou électronique pour des raisons de bon fonctionnement qu'il y ait regroupement entre les groupements.

Cette condition n'est toutefois pas obligatoire en pneumatique.

Un groupement ne peut comprendre que 2ⁿ cases, c'est-à-dire 1, 2, 4, 8, 16, 32,... cases.

e) - Cas de 6 variables

On utilise le même principe avec quatre tableaux pour six variables.

L'exemple de la figure 68 montre trois groupements :

      en vert sur quatre plans

      en rouge sur deux plans

      en bleu dans le même plan

La figure 69 montre dans l'espace un exemple de cases adjacentes.

Au-delà de 6 variables, la méthode de Karnaugh n'étant plus valable, on utilise la méthode dite de Mac Cluskey que nous décrirons ultérieurement afin de ne pas apporter de confusion avec celle de Karnaugh.

Nous allons continuer d'approfondir cette leçon par des applications pratiques des tableaux de Karnaugh sur une autre page afin de ne pas encombrer celle-ci. 

Cliquez ici pour la leçon suivante ou dans le sommaire prévu à cet effet.	Haut de page
Page précédente	Page suivante

Nombre de pages vues, à partir de cette date : le 15 JUILLET 2019