Veuillez patienter pendant le chargement de la page ! Merci !!!

Retour au site Contacter l'auteur

Comparaison avec la méthode de Karnaugh Synthèse Tableaux de Karnaugh

Simplification des fonctions

Bas de page

Créée le, 29/05/02

Mise à jour le, 13/03/03

4. - MÉTHODE DE QUINE-MAC CLUSKEY

Bien que peu employée, nous devons quand même citer une méthode différente de celle des tableaux de Karnaugh pour la simplification des fonctions de plusieurs variables. Il s'agit d'une méthode imaginée par le mathématicien américain W. V. QUINE et remodelée par son compatriote le Docteur Edwards J. Mac CLUSKEY Junior dans une thèse de doctorat qu'il présenta au M. I. T. (Massachusetts Institute of Technology) en juin 1956.

4.1. - DESCRIPTION DE LA MÉTHODE

Pour examiner cette méthode, nous prendrons un exemple à quatre variables. Partons de la table de vérité de la fonction f (a, b, c, d) qui est donnée à la figure 54.

Nous pouvons constater que la fonction f est «vraie» (égale à 1) pour onze combinaisons des variables a, b, c et d.

Donnons comme nom à chacune de ces combinaisons la valeur décimale qui correspond au code binaire formé par les variables a, b, c, d en considérant que a est le bit de poids fort et d le bit de poids faible.

Exemple :

0110 = bc : nous l'appellerons la combinaison 6 puisque 0110 en binaire équivaut à 6 en décimal.

Si nous récapitulons, la fonction f est donc la somme des combinaisons résumées figure 55 :

Cette liste peut être récapitulée de la façon suivante :

A partir de cette liste de combinaisons commence réellement la méthode de QUINE-MAC CLUSKEY.

La première chose à faire est de classer ces combinaisons en un ensemble successifs en fonction du nombre de zéros de la forme binaire de chaque combinaison en commençant par celle qui en compte le plus.

Le premier ensemble est donc formé par la combinaison 0 dont la forme binaire 0000 comporte quatre zéros. Le second ensemble regroupe les combinaisons comportant trois zéros ... jusqu'au cinquième qui est formé de la combinaison 15 dont la forme binaire 1111 ne comporte pas de zéro du tout.

Les cinq ensembles sont représentés figure 56.

La seconde phase de la méthode consiste à comparer les termes de chaque ensemble avec les termes de l'ensemble qui suit immédiatement de façon à éliminer une variable si cela est possible.

La combinaison 0000 de l'ensemble 1 doit donc être comparée aux quatre combinaisons de l'ensemble 2. Puis chacune des quatre combinaisons de cet ensemble 2 sera comparée à chacune des trois combinaisons de l'ensemble 3 et ainsi de suite jusqu'à l'ensemble 5...

Lorsque deux combinaisons ne diffèrent que d'UNE VARIABLE, celles-ci peuvent être associées pour n'en former plus qu'une dans laquelle la variable qui diffère peut être éliminée.

Quand une variable s'élimine dans une telle association, on signale ce fait en remplaçant cette variable par une croix (ou tout autre signe à votre convenance).

Dans l'exemple que nous avons choisi, les combinaisons 0 et 1 peuvent, par exemple, être associées puisque seule la variable d est différente :

Procédons ainsi en comparant chaque terme de chaque ensemble avec chaque terme de l'ensemble suivant et nous obtenons les combinaisons décrites dans la figure 57.

Nous obtenons de nouveaux membres regroupés à présent dans quatre ensembles I, II, III et IV. Recommençons la même opération avec ces nouveaux ensembles. La figure 58 donne les nouvelles combinaisons obtenues.

Dans les principes généraux de la méthode de QUINE-MAC CLUSKEY, il convient de continuer ce processus jusqu'à ce qu'il n'y ait plus de combinaison possible entre un de ces ensembles et le suivant.

Dans l'exemple choisi, nous en sommes arrivés à ce point. De plus, nous constatons dans cette figure que plusieurs combinaisons sont identiques. Nous ne garderons bien sûr que les groupements différents que nous appellerons A, B, C, D, E et F (figure 58).

La fonction f prend alors la forme :

f = A + B + C + D + E + F, Soit :

f = + + + b + a + ab

REMARQUE :

Dans tous les regroupements que nous avons effectués, il aurait pu arriver que certains termes d'un ensemble ne se combinent avec aucun terme de l'ensemble suivant. Ces termes sont alors des termes premiers et il convient de ne pas les oublier dans l'équation finale.

