Chapitre 4

Minimisation

La minimisation est une partie importante du design de circuits logiques. On doit

simplifier le plus possible la fonction logique avant d’essayer d’implanter le circuit logique.
Deux types de minimisation sont possibles : minimisation au niveau logique, et la minimi-
sation au niveau électronique. Dans le premier cas, on manipule les équations pour obtenir
une fonction logique plus simple. Dans le deuxième cas, on réarrange le circuit logique
pour réduire sa complexité, et son coût.

4.1 Diagrammes de Karnaugh

La complexité des circuits logiques est directement reliée à la complexité de la fonction

logique qu’elle implémente. On peut utiliser les théorèmes pour simplifier la fonction
logique, mais ce peut être long et difficile pour des fonctions de plusieurs variables. Une
méthode très utilisée pour simplifier des fonctions logiques est la méthode des diagrammes
de Karnaugh.

Les équations produites par les diagrammes de Karnaugh sont toujours sous l’une de
deux formes : somme de produits ou produits de sommes. L’équation résultante minimise
le nombre de termes, et donc la complexité du circuit logique correspondant.

4.1.1 Diagramme à deux variables

Le plus simple diagramme de Karnaugh est celui à deux variables, montré à la figure
4.1. Une fonction à deux variables possède un maximum de quatre mintermes, et donc

1
 CHAPITRE 4. MINIMISATION

le diagramme de Karnaugh est un carré divisé en quatre. La première figure montre

l’emplacement des mintermes, et la seconde figure montre l’équation qui correspond à
chaque minterme.

Y Y
Y Y
0 1 0 1
X X
0 m0 m1 0 X0Y 0 X0Y

X 1 m2 m3 X 1 XY 0 XY

Figure 4.1 – Diagramme de Karnaugh pour une fonction à 2 variables

Le diagramme de Karnaugh (ou table de Karnaugh) est rempli à partir de la table de

vérité. On ajoute les 1 et 0 aux endroits appropriés, selon l’emplacement du minterme.
Pour simplifier la fonction, on essaie de créer des rectangles les plus gros possibles en
regroupant des 1, pour obtenir des mintermes, ou des 0, pour obtenir des maxtermes. Deux
exemples sont montrés à la figure 4.2.

Y Y
Y Y
0 1 0 1
X X
0 0 0 0 0 1

X 1 0 1 X 1 1 1

X ·Y X +Y
Figure 4.2 – Exemples de diagrammes de Karnaugh pour une fonction à 2 variables

4.1.2 Diagramme à trois variables

Le diagramme de Karnaugh pour trois variables est montré à la figure 4.3. Noter que
les mintermes sont organisés comme un code Gray : un seul bit change en passant d’une
case à une autre. Le processus de simplification est le même que celui de deux variables :
on essaie de créer des carrés ou rectangles qui englobent le plus de 1. Dans tous les cas,
que ce soit à 2, 3, 4 variables ou plus, il faut minimiser le nombre de regroupements, et
maximiser la taille des regroupements.

2
 CHAPITRE 4. MINIMISATION

Y
YZ
00 01 11 10
X
0 m0 m1 m3 m2

X 1 m4 m5 m7 m6

Figure 4.3 – Diagramme de Karnaugh pour une fonction à 3 variables

Exemple 1
P
Simplifier la fonction suivante : F = (2, 3, 4, 5).

Pour chaque minterme de la fonction, on place un 1 à l’endroit correspondant dans le

diagramme de Karnaugh.

Y
YZ
00 01 11 10
X
0 0 0 1 1

X 1 1 1 0 0

Figure 4.4 – Diagramme de Karnaugh pour l’exemple 1

La fonction simplifiée donne : F = XY 0 + X 0 Y .

Exemple 2
P
Simplifier la fonction suivante : F = (3, 4, 6, 7).

La fonction simplifiée donne F = Y Z + XZ 0 .

Pour un diagramme de Karnaugh à trois variables, le nombre de carrés encerclés doit

toujours être une puissance de 2. Plus on encercle de carrés, moins il y aura de variables
dans le produit créé :

3
 CHAPITRE 4. MINIMISATION

Y
YZ
00 01 11 10
X
0 0 0 1 0

X 1 1 0 1 1

Figure 4.5 – Diagramme de Karnaugh pour l’exemple 2

• Un carré de un minterme représente un terme à trois variables,

• Un groupe de deux mintermes représente un terme à deux variables,
• Un groupe de quatre mintermes représente un terme à une variable,
• Un groupe de huit mintermes englobe tout le diagramme, et est toujours égal à 1.

