3.3. Regroupement dans les tableaux de Karnaugh

La simplification des expressions logiques. Le tableau de Karnaugh. Cours ... Les théorèmes de l'algèbre booléenne (cf. cours L'algèbre de Boole) sont les ...

ads

un extrait du document


Présentation La description des systèmes logiques et numériques par l'algèbre de Boole
a pour objectif la conception et la réalisation matérielle de ces systèmes.
Afin d'en réduire la difficulté et le coût, on est amené à simplifier au
maximum les équations booléennes. Deux techniques peuvent être utilisées :
. les théorèmes de Boole : technique algébrique dépendant de l'expérience
et de "l'instinct",
. les tableaux de Karnaugh : technique graphique suivant une démarche
systématique.
Ces méthodes exigent que l'on exprime les équations logiques sous la
forme d'une somme de produits.
Exemples :
[pic]
Note : Dans une somme de produits, le signe de complémentation ne peut
pas surmonter plus d'une variable d'un terme. Exemples :
|[pic] |ne sont pas des |
| |sommes de produits; |
|[pic] |est une somme de |
| |produits. |
La simplification algébrique Les théorèmes de l'algèbre booléenne (cf. cours L'algèbre de Boole) sont
les outils de la simplification des expressions d'un circuit logique.
Malheureusement, il n'est pas toujours facile de savoir quels théorèmes il
faut invoquer pour obtenir le résultat minimal. D'ailleurs, rien ne nous
dit que l'expression simplifiée est la forme minimale et qu'il n'y a pas
d'autres simplifications possibles. Pour toutes ces raisons, la
simplification algébrique est un processus "d'approximations successives"
pouvant toutefois, l'expérience aidant, amener à de bons résultats.
On trouve dans cette technique toujours deux étapes essentielles :
. la transformation de l'expression pour obtenir une somme de produits,
. l'analyse de chaque produit pour trouver les variables communes, puis la
mise en facteur de ces dernières, quand elle permet d'éliminer un ou
plusieurs termes. Les tableaux de Karnaugh Le tableau de Karnaugh est un outil graphique qui permet de simplifier de
manière méthodique une équation logique ou le processus de passage d'une
table de vérité à son circuit correspondant. Bien que les tableaux de
Karnaugh soient applicables à des problèmes ayant un nombre quelconque de
variables d'entrée, ils ne sont plus d'une grande utilité en pratique quand
le nombre de variables dépasse 6 ou 7. Dans ce cas, il est préférable de
traiter le problème avec un programme informatique.
Chaque tableau de Karnaugh est associé à une seule variable de sortie de
la table de vérité. 1 La description des tableaux de Karnaugh Les cases d'un tableau de Karnaugh sont désignées (par les variables A,
B, ... , les constantes 0, 1, ou les barres) de manière que deux cases
adjacentes n'aient qu'une seule variable dont l'état soit différent. Le
codage est effectué en BINAIRE REFLECHI.
[pic] [pic]
Notez qu'une case de la colonne extrême gauche du tableau est adjacente à
la case de la colonne extrême droite de la même ligne. On considère donc le
tableau circulaire dans le sens des colonnes comme des lignes.
Figure 1: tracé rapide d'un tableau de Karnaugh
[pic]
Sur 1 variable: présence de la barre = « 1 »,
absence de la barre = « 0 ». 2 Placement des combinaisons de la table de vérité dans le tableau [pic]
3 Regroupement dans les tableaux de Karnaugh
Méthode:
Pour vérifier qu'un groupement est autorisé, on prolonge son axe de
symétrie à travers les variables. Il faut alors que chaque variable soit
symétrique (opposée ou identique) de part et d'autre de l'axe du groupement
sur toute la largeur du groupe (et non sur la largeur du tableau). 1 Table à 4 variables
Groupements de 8 cases autorisés (8)
[pic] [pic]
Groupements de 4 cases autorisés (24) [pic] [pic] [pic]
2 Table à 5 variables
Groupements de 8 cases autorisés (36) [pic]
[pic] Groupements de 8 cases interdits (16) [pic]
4 Insertion de binaire naturel dans un tableau de Karnaugh L'objectif de l'exercice est de ne plus avoir à rechercher les
correspondances entre les combinaisons des variables d'entrée en binaire
naturel et leur position dans le tableau de Karnaugh en binaire réfléchi.
La plupart des problèmes utilisant des entrées en binaire naturel, cette
méthode permet de placer directement et plus rapidement l'état des sorties
dans le tableau de Karnaugh. Table de vérité en binaire naturel |D |C |B |A |N (déc.)|x |
|0 |0 |0 |0 |0 |0/1 |
|0 |0 |0 |1 |1 |0/1 |
|0 |0 |1 |0 |2 |0/1 |
|0 |0 |1 |1 |3 |0/1 |
|0 |1 |0 |0 |4 |0/1 |
|0 |1 |0 |1 |5 |0/1 |
|0 |1 |1 |0 |6 |0/1 |
|0 |1 |1 |1 |7 |0/1 |
|1 |0 |0 |0 |8 |0/1 |
|1 |0 |0 |1 |9 |0/1 |
|1 |0 |1 |0 |10 |0/1 |
|1 |0 |1 |1 |11 |0/1 |
|1 |1 |0 |0 |12 |0/1 |
|1 |1 |0 |1 |13 |0/1 |
|1 |1 |1 |0 |14 |0/1 |
|1 |1 |1 |1 |15 |0/1 | [pic] -----------------------
[pic]
ads