Méthode tabulaire Quine-McCluskey
Dans le chapitre précédent, nous avons discuté de la méthode K-map, qui est une méthode pratique pour minimiser les fonctions booléennes jusqu'à 5 variables. Mais, il est difficile de simplifier les fonctions booléennes ayant plus de 5 variables en utilisant cette méthode.
La méthode tabulaire Quine-McClukey est une méthode tabulaire basée sur le concept d'implicants premiers. Nous savons queprime implicant est un terme produit (ou somme), qui ne peut pas être réduit davantage en le combinant avec tout autre terme produit (ou somme) de la fonction booléenne donnée.
Cette méthode tabulaire est utile pour obtenir les principaux implicants en utilisant à plusieurs reprises l'identité booléenne suivante.
xy + xy '= x (y + y') = x.1 = x
Procédure de la méthode tabulaire Quine-McCluskey
Suivez ces étapes pour simplifier les fonctions booléennes à l'aide de la méthode tabulaire Quine-McClukey.
Step 1 - Organiser les termes minimum donnés dans un ascending orderet faites les groupes en fonction du nombre de ceux présents dans leurs représentations binaires. Alors, il y auraat most ‘n+1’ groups s'il y a 'n' variables booléennes dans une fonction booléenne ou 'n' bits dans l'équivalent binaire de termes min.
Step 2 - Comparez les termes minimum présents dans successive groups. S'il y a un changement dans la position d'un bit seulement, prenez la paire de ces deux termes min. Placez ce symbole '_' dans la position de bit différée et conservez les bits restants tels quels.
Step 3 - Répétez l'étape 2 avec les termes nouvellement formés jusqu'à ce que nous ayons tous prime implicants.
Step 4 - Formuler le prime implicant table. Il se compose d'un ensemble de lignes et de colonnes. Les implicants Prime peuvent être placés en rangées et les termes minimum peuvent être placés en colonnes. Placez '1' dans les cellules correspondant aux termes min qui sont couverts dans chaque implicant premier.
Step 5- Trouvez les principaux implicants essentiels en observant chaque colonne. Si le terme minimum n'est couvert que par un seul implicant premier, alors il estessential prime implicant. Ces implicants principaux essentiels feront partie de la fonction booléenne simplifiée.
Step 6- Réduire la table des implicants premiers en supprimant la ligne de chaque implicant premier essentiel et les colonnes correspondant aux termes min qui sont couverts dans cet implicant premier essentiel. Répétez l'étape 5 pour la table d'implicants principaux réduits. Arrêtez ce processus lorsque tous les termes minimum d'une fonction booléenne donnée sont terminés.
Exemple
Laissez-nous simplify la fonction booléenne suivante, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ en utilisant Quine-McClukey méthode tabulaire.
La fonction booléenne donnée est dans sum of min termsforme. Il a 4 variables W, X, Y & Z. Les termes minimum donnés sont 2, 6, 8, 9, 10, 11, 14 et 15. L'ordre croissant de ces termes minimum basé sur le nombre de termes présents dans leur l'équivalent binaire est 2, 8, 6, 9, 10, 11, 14 et 15. Le tableau suivant montre cesmin terms and their equivalent binary représentations.
| Nom de groupe | Termes minimum | W | X | Oui | Z |
|---|---|---|---|---|---|
| GA1 | 2 | 0 | 0 | 1 | 0 |
| 8 | 1 | 0 | 0 | 0 | |
| GA2 | 6 | 0 | 1 | 1 | 0 |
| 9 | 1 | 0 | 0 | 1 | |
| dix | 1 | 0 | 1 | 0 | |
| 11 | 1 | 0 | 1 | 1 | |
| 14 | 1 | 1 | 1 | 0 | |
| GA4 | 15 | 1 | 1 | 1 | 1 |
Les termes minimum donnés sont classés en 4 groupes en fonction du nombre de termes présents dans leurs équivalents binaires. Le tableau suivant montre lesmerging of min terms des groupes adjacents.
| Nom de groupe | Termes minimum | W | X | Oui | Z |
|---|---|---|---|---|---|
| GB1 | 2,6 | 0 | - | 1 | 0 |
| 2,10 | - | 0 | 1 | 0 | |
| 8,9 | 1 | 0 | 0 | - | |
| 8,10 | 1 | 0 | - | 0 | |
| GB2 | 6,14 | - | 1 | 1 | 0 |
| 9,11 | 1 | 0 | - | 1 | |
| 10,11 | 1 | 0 | 1 | - | |
| 10,14 | 1 | - | 1 | 0 | |
| 11,15 | 1 | - | 1 | 1 | |
| 14,15 | 1 | 1 | 1 | - |
Les termes min, qui ne diffèrent que par une position d'un bit des groupes adjacents, sont fusionnés. Ce bit différent est représenté par ce symbole, «-». Dans ce cas, il y a trois groupes et chaque groupe contient des combinaisons de deux termes minimum. Le tableau suivant montre lesmerging of min term pairs des groupes adjacents.
| Nom de groupe | Termes minimum | W | X | Oui | Z |
|---|---|---|---|---|---|
| GB1 | 2,6,10,14 | - | - | 1 | 0 |
| 2,10,6,14 | - | - | 1 | 0 | |
| 8,9,10,11 | 1 | 0 | - | - | |
| 8,10,9,11 | 1 | 0 | - | - | |
| GB2 | 10,11,14,15 | 1 | - | 1 | - |
| 10,14,11,15 | 1 | - | 1 | - |
Les groupes successifs de paires de termes minimum, qui ne diffèrent que par une position d'un bit, sont fusionnés. Ce bit différent est représenté par ce symbole, «-». Dans ce cas, il y a deux groupes et chaque groupe contient des combinaisons de quatre termes min. Ici, ces combinaisons de termes de 4 min sont disponibles sur deux lignes. Ainsi, nous pouvons supprimer les lignes répétées. Le tableau réduit après suppression des lignes redondantes est illustré ci-dessous.
| Nom de groupe | Termes minimum | W | X | Oui | Z |
|---|---|---|---|---|---|
| GC1 | 2,6,10,14 | - | - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - | - | |
| GC2 | 10,11,14,15 | 1 | - | 1 | - |
Une fusion supplémentaire des combinaisons de termes minimaux de groupes adjacents n'est pas possible, car ils sont différés sur plus d'un bit. Il y a trois lignes dans le tableau ci-dessus. Ainsi, chaque ligne donnera un implicant principal. Par conséquent, laprime implicants sont YZ ', WX' et WY.
le prime implicant table est illustré ci-dessous.
| Conditions minimales / Implicants Prime | 2 | 6 | 8 | 9 | dix | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| YZ’ | 1 | 1 | 1 | 1 | ||||
| WX’ | 1 | 1 | 1 | 1 | ||||
| WY | 1 | 1 | 1 | 1 |
Les principaux implicants sont placés en ligne et les termes minimum sont placés en colonne. Les 1 sont placés dans les cellules communes des premières lignes d'implication et des colonnes de terme minimum correspondantes.
Les termes min 2 et 6 ne sont couverts que par un seul implicant premier YZ’. Donc, c'est unessential prime implicant. Cela fera partie de la fonction booléenne simplifiée. Maintenant, supprimez cette ligne implicante principale et les colonnes de terme minimum correspondantes. Le tableau d'implants primaires réduits est présenté ci-dessous.
| Conditions minimales / Implicants Prime | 8 | 9 | 11 | 15 |
|---|---|---|---|---|
| WX’ | 1 | 1 | 1 | |
| WY | 1 | 1 |
Les termes min 8 et 9 ne sont couverts que par un seul implicant premier WX’. Donc, c'est unessential prime implicant. Cela fera partie de la fonction booléenne simplifiée. Maintenant, supprimez cette ligne implicante principale et les colonnes de terme minimum correspondantes. Le tableau d'implants primaires réduits est présenté ci-dessous.
| Conditions minimales / Implicants Prime | 15 |
|---|---|
| WY | 1 |
Le terme minimum 15 n'est couvert que par un seul implicant principal WY. Donc, c'est unessential prime implicant. Cela fera partie de la fonction booléenne simplifiée.
Dans cet exemple de problème, nous avons trois implicants principaux et tous les trois sont essentiels. Par conséquent, lasimplified Boolean function est
f(W,X,Y,Z) = YZ’ + WX’ + WY.