AccueilđŸ‡«đŸ‡·Chercher

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

ABCDS
00001
00010
00101
00110
01000
01010
01101
01110
10001
10010
1010x
1011x
1100x
1101x
1110x
1111x

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 0Colonne 1
000000x0
0010x000
10000x10
0110x010
101010x0
11001x00
1011x110
1101101x
11101x10
1111110x
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 0Colonne 1Colonne 2
000000x0x0x0
0010x000xx10
10000x101xx0
0110x0101x1x
101010x011xx
11001x00
1011x110
1101101x
11101x10
1111110x
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 0Colonne 1Colonne 2
000000x0x0x0
0010x000xx10
10000x101xx0
0110x0101x1x
101010x011xx
11001x00
1011x110
1101101x
11101x10
1111110x
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.

x0x0xx101xx01x1x11xx
0000X
0010XX
0110X
1000XX

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

  1. 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)
  2. 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)
  3. 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 )
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.