4.1.3 Diagramme à quatre variables

Le diagramme de Karnaugh à quatre variables est construit de la même façon que

ceux de deux et trois variables. Dans ce cas-ci, on a un carré de 4×4 cases. Le diagramme
est montré à la figure 4.6. Tout comme les diagrammes à trois variables, pour simplifier
une fonction, il faut minimiser le nombre de regroupements, et maximiser la taille des
regroupements.

Y
YZ
00 01 11 10
WX
00 m0 m1 m3 m2

01 m4 m5 m7 m6
X
11 m12 m13 m15 m14
W
10 m8 m9 m11 m10

Figure 4.6 – Diagramme de Karnaugh pour une fonction à 4 variables

4
 CHAPITRE 4. MINIMISATION

Exemple 3
P
Simplifier la fonction suivante : F = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)

Y
YZ
00 01 11 10
WX
00 1 1 0 1

01 1 1 0 1
X
11 1 1 0 1
W
10 1 1 0 0

Figure 4.7 – Diagramme de Karnaugh pour l’exemple 3

La fonction simplifiée donne F = Y 0 + XZ 0 + W 0 Z 0 .

4.2 Impliquants premiers

En choisissant des carrés adjacents dans un diagramme de Karnaugh, il faut :

1. S’assurer que tous les mintermes sont couverts
2. Minimiser le nombre de termes
3. Maximiser le nombre de carrés recouverts par un groupement
Il y a parfois plus d’une solution possible, ou plus d’une option pour couvrir tous les
termes. On peut simplifier un peu le choix des regroupements si on définit deux types de
regroupements :
1. Impliquant premier : c’est un regroupement obtenu en groupant le maximum de
cases adjacentes dans le diagramme de Karnaugh.
2. Impliquant premier essentiel : si une case est couverte par un seul impliquant
premier, alors cet impliquant est essentiel.
Les impliquants premiers d’une fonction sont obtenus en groupant le maximum de cases.
Ceci veut dire, par exemple, qu’un 1 seul sur le diagramme représente un impliquant
primaire s’il n’est pas adjacent à aucun autre 1. Les impliquants premiers essentiels sont
ceux qui recouvrent seulement une case.

5
 CHAPITRE 4. MINIMISATION

Exemple 4

Identifier les impliquants premiers essentiels de la fonction suivante à 3 entrées :

X
F= (1, 3, 4, 5, 6)

Le diagramme de Karnaugh est :

Y
YZ
00 01 11 10
X
0 0 1 1 0

X 1 1 1 0 1

Figure 4.8 – Diagramme de Karnaugh pour l’exemple 4

Il y a quelques possibilités d’impliquants. Les mintermes 3 et 6 sont seulement couverts

par un impliquant. Ceux-ci sont donc des impliquants premiers essentiels. Les termes
XY 0 et Y 0 Z ne sont pas des impliquants premiers essentiels. Pour couvrir tous les 1 du
diagramme, on doit choisir l’un ou l’autre :

Y Y
YZ YZ
00 01 11 10 00 01 11 10
X X
0 0 1 1 0 0 0 1 1 0

X 1 1 1 0 1 X 1 1 1 0 1

Z Z

Figure 4.9 – Deux choix d’impliquants pour l’exemple 4

La fonction est :
F = X 0 Z + XZ 0 + Y 0 Z = X 0 Z + XZ 0 + XY 0

6
 CHAPITRE 4. MINIMISATION

Exemple 5

Identifier les impliquants premiers essentiels de la fonction suivante à 4 entrées :

X
F= (0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)

Le diagramme de Karnaugh de cette fonction est montré à la figure 4.10. Il y a plusieurs

possibilités pour créer des regroupements.

Y
YZ
00 01 11 10
WX
00 1 0 1 1

01 0 1 1 0
X
11 0 1 1 0
W
10 1 1 1 1

Figure 4.10 – Diagramme de Karnaugh pour l’exemple 5

Les impliquants premiers essentiels sont montrés à la figure 4.11a. Ce sont des impli-
quants essentiels, parce que les deux 1 encerclés en bleu peuvent seulement être groupés
par les impliquants montrés. En groupant ces 1, il faut maximiser le nombre de termes
groupés, et donc on obtient les impliquants de la figure 4.11a. Les impliquants premiers
sont montrés à la figure 4.11b. Il y a plusieurs possibilités pour regrouper les mintermes
qui ne sont pas groupés par les impliquants essentiels. On a quatre possibilités pour la
fonction simplifiée :

