ISSLg
- Cours d'électronique
Les diagrammes de
Karnaugh
Navigation> electronique/automatisme/karnaugh/karnaugh
Ce cours est une adaptation du site : http://www.positron-libre.com/cours/electronique/logique-combinatoire/tableau-karnaugh/tableau-karnaugh.php
avec renumérotation des cases et replacement des variables d'entrées
pour être compatible avec le système de numérotation binaire : c'est la
méthode Philippot ;-)
Utilité
Nous avons vu que les règles et propriétés de l'algèbre de Boole
permettent de simplifier les fonctions ; cette méthode est cependant
relativement lourde et ne permet jamais de savoir si l'on aboutit à une
expression minimale de la fonction ou pas.
Le
diagramme de Karnaugh, permet d'arriver de manière plus aisée à
l'expression minimale d'une fonction.
L'idée
de Karnaugh
Dans le cas de deux variables binaires, nous avons quatre possibilités
(ou combinaisons) à envisager que nous traduisons sous la forme de la
table
de vérité suivante :
![](files/table-verite-2-variables.jpg)
A chaque combinaison des variables est associée une valeur de la
fonction.
L'idée de KARNAUGH est d'associer une surface à chaque combinaison des
variables, en adoptant la
représentation suivante :
![](files/tableau-karnaugh-4-cases.jpg)
Nous disposons donc de 4 cases correspondant aux 4 combinaisons de
variables.
La case 0=0b00 correspond à la combinaison b=0
a=0 ==> (/b . /a)
La case 1=0b01 correspond à la combinaison b=0
a=1 ==> (/b
. a)
La case 2=0b10 correspond à la combinaison b=1
a=0 ==> (b
. /a )
La case 3=0b11 correspond à la combinaison b=1
a=1 ==> (b . a)
Pour chacune des cases nous associons un
produit de variables
Dans chacune de ces cases sera inscrite la valeur de la fonction pour
la combinaison de variables correspondant à cette case.
En suivant l'exemple déjà représenté ci-dessus nous avons :
case n° 2 ==> combinaison de variables b = 1 et a = 0 ==> valeur de la
fonction = 0.
![](files/tableau-karnaugh-4-cases-rempli.jpg)
Il ressort alors graphiquement que, dans notre exemple, la fonction est
indépendante de b (les lignes sont identiques quelque soit b).
Remarque
:
Si la table de vérité reprend plusieurs fonctions (c-à-d plusieurs
sorties pilotées par les mêmes entrées), il vous faudra autant de
diagrammes que de fonctions (équations) à simplifier.
Représentation
d'un tableau de Karnaugh
Un tableau de Karnaugh peut se représenter sous les formes suivantes :
![](files/tableau-karnaugh-4-cases-v3.jpg)
Ces
trois représentations sont équivalentes.
Un tableau de Karnaugh nous renseigne donc sur les données suivantes :
- Le nom de la fonction (par ex : X),
- Le nom des variables (a, b),
- L'état des variables : 0 , 1 ou une barre représentant
l'état 1,
- La valeur de la fonction (1 ou 0).
![](files/contenu-tableau-karnaugh.jpg)
Tableau
à deux variables
Numérotation des cases :
![](files/tableau-karnaugh-4-cases.jpg)
A chaque case est associé un doublet des valeurs a, b.
Exemple : La case n° 0 représentera le doublet {0,0} où a = 0
et b = 0.
Nous pouvons dire également que la case n°0 correspond au produit (/a
. /b
).
Tableau
à trois variables
Numérotation des cases (remarquez l'inversion de 2 & 3 ainsi
que de 6 & 7):
![](files/tableau-karnaugh-8-cases.jpg)
A chaque case est associé un triplet des valeurs a, b, c.
Exemple : La case n° 0 représentera le triplet {0,0,0} ou a = 0, b = 0
et c = 0.
Nous pouvons dire également que la case n°0 correspond au produit (/a
. /b . /c
).
Tableau
à quatre variables
Numérotation des cases :
(remarquez l'inversion de 2 & 3 ; de 6 & 7 ; de 10
& 11 ; de 14 & 15 ainsi que des 2 dernières lignes)
![](files/tableau-karnaugh-16-cases.jpg)
A chaque case est associé un quadruplet des valeurs a, b, c, d.
Exemples :
La case n° 8 représentera le quadruplet {1,0,0,0} ou d = 1,
c = 0, b = 0 et a = 0 (d . /c
. /b . /a
).
La case n° 15 représentera le quadruplet {1,1,1,1} ou d = 1, c = 1, b =
1 et a = 1 (d . c
. b . a
).
La case n° 10 représentera le quadruplet {1,0,1,0} ou d = 1, c = 0, b =
1 et a = 0 (d . /c . b . /a
).
Les
cases adjacentes
Dans chaque cas, l'ordre d'écriture des états des variables fait qu'entre deux
cases voisines (en ligne ou en colonne)
une
seule variable change d'état ; on dit de telles cases
qu'elles sont adjacentes.
![](files/tableau-karnaugh-16-cases-adjacente.jpg)
La case 1 correspond à d = 0 ; c = 0 ; b = 0
; a = 1
La case 3 correspond à d = 0 ; c = 0 ; b = 1
; a = 1
Lorsque nous passons de 1 à 3, seule la variable "b" change d'état : 1
et 3 sont adjacentes.
Lorsque nous passons de 1 à 0, seule la variable "a" change d'état : 1
et 0 sont adjacentes.
Lorsque nous passons de 1 à 5, seule la variable "c" change d'état : 1
et 5 sont adjacentes.
Enfin, lorsque nous passons de 1 à 9, seule la variable "d" change
d'état : 1 et 9 sont adjacentes.
Nous venons de déterminer les adjacences de la case n° 1.
Cette
notion de cases adjacentes est fondamentale !
Ecriture
d'une table de vérité dans un tableau de
Karnaugh
Supposons que l'étude d'un dispositif nous ait conduit à la table
de vérité suivante :
cases |
c |
b |
a |
| x |
0 |
0 |
0 |
0 |
| 1 |
1 |
0 |
0 |
1 |
| 0 |
2 |
0 |
1 |
0 |
| 0 |
3 |
0 |
1 |
1 |
| 1 |
4 |
1 |
0 |
0 |
| 1 |
5 |
1 |
0 |
1 |
| 0 |
6 |
1 |
1 |
0 |
| 0 |
7 |
1 |
1 |
1 |
| 0 |
soit x = /c . /b . /a + /c . b . a +
c . /b . /a
Pour remplir le tableau de Karnaugh, il suffit de reporter la
valeur de x dans chaque case correspondante selon la numérotation
ci-avant :
![](files/table-fonction-x.jpg)
Repérage de zones dans un tableau de
Karnaugh
Dans un diagramme à 4 variables, nous pouvons observer les faits suivants :
![](files/tableau-zones.jpg)
quand un terme ne contient qu'une variable il occupe une zone de 8 cases,
quand un terme est un produit de 2 variables il occupe une zone de 4 cases,
quand un terme est un produit de 3 variables il occupe une zone de 2 cases,
quand un terme est un produit de 4 variables il occupe une zone d'1 cases.
Cette propriété est due à l'adjacence des cases.
Simplification d'une fonction dans un tableau de
Karnaugh
En regroupant les cases adjacentes par 2, on suprime une variable des termes correspondants.
Pour supprimer deux variables, il faut disposer de 4 cases
adjacentes.
Pour en supprimer 3 il faut 8 cases adjacentes, etc...
Exemples:
![](files/exemple1.jpg)
Y = /d . c . b . a + d . /b . /a + d . /c . /a
![](files/exemple2.jpg)
Y = c . /b . a + d . a
![](files/exemple3.jpg)
Y = /c . /a
Méthode :
La méthode de lecture des fonctions dans un tableau de Karnaugh consiste donc à regrouper les cases
adjacentes par 2n, n étant le plus grand possible. On essaie de regrouper toutes les cases
à 1 de cette manière, les chevauchements de groupes étant permis.
Dans un diagramme à 4 variables (16 cases) :
-
Une zone de 8 cases définira une variable,
-
une zone de 4 cases définira un produit de 2 variables,
-
une zone de 2 cases définira un produit de 3 variables,
-
une zone d'1 cases définira un produit de 4 variables.
On lit enfin la fonction, en ne conservant pour chaque groupes
que les variables qui ne changent pas d'état.
Petite astuce 1 :
Si
vous avez plus de cases à 1 que de cases à 0, il est plus facile de
regrouper les 0 comme ci-dessus, et vous obtenez alors la négation
(NOT) de votre fonction.
Petite astuce 2 :
Il arrive parfois qu'une fonction soit indéfinie pour certaines combinaisons
des variables, pour différentes raisons ; la plus courante est que certaines combinaisons
des variables étant impossibles, on ne juge pas utile de donner une valeur
particulière à la fonction pour ces combinaisons là.
Dans les cases correspondantes du tableau de Karnaugh, on placera un signe particulier (Ø : élément indéterminé).
Lors du regroupement des cases nous transformons le Ø en 0 ou en 1
suivant la convenance ou les simplifications qui peuvent en découler.
Auteur :
Philippot Marc - 25/02/2011