Optimisation des circuits combinatoires

aintenant que la base théorique fondant l’algèbre de Boole a été couverte et que nous avons illustré son applicabilité dans le cadre des circuits logiques combinatoires, nous allons nous pencher sur le problème de l’optimisation de ces circuits.

L’économie des ressources matérielles est un problème d’importance et un défi de taille. Le défi réside principalement dans l’explosion combinatoire des solutions possibles pour une même fonction logique. On sait par exemple qu’un circuit combinatoire à 2 entrées peut implémenter jusqu’à 16 fonctions logiques. Chacune de ces fonctions logiques peut avoir une multitude de réalisations physiques possibles et il faut faire le tri parmi celle-là pour trouver la meilleure. Le nombre de fonctions logiques passe à 256 pour un circuit à 3 entrées et le nombre de réalisations possibles est d’autant plus grand. Ce nombre est 65 536 pour un circuit à 4 entrées, et il ne cesse de grossir inconsidérément avec le nombre d’entrées du circuit. L’expression générale de cette relation est donnée par :

Nombre de fonctions pour n entrées = 2^k, où k=2ⁿ

Aussi, les premiers travaux scientifiques réalisés dans le cadre des circuits logiques ont traité de la problématique d’optimisation des circuits combinatoires. Ces travaux forment une base théorique essentielle pour qui veut travailler dans le domaine de l’électronique numérique. Il existe de nombreuses techniques d’optimisation.

Nous nous intéresserons plus particulièrement à deux d’entre elles. La première méthode est celle des tables de Karnaugh. Il s’agit d’une méthode graphique recourant à une disposition spatiale des valeurs logiques fort ingénieuse, mais elle demeure confinée à une utilisation par les humains. Cette méthode, quoiqu’élégante, trouve en effet rapidement ses limites et ne permet pas de résoudre des problèmes complexes tels que la simplification de fonctions logiques à sept variables et plus.

La seconde méthode comble cette lacune en abandonnant la disposition spatiale au profit d’un recensement exhaustif des combinaisons des minterms. Eût égard à l’explosion combinatoire susmentionnée, cette méthode demeure réservée à une exécution machine. Elle sera pour nous néanmoins un moyen d’approfondir les concepts relatifs à la simplification des fonctions logiques.

4.1 Table de Karnaugh

Nous commençons ce chapitre par considérer les tables de Karnaugh. Les tables de Karnaugh sont une représentation tabulaire des diagrammes de Venn présentés au chapitre 2. Les tables de Karnaugh représentent des fonctions à plusieurs variables, le nombre de variables pouvant aller de deux (2) à un maximum de six (6). Nous allons considérer dans un premier temps le cas des tables de Karnaugh à 2, 3 et 4 variables. Les tables de Karnaugh à 5 ou 6 variables seront également présentées mais on préférera solutionner ce type de problèmes par une approche dite de variables inscrites. Nous considérerons donc attentivement les techniques relatives à l’inscription des variables indépendantes dans les tables de Karnaugh après avoir traité des considérations relatives aux problèmes d’optimisation à cas facultatifs.

4.1.1 Table de Karnaugh à deux variables

La figure suivante présente une fonction logique représentée sous forme d’une table de vérité et la table de Karnaugh qui lui est associé.

1 A B F 0 0 0 0 1 1 1 0 0 1 1 1 1	1 1
Table de vérité	Table de Karnaugh

Comme on peut le constater, les valeurs de la fonction F sont déplacées vers l’intérieur de la table de Karnaugh alors que les variables indépendantes sont distribuées sur sa périphérie. L’intérêt de l’opération réside dans l’adjacence des valeurs logiques de la fonction F. Lorsque deux cellules sont adjacentes et qu’elles contiennent la même valeur logique, elles peuvent être réunies pour former un seul terme.

4.1.2 Table de Karnaugh à trois variables

La figure suivante présente un exemple de table de Karnaugh à trois variables. La fonction logique dépend des trois variables A, B et C. Ces dernières sont réparties en périphérie de la table de Karnaugh. L’inscription BC indique les valeurs prises par les variables B et C respectivement. Ainsi, 00 correspond à B=0, C=0; 01 à B=0, C=1, et ainsi de suite.

Il importe de relever l’évolution des variables BC. Contrairement à ce que l’on retrouve dans les tables de vérité, l’ordre d’énumération des valeurs BC n’est pas celui de la représentation binaire des nombres (en l’occurrence 00, 01, 10 et 11); il s’agit d’une énumération associée à un code dit de Grey. Ce dernier sera couvert au chapitre 7. On peut d’ores et déjà remarquer que d’une valeur à la suivante, un seul bit change. C’est cette propriété qui permet à deux cellules adjacentes de former un terme unique.

Par exemple, les termes voisins AC et ABC peuvent être unis pour former le terme simplifié AC :

AC + ABC =AC (+B )=AC(1)=AC

Le code de Grey étant cyclique, cette propriété des cellules adjacentes est valide même aux extrémités de la table de Karnaugh.

Par exemple, les termes voisins et B peuvent être unis pour former le terme simplifié :

+ B =(+B )= (1)=

4.1.3 Table de Karnaugh à quatre variables

