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 Livre d'Or Livre d'Or Annuaires Sites

Signet : 
     Bas de page  


Méthode Matricielle d'Huffman et Polygone de Fusion :


2. 3. - MÉTHODE MATRICIELLE D'HUFFMAN


Nous savons que le tableau de Karnaugh ne permet pas de résoudre directement un problème séquentiel. En effet, il ne peut exister pour chaque combinaison des variables d'entrée qu'une valeur pour la sortie, c'est-à-dire une valeur par case élémentaire du tableau.

Il convient donc de rechercher une représentation qui permette l'introduction d'une ou de plusieurs variables secondaires comme vu précédemment.

2. 3. 1. SÉQUENCE

On appelle séquence une succession bouclée d'états stables séparés par des états transitoires.

La figure 19 représente un exemple de séquence.

Exemple_de_sequence.gif

2. 3. 2. - RÉSOLUTION D'UN PROBLÈME PAR LA MÉTHODE MATRICIELLE

Pour illustrer cette méthode, reprenons encore le même exemple.

a)  Analyse

On dispose de deux variables d'entrée «m» et «a».

Ces deux variables permettent d'obtenir 22 = 4 combinaisons.

Comme point de départ, on se sert d'un tableau avec quatre colonnes correspondant aux combinaisons des entrées que l'on range selon le code binaire réfléchi. Dans une cinquième colonne, on inscrira la valeur binaire de l'état de sortie. Le tableau est représenté figure 20.

Tableau_de_depart.gif

Reprenons le fonctionnement du montage et définissons le nombre d'états stables :

Nombre_0.gif  État initial                                        a = 0,  m = 0  avec  L = 0

Nombre_1.gif  Action sur m                                    a = 0,  m = 1  d'où  L = 1

Nombre_2.gif  m est relâché                                  a = 0,  m = 0  et  L  toujours à 1

Nombre_3.gif  Action sur a                                     a = 1,  m = 0  et  L = 0

Nombre_4.gif  Action simultanée sur a et m         a = 1,  m = 1  on a choisi de privilégier l'arrêt : L = 0

 b)  Construction de la matrice primitive des états.

On appelle matrice primitive des états un tableau du modèle de la figure 20 dans lequel il y a une ligne par état stable tel que représenté figure 21.

On positionne chaque état stable dans la case pour laquelle les variables «m» et «a» sont aux valeurs ayant entraîné cet état stable.

 

 

Matrice_primitive_des_etats_stables.gif

 

Exemple :

Pour  a = 0, m = 0                état stable Nombre_0.gif, L = 0

           a = 0, m = 1                état stable Nombre_1.gif, L = 1

           a = 0, m = 0                état stable Nombre_2.gif, L = 1

           a = 1, m = 0                état stable Nombre_3.gif, L = 0

           a = 1, m = 1                état stable Nombre_4.gif, L = 0

Il est maintenant nécessaire de positionner les états transitoires.

Les états transitoires sont situés à l'intersection de la ligne sur laquelle figure l'état stable initial et de la colonne dans laquelle figure l'état stable suivant.

La figure 22 montre ces états transitoires.

Matrice_primitive_des_etats_stables_et_transitoires.gif

Nous savons qu'il est impossible que deux variables commutent simultanément. Pour matérialiser ceci sur la matrice primitive, il convient de hachurer pour les éliminer, toutes les cases pour lesquelles sur une même ligne deux variables changent par rapport à la combinaison des variables qui a provoqué l'état stable inclus dans cette ligne.

Nous obtenons ainsi le tableau de la figure 23.

Dans notre exemple :    pour l'état stable Nombre_0.gif   a = 0,  m = 0,  il faut hachurer la case où a = 1,  m = 1

                                         pour l'état stable Nombre_1.gif   a = 0,  m = 1,  il faut hachurer la case où a = 1, m = 0

                                         pour l'état stable Nombre_2.gif   a = 0,  m = 0,  il faut hachurer la case où a = 1, m = 1

                                         pour l'état stable Nombre_3.gif   a = 1,  m = 0,  il faut hachurer la case où a = 0, m = 1

                                         pour l'état stable Nombre_4.gif   a = 1,  m = 1,  il faut hachurer la case où a = 0, m = 0

Matrice_primitive_des_etats.gif