Arrivé à ce stade, il convient de vérifier si l'équation obtenue ne peut pas encore être simplifiée. Pour éliminer les éventuels termes superflus, formons une grille dite «diagramme des termes premiers».

Ce diagramme représenté figure 59 comporte onze colonnes correspondant aux combinaisons initiales 0, 1, 2, 4, 6, 8, 9, 12, 13, 14 et 15. Il comprend d'autre part six lignes horizontales correspondant aux six groupements A, B, C, D, E et F obtenus après les différents processus de simplification.

Sur chaque ligne, marquons d'une croix les combinaisons ayant servies à former le groupement considéré.

Par exemple pour le groupement A qui fait intervenir les combinaisons 0, 1, 8 et 9, nous avons coché sur la ligne A les colonnes 0, 1, 8 et 9. Après avoir fait de même pour les lignes B, C, D, E et F, nous constatons que certaines colonnes (1, 2 et 15) ne comportent qu'une seule croix que nous entourons alors d'un cercle. Ces combinaisons sont situées sur les lignes A, B, et F qui sont appelées «lignes de base».

Nous constatons que d'autre part les combinaisons incluses dans les lignes C, D, E se retrouvent au moins une fois dans les lignes A, B et F. Les lignes C, D et E peuvent donc être supprimées et la fonction f se simplifie donc encore pour devenir :

f = A + B + F

f = + + ab

4.2. - COMPARAISON AVEC LA MÉTHODE DE KARNAUGH

A titre de comparaison, effectuons le même exercice par la méthode des tableaux de KARNAUGH. A l'aide de la table de vérité rappelée figure 60-a, établissons le tableau de KARNAUGH correspondant (figure 60-b).

Les regroupements effectués dans ce tableau (cerclés de rouge dans la figure) donnent immédiatement la solution :

f = 1 + 2 + 3

f = + + ab

On retrouve le même résultat que précédemment.

CONCLUSIONS :

A la lumière de cet exemple, résolu d'une part avec la méthode de QUINE MAC CLUSKEY, d'autre part grâce à un tableau de Karnaugh, il apparaît que la seconde est nettement plus simple, rapide et séduisante que la première. Ceci explique que cette première méthode soit quasiment inemployée. Nous ne nous étendrons pas davantage sur elle.

Précisons toutefois à sa décharge que cette méthode de QUINE MAC CLUSKEY s'applique quel que soit le nombre de variables alors que la méthode des tableaux de Karnaugh se complique notablement lorsque le nombre de variables augmentent et devient supérieur à 6 ou 7.

5. - SYNTHÈSE

Dans ce chapitre appelé synthèse, nous allons faire un rappel de toutes les notions importantes nécessaires à l'étude et à la réalisation de circuits et de schémas d'électronique logique combinatoire puisque la logique combinatoire a été l'objet de notre préoccupation dans les trois premières théories.

En effet, on appelle logique combinatoire tout circuit dans lequel les sorties sont uniquement fonction des valeurs des entrées, indépendamment du temps.

5.1. - VARIABLE

On appelle variable logique toute quantité susceptible de prendre seulement deux valeurs 1 ou 0.

5.2. - FONCTION

Lorsque deux variables booléennes simples a et b varient de telle façon qu'à chaque valeur de a correspond une valeur bien déterminée de b, la quantité b est fonction de a.

Nous écrivons b = f(a).

5.3. - TABLES DE VÉRITÉ

La figure 61 récapitule les diverses fonctions logiques de base.

A chaque fonction logique, correspond une table de vérité et une équation logique. La table de vérité indique l'état de la sortie de la fonction considérée, en fonction de l'état des variables d'entrée.

5.4. - SYMBOLES GRAPHIQUES

La figure 62 donne les différentes représentations graphiques utilisées pour les fonctions logiques.

5.5. - TABLEAUX DE KARNAUGH

Le nombre de cases, constituant le tableau, est fonction du nombre de variables mises en jeu. On a vu qu'une variable pouvait prendre deux états : «1» ou «0».

Deux variables pourront prendre quatre combinaisons d'états :

1 Þ «0» et «0»

2 Þ «0» et «1»

3 Þ «1» et «0»

4 Þ «1» et «1»

Le nombre de combinaisons possibles est donné par la formule :

x = 2n avec n = nombres de variables.

5.5.1. - TABLEAU DE KARNAUGH A UNE SEULE VARIABL E

Exemple : fonction OUI, x = a.

L'état électrique de S n'est fonction que de «a». on a : x = 21 = 2 cases.