La table de Karnaugh à quatre variables est certainement le cas de figure le plus utilisé. Les lignes cette fois prennent les valeurs de deux variables et non plus d’une seule, et sont arrangés selon le code de Grey :

Les lignes correspondent aux variables A et B, les colonnes aux variables C et D.

Il est possible de combiner deux cellules adjacentes, quatre cellules adjacentes formant un carré ou un rectangle et encore huit cellules formant un rectangle comme l’illustrent les exemples suivants :

Cas de deux cellules adjacentes :

Cas de quatre cellules adjacentes formant un carré ou un rectangle :

Cas de huit cellules adjacentes formant un rectangle :

Une façon simple de retrouver le terme formé par l’union des cellules est d’éliminer les variables qui se prennent les deux valeurs logiques possibles (0 et 1) et de ne garder que celles qui ne sont présentes que sous une seule des deux formes (0 ou 1). Si la valeur logique est 0, la variable apparaîtra dans le terme simplifié sous forme négative (inversé), si cette valeur logique est 1, la variable apparaît sous forme positive (non-inversée). Considérons à cet effet notre dernier exemple: la variable A prend les deux formes logiques 0 et 1, notamment aux lignes 1 et 3; il en est de même pour les variables B (ligne 1 et 2) et D (colonne 1 et 2). Il ne reste donc que la variable  C qui prend uniquement la valeur 0. Le terme ainsi obtenu s’écrit sous forme négative :

Rappelons que la cyclicité du code de Grey permet d’unir les cellules adjacentes aux extrémités de la table de Karnaugh. L’exemple suivant présente l’union de huit cellules de cette sorte :

4.1.4 Évaluation de la fonction logique

Jusqu’ici, nous nous sommes contentés d’extraire un terme des tables de Karnaugh sans évaluer la fonction logique. Avant de présenter la méthode de simplification par table de Karnaugh de manière systématique et rigoureuse, considérons pas à pas un exemple pédagogique. Reprenons à cet effet l’exemple précédent de la fonction à quatre variables A, B, C et D. Les deux cellules à droite de la seconde ligne contiennent des 1 et peuvent être unis :

La simplification des termes veut cependant que l’on cherche à simplifier au mieux la fonction logique. Or il apparaît qu’une cellule plus large englobe le terme précédent : il suffit pour cela d’inclure les deux cellules à droite de la troisième ligne :

Ce nouveau terme peut à son tour être englobé dans une cellule encore plus large, et ce en incluant les quatre cellules à gauche des lignes 2 et 3.

La figure suivante présente ce résultat. À ce stade, on constate que la cellule ne peut plus être étendue et constitue le terme le plus simple pour l’ensemble de ces minterms. Nous avons donc un premier terme d’une expression disjonctive : B.

Un second rectangle contenant lui aussi huit éléments nous apparait aux colonnes 1 et 2, formant le terme :. Il importe de noter que ces deux rectangles partagent quatre cellules.

Le procédé de simplification ne peut cependant être arrêté à ce stade puisqu’il reste encore deux cellules contenant des 1. Ces deux cellules étant adjacentes, il serait possible de les unir comme l’illustre la figure suivante :

Cette expression n’est cependant pas optimale. Il apparaît en effet qu’un rectangle encore plus large peut inclure ces deux cellules. Pour ce faire. Il faut avoir recours à certaines cellules déjà utilisées.

Cette nouvelle expression est plus simple que la précédente, mais elle n’est toujours pas optimale. En effet, une inspection plus attentive du problème permet de trouver un rectangle encore plus large regroupant l’ensemble des cellules du nouveau rectangle.

 

Pour ce faire, il faut recourir à la propriété de cyclicité du code de Grey. Il est alors possible de réunir des cellules aux extrémités de la table de Karnaugh comme l’indique la figure suivante :

À ce stade, aucun rectangle n’est entièrement contenu dans un rectangle plus large, et l’ensemble des rectangles couvre la totalité des cellules contenant un 1. La section 4.1.6 aura soin de donner les noms des concepts essentiels couverts ici et d’énoncer clairement l’algorithme de simplification.

4.1.5 Unir les maxterms

Il est également possible d’unir les maxterms d’une table de Karnaugh plutôt que les minterms comme nous l’avons fait jusqu’ici. Pour ce faire, il suffit de procéder de manièere inverse.

On cherchera à réunir les 0 plutôt que les 1 dans la table. Les variables dans les termes ainsi obtenus sont exprimés sous forme positive (non inversée) si elles ne prennent que la valeur 0, autrement, elles sont exprimées sous forme négative (inversée). La fonction simplifiée est exprimée sous forme d’un produit de sommes.

Dans notre exemple, il n’est possible de réunir qu’un seul rectangle. Ce dernier comprend la variable A sous ses deux formes (ligne 1 et ligne 4). Elle est éliminée du terme obtenu par l’union.  Les autres variables se présentent sous une seule forme : B prend uniquement la valeur 0 et sera représentée sous forme positive dans le terme ; C prend uniquement la valeur 1 et sera représentée sous forme négative dans le terme ; D prend uniquement la valeur 1 et sera représentée sous forme négative dans le terme. Le terme résultant peut également être obtenu algébriquement comme suit :

 = =B + +

