Électronique numérique : logique/Compléments sur la simplification

Simplification par Karnaugh pour plus de quatre variables

Les tableaux de Karnaugh permettent d'obtenir les formes disjonctives ou conjonctives simplifiées en regroupant des termes (contenants des 1 ou des 0). Cela fonctionne très bien jusqu'à 4 variables. Que se passe-t-il après ?

Si l'on réalise un tableau de Karnaugh à 5 variables (partie gauche de la figure ci-dessous) on remarque qu'à côté des regroupements traditionnels il en existe qui ne sont plus contigus (flèche rouge sur le dessin).


Définition
Pour deux cases distinctes, on parle de contiguïté géométrique (ou physique) si les deux cases qui sont l'une à côté de l'autre. Pour deux cases distinctes, on parle de contiguïté logique si les deux cases ne diffèrent que par une valeur logique.

Ce qui fait l'intérêt des tableaux de Karnaugh c'est que la contiguïté géométrique est équivalente presque partout à la contiguïté logique. Il n'y a que sur les bords où ce n'est plus vrai. Tout cela simplifie énormément les techniques de simplifications.

Cette propriété est perdue si l'on dépasse les 4 variables comme cela est montré dans la partie gauche de la figure ci-dessous. Oui les deux rectangles rouges se simplifient car passer de l'un à l'autre se fait par changement d'une seule variable seulement. Ils sont contigus logiquement mais malheureusement pas physiquement. La simplification est donc plus difficile à mettre en œuvre dans ce tableau de Karnaugh, mais pas impossible. On discute de ces tableaux de Karnaugh à cinq variables dans un autre projet.

Une technique plus intéressante consiste à réaliser un tableau de Karnaugh dans l'espace.

ATTENTION : les parties gauches et droites de cette figure ne correspondent pas à la même fonction logique !

La partie droite de la figure ci-dessus est composée de deux tableaux de Karnaugh superposés, un pour la cinquième variable e = 0 et un pour e = 1. On regroupe ensuite dans l'espace, sur un ou deux tableaux (avec des carrés, des rectangles, des cubes et des parallélépipèdes ayant tous un nombre de cases qui est une puissance de deux. En pratique on peut dessiner les tableaux de Karnaugh les uns à côté des autres et à se les imaginer superposés.

Exemple de superposition pour six variables