Il est maintenant nécessaire d'examiner les cases restantes.

Ligne 1 :

Case  10  (a = 1,  m = 0)

Si l'on appuie sur «a» alors que L est éteinte, on évolue vers une situation analogue à l'état stable Nombre_3.gif (a = 1, m = 0, L = 0), on écrit donc 3 dans la case ce qui montre que l'on passe par l'état transitoire 3.

Ligne 2 :

Case 11  (a = 1,  m = 1)

Si l'on appuie sur «a» alors que «m» n'a pas été relâché, on va vers l'extinction de la lampe donc vers l'état stable Nombre_4.gif (a = 1, m = 1, L = 0). On inscrit 4 dans la case.

Ligne 3 :

Case 01  (a = 0, m = 1)

Si l'on appuie sur «marche» alors que la lampe est déjà allumée, ceci n'a pas d'effet et on va vers l'état stable Nombre_1.gif (a = 0, m = 1, L = 1), on écrit donc 1 dans la case.

Ligne 4 :

Case 00  (a = 0, m = 0)

On relâche «a» et la lampe reste éteinte, on va donc vers l'état stable Nombre_0.gif (a = 0, m = 0, L = 0), on écrit 0 dans la case.

Ligne 5 :

1)  Case 01  (a = 0, m = 1)

On relâche «a» alors que «a» et «m» étaient actionnés et que L était éteinte. La lampe se rallume car on revient à l'état stable Nombre_1.gif (a = 0, m = 1, L = 1), on écrit donc 1 dans la case.

2)  Case 10  (a = 1, m = 0)

On relâche le bouton marche alors que L est éteinte, on revient donc vers l'état stable Nombre_3.gif (a = 1, m = 0, L = 0), on écrit donc 3 dans la case.

On obtient ainsi la matrice primitive complétée de la figure 24.

Matrice_primitive_des_etats_completee.gif

c)  Recherche de la matrice contractée

Il est souhaitable de ramener la matrice primitive des états à une matrice contractée afin de diminuer le nombre de lignes supplémentaires, celles-ci introduisant de nouvelles excitations et de nouvelles variables complémentaires ou transferts.

Règles de contraction ou de fusion :

     Il est possible de contracter la matrice primitive des états en superposant deux lignes si elles présentes verticalement les mêmes états.

     On peut fusionner deux lignes en une seule lorsqu'il y a un état stable ou un transitoire de même numéro situé dans la même colonne ou un état stable ou transitoire avec une case hachurée située dans la même colonne, en effet, la case hachurée indique que, pour des raisons technologiques, ce cas ne peut se produire et est donc indifférent.

     Les états de sortie n'interviennent pas dans les superpositions possibles.

Étude des possibilités pour la ligne 1 :

Comparons la ligne 1 avec la ligne 2 : elles ne sont pas superposables car pour a = 0 et m = 0, on a l'état Nombre_0.gif sur la première ligne et 2 sur la seconde.

Comparons la ligne 1 avec la ligne 3 : elles ne sont pas superposables car on a Nombre_0.gif sur la première ligne et 2 sur la troisième pour a = 0 et m = 0.

Comparons la ligne 1 avec la ligne 4 : ces deux lignes sont superposables car on a Nombre_0.gif correspond à 0, à 1 correspond une impossibilité, à une impossibilité correspond 4, à 3 correspond Nombre_3.gif.

Comparons la ligne 1 avec la ligne 5 : ces deux lignes sont superposables.

Pour la ligne 2, les combinaisons possibles sont :

Lignes 2 et 3 superposables.

Lignes 2 et 4 non superposables.

Ligne 2 et 5 superposables.

Pour la ligne 3, les combinaisons possibles sont :

Lignes 3 et 4 non superposables

Lignes 3 et 5 superposables

Pour la ligne 4, les combinaisons possibles sont :

Lignes 4 et 5 superposables

d)  Polygone de fusion

Répartissons sur un cercle en comptant dans le sens des aiguilles d'une montre les cinq points matérialisant les cinq lignes de la matrice primitive des états : nous obtenons la figure 25.

Les_sommets_du_polygone_de_fusion.gif

Relions ensemble toutes les lignes superposables comme représenté figure 26.

Polygone_de_fusion.gif

e)  Interprétation du polygone de fusion

