Qu'est-ce que la table de Karnaugh et quel est son rôle ?
Dans les articles précédents, nous avons abordé la table de vérité, qui est une méthode de représentation d'une fonction logique sous forme de tableau contenant les entrées et les sorties. À partir de la table de vérité, nous avons appris à extraire les équations algébriques, ou ce que nous appelons les expressions booléennes. Nous les extrayons sous deux formes : la première expression, appelée Somme de Produits (SdP), et la seconde, appelée Produit de Sommes (PdS).
Ensuite, nous avions besoin des règles et lois de l'algèbre booléenne pour simplifier ces expressions, lesquelles étaient souvent longues et susceptibles d'entraîner des erreurs. C'est ici qu'intervient la solution proposée par le chercheur Maurice Karnaugh, qui a conçu une table ressemblant à une table de vérité, mais légèrement différente, et qui porte son nom : la table de Karnaugh.
L'avantage majeur de ce tableau « magique » est qu'il nous permet d'extraire directement l'expression algébrique sous sa forme simplifiée à partir du tableau, sans avoir besoin de recourir aux règles et lois de l'algèbre booléenne pour la simplification (sauf dans certains cas particuliers que nous étudierons).
Comment construire une table de Karnaugh ?
Comme nous l'avons mentionné précédemment, la table de Karnaugh ressemble à une table de vérité. En réalité, nous nous basons sur la table de vérité pour construire et remplir la table de Karnaugh. Autrement dit, il est nécessaire d'établir d'abord la table de vérité et de déterminer les états de sortie, puis de la convertir en table de Karnaugh pour extraire l'expression algébrique simplifiée. Alors, comment construit-on une table de Karnaugh ?
Table de Karnaugh à deux entrées (variables)
Dans ce cas, il est effectivement facile d'extraire l'expression algébrique sans nécessairement recourir à une table de Karnaugh, car l'expression sera simple et son extraction à partir de la table de vérité suffira, sans nécessiter un effort considérable.
Cependant, il est essentiel de se familiariser avec la structure de la table de Karnaugh à deux entrées, qui se présente sous la forme suivante :
Quant aux quatre cases vides, elles représentent l'emplacement où nous inscrirons les états de la sortie F, bien que nous n'écrivions généralement pas le nom de la sortie dans la table de Karnaugh elle-même.
Très bien. Maintenant, prenons un exemple concret de table de vérité avec des valeurs définies pour la sortie F, et remplissons la table de Karnaugh correspondante.
En ce qui concerne l'ordre des variables dans une table de Karnaugh, il est effectivement possible de le modifier selon vos préférences personnelles. Il n'est pas nécessaire de suivre un ordre spécifique. Par exemple, on peut placer B sur l'axe horizontal et A sur l'axe vertical, comme illustré dans le schéma ci-dessous.
Mais attention ! Tout changement dans l'ordre des variables dans la table de vérité OU dans la table de Karnaugh affectera l'ordre de remplissage des valeurs de sortie F.
Table de Karnaugh à trois variables
Passons maintenant à la table de vérité à 3 variables ou entrées. Dans ce cas, nous prenons deux variables sur l'axe horizontal du tableau (par exemple AB) et la troisième variable sur l'axe vertical, comme illustré dans le schéma ci-dessous.
En ce qui concerne l'axe horizontal qui contient deux variables, il existe une règle importante à respecter lors de l'attribution des valeurs booléennes à AB : un seul bit doit changer lors du passage d'une colonne à la suivante. Il est impossible de changer les deux bits simultanément entre deux colonnes adjacentes.
On peut modifier l'ordre d'assignation des valeurs AB dans une table de Karnaugh tant que la règle que nous avons mentionnée n'est pas violée. Par conséquent, une table de Karnaugh peut être écrite sous plusieurs formes, et toutes sont correctes. Par exemple, ces tableaux sont tous valides :
Cependant, bien que toutes soient correctes, il est préférable d'utiliser une seule forme de tableau, celle qui est couramment employée par les enseignants, les ingénieurs et dans les manuels scolaires, afin d'éviter toute confusion initiale.
Remplir une table de Karnaugh à partir d'une table de vérité
Pour commencer, nous pouvons associer chaque ligne de la table de vérité à sa case correspondante dans la table de Karnaugh, et placer la valeur de la sortie dans la cellule appropriée.
Lors du remplissage d'une table de Karnaugh avec les valeurs de la sortie F, on observe un ordre spécifique de remplissage qu'on peut mémoriser et appliquer pour remplir toutes les tables similaires avec le même ordre
Cependant, il faut noter, comme nous l'avons mentionné précédemment, que cet ordre n'est valable que dans ce cas précis concernant la table de vérité et la table de Karnaugh. Si nous modifions l'ordre des entrées dans la table de vérité ou si nous changeons l'ordre des valeurs AB dans la table de Karnaugh, l'ordre de remplissage changera également.
C'est pourquoi nous vous recommandons de suivre un seul ordre, celui qui est le plus courant et le plus largement utilisé.
Par exemple, je vais modifier l'ordre des entrées dans la table de vérité et nous observerons la différence.
Table de Karnaugh à quatre variables
Passons maintenant à la table de vérité la plus grande avec 4 variables ou entrées. Dans ce cas, nous dessinons une table de Karnaugh en plaçant deux variables sur l'axe horizontal et deux variables sur l'axe vertical. Concernant le remplissage des états des variables, nous respectons la règle que nous avons étudiée précédemment : un seul bit doit changer lors du passage d'une ligne à l'autre ou d'une colonne à l'autre.
Transférons maintenant les valeurs booléennes de la sortie F vers la table de Karnaugh. Nous allons suivre un ordre spécifique, qui est valable dans le cas où la table de vérité et la table de Karnaugh sont construites selon la méthode décrite ci-dessus.
Prenons un exemple et remplissons une table de Karnaugh à partir d'une table de vérité qui contient la sortie F.
Après avoir appris à convertir une table de vérité en table de Karnaugh, il nous reste à connaître la méthode d'extraction de l'expression booléenne algébrique simplifiée à partir de la table de Karnaugh, que nous expliquerons dans un autre article
extraire l'expression algébrique simplifiée d'une table de Karnaugh
Règles fondamentales pour extraire l'expression logique d'une table de Karnaugh
Comme nous le faisions dans la table de vérité pour extraire l'expression logique algébrique en listant les lignes contenant des 1, de même dans la table de Karnaugh nous nous concentrons sur les cellules qui contiennent des 1 en identifiant les cellules adjacentes contenant également des 1, tout en respectant certaines conditions spécifiques.
Règle des regroupements:
- Regrouper uniquement les cellules contenant des 1.
- Les groupes doivent être rectangulaires ou carrés (pas de formes en L ou irrégulières).
- La taille des groupes doit être une puissance de 2 : 1, 2, 4, 8, 16 cellules.
- Chaque groupe doit être le plus grand possible.
- Un même 1 peut appartenir à plusieurs groupes (recouvrement autorisé).
- Tous les 1 doivent être couverts par au moins un groupe.
Exemple 1:
Exemple 2:
Nous observons dans la table de Karnaugh du premier exemple que le premier groupe en orange contient 4 cellules avec des 1. Comme nous l'avons mentionné dans les règles, nous devons toujours nous efforcer de former des groupes contenant le plus grand nombre possible de 1, et on ne peut pas diviser ce groupe en deux groupes plus petits.
Ensuite, nous avons le deuxième groupe en vert qui contient deux cellules éloignées du premier groupe et non adjacentes à d'autres cellules contenant des 1. Par conséquent, nous les avons formées en un groupe séparé.
Dans le deuxième tableau du deuxième exemple, nous observons l'une des règles importantes : les cellules contenant des 1 peuvent appartenir à plusieurs groupes (recouvrement autorisé).
Exemples avec des erreurs courants :
Maintenant, je vais présenter quelques erreurs courantes à éviter afin de ne pas obtenir une expression non simplifiée ou un résultat incorrect.
Dans cet exemple, nous observons que le groupe a une forme en L, ce qui est totalement incorrect. Toutes les cellules doivent être adjacentes les unes aux autres, et par conséquent, la forme du groupe doit toujours être un rectangle ou un carré uniquement.
Dans cet exemple, dans le premier tableau, nous n'avons pas respecté la règle qui stipule qu'il faut prendre le plus grand nombre possible de cellules contenant des 1 tout en étant adjacentes. Dans le deuxième tableau, nous voyons le groupement correct.
Principe de l'enroulement
Il nous reste à mentionner un point très important : nous considérons que la première et la dernière colonnes sont adjacentes, et par conséquent, les cellules situées dans la première et la dernière colonnes peuvent être regroupées en un seul groupe.De même, la première et la dernière ligne ont leurs cellules adjacentes entre elles.
- La colonne la plus à gauche et la colonne la plus à droite sont adjacentes
- La ligne la plus en haut et la ligne la plus en bas sont adjacentes
- Les quatre coins sont mutuellement adjacents (dans une table 4×4)
Voici quelques exemples pour illustration :
Post a Comment