Relevons que la forme conjonctive simplifiée est la même que celle de l’expression disjonctive simplifiée. C’est là un cas particulier qui n’a aucune valeur de généralité.

4.1.6 Impliquant/impliqué premier et essentiel

La présente section va nous permettre de définir un lexique qui nous sera utile pour mieux comprendre les algorithmes de simplification des fonctions logiques. Les termes seront introduits dans le contexte des tables de Karnaugh bien que leur applicabilité soit plus générale. L’étude de la méthode Quine-McCLuskey permettra de mieux apprécier la généralisation.

·         Nous définissons l’impliquant (resp. l’impliqué) comme un terme regroupant des cellules adjacentes d’une table de Karnaugh contenant la valeur logique 1 (resp. 0) et formant un rectangle dont les côtés sont une puissance de 2 (1, 2, 4).

·         Nous définissons également l’impliquant premier (resp. l’impliqué premier) comme un impliquant (resp. un impliqué) défini par un rectangle qui ne peut être circonscrit dans aucun rectangle associé à un autre impliquant (resp. impliqué).

·         Nous définissons finalement l’impliquant premier essentiel (resp. l’impliqué premier essentiel) comme un impliquant premier (resp. un impliqué premier) qui possède au moins une cellule qui n’est contenue dans aucun autre impliquant premier (resp. impliqué premier).

L’algorithme de simplification à l’aide d’une table de Karnaugh s’énonce alors comme suit :

1.             Trouver les impliquants/impliqués premiers en commençant par ceux qui comportent le plus de cellules

2.             Identifier les impliquants/impliqués premiers essentiels

3.             Si il reste des cellules, les associer à des impliquants/impliqués premiers qui soient :

·         Les plus gros possibles (comportant le plus de cellules possibles)

·         Les moins nombreux possible (réduire le nombre d’impliquant/impliqués premiers)

Illustrons ceci par un exemple (nous considérons uniquement le cas d’expressions disjonctives) :

1.         On commence par chercher des impliquants premiers comportant 8 cellules : Il n’y en a pas.

 

On cherche des impliquants premiers comportant 4 cellules : il y en a une seule.	On cherche des impliquants premiers comportant 2 cellules : il y en a quatre.

 

2.         On identifie les impliquants premiers essentiels, il y en a deux

3.         On élimine des impliquants premiers de sorte à garder :

·         Les plus gros possibles

·         Le moins possible

Ce qui nous permet d’exprimer la fonction logique : f (A, B, C, D) = +ACD+BC.

Le procédé est identique pour trouver l’expression conjonctive simplifiée :

1.                  On commence par chercher des impliqués premiers comportant 8 cellules : Il n’y en a pas.

On cherche des impliqués premiers comportant 4 cellules : il y en a une seule.	On cherche des impliqués premiers comportant 2 cellules : il y en a quatre.

 

2.         On identifie les impliqués premiers essentiels, il y en a deux

3.         On élimine des impliqués premiers de sorte à garder :

·         Les plus gros possibles

·         Le moins possible

Ce qui nous permet d’exprimer la fonction logique : f (A, B, C, D) = (+C )( A+ +)( B++D ).

4.1.7 Karnaugh avec cas facultatifs

Il arrive parfois qu’une fonction logique ne soit pas définie pour l’ensemble des combinaisons possibles de ses variables d’entrée. Ces combinaisons, pour lesquelles les sorties sont dites facultatives, résultent souvent de la pratique où nombre de cas ne sont pas à considérer. Ce qu’on entend par le fait de dire que la sortie est facultative, c’est qu’elle peut prendre indifféremment la valeur 0 ou 1 sans affecter le comportement attendu du système.

Les techniques d’optimisation profitent alors de cette tolérance pour optimiser davantage le résultat. Grâce à leur qualité d’illustration graphique, les tables de Karnaugh permettent une exploitation élégante de ces conditions favorables.

Considérons l’exemple donné par la table de vérité suivante. La dernière ligne englobe l’ensemble des combinaisons non énumérée (représentés par deux tirets --) et correspondant aux minterms 10 à 15 de la fonction f. Les valeurs facultatives de f  sont représentés par un seul tiret (-).

L’équivalent de cette table de vérité en table de Karnaugh suit :

Afin de résoudre ce problème, il est conseillé d’agir comme si tous les cas facultatifs étaient des minterms de la fonction à simplifier. Il suffit alors d’appliquer la méthode de simplification par table de Karnaugh comme nous le faisions à la section 4.1.6 à quelques différences près.

1.                  On commence par recenser les impliquants premiers :

2.         On élimine les impliquants premiers ne comportant que les cas facultatifs :

3.         On identifie les impliquants premiers essentiels, il y en a quatre.

Si nécessaire, on choisit d’autres impliquants premiers pour couvrir les minterms de départ (donc sans compter les cas facultatifs). Dans notre exemple, les impliquants premiers essentiels couvrent déjà l’ensemble des minterms; le processus de simplification est donc terminé :

f (a₃, a₂, a₁, a₀) = + a₁a₀ + a₂a₁ + a₃a₀

