ELE1300Quine-McCluskey

2

Kesséssa?Quine-McCluskey est une méthode (un algorithme) de simplification de fonctions logiques

Une table de Karnaugh permet de simplifier une fonction de 2 à 6 variables maximum. Au-delà, Quine-McCluskey prend le relais (utile jusqu’à10 variables)

L’algorithme de Q-MC est surtout destiné à une utilisation logicielle. Pour ce cours, IL EST IMPORTANT DE SAVOIR L’EXÉCUTER

3

Étapes de l’algorithme1. Exprimer la fonction sous forme canonique disjonctive

2. Exprimer les minterms sous forme binaire

3. Grouper les termes selon leurs 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. Vérifier si la fonction est entièrement exprimée par sesimpliquants essentiels, auquel cas arrêter

9. Si on n’a pas fini à l’étape (8), choisir les impliquants premiers appropriés

4

Exemple simple:

On va illustrer la technique sur un exemple à trois variables (que l’on pourrait aussi bien résoudre au moyen d’une table de Karnaugh)

F(A,B,C) = AB+AB+AC+BC

5

Exécution de l’algorithme Q-MC1. Exprimer la fonction sous forme canonique disjonctive

F(A,B,C) = AB+AB+AC+BC= ABC+ABC+ABC+ABC+ABC+ABC

2. Exprimer la fonction sous forme binaire

F(A,B,C) = 001+010+011+100+101+111

3. Grouper les termes selon leur poids (somme des bit de 1)Poids 1 Poids 2 Poids 3

001010100

011101

111

6

Exécution de l’algorithme Q-MC (…)

4. Unir les termes deux à deux

001010100011101

111

0x1x0101x10xx111x1

7

Exécution de l’algorithme Q-MC (…)

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

001010100011101

111

0x1x0101x10xx111x1

xx1xx1

xx1

8

Exécution de l’algorithme Q-MC (…)

6. Identifier les impliquants premiers

Les impliquants premiers (pas de crochet):01x, 10x, xx1

Ce qui donne, respectivement:AB, AB, C

001010100011101

111

0x1x0101x10xx111x1

xx1

9

Exécution de l’algorithme Q-MC (…)

7. Identifier les impliquants premiers essentiels

On cherche les colonnes où se retrouve un seul signe, Les lignescorrespondantes sont des impliquants premier.

Ici, tous les impliquants premiers sont essentiels

01x10xxx1

001 010 100 011 101 111

* ** *

* * * *

1 2 3 64 5

10

Exécution de l’algorithme Q-MC (…)

8. Vérifier si la fonction est entièrement exprimée par les impliquants premiers essentiels. Auquel cas arrêter.

NOTE : Comme tous les impliquants de la fonction F sont iciessentiels, la condition est forcément remplie.

01x10xxx1

001 010 100 011 101 111

* ** *

* * * *

11

Exécution de l’algorithme Q-MC (…)

Conclusion:

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

Ce que nous aurions pu trouver avec une table de Karnaugh:

0 1

4 5

1

0100

03 2

7 6

1011

1

0

1

1

1

1

0

1

12

Un exemple plus costaudÉtape 1 : Exprimer la fonction sous forme canonique disjonctive.

0 0 0 0 00 0 0 1 00 0 1 0 10 0 1 1 00 1 0 0 10 1 0 1 10 1 1 0 10 1 1 1 11 0 0 0 01 0 0 1 11 0 1 0 01 0 1 1 01 1 0 0 01 1 0 1 11 1 1 0 01 1 1 1 0

A B C D S

S ABC D ABC D ABCD

ABC D ABCD ABCD ABCD

= + +

+ + + +

13

Un exemple plus costaud (…)Étape 2 : Exprimer les « mintermes » sous forme binaire.

0010 0100 0101 0110 0111 1001 1101S ABCD ABCD ABCD ABCD ABCD ABCD ABCD= + + + + + +

Étape 3 : Grouper les termes selon leurs poids (nombre de 1).

0010

0100

0101

0110

1001

0111

1101

poids 1

poids 2

poids 3

14

Un exemple plus costaud (…)Étape 4 :

