5 Simplification logique
1.1. Objectifs
- Formuler une expression logique en forme canonique Produit de sommes ou Somme de produits, et convertir entre les deux formes
- Simplifier une expression au moyen d’un diagramme de Karnaugh
- Simplifier une expression par la méthode Quine-McCluskey
- Se familiariser avec les approches d’implémentation des fonctions simplifiées
1.2. Expressions équivalentes
Un des aspects ennuyeux des expressions logiques est que la correspondance entre expression et fonction logique n’est pas biunivoque : plusieurs expressions différentes peuvent correspondre à une seule et même fonction. De plus, certaines des expressions équivalentes peuvent être plus complexes que d’autres. Lorsque vient le temps d’implémenter avec des portes une fonction logique, il est la plupart du temps plus efficace d’implémenter selon une expression plus simple, voire minimale. On doit donc considérer des approches systématiques et efficaces pour simplifier les expressions logiques.
Quand une expression booléenne est implémentée avec des portes logiques, chaque terme nécessite une porte et chaque variable au sein d’un terme correspond à une entrée de la porte. On appelle littéral une variable qui apparaît dans un terme, sous forme complémentée ou non. Par exemple, l’expression compte huit littéraux. Si on réduit le nombre de termes, le nombre de littéraux, ou les deux, on obtiendra une expression qui sera plus simple à implémenter avec des portes.
1.3. Formes canoniques
1.3.1. Minterms et maxterms
Dans une expression, une variable peut apparaître telle quelle ou complémentée . Si on considère les combinaisons possibles de deux variables via un opérateur ET, on a alors quatre possibilités : . Chacun de ces quatre termes s’appelle un minterm.
De façon équivalente (duale, en vérité), variables reliées par une fonction OU peuvent donner lieu à termes distincts, appelés maxterms.
De façon générale, pour variables, on aura minterms ou maxterms différents possibles.
Pour étiqueter les différents minterms ou maxterms, on a établi une convention de numérotation. Le numéro d’étiquette d’un minterm est construit de la façon suivante. Une variable complémentée amène un bit d’étiquette 0, une variable telle quelle amène un bit d’étiquette 1. En ordonnant les bits selon l’ordre alphabétique des variables, on obtient un vecteur de bits qui donnera le numéro à assigner au minterm. Par exemple, le minterm donnera l’étiquette 101, donc le numéro de minterm (en équivalent décimal) 5.
La règle pour les maxterms est duale : une étiquette 0 pour une variable telle quelle, et une étiquette 1 pour une variable complémentée. Chaque maxterm est le complément du minterm correspondant (de même numéro), et vice versa.
Dans le tableau 1, on montre les symboles de la forme pour les minterms et pour les maxterms, avec qui est l’équivalent décimal de la combinaison de bits correspondante.
Minterm | Symb. | Maxterm | Symb. | |||
---|---|---|---|---|---|---|
0 | 0 | 0 | ||||
0 | 0 | 1 | ||||
0 | 1 | 0 | ||||
0 | 1 | 1 | ||||
1 | 0 | 0 | ||||
1 | 0 | 1 | ||||
1 | 1 | 0 | ||||
1 | 1 | 1 |
Pour la fonction dont le tableau de vérité est le suivant :
0 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | |
1 | 0 | 0 | 1 | |
1 | 0 | 1 | 1 | |
1 | 1 | 0 | 1 | |
1 | 1 | 1 | 1 |
on peut donc écrire
puisque ce sont les termes pour lesquels la fonction vaut 1. Cette forme d’expression est une forme canonique appelée somme de produits.
Pour simplifier la notation, on peut écrire de façon plus compacte
où on ne met que les numéros des minterms participant à la somme.
Si on veut exprimer le complément d’une fonction, on peut lire dans le tableau de vérité les combinaisons pour lesquelles la fonction vaut 0. En prenant un minterm pour chaque combinaison où la fonction vaut 0 et en faisant un OU de ces termes, on obtient une expression en somme de produits pour le complément de la fonction. Ainsi, pour la fonction , on a
Si on complémente , on obtiendra naturellement . En appliquant le théorème de DeMorgan à chaque terme, on trouve
Cette forme d’expression est aussi une forme canonique appelée produit de sommes.
Pour simplifier la notation, on peut écrire de façon plus compacte
où on ne met cette fois que les numéros des maxterms participant au produit.
1.3.2. Somme de produits
Pour variables binaires, on a minterms différents possibles. Les minterms qui participent à la somme dans l’expression en forme canonique somme de produits sont ceux qui produisent un 1 dans le tableau de vérité de la fonction. Puisque la fonction peut valoir 0 ou 1 pour chaque minterm, le nombre total de fonctions différentes qui peuvent être définies avec variables est de .
Si on veut convertir en forme canonique somme de produits l’expression pour une fonction qui ne serait pas sous cette forme, on commence par faire l’expansion de l’expression en forme somme de produits. Ensuite, on vérifie chaque terme pour voir si toutes les variables en font partie. S’il manque une ou des variables, on peut faire un ET du terme avec une expression du type dans laquelle est une variable manquante. Ce ET ne change pas la valeur de la fonction puisque .
Évidemment, on peut toujours trouver la formulation en forme canonique en se basant sur le tableau de vérité.
1.3.3. Produit de sommes
Si on veut convertir en forme canonique produit de sommes l’expression pour une fonction qui ne serait pas sous cette forme, on commence par faire l’expansion de l’expression en forme produit de sommes. Pour ce faire, on peut avantageusement faire appel à la distributivité de sur . Ensuite, on vérifie chaque terme pour voir si toutes les variables en font partie. S’il manque une ou des variables, on peut faire un OU du terme avec une expression du type dans laquelle est une variable manquante. Ce OU ne change pas la valeur de la fonction puisque .
1.3.4. Conversion entre formes canoniques
Prenons notre exemple précédent . On sait que . Si on prend le complément de par le théorème de DeMorgan, on obtient .
En effet, de minterm à maxterm, on a . Le maxterm d’indice est le complément du minterm de même indice , et vice versa.
1.3.5. Formes standard
Les expressions canoniques en somme de produits et en produit de sommes ne sont généralement pas simples, car toutes les variables doivent être présentes. Pour l’implémentation, on cherchera des expressions en formes somme de produits ou produit de sommes dans lesquelles les termes pourront être simplifiés. C’est-à-dire que les termes pourront comporter une, deux, trois, etc. variables plutôt qu’obligatoirement toutes les variables. Toujours pour notre fonction exemple, on peut écrire
Lorsqu’on implémente une telle fonction avec des portes logiques, il faut une porte ET pour chaque terme produit (qui comporte plus d’une variable) et une porte OU pour faire la somme finale. On obtient une implémentation à deux niveaux.
De façon duale, on peut également obtenir une formulation en produit de sommes qui aboutira à une implémentation à deux niveaux avec une porte OU par terme et une porte ET pour le produit final.
1.4. Objectifs de minimisation
Étant donné une fonction logique de variables , on veut déterminer une expression pour cette fonction sous la forme somme de produits (S de P) ou produit de sommes (P de S) qui
- comporte un nombre minimum de termes produits (pour la forme S de P) ou de termes sommes (pour la forme P de S);
- est telle qu’aucune expression pour comportant le même nombre de termes n’utilise moins de littéraux.
1.5. Diagrammes de Karnaugh
Une méthode visuelle permet de simplifier l’expression logique d’une fonction en systématisant une procédure faisant appel à un diagramme qui fait ressortir les simplifications possibles.
Un diagramme de Karnaugh (diag-K) est constitué d’un regroupement de cellules carrées, chaque cellule correspondant à un minterm possible. Les cellules sont organisées de façon à ce que lorsqu’on passe d’une cellule à une cellule adjacente (horizontalement ou verticalement), un seul bit du minterm change, ce qui revient à dire qu’une seule variable passe de telle quelle à complémentée.
Cela fait en sorte que si la fonction est 1 pour deux minterms adjacents, la somme des deux minterms pourra être simplifiée en un seul terme dans lequel la variable correspondant au bit qui change est absente. Par exemple, on pourrait avoir pour deux minterms adjacents . Ici, les deux minterms adjacents diffèrent par la variable , qui sera donc supprimée du terme produit résultant.
Figure 1 : Diag-K à deux variables
Figure 2 : Diag-K à trois variables, avec minterms
Sur un diag-K à trois variables, on voit que les bits sont ordonnés selon un code Gray, de façon à ce qu’un seul des bits change lorsqu’on passe d’une cellule à la suivante horizontalement. L’adjacence se poursuit en bout de diagramme : par exemple, la cellule 100 () est adjacente horizontalement à la cellule 000 (). On peut imaginer le diagramme comme replié sur lui-même pour visualiser cette adjacence.
Figure 3 : Diag-K avec adjacence horizontale
Sur un diag-K à quatre variables, l’adjacence repliée est aussi bien horizontale que verticale.
Pour plus de quatre variables, il devient difficile d’utiliser cette méthode : les diagrammes sont de grande taille et, surtout, les règles d’adjacence ne sont plus aussi facilement observables. Les risques d’erreurs sont plus grands.
Figure 4 : Diag-K à quatre variables
1.5.1. Procédure de simplification
Pour utiliser un diag-K pour minimiser une fonction logique,
- Les minterms de la fonction à minimiser sont identifiés en insérant un 1 dans la cellule correspondant à chaque minterm.
- On cherche dans le diagramme pour trouver des regroupements de deux cellules adjacentes qui sont marquées d’un 1.
- Chaque groupe de deux cellules 1 adjacentes est marqué comme groupe. Un même minterm peut être incorporé à plus d’un groupe.
- Il est aussi possible de regrouper les groupes : deux groupes de 2 qui sont adjacents peuvent ainsi se regrouper en un groupe de 4. Les tailles de groupes doivent être des puissances de 2. Il est ainsi possible de créer des groupes de 2, 4, 8 ou 16 minterms.
- Une fois tous les regroupements identifiés, il est possible de lire l’expression de la fonction en somme de produits. Chaque groupement correspond à un terme produit, et la ou les variables dont le bit ne change pas dans le groupe sont conservées; les autres sont éliminées.
Considérons par exemple la fonction . Après la première étape, on obtient
Après les regroupements, on obtient un diag-K comportant trois regroupements
Figure 5 : Diagramme après les regroupements
Le groupe en rouge correspond au produit , celui en bleu correspond à et celui en vert correspond à . L’expression finale en somme de produits est donc .
1.5.2. Cas facultatifs
Certaines fonctions sont incomplètement définies, dans le sens où certaines combinaisons d’entrées ne se produiront jamais ou seront sans conséquences si elles se produisent. On parle de cas indifférents ou facultatifs (en anglais, don’t care). Pour la simplification, ces cas pourront être traités tantôt comme des 0, tantôt comme des 1, selon ce qui sera le plus avantageux.
Pour tenir compte de ces cas, les minterms seront notés avec un X dans le diagramme de Karnaugh. Dans l’exemple à quatre variables suivant, sur deux cas facultatifs, un seul, celui correspondant à , a été traité comme un 1, ce qui a permis de créer le regroupement en bleu. L’autre cas facultatif, correspondant à , n’a pas servi dans un regroupement, ce qui signifie qu’il a été traité comme un 0. La fonction résultante est donc .
Figure 6 : Diag-K avec cas facultatifs
1.5.3. Impliquants
Le choix des regroupements à utiliser doit toujours viser à s’assurer que :
- Tous les minterms de la fonction sont couverts par les regroupements choisis.
- Le nombre de termes retenus pour l’expression est minimal.
- Il n’y a pas de termes redondants, c’est-à-dire qui couvrent uniquement des minterms déjà couverts.
Il y a parfois plus d’une expression qui rencontre ces critères. Il est possible de systématiser le choix des termes en prenant en compte le caractère essentiel des termes.
Soit un terme produit de littéraux tirés de l’ensemble de variables . Si, pour une fonction logique définie pour le même ensemble de variables, la relation
pour tout tel que ,
tient, alors est un impliquant de . Cela signifie que la vérité du terme produit implique celle de . Tout minterm de est aussi un minterm de .
Exemple :
, , sont des impliquants évidents de .
, , , sont aussi des impliquants de .
Figure 7 : Diag-K pour l’exemple des impliquants
1.5.4. Impliquant premier
Un impliquant de la fonction est premier si n’importe quel terme produit obtenu de en supprimant un littéral n’est pas un impliquant de .
Ici, est un impliquant premier de , car ni ni ne sont des impliquants de . Mais n’est pas un impliquant premier de , car est un impliquant de . Sur un diagramme de Karnaugh, un impliquant premier (i.p.) est un groupe qui n’est contenu dans aucun autre groupe plus grand.
1.5.5. Couverture d’une fonction
Un sous-ensemble d’i.p. qui contient tous les minterms d’une fonction couvre la fonction.
Une couverture minimale est une couverture avec
- le nombre minimal d’impliquants premiers,
- le moins de littéraux parmi les couvertures avec nombre minimum d’impliquants.
1.5.6. Impliquant premier essentiel
Un i.p. est essentiel si et seulement s’il couvre un minterm de la fonction qui ne peut être couvert par un autre i.p. de la fonction. Une couverture de la fonction doit contenir tous les impliquants premiers essentiels (i.p.e.).
Un impliquant premier absolument inessentiel est un i.p. qui couvre des minterms qui sont tous couverts par les i.p.e. de la fonction.
1.5.7. Sélection des impliquants
Règles de sélection des impliquants
- Mettre de côté tous les i.p.e. Ils seront utilisés dans la solution finale.
- Éliminer tous les i.p. absolument inessentiels.
- Il reste à choisir parmi les i.p. inessentiels pour obtenir une couverture minimale.
Lorsque le problème est de taille réduite, on peut faire une recherche exhaustive de toutes les solutions possibles pour choisir la solution minimale.
1.5.8. Minimisation avec cas facultatifs
- Lorsqu’on détermine les i.p., on doit considérer les X comme des 1, de façon à pouvoir utiliser les i.p. rendus possibles par les cas facultatifs.
- Lors de la sélection des i.p. pour obtenir une couverture minimale, on ne doit pas essayer de couvrir les X.
1.5.9. Minimisation avec plusieurs fonctions
Si deux fonctions et ont des expressions minimales qui comportent un terme commun, une seule porte suffira pour générer ce terme au profit des deux fonctions.
Exemple :
Figure 8 : Fonction
Figure 9 : Fonction
Il est alors préférable de réutiliser les termes communs et de générer seulement les termes manquants pour la seconde fonction. Dans cet exemple, le terme sera calculé une seule fois. Les termes et sont nécessaires pour . Alors, pour , on fera
qui ne nous coûtera que le dernier terme produit et une somme de quatre termes.
1.6. Tableau de couverture Quine-McCluskey
La méthode de Quine-McCluskey systématise la sélection des impliquants en se basant sur des relations qui s’expriment en fonction d’un tableau de couverture.
Un tableau de couverture comporte une ligne pour chaque i.p. et une colonne pour chaque minterm de la fonction à minimiser . Un ✔ est inscrit à l’intersection de la ligne et de la colonne si l’i.p. de la ligne couvre le minterm de la colonne .
Le problème de minimisation devient alors : trouver une couverture pour la fonction qui
- contient le nombre minimum de lignes
- est telle qu’aucune autre couverture à nombre de lignes minimum comprend moins d’entrées 1 et 0 dans ses codes d’impliquants de ligne.
Dans le tableau de couverture, on identifie facilement les i.p.e. par les colonnes qui ne contiennent qu’un ✔. L’i.p. qui couvre une colonne qui ne contient qu’un ✔ est un i.p.e.
Puisque les i.p.e. doivent faire partie de la solution finale, toutes les colonnes couvertes par des i.p.e. seront couvertes dans n’importe quelle solution. On peut donc éliminer ces colonnes de la suite de la recherche de la solution, de même que les lignes correspondant aux i.p.e. On obtient ainsi un tableau de couverture réduit.
Il ne faut cependant pas oublier de mettre les i.p.e. dans la solution finale.
1.6.1. Tableau de couverture réduit
Le tableau de couverture réduit permet de se concentrer sur la sélection des i.p. dont la sélection n’est pas évidente a priori. Pour illustrer la discussion, considérons le tableau de couverture réduit suivant. est sans doute couvert pas un i.p.e. qui n’est pas montré ici.
✔ | ✔ | ✔ | ✔ | |||||
✔ | ✔ | ✔ | ✔ | |||||
✔ | &✔ | ✔ | ✔ | |||||
✔ | ✔ | |||||||
✔ | ✔ | ✔ | ✔ | ✔ | ✔ | ✔ |
1.6.2. Dominance de lignes
Une ligne domine une ligne (ce qui est noté ) si la ligne contient un ✔ dans toutes les colonnes où la ligne contient un ✔. Ici, on a mais ne domine pas . On peut voir aussi que domine plusieurs lignes.
En général, une dominante contient plus de ✔ que . Si elles ont le même nombre de ✔ (dans les mêmes colonnes), on a . Il n’y a pas de cas d’égalité ici.
Une ligne dominée par une autre peut être éliminée du tableau de couverture à condition que son nombre de littéraux soit supérieur ou égal à celui de la ligne dominante.
1.6.3. Dominance de colonnes
Une colonne domine une colonne (ce qui est noté ) si la colonne contient un ✔ dans toutes les lignes où la colonne contient un ✔. Ici, la colonne mais ne domine pas .
Une colonne dominant une autre colonne peut être éliminée du tableau de couverture, car le fait que la solution finale couvre la colonne dominée assure que la colonne dominante sera couverte aussi. Donc ici, la colonne peut être éliminée.
En cas d’égalité, comme on a ici pour , on peut librement choisir quelle colonne éliminer.
1.7. Implémentation des fonctions simplifiées
Les circuits logiques simplifiés en forme produit de sommes ou somme de produits sont souvent mis en oeuvre au moyen de portes NAND ou NOR plutôt qu’avec des portes ET et OU. La raison en est qu’il est plus simple en pratique de réaliser ces portes.
1.7.1. Implémentation à deux niveaux
Une fonction en forme somme de produits s’implémente évidemment avec des portes ET pour les produits et une porte OU pour la somme finale. Considérons par exemple .
Figure 10 : Somme de produits pour
La fonction peut aussi s’implémenter tout naturellement en faisant appel uniquement à des portes NAND. On peut vérifier facilement que le circuit suivant implémente la même fonction
Figure 11 : Somme de produits NAND
Cette configuration s’interprète plus facilement en représentant la porte de sortie comme une porte NOR avec les entrées complémentées (version équivalente de la porte NAND). En effet, la complémentation de chaque sortie de somme est compensée par la complémentation à l’entrée de la porte de sortie.
Figure 12 : Somme de produits NAND plus évidente
Quiz de fin de chapitre
Donnez le tableau de vérité pour les critères d’achat, en faisant glisser les bits 0 ou 1 pour remplir le tableau ci-dessous.
Remplissez le diagramme de Karnaugh pour le tableau de vérité suivant , en faisant glisser les bits 0 ou 1 pour remplir le tableau ci-dessous.
Tableau de vérité
abcd | Sortie |
---|---|
0000 | 0 |
0001 | 1 |
0010 | 0 |
0011 | 0 |
0100 | 1 |
0101 | 1 |
0110 | 1 |
0111 | 0 |
1000 | 1 |
1001 | 1 |
1010 | 0 |
1011 | 1 |
1100 | 1 |
1101 | 1 |
1110 | 1 |
1111 | 1 |
Appariez (en glissant les images de gauche) les tableaux de vérité avec les diagrammes de Karnaugh correspondants.
Les questions suivantes se rapportent au tableau de couverture suivant. Vous devez d’abord compléter le tableau en glissant les crochets dans les bonnes cases.