Méthode Quine-McCluskey

Conception logique numérique

La méthode Quine-McCluskey est également connue sous le nom de méthode tabulaire ou de tabulation.

L'utilisation de K-Map pour la simplification des fonctions booléennes est facile à utiliser, jusqu'à ce que les fonctions booléennes aient deux, trois, quatre, cinq ou même six variables, mais à mesure que le nombre de variables augmente, K-Map n'est pas pratique à utiliser.

La méthode Quine-McCluskey est la solution à utiliser pour les fonctions booléennes avec six variables ou plus.

Cette méthode peut également être utilisée pour la simplification de fonctions booléennes à 2, 3, 4, 5 et 6 variables.

Cette méthode a été développée par W.V. Quine et Edward. J. McCluskey.

La méthode Quine-McCluskey utilise la propriété selon laquelle les minterms adjacents pour une simplification de fonction booléenne donnée peuvent être réduits. Les minterms adjacents peuvent être réduits car ils ne diffèrent que d'un seul littéral.

Par exemple :

A'B'C et A'B'C sont des minterms adjacents car ils diffèrent d'un seul littéral C.

Nous savons que A'B'C = 000 et A'B'C = 001, donc 'C diffère.

Dans la méthode Quine-McCluskey, tous les termes d'une fonction booléenne donnée sont d'abord répertoriés. Les minterms sont ensuite écrits sous leur forme binaire équivalente.

Désormais, ces équivalents binaires de minterms sont classés par ordre croissant de 1, avec une ligne horizontale entre chacun de ces groupes.

Par exemple, supposons que les minterms soient: a'b'c', a'b'c, ab'c, ab'c', abc' et abc.

Leur équivalent binaire est - 000, 001, 101, 100, 110 et 111.

Disposez-les par ordre croissant, avec une ligne horizontale séparant chaque groupe. Ceci est résumé dans le tableau ci-dessous:

Minterms et leur équivalent binaire

Maintenant, lorsque ce regroupement est effectué, chaque nombre binaire est comparé à chaque nombre binaire du groupe immédiatement supérieur, et s'ils diffèrent uniquement par la position des bits, une coche est placée comme indiqué dans le tableau ci-dessous:

La représentation binaire est affichée dans la deuxième colonne avec « - » placé à une position différente.

Le processus présenté dans le tableau est répété jusqu'à ce qu'aucune autre combinaison de termes ne soit possible. Ceci est illustré dans le tableau ci-dessous:

Les termes obtenus à partir du tableau sont : -0- et 1—.

Les deux sont des impliquants principaux. Ces impliquants premiers sont respectivement égaux à b' et a.

Additionnez ces nombres premiers impliqués pour obtenir une fonction booléenne simplifiée = a + b'

Les étapes et la procédure ci-dessus pour la simplification de la fonction booléenne à l'aide de la méthode McCluskey sont résumées ci-dessous.

Étape 1 : Répertoriez tous les termes pour une fonction booléenne donnée sous forme binaire.

Étape 2 : Organisez ces minterms en groupes, avec un nombre croissant de 1, c'est-à-dire commencez avec le groupe avec le moins de 1, puis continuez à regrouper les minterms par ordre croissant de 1, avec une ligne horizontale séparant chaque groupe.

Étape 3 : Comparez chaque nombre binaire avec tous les autres nombres binaires du groupe immédiatement supérieur et s'ils ne diffèrent que par une position d'un bit, cochez (-) devant chaque terme qui a été combiné avec au moins un autre terme du groupe supérieur (chaque terme peut se combiner avec plusieurs termes, mais un seul - est requis).

Notez le terme combiné dans la colonne suivante avec - à la position qui diffère.

Étape 4 : Répétez le processus décrit à l'étape 3 pour générer les colonnes 3,4,... jusqu'à ce qu'aucune autre combinaison ne soit possible.

Les termes qui ne sont pas contrôlés dans tout ce processus sont appelés Implicants premiers car ils ne sont couverts par aucun autre terme comportant moins de littéraux.

Étape 5 : Répertoriez tous les impliquants principaux.

Étape 6 : Écrivez l’expression booléenne simplifiée.