Pour six variables, on peut utiliser 4 tableaux de karnaugh superposés (attention à l'ordre !), mais cette technique ne marche plus au-delà de six variables.

Pour éviter cette représentation spatiale (qui nécessite d'être un spécialiste de tetris 3D), on utilise la simplification algébrique.

Simplification algébrique

Ce chapitre utilise les propriétés de l'algèbre de Boole expliquées ici : Algèbre de Boole.


Définition
Une transformation par dualité consiste à transformer chaque membre d'une égalité pour obtenir une nouvelle égalité. La transformation consiste à changer tous les 0 en 1, tous les 1 en 0, tous les + en . et tous les . en +. ATTENTION, la transformation par dualité d'une expression ne donne pas une expression égale.

La technique pour obtenir une forme disjonctive simplifiée consiste à effectuer les parenthèses et ensuite à appliquer une des règles suivantes :

Tableau des identités remarquables

Noms	forme disjonctive	forme conjonctive
élément neutre	a . 1 = a	a + 0 = a
élément absorbant	a . 0 = 0	a + 1 = 1
idempotence	a . a = a	a + a = a
complément	$a.{\bar {a}}=0$	$a+{\bar {a}}=1$
commutativité	a . b = b . a	a + b = b + a
associativité	(a . b) . c = a . (b . c)	(a + b) + c = a + (b + c)
distributivité	a . (b + c) = a . b + a . c	a + (b . c) = (a + b).(a + c)
Relation diverse	a + (a . b) = a	a . (a + b) = a
Relation diverse	$a+({\bar {a}}.b)=a+b$	$a.({\bar {a}}+b)=a.b$
Relation diverse	$a+({\overline {a.b}})=1$	$a.({\overline {a+b}})=0$
Relation diverse	$a.({\overline {a.b}})=a.{\bar {b}}$	$a+({\overline {a+b}})=a+{\bar {b}}$
de Morgan	${\overline {a.b}}={\bar {a}}+{\bar {b}}$	$({\overline {a+b}})={\bar {a}}.{\bar {b}}$
de Morgan	$a.b={\overline {{\bar {a}}+{\bar {b}}}}$	$(a+b)={\overline {{\bar {a}}.{\bar {b}}}}$
consensus	$a.b+{\bar {a}}.c+b.c=a.b+{\bar {a}}.c$	$(a+b).({\bar {a}}+c).(b+c)=(a+b).({\bar {a}}+c)$
consensus généralisé	$a.b+{\bar {a}}.c+b.c.d=a.b+{\bar {a}}.c$	$(a+b).({\bar {a}}+c).(b+c+d)=(a+b).({\bar {a}}+c)$

Au temps des débuts de la logique, ce tableau était à savoir par cœur. Aujourd'hui, il existe des outils informatiques qui permettent de simplifier. Les seules choses à connaître sont peut-être liées à l'inclusion et à la combinaison expliquées plus loin.

Remarque importante : il est possible de passer d'une colonne à l'autre par dualité. Cela veut dire que seule la moitié du tableau est à connaître ! Le reste s'en déduit tout simplement.

Consensus

Le consensus mérite que l'on s'y arrête. Simplifier par consensus est très simple à partir du moment où l'on est capable de le détecter. Si ce n'est pas le cas, il vous faudra plusieurs lignes pour le faire.


Définition
Pour qu'il y ait un consensus entre deux termes il faut que dans ces deux termes une variable apparaisse complémentée dans un terme et pas dans l'autre. Le consensus est le produit de ce qui reste si l'on enlève la variable en question.

Exemple : $a.b+{\bar {a}}.c$ il y a un consensus de a qui est b.c


Définition
Pour qu'il y ait une simplification par consensus, il faut qu'il y ait un consensus et qu'un autre terme contienne le consensus. Ce terme en question doit disparaître.

Exemple : regardez les lignes du tableau ci-dessus pour consensus et consensus généralisé.

Remarques :

il ne faut pas confondre le consensus avec la simplification par consensus ! Il peut y avoir un consensus entre deux termes sans qu'il n'y ait de simplification par consensus.
le consensus ne sert pas qu'à simplifier. Il peut être parfois volontairement ajouté pour éviter les glitch mais nous n'aborderons pas ce problème ici.

Simplifications algébriques

Si l'on cherche une forme disjonctive simplifiée on peut procéder de la manière suivante :

on effectue d'abord toutes les parenthèses pour trouver une forme disjonctive,
on regroupe tous les termes qui ne diffèrent que d'une variable (combinaison) en ajoutant ces termes simplifiés,
on retire ensuite tous les termes qui sont inclus dans d'autres termes,
on cherche les simplifications par consensus.

Les combinaisons peuvent se faire plusieurs fois.

Exemple de combinaison :

$a.{\bar {b}}.{\bar {c}}+a.{\bar {b}}.c=a.{\bar {b}}$

La simplification par combinaison demande un peu de doigté (non exigé d'un étudiant de L1). Car si quatre termes se regroupent et que vous ne le voyez pas, vous pouvez faire des combinaisons dans le mauvais ordre. C'est pour cela que l'on vous dit d'ajouter les termes simplifiés : il permettront à la fin de retirer les termes initiaux par inclusion.

Exemple d'inclusion

$a.{\bar {b}}.{\bar {c}}\subset a.{\bar {b}}$

qui permet de simplifier :

$a.{\bar {b}}.{\bar {c}}+a.{\bar {b}}=a.{\bar {b}}$

Par dualité, j'obtiens aussi :

$a+{\bar {b}}+{\bar {c}}\subset a+{\bar {b}}$

qui permet de simplifier :

$(a+{\bar {b}}+{\bar {c}}).(a+{\bar {b}})=a+{\bar {b}}$

Exercices

Exercice 1

Utiliser les relations algébriques pour simplifier les équations suivantes et réaliser la synthèse en ET-NON.

$y_{1}={\bar {a}}.b.c+a.c+(a+b).{\bar {c}}$

$y_{2}=b.c+a.c+a.b+b$

$y_{3}=(a.{\bar {b}}+c).(a+{\bar {b}}).c$

$y_{4}=(a.c+b.{\bar {c}}).(a+{\bar {c}}).b$

$y_{5}={\bar {a}}.b.c+a.c+(a+b).{\bar {c}}$

$y_{6}=({\bar {a}}.b+a.{\bar {b}}).({\bar {a}}.{\bar {b}}+a.b)$

Elements de correction de l'exercice 1

$y_{1}={\bar {a}}.b.c+a.c+(a+b).{\bar {c}}={\bar {a}}.b.c+a.c+a.{\bar {c}}+b.{\bar {c}}$

Une simplification par combinaison donne : $y_{1}={\bar {a}}.b.c+a+b.{\bar {c}}$
La distributivité du + par rapport au . donne : $y_{1}=({\bar {a}}+a).(b+a).(c+a)+b.{\bar {c}}$
Le premier terme vaut un et si l'on effectue, on trouve : $y_{1}=b.c+a.c+b.a+a.a+b.{\bar {c}}$
Simplification par inclusion : $y_{1}=b.c+a+b.{\bar {c}}$
Simplification par combinaison : $y_{1}=a+b$