L'électronique numérique : Les tableaux de Karnaugh - Quiz
Les tableaux de Karnaugh
L'algèbre de Boole permet de décrire le fonctionnement d'un circuit logique sous la forme d'une expression composée de 0, de 1 et d'opérations logiques. Lorsque le nombre de variables augmente, ces expressions peuvent cependant devenir longues et difficiles à simplifier.
Le tableau de Karnaugh est une méthode graphique qui permet de représenter une fonction logique et de repérer facilement les simplifications possibles.
Son objectif est de trouver une expression logique plus simple qui produit exactement les mêmes résultats que l'expression d'origine, mais avec moins d'opérations logiques et donc, généralement, moins de portes dans le circuit.
Principe d'un tableau de Karnaugh
Un tableau de Karnaugh contient une case pour chaque combinaison possible des variables d'entrée. Dans chaque case, on inscrit la valeur de la sortie correspondant à cette combinaison : 0 ou 1.
Le nombre de cases dépend du nombre de variables :
- 2 variables → 4 cases ;
- 3 variables → 8 cases ;
- 4 variables → 16 cases ;
- 5 variables → 32 cases ;
- 6 variables → 64 cases.
En pratique, les tableaux de Karnaugh sont surtout utilisés pour des fonctions comportant un nombre limité de variables. Lorsque le nombre de variables devient important, des méthodes algorithmiques sont généralement plus adaptées.
Pourquoi les cases ne suivent-elles pas l'ordre binaire habituel ?
L'organisation des cases est particulière. Les lignes et les colonnes sont ordonnées selon le code Gray, et non selon l'ordre binaire classique.
Dans un code Gray, deux valeurs voisines ne diffèrent que par un seul bit.
Pour deux variables, l'ordre est :
00 → 01 → 11 → 10
Entre deux cases voisines, une seule variable change. Cette propriété est essentielle pour pouvoir regrouper les cases et simplifier les expressions.
Tableau de Karnaugh à deux variables
Avec deux variables A et B, le tableau contient quatre cases.
| A \ B | 0 | 1 |
|---|---|---|
| 0 | F(00) | F(01) |
| 1 | F(10) | F(11) |
Chaque case correspond donc à une combinaison précise des deux variables.
Si l'on veut représenter la fonction :
F = A · B
la sortie vaut 1 uniquement lorsque A = 1 et B = 1. Une seule case du tableau contient donc un 1.
Tableau de Karnaugh à trois variables
Avec trois variables A, B et C, on utilise généralement une variable pour les lignes et deux variables pour les colonnes.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | F(000) | F(001) | F(011) | F(010) |
| 1 | F(100) | F(101) | F(111) | F(110) |
L'ordre 00, 01, 11, 10 permet de conserver la propriété du code Gray entre les cases voisines.
Tableau de Karnaugh à quatre variables
Avec quatre variables A, B, C et D, on utilise généralement deux variables pour les lignes et deux pour les colonnes.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | F(0000) | F(0001) | F(0011) | F(0010) |
| 01 | F(0100) | F(0101) | F(0111) | F(0110) |
| 11 | F(1100) | F(1101) | F(1111) | F(1110) |
| 10 | F(1000) | F(1001) | F(1011) | F(1010) |
Là encore, les étiquettes suivent le code Gray. Une particularité importante apparaît : les bords du tableau sont considérés comme adjacents. La première colonne est donc voisine de la dernière, et la première ligne est voisine de la dernière.
Remplir un tableau de Karnaugh
Pour construire un tableau de Karnaugh, on commence par établir la table de vérité de la fonction.
Chaque combinaison d'entrée correspond à une case du tableau. On inscrit ensuite dans cette case la valeur de sortie correspondante.
Une fonction possédant quatre variables possède donc seize combinaisons possibles et nécessite seize cases dans son tableau.
Regrouper les 1
Pour simplifier une fonction exprimée sous la forme d'une somme de produits, on recherche des groupes de cases contenant des 1.
Les groupes doivent toujours contenir un nombre de cases correspondant à une puissance de 2 :
- 1 case ;
- 2 cases ;
- 4 cases ;
- 8 cases ;
- 16 cases ; etc.
Un groupe doit être constitué de cases adjacentes. Les cases situées en diagonale ne sont pas adjacentes.
Il faut rechercher les groupes les plus grands possibles, car plus un groupe contient de cases, plus l'expression obtenue est simple.
Pourquoi un groupe simplifie-t-il l'expression ?
Deux cases adjacentes ne diffèrent que par une seule variable. Lorsque cette variable prend successivement les valeurs 0 et 1 dans le groupe, elle peut disparaître de l'expression grâce aux lois de l'algèbre de Boole.
Par exemple :
A · B + A · B = A
La variable B disparaît car elle prend les deux valeurs possibles dans le groupe.
Regrouper deux cases
Supposons qu'un groupe de deux cases contienne :
A · B + A · B
On peut appliquer la factorisation :
A · (B + B)
Or :
B + B = 1
Il reste donc :
A
Le regroupement des deux cases permet ainsi de supprimer une variable.
Regrouper quatre cases
Un groupe de quatre cases permet de supprimer davantage de variables.
Dans un tableau à quatre variables, si quatre cases adjacentes ont la valeur 1 et que seules deux variables restent constantes dans tout le groupe, les deux autres variables disparaissent de l'expression.
Plus généralement, pour un groupe de 2n cases, n variables peuvent disparaître lorsque le groupe permet de les faire varier.
Les groupes doivent être les plus grands possibles
Il est préférable de former un groupe de quatre cases plutôt que deux groupes de deux lorsqu'un tel regroupement est possible.
De même, un groupe de huit cases est préférable à plusieurs groupes plus petits s'il permet de couvrir les mêmes 1.
Le but est d'obtenir le moins grand nombre de variables possible dans chaque terme.
Une case peut appartenir à plusieurs groupes
Une même case contenant un 1 peut appartenir à plusieurs groupes si cela permet d'obtenir une expression plus simple.
Il n'est donc pas nécessaire de chercher à répartir chaque case dans un seul groupe. Un chevauchement peut au contraire être utile pour réaliser les regroupements les plus grands possibles.
Toutes les cases contenant 1 doivent être couvertes
Lorsqu'on simplifie une fonction, chaque 1 du tableau doit être couvert par au moins un groupe.
On cherche cependant à éviter les regroupements inutiles. Un groupe qui n'ajoute aucune nouvelle combinaison de la fonction simplifiée n'est pas nécessaire.
L'adjacence sur les bords
Les bords d'un tableau de Karnaugh sont reliés entre eux. La première colonne est donc adjacente à la dernière colonne. De même, la première ligne est adjacente à la dernière ligne.
Cela permet de former des groupes qui semblent traverser le bord du tableau.
Par exemple, dans un tableau à quatre variables, les quatre cases situées dans les coins peuvent former un groupe de quatre si elles contiennent toutes un 1. Les coins sont considérés comme voisins grâce à l'adjacence des bords.
Les zéros et les fonctions POS
On peut également utiliser un tableau de Karnaugh en regroupant les 0 plutôt que les 1.
Cette méthode est particulièrement adaptée lorsque l'on souhaite obtenir une expression sous forme de produit de sommes, appelée forme POS (Product of Sums).
Le principe reste identique : on forme des groupes de 0 aussi grands que possible, toujours par groupes de 1, 2, 4, 8, etc.
Les conditions indifférentes
Certaines combinaisons d'entrée peuvent ne jamais se produire dans le fonctionnement réel d'un circuit. Leur sortie n'a alors pas besoin d'être définie.
Ces situations sont représentées dans un tableau de Karnaugh par un symbole X, appelé condition indifférente ou don't care.
Une case contenant un X peut être considérée comme un 0 ou comme un 1, selon ce qui permet d'obtenir la simplification la plus importante.
Une condition indifférente ne doit donc pas obligatoirement être utilisée dans un groupe.
Exemple de simplification
Considérons une fonction à trois variables A, B et C dont la sortie vaut 1 pour les combinaisons suivantes :
001, 011, 101, 111
On remarque que, dans toutes ces combinaisons, la variable C vaut 1. Les variables A et B peuvent prendre indifféremment les valeurs 0 ou 1.
Le tableau de Karnaugh permet donc de regrouper les quatre cases correspondantes en un seul groupe.
La fonction se simplifie en :
F = C
Le circuit n'a alors plus besoin de portes AND ou OR : la sortie peut être directement reliée à C.
Construire un circuit à partir d'un tableau de Karnaugh
Une fois les groupes déterminés, chaque groupe donne un terme de l'expression logique simplifiée.
Les différents termes sont ensuite reliés par une opération OU lorsqu'on utilise un regroupement des 1.
On obtient ainsi une expression logique simplifiée qui peut être transformée directement en circuit avec des portes NOT, AND et OR.
Le tableau de Karnaugh constitue donc une étape intermédiaire entre la table de vérité et le circuit logique.
Optimiser un circuit logique
La simplification par tableau de Karnaugh peut réduire le nombre de portes logiques nécessaires. Elle peut également réduire le nombre d'entrées utilisées par ces portes et le nombre d'étages logiques traversés par le signal.
Un circuit simplifié peut ainsi être plus petit, consommer moins de ressources et présenter un temps de propagation plus faible.
Dans un circuit numérique réel, cette optimisation peut donc avoir des conséquences importantes sur la complexité, la consommation et la vitesse du système.