Créée le, 19/06/2015

 Mise à jour le, 29/12/2019

Visiteurs N°  




Accueil
Site en Français Site en Anglais Nos Promotions Nouveau Blog Nouveautés Moteur de Recherche Votre Caddie Pour Vos Achats Votre Espace Membre Vos Signets et Vos Jeux Préférés Page de Bienvenue Statique
Sommaires
Électronique Fondamentale Technologie Fondamentale Testez vos Connaissances Électronique Théorique Digitale Électronique Pratique Digitale Lexique Électronique Numérique Data book TTL Data book CMOS Dépannage TVC Mathématique
Micro-ordinateurs
Théorique des Micro-ordinateurs Testez vos Connaissances Pratique des Micro-ordinateurs Glossaires sur les Ordinateurs
Physique
La lumière Champ d'action Rayonnement Électromagnétique
Technologies
Classification des Résistances Identification des Résistances Classification des Condensateurs Identification des Condensateurs
Formulaires Mathématiques
Géométrie Physique 1. - Électronique 1. 2. - Électronique 1. 3. - Électrotechnique 1. 4. - Électromagnétisme
Accès à tous nos Produits
E. T. F. - Tome I - 257 Pages E. T. F. - Tome II - 451 Pages E. T. F. - Tome III - 611 Pages E. T. D. - Tome I - 610 Pages N. B. M. - Tome I - 201 Pages E. T. M. - Tome I - 554 Pages Business à Domicile Ouvrages 34 pages gratuits Nos E-books Logiciel Géométrie Logiciel Composants Électroniques
Aperçu de tous nos Produits
E. T. F. - Tome I - 257 Pages E. T. F. - Tome II - 451 Pages E. T. F. - Tome III - 611 Pages E. T. D. - Tome I - 610 Pages E. T. M. - Tome I - 554 Pages Logiciel Géométrie Logiciel Composants Électroniques
Nos Leçons aux Formats PDF
Électronique Fondamentale Technologie Fondamentale Électronique Théorique Digitale Électronique Pratique Digitale Théorique des Micro-ordinateurs Mathématiques
Informatique
Dépannage Win98 et WinXP et autres Dépannage PC Glossaire HTML et Programmes JavaScript (en cours de travaux) PHP et Programmes Création de plusieurs Sites
Forums
Forum Électronique et Infos Forum Électronique et Poésie
Divers et autres
Formulaire des pages perso News XML Statistiques CountUs Éditeur JavaScript Nos Partenaires avec nos Liens Utiles Gestionnaire de Partenariat Nos Partenaires MyCircle Sondages 1er Livre d'Or 2ème livre d'Or Annuaires Sites

Signets : 
  Comparaison avec la méthode de Karnaugh         Synthèse      Tableaux de Karnaugh 
  Simplification des fonctions    Bas de page  


Méthode de Quine-Mac Cluskey et Comparaison avec la Méthode de Karnaugh :


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.

Table_de_verite.gif

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 = A_barre1.gifbcD_barre.gif : 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 :

Combinaisons_pour_lesquelles_f_egale_a_1.gif  

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.

Classement_des_combinaisons_en_ensembles.gif 

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 :

Exemple_de_combinaisons_0_et_1.gif

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.

Combinaisons_des_ensembles_1_2_3_4_et_5.gif



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.

Combinaisons_des_ensembles_I_II_III_IV.gif

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_barre.gifC_barre.gif + A_barre1.gifD_barre.gif + C_barre.gifD_barre.gif + bD_barre.gif + aC_barre.gif + 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é.

Grille_de_MAC_CLUSKEY.gif    

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 = B_barre.gifC_barre.gif + A_barre1.gifD_barre.gif + ab

Haut de page 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).

Table_de_verite1.gif

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

f = 1 + 2 + 3

f = B_barre.gifC_barre.gif + A_barre1.gifD_barre.gif + 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.

Haut de page 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.

Fonctions_elementaires_et_leur_table_de_verite.gif 

5. 4. - SYMBOLES GRAPHIQUES

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

Symboles_graphiques_des_differentes_fonctions_logiques.gif

Haut de page 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 :

Þ "0" et "0"

Þ "0"  et "1"

Þ "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 VARIABLE

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.

Tableau_de_Karnaugh_a_une_variable.gif

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

Tableau_de_Karnaugh1.gif

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).

Reperage_des_variables.gif

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.

Somme_de_deux_variables.gif

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.

Produit_de_deux_variables.gif

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

Soit S = aB_barre.gif + A_barre1.gifb, la figure 68 donne le tableau de Karnaugh correspondant.

On repère d'abord le produit  aB_barre.gif puis le produit A_barre1.gifb.

Tableau_de_Karnaugh_a_deux_variables.gif

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.

Tableau_de_Karnaugh_a_trois_variables.gif

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.

Table_de_verite_et_tableau_de_Karnaugh.gif  

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.

Haut de page 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).

Groupements_possibles.gif 

      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).

Autre_type_de_groupement.gif

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

Tableau_de_Karnaugh_de_la_fonction_S.gif

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_barre1.gifB_barre.gif + aB_barre.gif + A_barre1.gifb

La figure 74 donne les tableaux de Karnaugh correspondants.

Tableaux_de_Karnaugh.gif

L'équation simplifiée est donc :

L = A_barre1.gif + B_barre.gif

      Simplifier la fonction : L = bd + B_barre.gif + aB_barre.gifcd + B_barre.gifc + abc

La figure 75 donne les tableaux de Karnaugh correspondants.

Tableau_de_Karnaugh(1).gif

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

L = ac + bd + B_barre.gif

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 A_barre1.gif . B_barre.gif.

On écrit : a_ou_b_complementation.gif  = A_barre1.gif . B_barre.gif.

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 A_barre1.gif + B_barre.gif.

On écrit : a_et_b_complementation.gif = A_barre1.gif + B_barre.gif

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


  Cliquez ici pour la leçon suivante ou dans le sommaire prévu à cet effet.   Haut de page
  Page précédente   Page suivante 






Nombre de pages vues, à partir de cette date : le 15 JUILLET 2019

compteur gratuit

    




Envoyez un courrier électronique à Administrateur Web Société pour toute question ou remarque concernant ce site Web. 

Version du site : 10. 4. 12 - Site optimisation 1280 x 1024 pixels - Faculté de Nanterre - Dernière modification : 02 Septembre 2016.   

Ce site Web a été Créé le, 14 Mars 1999 et ayant Rénové, en Septembre 2016.