Comparer chaque terme d’un groupe avec chacun des termes du groupe suivant. Si deux termes diffèrent par un seul bit, un nouveau terme est produit avec un « × » à la position où il y a différence. Marquer les deux termes ayant engendréun nouveau terme.

0010

0100

0101

0110

1001

0111

1101

0×10 0010

0100

0101

0110

1001

0111

1101

0×10

010×

15

Un exemple plus costaud (…)

0010

0100

0101

0110

1001

0111

1101

0×10

010×

01×0

0010

0100

0101

0110

1001

0111

1101

0×10

010×

01×0

01×1

16

Un exemple plus costaud (…)

0010

0100

0101

0110

1001

0111

1101

0×10

010×

01×0

01×1

0010

0100

0101

0110

1001

0111

1101

0×10

010×

01×0

01×1

×101 ×101

011×

17

Un exemple plus costaud (…)

0010

0100

0101

0110

1001

0111

1101

0×10

010×

01×0

01×1

×101

011×

1×01

18

Un exemple plus costaud (…)Étape 5 : Répéter l’étape 4 avec les nouveaux termes jusqu’à ce qu’il n’y ait plus

d’association possible.

0010

0100

0101

0110

1001

0111

1101

0×10

010×

01×0

01×1

×101

011×

1×01

01×× 0010

0100

0101

0110

1001

0111

1101

0×10

010×

01×0

01×1

×101

011×

1×01

01××

19

Un exemple plus costaud (…)Étape 6 : Identifiez les implicants premiers ; ce sont les termes n’ayant pas été

associés à d’autres.

0010

0100

0101

0110

1001

0111

1101

0×10

010×

01×0

01×1

×101

011×

1×01

01××* *

*

** Implicant premier

20

Un exemple plus costaud (…)Étape 7 : Associer chaque implicant premier avec les termes de la fonction qu’ils

peuvent représenter et identifier les implicants premiers essentiels.

0×10

×101

1×01

01××

0010 0100 0101 0110 0111 1001 1101

*

*

*

*

***

*

*

*

* Implicant premier essentiel

21

Un exemple plus costaud (…)Étape 8 : Vérifier si les implicants premiers essentiels sont suffisants pour représenter tous les termes de la fonction. Si c’est le cas, la simplification est terminée.

0×10

×101

1×01

01××

0010 0100 0101 0110 0111 1001 1101

*

*

*

*

***

*

*

*

AC D ACD AB+ +0×10 1×01 01××

S =

22

Un exemple avec étape 9Autre exemple :

0 0 0 0 10 0 0 1 10 0 1 0 10 0 1 1 00 1 0 0 00 1 0 1 10 1 1 0 10 1 1 1 11 0 0 0 11 0 0 1 11 0 1 0 11 0 1 1 01 1 0 0 01 1 0 1 01 1 1 0 11 1 1 1 0

A B C D S

S ABC D ABCD ABC D ABCD

ABC D ABCD ABC D

ABCD ABC D ABC D

= + + +

+ + +

+ + +

23

Un exemple avec étape 9 (…)0000

0001

000× ×00×*

* Implicant premier

0010

1000

0101

0110

1001

1010

0111

1110

00×0

×000

0×01

×001

0×10

×010

100×

10×0

01×1

011×

×110

*

×0×0

××10

1×10

*

**

*

24

Un exemple avec étape 9 (…)

0×01

01×1

011×

×00×

0000 0001 0010 0101 0110 0111 1000 1001 1010 1110

×0×0

××10 *

* *

* *

* *

* * *

* * * *

* * *

*

Meilleur choix

S ABD BC C D= + +

25

Une méthode systématiquePour réaliser l’étape (7, 8 et) 9 : Méthode de Petrick

0×01 01×1 011× ×00× ×0×0 ××10

Les implicants premiers :

0x 1x 2x 3x 4x 5x

( ) ( ) ( ) ( ) ( ) ( )( )( )( )( )3 4 0 3 4 5 0 1 2 5 1 2 3 4 3 4 5 5P x x x x x x x x x x x x x x x x x x= + + + + + + + +

( )( )( )( )0 1 1 2 3 5 0 1 3 5 0 2 3 5 1 3 5 1 2 3 5x x x x x x x x x x x x x x x x x x x x x= + + = + + +