4.1.8 Karnaugh à variables inscrites

Nous avons vu précédemment que les tables de Karnaugh sont utilisées pour simplifier des fonctions à plusieurs variables, le nombre de variables allant de 2 à 6. Or nous n’avons abordé que les tables de Karnaugh à 2, 3 et 4 variables. Les deux derniers modèles sont en fait assez difficiles à utiliser et peu usités dans la pratique. On leur préfère une écriture plus élégante et plus facile à manier qui est celle des tables de Karnaugh à variables inscrites.

Une table de Karnaugh à variables inscrites est une table de Karnaugh habituelle dans laquelle on inscrit une ou plusieurs des variables indépendantes à l’intérieur de la table. Par exemple :

Nous allons considérer la méthode permettant d’inscrire une ou plusieurs variables dans une table de Karnaugh, puis nous nous pencherons sur les méthodes de simplification permettant d’extraire l’expression de la fonction booléenne ainsi décrite. Lorsqu’une variable se trouve dans une cellule d’une table de Karnaugh, il faut associer à la fonction le minterm résultant du produit logique (opérateur de conjonction ET) de cette variable par le minterm correspondant à la cellule considérée. Dans l’exemple précédent, nous aurions à la deuxième ligne et à la troisième colonne le minterm :

BCD

Pour inscrire ladite variable dans la table, il faut procéder à l’inverse. Considérons quelques exemples simples qui seront facilement généralisables. Prenons la fonction à 3 variables suivante et la table de Karnaugh qui lui est associée :

1 A B C f 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1

 

Pour passer de l’une à l’autre, il faut regrouper les lignes de la table de vérité deux à deux et considérer la valeur de la fonction selon la variable C :

1 A B C f 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1

f est égal à C : C   f est l’inverse de C :   f vaut toujours 1 : 1   f vaut toujours 0 : 0

On peut en fait utiliser la décomposition de Shannon pour généraliser la chose ainsi :

1 A B C f 0 0 0 s0 0 0 1 s1 0 1 0 s2 0 1 1 s3 1 0 0 s4 1 0 1 s5 1 1 0 s6 1 1 1 s7

On peut ici faire l’association entre cette dernière table de Karnaugh et le résultat présenté précédemment. On voit donc qu’il est possible de passer d’une fonction à n variables et de l’exprimer avec une table de Karnaugh à n-1 variables. Ce nouveau résultat peut-être réutilisé pour représenter la fonction par une table de Karnaugh pour n-2 variables. On pourra ainsi traiter un problème de simplification à cinq ou six variables indépendantes en utilisant une table de Karnaugh à quatre variables, simplement en inscrivant les variables restantes.

Quand on vient à simplifier une table de Karnaugh à variables inscrites, il est possible de réunir les cellules contenant la même variable inscrite. On peut alors procéder de manière ingénieuse en rappelant la règle de complémentation :

A+ =1

Ainsi, si nous reprenons la table de Karnaugh précédente, nous aurons :

1

Ce qui nous donne :

f (A,B,C) = +BC

Voici un exemple avec solution. Le lecteur est invité à détailler la solution afin de bien comprendre le fonctionnement :

Exemple :

f (A,B,C,D) = + AE + AE + BD + CD

Il est important de noter que la cellule correspondent au minterm ABD contient un 1 qui est inclus dans deux impliquants premiers, le premier contenant des E, le second des . Ce type d’inclusion est important et rappelle celui de notre exemple de fonction à trois variables.

4.2 Technique de Quine-McCluskey

La technique de Quine-McCluskey est proche de celle de la table de Karnaugh mais recourt à un formalisme permettant de manipuler plus que 6 variables. Ainsi, la technique de Quine-McCluskey permet de résoudre des problèmes à 10 voire 15 variables indépendantes. La technique de Quine-McCluskey étant principalement une méthode algorithmique destinée à une exécution logicielle, elle ne sera pas particulièrement utilisée dans le reste du manuel. Néanmoins, il importe au futur ingénieur de comprendre le fonctionnement de la technique et de pouvoir l’exécuter à la main pour faire le parallèle avec la méthode de Karnaugh.

4.2.1 Formulation de l’algorithme

La technique de Quine-McCluskey s’applique de la même manière aux expressions disjonctives qu’aux expressions conjonctives. Nous nous concentrerons dans ce qui suit sur le cas des expressions disjonctives. L’algorithme s’exprime ainsi :

1.        Exprimer la fonction sous forme canonique disjonctive ;

2.        Exprimer les minterms sous forme binaire ;

3.        Grouper les termes selon leur poids ;

4.        Unir les termes deux à deux ;

5.        Répéter l’étape (4) autant de fois que nécessaire ;

6.        Identifier les impliquants premiers ;

7.        Identifier les impliquants premiers essentiels ;

8.        Si la fonction est entièrement exprimée par ses impliquants premiers essentiels, arrêter ;

9.        Sinon, choisir, les impliquants premiers non essentiels permettant une couverture complète.

Nous allons l’illustrer par un exemple. Considérons la fonction suivante exprimée par sa table de vérité :

1.          Exprimer la fonction sous forme canonique disjonctive

