Apprendre › Chapitre 5
Méthode de Quine-McCluskey pas à pas
7 min de lecture · Équipe bitGateLab
Le tableau de Karnaugh est rapide pour quatre variables, mais il repose sur votre coup d'œil et cesse d'être pratique à partir de cinq. La méthode de Quine-McCluskey fait le même travail avec des tables et des règles mécaniques : elle ne demande aucune intuition, trouve toujours tous les impliquants premiers et sert de base aux programmes qui simplifient les fonctions logiques. Vous allez comprendre ici ses deux phases, apprendre à repérer les impliquants premiers essentiels et résoudre un exemple complet à quatre variables.
Vocabulaire : impliquants et impliquants premiers
- Un impliquant de F est un terme produit qui, lorsqu'il vaut 1, garantit que F vaut 1. Chaque minterme de F est un impliquant, tout comme n'importe quel groupe valide d'un tableau de Karnaugh.
- Un impliquant premier est un impliquant que l'on ne peut plus agrandir ; si vous lui retirez une variable, il couvre une ligne où F vaut 0. Il équivaut à un groupe maximal du tableau.
- Un impliquant premier essentiel est un impliquant premier qui couvre au moins un minterme qu'aucun autre impliquant premier ne couvre. Il figure obligatoirement dans toute solution minimale.
La méthode comporte deux phases : elle trouve d'abord tous les impliquants premiers en combinant des termes ; elle choisit ensuite le plus petit ensemble d'impliquants premiers qui couvre tous les mintermes.
Phase 1 : combiner les termes
Chaque terme s'écrit en binaire, et la position d'une variable éliminée est marquée par un tiret. Par exemple, avec les variables A, B, C, D, le terme 0-11 signifie ACD (B a été éliminée).
- Classez les mintermes selon le nombre de uns que contient leur code binaire.
- Comparez chaque terme d'un groupe avec chaque terme du groupe suivant. S'ils ne diffèrent que par un seul bit, combinez-les en plaçant un tiret à cette position, et marquez les deux termes d'origine comme utilisés.
- Recommencez avec la nouvelle liste. On ne combine que des termes dont les tirets occupent les mêmes positions.
- Lorsqu'il n'y a plus rien à combiner, les termes qui n'ont jamais été marqués sont les impliquants premiers.
Phase 2 : table des impliquants premiers
On dresse une table comportant une ligne par impliquant premier et une colonne par minterme de la fonction (les cas indifférents n'ont pas de colonne). On y coche les mintermes que couvre chaque impliquant premier. Ensuite :
- Cherchez les colonnes qui n'ont qu'une seule coche. L'impliquant premier de cette ligne est essentiel : sélectionnez-le et rayez toutes les colonnes qu'il couvre.
- Pour les colonnes restantes, choisissez le plus petit nombre d'impliquants premiers qui les couvre. Si deux impliquants couvrent la même chose, l'un ou l'autre convient ; préférez celui qui a le moins de littéraux.
Exemple complet. Simplifiez F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15).
Étape 1. Classer par nombre de uns.
| Uns | Mintermes |
|---|---|
| 0 | 0 (0000) |
| 1 | 2 (0010), 8 (1000) |
| 2 | 3 (0011), 5 (0101), 10 (1010) |
| 3 | 7 (0111), 11 (1011), 13 (1101) |
| 4 | 15 (1111) |
Étape 2. Première combinaison (paires). On compare les groupes voisins. Le 8 ne se combine ni avec le 3 ni avec le 5, car ils diffèrent par plus d'un bit.
| Groupes | Paires formées |
|---|---|
| 0 et 1 | (0,2) 00-0 ; (0,8) -000 |
| 1 et 2 | (2,3) 001- ; (2,10) -010 ; (8,10) 10-0 |
| 2 et 3 | (3,7) 0-11 ; (3,11) -011 ; (5,7) 01-1 ; (5,13) -101 ; (10,11) 101- |
| 3 et 4 | (7,15) -111 ; (11,15) 1-11 ; (13,15) 11-1 |
Les dix mintermes ont tous été marqués comme utilisés ; il y a 13 paires.
Étape 3. Deuxième combinaison (quadruplets). On combine les paires dont le tiret occupe la même position et qui diffèrent par un bit :
- (0,2) avec (8,10), ou bien (0,8) avec (2,10) : -0-0, couvre 0, 2, 8, 10.
- (2,3) avec (10,11), ou (2,10) avec (3,11) : -01-, couvre 2, 3, 10, 11.
- (3,7) avec (11,15), ou (3,11) avec (7,15) : --11, couvre 3, 7, 11, 15.
- (5,7) avec (13,15), ou (5,13) avec (7,15) : -1-1, couvre 5, 7, 13, 15.
Les 13 paires ont toutes été utilisées dans un quadruplet. Les quatre quadruplets ne se combinent plus entre eux (aucun n'a ses tirets aux mêmes positions qu'un autre tout en n'en différant que par un seul bit). Les impliquants premiers sont donc :
- P1 = -0-0 = BD
- P2 = -01- = BC
- P3 = --11 = CD
- P4 = -1-1 = BD
Étape 4. Table de couverture.
| Impliquant | 0 | 2 | 3 | 5 | 7 | 8 | 10 | 11 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|
| P1 BD | ✔ | ✔ | ✔ | ✔ | ||||||
| P2 BC | ✔ | ✔ | ✔ | ✔ | ||||||
| P3 CD | ✔ | ✔ | ✔ | ✔ | ||||||
| P4 BD | ✔ | ✔ | ✔ | ✔ |
Étape 5. Essentiels. Les colonnes 0 et 8 n'ont de coche que sur P1, donc P1 est essentiel. Les colonnes 5 et 13 n'ont de coche que sur P4, donc P4 est lui aussi essentiel. À eux deux, ils couvrent 0, 2, 5, 7, 8, 10, 13 et 15.
Étape 6. Couvrir le reste. Il manque les mintermes 3 et 11. P2 couvre les deux, et P3 également. L'un ou l'autre complète la solution avec le même nombre de littéraux.
Résultat : F = BD + BD + BC, ou bien F = BD + BD + CD. Les deux solutions ont trois termes et six littéraux.
Si vous représentez cette fonction dans un tableau de Karnaugh, P1 correspond aux quatre coins, P4 au bloc central, P2 aux colonnes 11 et 10 des lignes 00 et 10 (réunies par le bord) et P3 à la colonne 11 tout entière. La méthode tabulaire aboutit au même résultat sans qu'il soit nécessaire de voir le tableau.
Cas indifférents et tables cycliques
Les X sont inclus dans la phase 1 comme s'il s'agissait de uns, car ils peuvent aider à former des impliquants plus grands. Dans la phase 2, on les omet : ils n'ont pas de colonne, puisqu'il n'est pas obligatoire de les couvrir. Un impliquant premier formé uniquement de X n'est jamais nécessaire.
Il arrive qu'après avoir choisi les essentiels, ou même dès le départ, chaque colonne ait au moins deux coches et qu'il n'y ait aucune façon évidente de trancher. Cette situation s'appelle une table cyclique. On la résout par essais : vous choisissez un impliquant premier, vous retirez ce qu'il couvre et vous recommencez, en comparant les solutions obtenues. Pour les grandes tables, il existe une procédure algébrique (la méthode de Petrick) qui énumère toutes les couvertures possibles.
Erreurs fréquentes
- Combiner des termes dont les tirets occupent des positions différentes, comme 0-01 avec 00-1. Ce n'est pas valide, même s'ils semblent ne différer que par un bit.
- Oublier de marquer comme utilisés les deux termes de chaque combinaison, puis compter comme impliquant premier un terme qui ne l'est pas.
- Prévoir des colonnes pour les cas indifférents dans la table de couverture, ce qui oblige à les couvrir sans nécessité.
- Choisir des impliquants non essentiels avant les essentiels. Retenez d'abord les essentiels ; décidez ensuite du reste.
- Mal écrire le terme à partir du code : dans -0-1, B est complémentée (elle vaut 0), D ne l'est pas (elle vaut 1), et A et C disparaissent.
Essayez dans le simulateur
Le simulateur simplifie les fonctions avec ce type de procédure ; vous pouvez donc vous en servir pour contrôler chaque phase de votre travail à la main.
- Créez une table de vérité à quatre variables et mettez à 1 les mintermes de l'exemple.
- Effectuez les phases 1 et 2 sur papier et écrivez votre résultat.
- Observez l'expression minimale que donne l'outil ainsi que son tableau de Karnaugh ; repérez quel groupe correspond à chaque impliquant premier.
- Convertissez les deux solutions possibles en circuit sur le même schéma et changez les entrées pour confirmer qu'elles donnent toujours la même sortie.
Exercices
- Trouvez les impliquants premiers et l'expression minimale de F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15).
Réponse
Impliquants premiers : -00- (BC), -0-1 (BD) et --11 (CD). La colonne 0 n'est couverte que par BC, et la 7 uniquement par CD : tous deux sont essentiels et, ensemble, ils couvrent tout. F = BC + CD. L'impliquant BD est superflu.
- Résolvez F(A, B, C) = Σm(0, 1, 2, 5, 6, 7). Y a-t-il des impliquants premiers essentiels ?
Réponse
Les paires sont 00-, 0-0, -01, -10, 1-1 et 11-, et aucune ne se combine en quadruplet : il y a six impliquants premiers. Chaque minterme est couvert par exactement deux d'entre eux ; il n'y a donc pas d'essentiels (table cyclique). Deux solutions minimales : AB + BC + AC, ou AC + BC + AB.
- Simplifiez F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15).
Réponse
En incluant les X dans la phase 1, on obtient quatre impliquants premiers : -0-1 (BD), -01- (BC), --11 (CD) et 1--1 (AD). Dans la table, sans colonnes pour 1, 10 et 15 : le 2 n'est couvert que par BC, le 7 uniquement par CD et le 13 uniquement par AD. Les trois sont essentiels et couvrent aussi 3, 9 et 11. F = BC + CD + AD.
- Pourquoi ne compare-t-on pas le groupe à un seul un avec le groupe à trois uns dans la phase 1 ?
Réponse
Parce que deux codes comportant respectivement un et trois uns diffèrent par au moins deux bits, alors qu'ils doivent différer par exactement un bit pour se combiner.