Logique de base/Tableau de Karnaugh
Introduction
[modifier | modifier le wikicode]Bien que cela soit un très bon outil, l'algèbre de Boole n'autorise pas d'erreur. Il faudrait pouvoir utiliser les caractéristiques de l'algèbre de Boole et essayer de faire une résolution « graphique » et donc simplifier des équations booléennes.
Les tableaux de Karnaugh sont un bon outil pour le faire. Par contre, il demande une certaine compréhension au départ afin de connaître et comprendre toutes les astuces. D'abord, le tableau est construit selon le code binaire Gray.
Le code Gray
[modifier | modifier le wikicode]Le code binaire Gray, contrairement au code binaire naturel, permet de ne faire évoluer qu'un bit lorsque l’on passe d’un code à son suivant ou son précédent.
| MSB | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 3 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 2 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | |
| LSB | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
Les variables composant le tableau de Karnaugh seront codées selon le code Gray. L'avantage, c’est que la suite du dernier code est le premier (et inversement). Donc, le tableau ne sera pas écrit sur une surface plane, mais sur un cylindre, ce qui donnera des simplifications possibles.
De même, le tableau du code Gray possède des axes de symétrie :
- Si vous regardez l’axe du tableau lorsque le MSB passe de 1 à 0, les 4 lignes de dessous possède la symétrie axiale.
- Si vous regardez les 3 axes lorsque les MSB et le bit de poids 4 changent d'état, vous avez les symétries correspondantes pour les bits de poids inférieur.
Construction du tableau
[modifier | modifier le wikicode]Inutile en dessous de 3 variables car, dans ce cas, il est préférable d’utiliser directement les simplifications par l'algèbre de Boole.
À partir de 6 variables, le tableau devient de plus en plus imposant. Il est tout à fait logique, lorsqu'on a bien compris la méthode de recherche, de passer en 3D, c'est-à-dire de remplir un tableau suivant les 3 axes.
Pour le moment, on va se limiter à 4 ou 5 variables.
Les variables se répartissent sur les 2 côtés du tableau.
Exemple : Si l’on a 4 variables a, b, c et d :
- a et b seront placés en colonne,
- c et d seront placés en ligne,
ce qui donne le tableau suivant :
| F | a b | ||||
|---|---|---|---|---|---|
| 0 0 | 0 1 | 1 1 | 1 0 | ||
| c d | 0 0 | ||||
| 0 1 | |||||
| 1 1 | |||||
| 1 0 | |||||
De ce fait, on se retrouve avec 16 cases vides, correspondant aux 16 combinaisons possible de 4 variables pouvant prendre 2 états.
Chaque combinaison offre 3 solutions possibles de l'état de sortie de la variable F :
- 1 si la sortie est vraie
- 0 si la sortie est fausse
- X si la sortie est indéterminée, c'est-à-dire que, par exemple, le système ne peut pas fournir cette combinaison.
Voilà ce que peut donner un tableau rempli :
| F | a b | ||||
|---|---|---|---|---|---|
| 0 0 | 0 1 | 1 1 | 1 0 | ||
| c d | 0 0 | 0 | 0 | 1 | 1 |
| 0 1 | 1 | 1 | 1 | 0 | |
| 1 1 | 0 | X | X | 1 | |
| 1 0 | 1 | 1 | 1 | 0 | |
À partir du moment où le tableau est correctement rempli, on peut commencer à résoudre le système.
Résolution du tableau
[modifier | modifier le wikicode]Les rassemblements
[modifier | modifier le wikicode]Le but est très simple. Il faut effectuer des regroupements de 1 ou de X ; par paquets de 1, 2, 4 ,8, 16..... Ces regroupements doivent être des rectangles ou des carrés, jamais de travers, et les plus grands possible sachant qu'un élément déjà utilisé peut être repris.
Attention : ne pas oublier que le tableau de Karnaugh est écrit sur un cylindre.
Exemple : avec ce tableau :
| F | a b | ||||
|---|---|---|---|---|---|
| 0 0 | 0 1 | 1 1 | 1 0 | ||
| c d | 0 0 | 0 | 0 | 1 | 1 |
| 0 1 | 1 | 1 | 1 | 1 | |
| 1 1 | 0 | 0 | 0 | 1 | |
| 1 0 | 0 | 0 | 1 | 1 | |
on peut faire ces 3 rassemblements :
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Le suivant est inutile puisqu’il peut être fait par les 2 de gauche au dessus :
| F | a b | ||||
|---|---|---|---|---|---|
| 0 0 | 0 1 | 1 1 | 1 0 | ||
| c d | 0 0 | 0 | 0 | 1 | 1 |
| 0 1 | 1 | 1 | 1 | 1 | |
| 1 1 | 0 | 0 | 0 | 1 | |
| 1 0 | 0 | 0 | 1 | 1 | |
La résolution des rassemblements
[modifier | modifier le wikicode]Maintenant que l’on a pu, avec différentes sélections, prendre tous les 1, on essaie de résoudre les rassemblements. Pour cela, il faut que les variables participant au rassemblement concerné ne changent pas.
- Exemple avec le rassemblement bleu :
Dans les 4 cas possibles, la variable a est toujours à 1 et la variable d est toujours à 0
La solution bleue donne : (la barre au dessus de d, puisque la variable est à 0 dans ces 4 cas).
- Exemple avec le rassemblement vert :
Dans les 4 cas possibles, la variable c est toujours à 0 et la variable d est toujours à 1
La solution verte donne : (la barre au dessus de c, puisque la variable est à 0 dans ces 4 cas).
- Exemple avec le rassemblement rose :
Dans les 4 cas possibles, la variable a est toujours à 1 et la variable b est toujours à 0
La solution rouge donne : (la barre au dessus de b, puisque la variable est à 0 dans ces 4 cas).
La solution finale du tableau est :
En toute logique, cette solution est réduite au maximum.
Exercices
[modifier | modifier le wikicode] Faites ces exercices : tableaux de Karnaugh 1° partie.
|
Références
[modifier | modifier le wikicode]Électronique numérique : Fonctions logiques élémentaires