f (A,B,C,D) = BD+BCD+AB+ABD+ABC+ABCD+A+AC

2.          Exprimer les minterms sous forme binaire

f (A,B,C,D) = 0101+0111+1100+1101+1110+1111+1000+1010

Pour chaque minterm, on remplace les variables par leur équivalent binaire. Si la variable est inversée, on pose 0, si elle ne l’est pas, on pose 1. Par exemple :

3.         

Poids 1

Grouper les termes selon leurs poids

1.	1000
2.	Poids 2   1010
3.	0101
4.	1100
5.	Poids 3   0111
6.	1101
7.	Poids 4   1110
8.	1111

Le mot poids renvoie au nombre de 1 contenus dans la forme binaire des minterms.

4.          Unir les termes deux à deux

Cette procédure est clé. Il s’agit de générer une nouvelle colonne de termes en réunissant deux à deux les termes de la colonne précédente.

1.	1000	ü		10x0	Généré en combinant 1. et 2.
2.	1010	ü		1x00	Généré en combinant 1. et 4.
3.	0101	ü		1x10	Généré en combinant 2. et 7.
4.	1100	ü		01x1	Généré en combinant 3. et 5.
5.	0111	ü		x101	Généré en combinant 3. et 6.
6.	1101	ü		110x	Généré en combinant 4. et 6.
7.	1110	ü		11x0	Généré en combinant 4. et 7.
8.	1111	ü		x111	Généré en combinant 5. et 8.
				11x1	Généré en combinant 6. et 8.
				111x	Généré en combinant 7. et 8.

 

Pour unir deux termes ensemble, il faut qu’ils appartiennent à deux groupe de poids successifs (0 et 1;
1 et 2; 2 et 3; 3 et 4, et ainsi de suite), il faut qu’ils soient identiques à un bit près. Lorsque deux termes sont unis, on retranscrit le produit de leur union dans la nouvelle colonne en remplaçant par un x le bit qui différenciait. À chaque fois qu’un terme est utilisé pour générer un nouveau sur la nouvelle colonne, on l’indique par une coche (ü). Lorsque l’on passe d’une paire de groupes de poids successifs à la suivante, on l’indique par un trait délimitant les nouveaux groupes de poids.

5.          Répéter l’étape (4) autant de fois que nécessaire

On réunit les termes de la nouvelle colonne comme nous l’avions fait à l’étape (4). Pour que deux termes soient unis, en plus des conditions précédentes, il faut que les x soient au même endroit.

1.	10x0	ü		1xx0	Généré en combinant 1. et 7.
2.	1x00	ü		1xx0	Généré en combinant 2. et 3.
3.	1x10	ü		x1x1	Généré en combinant 4. et 9.
4.	01x1	ü		x1x1	Généré en combinant 5. et 8.
5.	x101	ü		11xx	Généré en combinant 6. et 10.
6.	110x	ü		11xx	Généré en combinant 7. et 9.
7.	11x0	ü
8.	x111	ü
9.	11x1	ü
10	111x	ü

Si le même terme est généré plusieurs fois, on ne garde qu’une seule copie. On répète alors l’étape (4) :

1.	1xx0		Impossible de combiner aucun des termes car
2.	x1x1		il n’y a pas de termes possédant les x au même
3.	11xx		Endroit

Ne pouvant plus réunir aucune paire de termes, l’étape (5) est terminée.

6.          Identifier les impliquants premiers

On reprend ici l’ensemble des étapes effectuées :

1000	ü		10x0	ü		1xx0
1010	ü		1x00	ü		x1x1
0101	ü		1x10	ü		11xx
1100	ü		01x1	ü
0111	ü		x101	ü
1101	ü		110x	ü
1110	ü		11x0	ü
1111	ü		x111	ü
			11x1	ü
			111x	ü

Tous les termes qui ne sont pas marqués (ü) sont des impliquants premiers : 1xx0, x1x1, 11xx. Cette écriture binaire se lit A, BD et AB respectivement.

7.          Identifier les impliquants premiers essentiels

Pour identifier les impliquants premiers essentiels, on utilise un tableau tel que sur les lignes, on dispose tous les impliquants premiers identifiés et que sur les colonnes, on pose les minterms de la fonction. On procède alors par identification :

	1000	1010	0101	1100	0111	1101	1110	1111
1xx0	*	*		*			*
x1x1			*		*	*		*
11xx				*		*	*	*

Un impliquant premier est essentiel si il est le seul à être associé à au moins un minterm. Ainsi, un minterm appartient à un impliquant premier essentiel si sa colonne ne comporte qu’un seule astérisque (*).

	1000	1010	0101	1100	0111	1101	1110	1111
1xx0	(*)	(*)		*			*
x1x1			(*)		(*)	*		*
11xx				*		*	*	*

Un impliquant premier est essentiel s’il comporte au moins une étoile entre parenthèses. Dans notre exemple, les impliquants premiers essentiels sont : 1xx0 et x1x1.

8.          Vérifier si la fonction est entièrement exprimée par ses impliquants essentiels

Pour ce faire, il faut refaire le tableau (il est aussi possible d’effectuer cette étape sur le même tableau précédent) en ne gardant que les impliquants essentiels :

	1000	1010	0101	1100	0111	1101	1110	1111
