Algorithme de Quine–McCluskey

Méthode de Quine-Mc Cluskey

La méthode de Quine-McCluskey est un algorithme systématique permettant de simplifier une fonction logique quelconque de plusieurs variables

Sommaire

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 suivantes :

f(A0,...,AN − 1) = R(N0,...,Nk − 1) + Φ(M0,...,Mp − 1)

(N0,...,Nk − 1) sont k valeurs (exprimée en binaire ou plus souvent en décimales) correspondant aux k cas où f(A0,...,AN − 1), avec le nombre (AN − 1...A0) = Nk, vaut 1 et (M0,...,Mp − 1) sont p valeurs correspondant aux p cas où f(A0,...,AN − 1), avec le nombre (AN − 1...A0) = Mp est indéterminé. Par exemple, l'expression d'une porte NAND sous cette forme serait : fNAND(a,b) = R(0,1,2).


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 (ab) vaut 00, 01 ou 10. Le terme 00 n'est pas un terme générateur car combiné avec 01, il donne naissance à un terme plus simple 0x. En revanche, 0x ne peut être combiné avec un autre terme, c'est donc un terme générateur. De la même manière x0 est un autre terme générateur.

Pour trouver les termes générateur, on utilise les valeurs (N0,...,Nk − 1) et (M0,...,Mp − 1) car, comme dans un tableau de Karnaugh, les termes indétermines peuvent conduire à des simplification.


La deuxième étape de l'algorithme correspond à l'élimination, parmi les termes générateurs, des termes redondants. Pour celà, on identifie les termes générateurs à partir desquels pour chaque (n0,...,nk − 1) peut-être écrit et on élimine ceux qui sont en trop.

Par exemple, dans le cas de la porte NAND, le terme 00 et 01 peuvent être écrit avec le terme générateur 0x mais celui-ci n'est pas utilisable pour écrire 10. L'utilisation du second générateur x0 est indispensable. Il n'y a pas de terme redondant.

Pour cette étape de simplification, on ne cherche à coder que les les valeurs (N0,...,Nk − 1). 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 à 10). L'expression de S s'écrit donc

S = R(0,2,6,8) + Φ(10,11,12,13,14,15)


Etape 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 ne peut être recombiné avec aucun autre terme de la colonne, c'est donc un terme générateur.
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érateur, 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é 6 termes générateur : x110, x0x0, xx10, 1xx0, 1x1x et 11xx.

Etape n°2 : Suppression des redondances

Pour identifier les termes redondants, on rempli un premier second de la manière suivantes : - 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.

x110 x0x0 xx10 1xx0 1x1x 11xx
0000 X
0010 X X
0110 X X
1000 X

Les termes x110 et 1xx0 sont à conserver car ils sont indispensables pour exprimer respectivement 0110 et 1000. x0x0 permet d'exprimer 0000 et 0010. xx10 n'apporte pas d'information complémentaire car il permet de coder des termes qui peuvent l'être par des générateurs déjà identifiés. Il est donc redondant. 1x1x et 11xx ne servent pas à exprimer des termes de R, ils sont donc également considérés comme redondants (ces termes ne servent en fait à exprimer que des termes de Φ.

Résultat final

S = B \cdot C \cdot \bar D + A \cdot \bar D + \bar B \cdot \bar D

Ce document provient de « M%C3%A9thode de Quine-Mc Cluskey ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Quine–McCluskey de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Méthode de Quine-Mc Cluskey — La méthode de Quine McCluskey (en) est un algorithme systématique permettant de simplifier une fonction logique quelconque de plusieurs variables. Sommaire 1 Principe de la méthode 2 …   Wikipédia en Français

  • Forme normale conjonctive — Article principal : Calcul des propositions. En logique booléenne et en calcul des propositions, une forme normale conjonctive (FNC) est une normalisation d une expression logique qui est une conjonction de clauses, autrement dit une… …   Wikipédia en Français

  • FND — Forme normale disjonctive Article principal : Calcul des propositions. En logique booléenne ou en Calcul des propositions, une forme normale disjonctive (FND) est une normalisation d une expression logique qui est une disjonction de clauses… …   Wikipédia en Français

  • Forme normale disjonctive — Article principal : Calcul des propositions. En logique booléenne ou en Calcul des propositions, une forme normale disjonctive (FND) est une normalisation d une expression logique qui est une disjonction de clauses conjonctives. Elle est… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”