Nous obtenons deux triangles de sommets 1-5-4 et de sommets 2-5-3.

Règle :

Nous pouvons fusionner par exemple 2-3-5...n sommets reliés entre eux mais chaque sommet ne doit figurer que dans un seul groupement de telle sorte que dans notre cas, on peut réaliser les groupements :

1-4-5  et  2-3  ou  2-3-5  et  1-4

Nous préférerons 1-4-5 et 2-3 car à l'intérieur de chaque groupement l'état des sorties est identique.

Ceci va faciliter ultérieurement les groupements dans l'ultime tableau de Karnaugh, mais ce n'est pas obligatoire et surtout pas toujours possible.

f)  Matrice contracée ou tableau de fusion.

Superposons les lignes 1-4-5 représentées figure 27.

Lignes_1_4_5_avant_contraction.gif

La figure 28 montre les lignes 1-4-5 après contraction.

Lignes_1_4_5_fusionnees.gif

La figure 28 nous montre que les états stables l'emportent sur les transitoires à la fusion.

La figure 29 représente les lignes 2-3 de la matrice primitive avant fusion.

Lignes_2_3_avant_fusion.gif

La figure 30 représente les lignes 2-3 après fusion.

Lignes_2_3_apres_fusion.gif

Nous pouvons reconstituer une matrice dite contractée au moyen des lignes 1-4-5 et 2-3. La figure 31 représente cette matrice contractée.

Matrice_contractee.gif

Nous voyons à la figure 31 que la matrice contractée comprend deux lignes, ce qui signifie que les variables complémentaires ou transferts sont au nombre de un seulement que l'on appelle x.

Pour une matrice de 21 = 2 lignes, on a 1 variable complémentaire, pour 22 = 4 lignes, on a 2 variables complémentaires et pour 2n lignes, on a n variables.

Si la matrice comprend 20 = 1 ligne, le système examiné peut se résumer à un système combinatoire (aucune variable complémentaire).

g)  Établissement du tableau de Karnaugh ramenant le problème à un problème combinatoire.

Établissons le tableau de Karnaugh de la sortie en reportant les valeurs binaires de la sortie pour les états stables considérés dans la matrice contractée.

On recherchera l'état L pour un état stable donné dans la matrice primitive des états (figure 21).

Pour Nombre_0.gif    L = 0

Pour Nombre_1.gif    L = 1

Pour Nombre_2.gif    L = 1

Pour Nombre_3.gif    L = 0

Pour Nombre_4.gif    L = 0

Nous obtenons la figure 32.

Il reste trois cases à remplir pour les états transitoires.

Nous reporterons l'état logique de la sortie (1 ou 0) pour l'état stable vers lequel l'état transitoire considéré évolue.

L'état transitoire 1 évolue vers l'état stable Nombre_1.gif pour lequel L = 1

L'état transitoire 4 évolue vers l'état stable Nombre_4.gif pour lequel L = 0

L'état transitoire 3 évolue vers l'état stable Nombre_3.gif pour lequel L = 0

Reportons ces valeurs dans la matrice de la figure 32.

Nous obtenons le tableau de Karnaugh de la figure 33.

Tableau_de_Karnaugh_obtenu_a_partir_de_la_matrice_contractee.gif

A partir de ce tableau de Karnaugh, le problème est redevenu un problème combinatoire.

Nous pouvons réaliser les groupements comme nous avons appris à le faire. Ils sont représentés figure 34.

Nous obtenons l'équation de L suivante :

L = A_barre1.gifm + A_barre1.gifx

Soit  L = A_barre1.gif(m + x)

On retrouve bien l'équation obtenue par les méthodes précédentes.

Nous disposons donc de 2 méthodes pour résoudre un problème séquentiel :

  • La méthode des phases généralisée

  • La méthode matricielle d'HUFFMAN

Nous préférerons la méthode d'Huffman qui est plus abstraite mais à la fois plus systématique et plus sûre. Toutefois, la méthode des phases généralisée présente l'avantage de permettre une visualisation des aléas de fonctionnement possibles et leurs éliminations plus facile. On peut donc seulement recommander l'utilisation de la méthode des phases comme vérification d'un schéma obtenu par la méthode d'Huffman afin de rechercher d'éventuels aléas.

Examinons à présent les bascules bistables.  


  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.