1xx0	(*)	(*)		*			*
x1x1			(*)		(*)	*		*

Pour que la fonction soit entièrement décrite par ses impliquant essentiels, il faut que chaque colonne comporte au moins une étoile. C’est le cas de notre exemple. La technique de Quine-McCluskey s’arrête à ce point :

f (A,B,C,D) = 1xx0 + x1x1 = A+BD

Nous verrons plus loin comment faire si la fonction n’est pas décrite par ses impliquants premiers. Il est suggéré au lecteur de reprendre cet exemple avec une table de Karnaugh.

Exemple : Soit une fonction à simplifier par la méthode de Quine-McCluskey et définie par sa table de vérité :

1.             Exprimer la fonction sous forme canonique disjonctive

f (A,B,C,D) = + BD + BCD + AC + ABD+ABC+ ABCD

2.             Exprimer les minterms sous forme binaire

f (A,B,C,D) = 0000 + 0101 + 0111 + 1010 + 1101 + 1110 + 1111

3.             Grouper les termes selon leurs poids

1.	0000
2.	0101
3.	1010
4.	0111
5.	1101
6.	1110
7.	1111

Remarquer qu’il n’y a pas de minterm dans le groupe de poids 1!

4.             Unir les termes deux à deux

1.	0000			01x1	Généré en combinant 2. et 4.
				x101	Généré en combinant 2. et 5.
2.	0101	ü		1x10	Généré en combinant 3. et 6.
3.	1010	ü		x111	Généré en combinant 4. et 7.
4.	0111	ü		11x1	Généré en combinant 5. et 7.
5.	1101	ü		111x	Généré en combinant 6. et 7.
6.	1110	ü
7.	1111	ü

5.             Répéter l’étape (4) autant de fois que nécessaire

1.	01x1	ü		x1x1	Généré en combinant 1. et 5.
2.	x101	ü		x1x1	Généré en combinant 2. et 4.
3.	1x10
4.	x111	ü
5.	11x1	ü
6.	111x

Si le terme est généré deux fois, il ne faut en garder qu’une seule copie :

1.

x1x1

Puisqu’il ne reste qu’un seul terme, il n’est plus possible de répéter l’étape quatre.

6.             Identifier les impliquants premiers

0000			01x1	ü		x1x1
			x101	ü
0101	ü		1x10
1010	ü		x111	ü
0111	ü		11x1	ü
1101	ü		111x
1110	ü
1111	ü

Les impliquants premiers sont : 0000, 1x10, 111x, x1x1.

7.             Identifier les impliquants premiers essentiels

	0000	0101	1010	0111	1101	1110	1111
0000	(*)
1x10			(*)			*
111x						*	*
x1x1		(*)		(*)	(*)		*

Les impliquants essentiels sont : 0000, 1x10, x1x1

8.             Vérifier si la fonction est entièrement exprimée par ses impliquants essentiels

	0000	0101	1010	0111	1101	1110	1111
0000	(*)
1x10			(*)			*
x1x1		(*)		(*)	(*)		*

Sur chaque colonne il y a au moins une étoile. Nous pouvons donc nous arrêter là. On trouve :

f (A,B,C,D) = + AC + CD

4.2.2 Choix des impliquants premiers

Dans la section précédente, il n’a jamais été utile d’appliquer l’étape (9) de l’algorithme. Cette étape peut parfois être simple à effectuer si la solution est évidente. Considérons par exemple le cas d’une fonction pour laquelle l’application de la technique de Quine-McCluskey mène au résultat suivant :

	0000	0001	0010	0101	0110	0111	1000	1001	1010	1110
0x01		*		*
01x1				*		*
011x					*	*
x00x	*	*					*	(*)
x0x0	*		*				*		*
xx10			*		*				*	(*)

Comme on peut s’en rendre compte, les impliquants essentiels sont : x00x, xx10.Si on reproduit cette table avec les impliquants essentiels uniquement, nous obtenons :

	0000	0001	0010	0101	0110	0111	1000	1001	1010	1110
x00x	*	*					*	(*)
xx10			*		*				*	(*)

Les minterms 0101, 0111 ne sont pas couverts par les impliquants essentiels. Il nous faut donc trouver les impliquants premiers permettant de recouvrer ces minterms tout en minimisant la fonction. On reproduit pour ce faire la table avec les impliquants premiers restants et les minterms correspondant :

Comme on peut le voir, le choix est simple : x0x0 est automatiquement éliminé car il ne couvre pas les minterms manquants. Le meilleur choix est 01x1 car il a l’avantage de couvrir les deux minterms en même temps, ce qui n’est pas le cas des deux autres impliquants premiers.

f (A,B,C,D) = x00x + xx10 + 01x1 = + C + BD

Il est suggéré au lecteur de reprendre cet exemple avec une table de Karnaugh.

4.2.3 Méthode de Petrick

Choisir les impliquants premiers de l’étape (9) de la méthode Quine-McCluskey n’est pas toujours aisé. Il est alors préférable d’avoir recours à une méthode systématique. La méthode de Petrick est une méthode systématique utilisant l’algèbre de Boole. Reprenons pour l’illustrer le tableau précédent :

	0000	0001	0010	0101	0110	0111	1000	1001	1010	1110
