MĂ©thode de Quine-Mc Cluskey
La méthode de Quine-McCluskey est un algorithme systématique pour minimiser une fonction booléenne quelconque, développé par Willard V. Quine, puis étendu par Edward J. McCluskey[1] - [2] - [3].
Principe de la méthode
L'algorithme se dĂ©roule en deux Ă©tapes. Pour faciliter la mise en Ćuvre de la mĂ©thode, la fonction logique doit ĂȘtre exprimĂ©e soit sous forme tabulaire (table de vĂ©ritĂ©, tableau de Karnaugh), soit sous la forme suivante :
oĂč sont valeurs (exprimĂ©es en binaire ou plus souvent en dĂ©cimal) correspondant aux cas oĂč , avec le nombre , vaut 1 et sont valeurs correspondant aux cas oĂč , avec le nombre est indĂ©terminĂ©. Par exemple, l'expression d'une porte NAND sous cette forme serait : .
La premiĂšre Ă©tape de l'algorithme correspond Ă la recherche de l'ensemble des termes gĂ©nĂ©rateurs. Un terme est gĂ©nĂ©rateur s'il ne peut ĂȘtre combinĂ© avec aucun autre terme pour donner un terme plus simple.
Par exemple, dans le cas de la porte NAND, la fonction vaut 1 lorsque vaut , ou . Le terme n'est pas un terme gĂ©nĂ©rateur car combinĂ© avec , il donne naissance Ă un terme plus simple . En revanche, ne peut ĂȘtre combinĂ© avec un autre terme, c'est donc un terme gĂ©nĂ©rateur. De la mĂȘme maniĂšre est un autre terme gĂ©nĂ©rateur.
Pour trouver les termes générateurs, on utilise les valeurs et car, comme dans un tableau de Karnaugh, les termes indéterminés peuvent conduire à des simplifications.
La deuxiĂšme Ă©tape de l'algorithme correspond Ă l'Ă©limination, parmi les termes gĂ©nĂ©rateurs, des termes redondants. Pour cela, on identifie les termes gĂ©nĂ©rateurs Ă partir desquels chaque peut-ĂȘtre Ă©crit et on Ă©limine ceux qui sont en trop.
Par exemple, dans le cas de la porte NAND, le terme et peuvent ĂȘtre Ă©crit avec le terme gĂ©nĂ©rateur mais celui-ci n'est pas utilisable pour Ă©crire . L'utilisation du second gĂ©nĂ©rateur est indispensable. Il n'y a pas de terme redondant.
Pour cette étape de simplification, on ne cherche à coder que les valeurs . Les valeurs indéterminés nous sont ici inutiles.
Illustration sur un exemple
Table de vérité
Considérons la table de vérité suivante
A | B | C | D | S |
---|---|---|---|---|
0 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | x |
1 | 0 | 1 | 1 | x |
1 | 1 | 0 | 0 | x |
1 | 1 | 0 | 1 | x |
1 | 1 | 1 | 0 | x |
1 | 1 | 1 | 1 | x |
L'exemple n'est pas totalement fortuit. Il s'agit en fait de la table de vérité servant au codage de la barre située en bas à gauche d'un afficheur 7 segments (allumée quand on souhaite afficher 0, 2, 6 ou 8, éteinte quand on a comme code 1, 3, 4, 5, 7 ou 9 et indéterminée pour les codes supérieurs à 9). L'expression de S s'écrit donc
Ătape n°1 : Identification des termes gĂ©nĂ©rateurs
Pour identifier les termes générateurs, on remplit un premier tableau de la maniÚre suivantes : 1°) Dans la premiÚre colonne, on écrit tous les termes portant la fonction à 1 ou à une forme indéterminée. Les termes sont triés en fonction du nombre de 1 qu'ils contiennent.
Colonne 0 |
---|
0000 |
0010 |
1000 |
0110 |
1010 |
1100 |
1011 |
1101 |
1110 |
1111 |
On tente alors de combiner les termes afin d'Ă©liminer ceux qui ne sont pas gĂ©nĂ©rateurs. L'intĂ©rĂȘt de les avoir triĂ©s en fonction du nombre de 1 qu'ils contiennent permet de simplifier cette Ă©tape. Dans la colonne 0, on raye tour Ă tour les termes utilisĂ©s dans une recombinaison et on inscrit dans la colonne 1 du tableau les termes issues de ces recombinaisons.
- 0000 peut ĂȘtre recombinĂ© avec 0010 pour former le terme 00x0.
- 0000 peut ĂȘtre recombinĂ© avec 1000 pour former le terme x000.
- 0010 peut ĂȘtre recombinĂ© avec 1010 pour former le terme x010.
- etc ...
Colonne 0 | Colonne 1 |
---|---|
0000 | 00x0 |
0010 | x000 |
1000 | 0x10 |
0110 | x010 |
1010 | 10x0 |
1100 | 1x00 |
1011 | x110 |
1101 | 101x |
1110 | 1x10 |
1111 | 110x |
11x0 | |
111x | |
11x1 | |
1x11 | |
On réitÚre alors cette opération avec les termes de la Colonne 1 : dans la colonne 0, on raye tour à tour les termes utilisés dans une recombinaison et on inscrit dans la colonne 2 du tableau les termes issues de ces recombinaisons. Ces termes sont composés de 2 x.
- 00x0 peut ĂȘtre recombinĂ© avec 10x0 pour former le terme x0x0.
- x000 peut ĂȘtre recombinĂ© avec x010 pour former le terme x0x0.
- 0x10 peut ĂȘtre recombinĂ© avec 1x10 pour former le terme xx10.
- etc ...
- x110 peut ĂȘtre recombinĂ© avec x010 pour former le terme xx10.
Colonne 0 | Colonne 1 | Colonne 2 |
---|---|---|
0000 | 00x0 | x0x0 |
0010 | x000 | xx10 |
1000 | 0x10 | 1xx0 |
0110 | x010 | 1x1x |
1010 | 10x0 | 11xx |
1100 | 1x00 | |
1011 | x110 | |
1101 | 101x | |
1110 | 1x10 | |
1111 | 110x | |
11x0 | ||
111x | ||
11x1 | ||
1x11 | ||
On réitÚre ce mécanisme jusqu'à ce qu'on ne puisse plus combiner de termes. Dans ce cas, tous les termes de la colonne 2 sont générateurs, mais dans d'autre cas de figure, on pourrait trouver une colonne 3 avec des termes portant 3x.
Colonne 0 | Colonne 1 | Colonne 2 |
---|---|---|
0000 | 00x0 | x0x0 |
0010 | x000 | xx10 |
1000 | 0x10 | 1xx0 |
0110 | x010 | 1x1x |
1010 | 10x0 | 11xx |
1100 | 1x00 | |
1011 | x110 | |
1101 | 101x | |
1110 | 1x10 | |
1111 | 110x | |
11x0 | ||
111x | ||
11x1 | ||
1x11 | ||
On a donc identifié 5 termes générateurs : x0x0, xx10, 1xx0, 1x1x et 11xx.
Ătape n°2 : Suppression des redondances
Pour identifier les termes redondants, on remplit un second tableau de la maniÚre suivante : - en colonne, on retrouve les termes générateurs - en ligne, on retrouve les termes à exprimer (uniquement ceux de l'expression R puisque les cas indéterminés ne sont pas à coder). - dans les cases, on identifie quel terme générateur est utilisé pour écrire le terme à exprimer.
x0x0 | xx10 | 1xx0 | 1x1x | 11xx | |
---|---|---|---|---|---|
0000 | X | ||||
0010 | X | X | |||
0110 | X | ||||
1000 | X | X | |||
Le terme x0x0 est à conserver car il est indispensable pour exprimer 0000. Le terme xx10 est à conserver car il est indispensable pour exprimer 0110. x0x0 et xx10 sont nécessaires. De plus, ils sont suffisants : ils réalisent déjà tous les termes de R.
1xx0 ne réalise rien de nouveau ; 1x1x et 11xx n'expriment que des termes de , ils sont donc également considérés comme redondants.
RĂ©sultat final
Les termes conservés étant et , on obtient :
Références
- Willard Van Orman Quine, « The Problem of Simplifying Truth Functions », The American Mathematical Monthly, vol. 59, no 8,â , p. 521â531 (DOI 10.2307/2308219, JSTOR 2308219)
- Willard Van Orman Quine, « A Way to Simplify Truth Functions », The American Mathematical Monthly, vol. 62, no 9,â , p. 627â631 (DOI 10.2307/2307285, JSTOR 2307285)
- Edward J. McCluskey, Jr., « Minimization of Boolean Functions », Bell System Technical Journal, vol. 35, no 6,â , p. 1417â1444 (DOI 10.1002/j.1538-7305.1956.tb03835.x, lire en ligne, consultĂ© le )