F = BD + BD 0 + CD + AD
= BD + BD 0 + CD + AB0
= BD + BD 0 + B0 C + AD
= BD + BD 0 + B0 C + AB0

7
 CHAPITRE 4. MINIMISATION

Y Y
YZ YZ
00 01 11 10 00 01 11 10
WX WX
00 1 0 1 1 00 1 0 1 1

01 0 1 1 0 01 0 1 1 0
X X
11 0 1 1 0 11 0 1 1 0
W W
10 1 1 1 1 10 1 1 1 1

Z Z
a) Impliquants premiers essentiels b) Impliquants premiers
Figure 4.11 – Diagramme de Karnaugh pour l’exemple 5

4.3 Conditions indifférentes

Jusqu’à maintenant, lorsqu’on crée une table de vérité pour une fonction, on place les 1
aux endroits où la fonction est vrai, puis on rempli le reste des combinaisons de 0. Dans
certains cas, il y a des combinaisons d’entrées qui ne sont pas possibles lorsqu’on crée
des tables de vérité. Par exemple, en DCB, il y a 6 combinaisons qui ne sont pas utilisées
(de 10 à 15). La plupart du temps, lorsque des combinaisons ne sont pas utilisées, on est
indifférent à la valeur de sortie. On utilise alors un X (au lieu d’un 0 ou 1) dans la table de
vérité. En anglais, cette condition est appelée un don’t care. Les mintermes ou maxtermes
qui ont des conditions indifférentes sont exprimées avec un d.

Les conditions indifférentes peuvent être utilisées dans les diagrammes de Karnaugh
pour créer des regroupements plus gros. Par contre, il n’est pas nécessaire d’utiliser ces
conditions ; on les utilise seulement pour faire des regroupements plus gros, pas pour créer
plus de regroupements.

Exemple 6

Simplifier la fonction suivante :

X
F(W , X, Y , Z) = (1, 2, 3, 7, 11, 15) + d(0, 5)

Le diagramme de Karnaugh est montré à la figure 4.12. On a deux groupes de 4

mintermes : a utilisé un des X pour faire un groupe plus gros. L’autre X n’est pas utilisé.
La fonction est :
F = W 0 X 0 + ZY

8
 CHAPITRE 4. MINIMISATION

Y
YZ
00 01 11 10
WX
00 X 1 1 1

01 0 X 1 0
X
11 0 0 1 0
W
10 0 0 1 0

Figure 4.12 – Diagramme de Karnaugh pour l’exemple 6

Exemple 7

Simplifier la fonction suivante :

X
F(A, B, C, D) = (0, 4, 10, 14) + d(1, 2, 3, 5, 6, 11, 15)

Le diagramme de Karnaugh est montré à la figure 4.13. On a deux groupes de 4

mintermes qui utilisent des X. Les autres X ne sont pas utilisés.

C
CD
00 01 11 10
AB
00 1 X X X

01 1 X 0 X
B
11 0 0 X 1
A
10 0 0 X 1

Figure 4.13 – Diagramme de Karnaugh pour l’exemple 7

La fonction est :
F = A0 C 0 + CD 0

9
 CHAPITRE 4. MINIMISATION

4.4 Simplification par produit de sommes

On peut aussi utiliser les diagrammes de Karnaugh pour simplifier des fonctions
représentées par un produit de sommes. Dans ce cas-ci, on modifie un peu la procédure.
Au lieu de faire des regroupements de 1, on fait les regroupements avec des zéros ; ceci
nous donne le complément de la fonction. On applique ensuite le théorème de Demorgan
à la fonction simplifiée. Cette méthode fonctionne aussi avec les conditions indifférentes.

Exemple 8

Simplifier la fonction suivante sous un produit de sommes.

X
F(A, B, C, D) = (0, 1, 2, 5, 8, 9, 10)

Le diagramme de Karnaugh est montré à la figure 4.14. On regroupe les 0 au lieu des 1.

C
CD
00 01 11 10
AB
00 1 1 0 1

01 0 1 0 0
B
11 0 0 0 0
A
10 1 1 0 1

Figure 4.14 – Diagramme de Karnaugh pour l’exemple 8

La fonction sous forme de somme de produit est :

F 0 = AB + CD + BD 0

Puis on applique le théorème de Demorgan, pour obtenir un produit de sommes :

F = (A0 + B0 ) · (C 0 + D 0 ) · (B0 + D)

10