0x01		*		*
01x1				*		*
011x					*	*
x00x	*	*					*	*
x0x0	*		*				*		*
xx10			*		*				*	*

Chaque impliquant premier doit être associé à une variable booléenne. Le tableau suivant présente cette correspondance :

0x01	01x1	011x	x00x	x0x0	xx10
x0	x1	x2	x3	x4	x5

Une fois cette association faite, on écrit une équation algébrique représentant le tableau précédent. Dans notre exemple, cette équation est :

P = (x₃+x₄)(x₀+x₃)(x₄+x₅)(x₀+x₁)(x₂+x₅)(x₁+x₂)(x₃+x₄)(x₃)(x₄+x₅)(x₅)

Cette équation est sous forme de produit de somme (expression conjonctive). Celle-ci se déduit directement du tableau obtenu à l’étape (7) de la technique de Quine-McCluskey. Pour ce faire, chaque colonne est traduite en une somme de variables. Les variables de chacune des sommes correspondent à celles associées aux impliquants premiers pour lesquels on trouve une étoile sur la colonne considérée.

Par exemple, la première colonne contient deux étoiles. L’une sur la ligne de l’impliquant premier x00x et l’autre sur celle de x0x0. Les variables associées à ces impliquants premiers sont, respectivement, x₃ et x₄. La somme associée à la première colonne est donc (x₃+x₄). De la même façon, on associe à la seconde colonne la somme (x₀+x₃). Et ainsi de suite.

Une fois l’équation représentant le tableau obtenu à l’étape (7) trouvée, on procède à une première simplification en appliquant le théorème d’absorption de l’algèbre de Boole qui stipule :

(X+Y)(X) = X

Dans le cas de l’équation P trouvée précédemment, on obtient :

P = (x₃+x₄)(x₀+x₃)(x₄+x₅)(x₀+x₁)(x₂+x₅)(x₁+x₂)(x₃+x₄)(x₃)(x₄+x₅)(x₅)

P = (x₀+x₁)(x₁+x₂)(x₃) (x₅)

Une fois cette simplification effectuée, on convertit P en somme de produits.

P = (x₀+x₁)(x₁+x₂)(x₃) (x₅)

P = x₀x₁x₃x₅ + x₁x₃x₅ + x₀x₂x₃x₅ + x₁x₂x₃x₅

À cette étape, on applique la forme disjonctive du théorème d’absorption :

X+XY = X

Nous trouvons :

P = x₀x₁x₃x₅ + x₁x₃x₅ + x₀x₂x₃x₅ + x₁x₂x₃x₅

P = x₁x₃x₅ + x₀x₂x₃x₅

Chaque produit de variables correspond à une combinaison possible des impliquants premiers couvrant l’ensemble des minterms. Il s’agit alors de choisir la combinaison de coût minimal. Dans le cas de notre exemple, il s’agit de la combinaison x₁x₃x₅. En se rapportant aux définitions de ces variables, on trouve :

f (A,B,C,D) = x₁ + x₃ + x₅ = BD + + C

Puisque toutes les combinaisons que l’on puisse trouver incluent les impliquants premiers essentiels, il est possible d’appliquer la méthode de Petrick sans inclure ces derniers. On considère alors simplement les impliquants premiers non essentiels et les minterms non couverts. Dans l’exemple précédent, nous aurions à construire la table suivante :

Afin de déterminer le bon candidat, on applique la méthode de Petrick. On associe à chaque impliquant premier une variable :

P = (x₀+x₁)(x₁+x₂)

P = x₀x₁ + x₀x₂ + x₁ + x₁x₂

P = x₀x₂ + x₁

On choisi la solution la moins coûteuse, dans ce cas x₁ (01x1). Puisqu’il a déjà été déterminé que les impliquants essentiels étaient x00x et xx10, il suffit d’ajouter l’impliquant premier trouvé par la méthode de Petrick. On trouve finalement que :

f (A,B,C,D) = x00x + xx10 + 01x1 = + C + BD

4.2.4 Méthode de Quine-McCluskey et expression conjonctive

Nous allons présenter ici un exemple de problème où l’on aura recours à la méthode Quine-McCluskey où l’expression simplifiée recherchée est sous forme conjonctive. Pour ce faire, nous considérons la table de vérité de la fonction logique F(A,B,C,D) :

A	B	C	D	F
0	0	0	0	-
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	-
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	-
1	1	1	1	-

1) Nous commençons par retranscrire les maxterms de la fonction F sous forme binaire en soulignant les maxterms facultatifs — exemple : 1110 pour ( ++ + D ):

 

F(A,B,C,D) = 0000 + 0001 + 0101+ 0110 + 0111 + 1000 + 1110 + 1111

 

2) Une fois cela fait, nous procédons par la méthode Quine-McCluskey pour simplifier la fonction F(A,B,C,D) et identifier les impliqués premiers de la même façon que nous le faisions pour  trouver les impliquants premiers :

 

√	0000			000x
√	0001			x000
√	1000			0x01			x11x
√	0101			01x1
√	0110		√	011x
√	0111		√	x110
√	1110		√	x111
	1111		√	111x