S ABD BC C D= + +

1x 3x 5x01×1 ×00× ××10

Expression logique de la réalisation de la fonction :

26

Un exemple parfait (…)

0 0 0 10 0 1 10 1 0 10 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1

A B C S

Autre exemple :

S ABC ABC ABC

ABC ABC ABC

= + +

+ + +

27

Un exemple parfait (…)

000

001

00×

010

101

110

111

0×0

×01

×10

1×1

11×

*

* Implicant premier

*****

28

Un exemple parfait (…)

00×

0×0

×01

×10

000 111

1×1

11×

* *

* *

*

110101010001

*

**

* *

*

*

29

Un exemple parfait (…)Méthode de Petrick.

00× 0×0 ×01 ×10 1×1 11×

Les implicants premiers :

0x 1x 2x 3x 4x 5x

( )( )( )( )( )( )0 1 0 2 1 3 2 4 3 5 4 5P x x x x x x x x x x x x= + + + + + +

Expression logique de la réalisation de la fonction :

0 1 3 4 0 2 3 4 0 3 4 1 2 3 4 0 1 4 5 0 2 3 5 0 3 4 5 1 2 5x 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= + + + + + + +

S AB BC AC= + + S AC BC AB= + +

30

Moment de détente littéraireAlain Mabanckou, jeune auteur (~40 ans) d’origine congolaise a reçu aujourd’hui même

le prix Renaudotpour son roman

Mémoire de porc-épic publié aux éditions du

Seuil.Un grand bravo !

31

Revenons à nos moutons

Mouais Monsieur, la méthode de Petrick c’est cool, mais peut-on faire plus vite?

La question ne se pose pas si la réponse était non ☺

Il existe une méthode assez rapide mais relativement difficile à comprendre. On va y aller par étapes, alors un peu de silence (M.-A. et C. svp…),

de la concentration.

Prêts? On y va…

32

Réduction du tableauPour réaliser l’étape (7, 8 et) 9 : comme la Méthode de Petrick

« dominante » : Une colonne (ligne) est domine une autre lorsqu’elle l’inclut.

Une colonne peut être éliminée :

si elle est identique à une autre colonneou

si elle est 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éou

si elle est dominée par une autre ligne dont le coût* n’est pas plus élevé.

* coût : contribution à la complexité du circuit (nombre de portes, nombre d’entrées).

33

Réduction du tableau (…)

0×01

01×1

011×

×00×

0000 0001 0010 0101 0110 0111 1000 1001 1010 1110

×0×0

××10 *

* *

* *

* *

* * *

* * * *

* * *

*

2

1

4

4

3

34

Exemple avec des cas facultatifs :

0001 0010 0100 0111P ABCD ABC D ABC D ABCD= + + +

0 0 0 0 00 0 0 1 10 0 1 0 10 0 1 1 00 1 0 0 10 1 0 1 00 1 1 0 00 1 1 1 11 0 0 0 11 0 0 1 01 0 1 0

1 1 1 1

A B C D P

à (sans objet)

1000 1010 1011 1100ABC D ABC D ABCD ABC D+ + + +

1101 1110 1111ABCD ABC D ABCD+ + +

À noter :

Ici, les cas facultatifs sont considérés comme des 1

Cas facultatifs

35

0001

0010

×010 1××0* *

* Implicant premier

0100

1000

1010

1100

0111

1011

1101

1110

1111

×100

10×0

1×00

101×

1×10

110×

11×0

×111

1×11

11×1

111×

**

*

1×1×

11××**

Cas facultatifs (…)

36

0001

×010

×100

0001 0010 0100 0111 1000

*

*

×111

1××0

1×1×

11××

*

*

*

À noter :

Ici, les cas facultatifsne sont pas considérés

P ABCD BC D BC D BCD AD= + + + +

Cas facultatifs (…)

37

Prochain cours???

On va découvrir ce que c’est qu’une machine à états finis.On va pouvoir faire des robots et tout plein de machins chouettesOn va réaliser à quel point le numérique c’est fort!!!Mais avant de plonger, on va un peu s’amuser

38

Prochain cours???