La figure 63 donne le tableau de Karnaugh de cette fonction.

5.5.2. - TABLEAU DE KARNAUGH A DEUX VARIABLES

La figure 64 donne la configuration du tableau de Karnaugh dans le cas de deux variables.

Exemple : S = a + b x = 22 = 4 cases

a) Repérage des deux variables :

L'état «1» d'une variable occupe la moitié des cases,

L'état «0» d'une variable occupe l'autre moitié (figure 65).

b) Repérage d'une somme de deux variables :

Cette somme est représentée par l'ensemble des cases appartenant aux deux variables,

Le repérage se fera par des «0» et des «1» qui ont la même signification que dans les tables de vérité, soit S = a + b.

La figure 66 donne la table de vérité et le tableau de Karnaugh correspondant.

c) Repérage d'un produit de deux variables :

Ce produit est représenté par l'ensemble des cases communes aux deux variables comme pour les cercles d'Euler, Soit S = a . b.

La figure 67 donne la table de vérité et le tableau de Karnaugh correspondant.

d) Repérage d'une fonction quelconque à deux variables :

Soit S = a + b, la figure 68 donne le tableau de Karnaugh correspondant.

On repère d'abord le produit a puis le produit b.

5.5.3. - TABLEAU DE KARNAUGH A TROIS VARIABLES

x = 23 = 8 cases

Soit S = a + bc, la figure 69 donne le tableau de Karnaugh de cette fonction.

5.5.4. - TABLEAU DE KARNAUGH A QUATRE VARIABLES

x = 24 = 16 cases

Soit S = (a + b) . (c + d), la table de vérité et le tableau de Karnaugh de cette fonction sont représentés figure 70.

5.5.5. - CAS DE PLUS DE QUATRE VARIABLES

On utilise plusieurs tableaux de Karnaugh à quatre variables que l'on superpose. Leur nombre double à chaque fois que l'on ajoute une nouvelle variable au-delà de quatre.

Exemple : 4 variables = 1 tableau

5 variables = 2 tableaux

6 variables = 4 tableaux

7 variables = 8 tableaux

On peut également employer la méthode de Mac CLUSKEY vue précédemment.

5.6. - SIMPLIFICATION DES FONCTIONS

La représentation des fonctions sur un tableau de Karnaugh permet de déceler rapidement des simplifications.

5.6.1. - RÈGLE :

L'équation minimale sera obtenue en pratiquant les groupements maximaux par puissance de 2, (2, 4, 8 cases), de cases adjacentes.

L'expression d'un groupement contient uniquement les variables qui ne changent pas d'état (figure 71).

Autre type de groupement possible :

Il faut considérer le tableau de la figure 72 comme pouvant se rouler sur lui-même pour se rejoindre sur les lignes AB et CD ou sur les lignes AC et BD.

Seule la surface d'un tore pourrait rendre cette image (figure 72-b).

Quand les groupements sont réalisés, on en déduit les équations minimales.

5.6.2. - EXEMPLES :

Soit la fonction S = a + ab dont la figure 73 donne le tableau de Karnaugh

L'équation déduite du groupement est S = a, a est la seule variable qui dans ce groupement ne change pas d'état.

Simplifier la fonction : L = + a + b

La figure 74 donne les tableaux de Karnaugh correspondants.

L'équation simplifiée est donc :

L = +

Simplifier la fonction : L = bd + + acd + c + abc

La figure 75 donne les tableaux de Karnaugh correspondants.

D'où l'équation simplifiée :

L = ac + bd +

5.7. - THÉORÈME DE DE MORGAN

1er théorème :

Le complément d'une somme est égal au produit de chacun de ses termes complémentés. Ainsi, le complément de a + b est . .

On écrit : = . .

2ème théorème :

Le complément d'un produit est égal à la somme de chacun de ses termes complémentés. Ainsi, le complément de a . b est + .

On écrit : = +

Dans le chapitre suivant, nous vous proposons deux problèmes résolus qui vous permettront de mettre en pratique l'ensemble des connaissances acquises.

Nous vous proposons pour finir plusieurs séries d'exercices dont les solutions sont données après chaque série. (Sur un autre site prévu à cet effet).

Fin de cette leçon et nous allons apprendre à résoudre quelques problèmes sur une autre page afin de ne pas encombrer celle-ci.

Cliquez ici pour la leçon suivante ou dans le sommaire prévu à cet effet.

Haut de page

Sommaire électronique digital

Sommaire électronique fondamental

Page d'accueil avec toutes les leçons

Daniel