On trouve alors les impliqués premiers sous forme binaire :

 

 

 

 

3) À cette étape, on identifie les impliqués essentiels de F(A,B,C,D). Il est à noter ici que les colonnes n’incluent pas les maxterms facultatifs.

 

		0001	0101	0111	1000
x1	000x	*
x2	x000				(*)
x3	0x01	*	*
x4	01x1		*	*
x5	x11x			*

Impliqués essentiels :

4) Se pose alors la question de savoir si les impliqués essentiels couvrent l’ensemble des maxterms ? La fonction F n’admet qu’un seul impliqué essentiel. À l’évidence, ce dernier ne couvre que le maxterm 1000 et pas l’ensemble des maxterms de la fonction F. On utilise alors la méthode de Petrick pour identifier les impliqués premiers non essentiels permettant une couverture complète de la fonction. On recherche bien entendu une couverture au moindre coût.

 

P(x₁, x₂, x₃, x₄, x₅) = (x₁ + x₃) (x₃ + x₄) (x₄ + x₅) (x₂)

= (x₃ + x₁x₄) (x₄ + x₅) (x₂)

= x₂x₃x₄ + x₁x₂x₄ + x₂x₃x₅ + x₁x₂x₄x₅

Nous avons le choix entre quatre solutions possibles. Les coûts minimaux (implémentation en NOR) associés aux différentes combinaisons des impliqués premiers sont donnés par :

x₂x₃x₄ = (3+1) + 3(3+1) = 16

x₁x₂x₄ = (3+1) + 3(3+1) = 16

x₂x₃x₅ = (3+1) + 2(3+1) + (2+1) = 15

x₁x₂x₄x₅ = (4+1) + 3(3+1) + (2+1) = 20

On choisit la troisième option de sorte à réduire le coût du circuit final. Nous obtenons par conséquent :

F(A, B, C, D) = (B+C+D)(A+C+)(+)

Relevons qu’il est possible de confirmer ce résultat en utilisant une table de Karnaugh :

4.2.5 Réduction du tableau

Une autre technique consiste à réduire le tableau obtenu à l’étape (7). Afin d’illustrer la méthode, reprenons l’exemple précédent :

	0000	0001	0010	0101	0110	0111	1000	1001	1010	1110
0x01		*		*
01x1				*		*
011x					*	*
x00x	*	*					*	*
x0x0	*		*				*		*
xx10			*		*				*	*

Une notion importante pour effectuer la réduction du tableau est celle de domination :

Ainsi, on acceptera que :

La réduction du tableau consiste à éliminer les lignes et les colonnes selon les critères suivants :

Une colonne peut être éliminée : si elle est identique à une autre colonne ·         si elle domine une autre colonne. Une ligne peut être éliminée : si elle est identique à une autre ligne dont le coût n’est pas plus élevé ·         si elle est dominée par une autre ligne dont le coût n’est pas plus élevé.

Pour mieux comprendre le fonctionnement de la méthode, reprenons le tableau de notre exemple. On s’aperçoit que la colonne du minterm 0010 est identique à celle du minterm  1010. Nous pouvons éliminer l’une des deux :

	0000	0001	0010	0101	0110	0111	1000	1001	1110
0x01		*		*
01x1				*		*
011x					*	*
x00x	*	*					*	*
x0x0	*		*				*
xx10			*		*				*

De la même façon, la colonne de 0000 est identique à celle de 1000. On élimine une des deux :

	0000	0001	0010	0101	0110	0111	1001	1110
0x01		*		*
01x1				*		*
011x					*	*
x00x	*	*					*
x0x0	*		*
xx10			*		*			*

La colonne de 0000 domine celle de 1001. On élimine celle de 0000 :

	0001	0010	0101	0110	0111	1001	1110
0x01	*		*
01x1			*		*
011x				*	*
x00x	*					*
x0x0		*
xx10		*		*			*

 

De la même façon, les colonnes 0001 domine celle de 1001, on peut donc l’éliminer :

	0010	0101	0110	0111	1001	1110
0x01		*
01x1		*		*
011x			*	*
x00x					*
x0x0	*
xx10	*		*			*

Les colonnes 0010 et 0110 dominent celle de 1110. Elles doivent être éliminées :

	0101	0111	1001	1110
0x01	*
01x1	*	*
011x		*
x00x			*
x0x0
xx10				*

On peut maintenant procéder à l’élimination des lignes. On sait qu’une ligne est éliminée si elle est dominée par une autre. Comme on peut le voir, la ligne de l’impliquant premier 01x1 domine celle de 0x01 et de 011x (son coût est également inférieur à la somme des leur). On élimine les deux lignes :

	0101	0111	1001	1110
01x1	*	*
x00x			*
x0x0
xx10				*

Finalement, la ligne de x0x0 est dominée par toutes les autres. Elle doit être éliminée :

	0101	0111	1001	1110
01x1	*	*
x00x			*
xx10				*

 

Le tableau est maintenant complètement réduit. Nous pouvons déduire l’expression de la fonction :

Remarque

f (A,B,C,D) = x00x + xx10 + 01x1 = + C + BD