Warning: include(header.php) [function.include]: failed to open stream: Permission denied in /homepages/15/d248849740/htdocs/electronique/cour.php on line 172

Warning: include() [function.include]: Failed opening 'header.php' for inclusion (include_path='.:/usr/lib/php5') in /homepages/15/d248849740/htdocs/electronique/cour.php on line 172


Méthodes de simplification des fonctions logiques
  • Auteur : jarod01
  • Difficultée :
  • Créé : le 22/06/2009 à 20:57:27
  • Modifié : le 22/06/2009 à 21:03:32
  • Avancement : 100%

Dans ce tutoriel, nous allons apprendre les techniques de simplification des fonction logique combinatoire par différentes méthodes: méthode algébrique, méthode de Kharnaugh et la méthode des consensus.


Méthode algébrique

Elle consiste à effectuer des calculs algébriques sur l'expression connue de la fonction pour la simplifier. Pour cela, on utilise les propriétés et théorèmes de l'algèbre de Boole.

Algèbre de Boole :



L'ensemble de Boole B={0,1} munit des fonctions logiques élémentaires NO (complément), AND (appelé multiplication logique) et OR (appelé addition logique) constitue une algèbre. Nous allons donner ci-dessous les différentes propriétés de ces opérateurs:
Le calcul algébrique est grandement facilité par l'utilisation des théorèmes de De Morgan et de Shannon.

Théorème de De Morgan



Le complément d'un produit est égal au produit des compléments:
overline{A+B+C+...}=overline{A}.overline{B}.overline{C}... et overline{A.B.C...}=overline{A}+overline{B}+overline{C}+....


Théorème de Shannon



Le complément d'une fonction logique s'obtient en complémentant chacune des variables et en permutant les opérateurs ET et OU :
overline{f(A,B,C,+,.)} = f(overline{A},overline{B},overline{C},+,.)


Exemple: Soit la fonction F(a,b,c) = overline{a} b c + a overline{b} c + a b c + a b overline{c} . On peut utiliser l'associativité de l'addition logique, la distributivité de la multiplication logique par rapport à l'addition logique et réécrire l'expression précédente sous la forme:

F(a,b,c) = (overline{a}.b.c + a.b.c) + a.overline{b}.c + a.b.overline{c} = b.c + a.overline{b}.c + a.b.overline{c} = b.(c + a.overline{c}) + a.overline{b}.c

En utilisant les autres propriétes: l'idempotence, l'élément neutre ...etc, on aboutit à l'expression suivante:

F(a,b,c) = b.(c + overline{c}).(1 + a) + a.overline{b}.c = b + a.overline{b}.c = (b + overline{b}).a.c = a.c

Théoriquement, on peut obtenir ainsi l'expression simplifiée, mais le calcul algebrique n'est pas toujours aisé, surtout lorsque le nombre des variables devient important. D'autre part, on n'est jamais sûr que l'expression obtenue est la plus simple.

Méthode de simplification de Kharnaugh

Une fonction combinatoire est définie par sa table de vérité. On affecte la valeur 0 ou 1 à chacune des 2n combinaisons des n variables logiques d'entrée. L'inconvénient de l'utilisation de la table de vérité est que deux combinaisons voisines ne sont pas adjacentes.

La méthode de Kharnaugh est basée sur l'utilisation du tableau de Kharnaugh qui est une forme particulière de table de vérité.

Tableau de Kharnaugh



C'est une table de vérité à deux dimensions. L'intersection d'une ligne avec une colonne constitue une case. Les variables sont divisées en deux groupes: des variables lignes et des variables lignes et des variables colonnes. Le tableau est construit tel que deux cases adjacentes correspondent à deux combinaisons adjacentes.

Cas de deux variables :



Le tableau est composé de quatre cases (deux lignes et deux colonnes), une variable ligne et une variable colonne. On obtient donc le tableau suivant:
Image

Définir une fonction logique par son tableau de Kharnaugh, c'est donc remplir chaque case du tableau par la valeur logique que prend la fonction.

Cas de trois variables :



Le tableau est composé de huit cases: deux variables colonne (a et b), et une variable ligne (c). Il est composé de quatre colonnes et deux lignes.
Image


Cas de quatre variables :



Le tableau est composé de 16 cases: deux variables colonnes (a et b) et deux variables lignes (c et d):

Image

Il faut noter que les cases extrêmes d'une même ligne sont adjacentes, de même les cases extrêmes d'une même colonne sont adjacentes.

Cas de cinq variables :



Le tableau est composé de 32 cases: trois variables colonnes (a, b et c) et deux variables lignes (d et e):
Image


Dans ce cas, il faut revoir la définition de l'adjacence des cases dans le tableau: deux cases sont adjacentes si elles ont un coté commun ou bien si elles sont symétriques par rapport à un axe de symétrie.

Il faut noter qu'il y a des axes de symétrie principaux et des axes de symétrie secondaires.

Méthode du tableau de Kharnaugh



Une fonction définie par sa table de vérité est aussi bien définie par le tableau de Kharmagh correspondant. Pour illustrer la méthode, on va utiliser l'exemple de la fonction F définie par sa table de vérité suivant:

abcdF
00001
00011
00100
00111
01001
01011
01101
01110
10000
10011
10100
10110
11001
11010
11101
11110


Le tableau de Kharnaugh de la fonction F est donc le suivant:

Image


Contraction des cases adjacente



Chaque case 1 correspond à un minterme et deux cases adjacentes correspondent à deux mintermes adjacents.
C'est quoi un minterme ?????

Un minterme est un produit des n variables, où toutes les variables apparaissent complémentées ou non.
Exemple: si nous avons trois variables a, b et c, les termes suivants sont des mintermes: a b overline{c}, a overline{b} overline{c}, a b c.
Par contre les produits logiques qui suivent ne sont pas des mintermes: b overline{c}, a overline{b}, a c.
Pour former le minterme correspond à une combinaison des variables, il faut complémenter les variables qui ont la valeur logique 0, les variables qui prennent la valeur 1 sont non complémentées.
Exemple: Pour la combinaison (a,b,c)=(0,1,0) le minterme correspondant est overline{a} b overline{c}.

Alors, ça veut dire quoi "deux mintermes adjacents" ?

Ok, ok, je vous expliques. On dira que deux mintermes sont adjacents, si et seulement s'ils ne différents que par rapport à une seule variable qui apparait complémenté dans l'un et non complémenté dans l'autre. De même, deux combinaisons des variable sont dites adjacentes si elles ne différents que par rapport à la valeur d'une seule variable.
Exemple: Toujours pour trois variables a, b et c, les mintermes suivants sont adjacents: a b overline{c} et a overline{b} overline{c}. Par contre les mintermes a b c et a overline{b} overline{c} ne le sont pas.

Revenons à nos moutons. On disait que chaque case 1 correspond à un minterme de deux cases adjacentes correspondent à deux mintermes adjacents. Par exemple les deux premières cases de la première ligne correspondent aux mintermes: overline{a} overline{b} overline{c} overline{d} et overline{a} b overline{c} overline{d}.
Dans l'expression de la fonction, sous la première forme, apparaitrons ces deux mintermes, leurs somme logique peut etre simplifier en éliminant la variable b, ce qui donne: overline{a} overline{b} overline{c} overline{d} + overline{a} b overline{c} overline{d} = overline{a} overline{c} overline{d}. On dira donc que la contraction de ces deux cases 1 adjacentes correspond au produit logique overline{a} overline{c} overline{d}.

De même, on peu effectuer une contraction de quatre cases 1 deux à deux adjacentes. Les quatre premières cases du tableau de Kharnaugh sont des cases 1 adjacentes, elles peuvent donc etre contracter, elles donnent le produit logique suivant : overline{a} overline{b} overline{c} overline{d} + overline{a} b overline{c} overline{d} + overline{a} overline{b} overline{c} d + overline{a} b overline{c} d = overline{a} overline{c}.

On peu effectuer des contractions d'un nombre plus important de cases 1 adjacentes. Cependant, ce nombre doit être une puissance de 2, c'est à dire qu'on peu effectuer des contractions de deux cases 1 adjacentes, de quatre cases 1 adjacentes, de 8 cases 1 adjacentes ... etc.

Méthode de simplification



Cette méthode consiste à trouver un minimum de contractions de tailles maximales qui rassemblent toutes les cases 1 de la fonction logique. Chacune de ces contractions correspond à un produit logique, la somme logique de ces produits constitue l'expression la plus simple de la fonction sous forme d'une somme de produits.

Pour trouver donc l'expression simplifiée de la fonction, il faut:
Dans l'exemple de la fonction F precedente, on ne peu pas effectuer de contraction de 8 cases 1. Par contre, on peut réaliser des contractions de 4 cases 1:

Image


Donc l'expression, sous forme d'une somme de produit, la plus simple de la fonction F est l suivante:
F = overline{a} overline{c} + overline{b} overline{d} + overline{b} overline{c} d + overline{a} overline{b} d ~~~~~~(1)

Dans cette méthode, on a utilisé les cases 1 de la fonction, mais on aurait pu aussi bien employer les cases 0 de la fonction. Pour l'expliquer, on va definir un nouveau terme bien utilisé aussi:
Le maxterme est une somme logique de n variables, ou toutes les variables apparaissent complémentées ou non.

Donc, la méthode est exactement la même à la différence près: les cases 0 correspondent à des maxtermes et la contraction de deux cases 0 adjacentes correspond à une somme logique où la variable qui change entre les deux maxtermes es éliminée. D'autre part, l'expression simplifiée obtenue sera sous la forme d'un produit de sommes logiques.

Utilisons les cases 0 de la fonction F précédentes. Elles ne permettent que des contractions de deux cases. On a quatre contractions de deux cases qui correspondent aux sommes logiques suivantes: ( overline{a} + b + d), ( b + overline{c} + d), ( overline{b} + overline{c} +overline{d} ) et ( overline{a} + overline{c} + overline{d} ). Donc, l'expression la plus simple de la fonction F sous la forme d'un produit de somme est la suivante:
F = ( overline{a} + b + d).( b + overline{c} + d).( overline{b} + overline{c} +overline{d} ).( overline{a} + overline{c} + overline{d} ) ~~~~~~~~(2).

En général, les deux expressions simplifiées obtenues sont équivalentes, c'est à dire que leur réalisation nécessite autant de circuits intégrés pour l'une que pour l'autre. Donc, on utilisera comme expression simplifiée de la fonction F indifféremment la relation (1) ou la relation (2).

Cas des fonctions incomplètement définies.



Parfois, la fonction à réaliser n'est pas complètement définie, c'est à dire que pour certaines combinaisons des variables, la valeur logique que prend la fonction n'est pas connue. Ceci pour plusieurs raisons:
Les cases du tableau de Kharnaugh correspondentes à ces combinaisons sont appelées des cases £.

Le symbole "£" est celui que j'utiliserai tout le long de ce paragraphe, vous n'êtes pas obligés de suivre cette notation, d'ailleurs si vous consulter des livres traitant ce sujet, vous trouverait d'autres symboles, donc, ce n'est pas une notation international (c'est la mienne peut être)

Pour trouver l'expression la plus simple de la fonction logique, on pourra utiliser ces cases £, selon le cas soit comme des cases 1, soit comme des cases 0. Il n'y a pas de règle permettant un choix judicieux, mais en général on attribuera a chaque case £ la valeur(0 ou 1) qui permet d'obtenir le plus petit nombre de contractions de plus grande taille possible qui englobent toutes les cases.

Pour éclaircir ce point, considérons une fonction logique G incomplètement définie dont le tableau de Kharnaugh est le suivant:

Image


Cette fonction G prend la valeur 1 pour quatre cases et la valeur 0 pour cinq cases. Pour les cases restantes, elle est indéfinie. On ne peut pas espérer obtenir des contractions de plus de 4 cases quelques soit les valeurs qu'on attribuera aux cases £. Il faut donc essayer d'affecter à chaque case £ une valeur de telle manière à recouvrir toutes les cases par un nombre minimum de contractions.

Si on utilise les cases 1, on peut avoir deux contactions de quatre cases. Par contre si on utilise les cases 0 on n'aura pas moins de trois contractions. Donc, le choix judicieux pour les cases £ est le suivant:

Image

Dans ce cas, l'expression la plus simple de la fonction G est:
G = b overline{c} + overline{a} d


Il est clair que c'est une réalisation particulière de la fonction G.
La méthode de simplification de Kharnaugh, qui est une méthode graphique, devient pénible à utiliser dès qu'on a plus de cinq variables, car le tableau devient de dimensions importantes, les cases adjacentes moins faciles à repérer et les contractions optimales moins évidentes. D'autre part, il est difficile de rendre cette méthode programmable. D'un autre cote, cette méthode impose de revenir à l'expression de la fonction sous une forme canonique, même si elle est partiellement simplifiée.


Méthode de simplification utilisant les consensus

Dès que nous avons plus de cinq variable, il est préférable d'utiliser la méthode des consensus. Cette méthode repose sur la propriété suivante: si dans l'expression logique, à simplifier, nous avons la somme logique de deux termes de la forme:
a.f(b,c,...)+ overline{a} .g(b,d,...)=a.f(b,c,...)+ overline{a} .g(b,c,...)+f(b,c,...).g(b,c,...)

Où les fonction f(b,c,...) et g(b,c,...) dépendent des autres variables, mais pas de a (ni de overline{a}). Le produit f(b,c,..).g(b,c,...) représente le consensus des termes a.f(b,c,...) et overline{a}.g(b,c,..) par rapport à la variable a. Dans la terminologie de la théorie des ensembles, c'est équivalent à dire que l'intersection est incluse dans la réunion.

Il est donc possible de rajouter le consensus de deux termes, par rapport à une variable, sans changer l'expression logique.

La question qui se pose est quel est l'intérêt de rajouter des consensus alors que le but c'est de simplifier l'expression logique?
En général, le fait d'adjoindre des consensus permet de supprimer des termes.

Soit, par exemple, la fonction logique H(a,b,c,d) partiellement simplifiée: H= overline{a} overline{b} overline{c} + b overline{c} overline{d} + overline{a} overline{b} d + a overline{b} d + bd. Cherchons les consensus possible par rapport à la variable a, on a les termes suivant: overline{b} overline{c} d et overline{b} d. Si nous les rajoutons à l'expression de la fonction H on obtient:
H= overline{a} overline{b} overline{c} + b overline{c} overline{d} + overline{a} overline{c} d + a overline{b} d + overline{b} overline{c} d + overline{b} d

On pourra alors supprimer le terme a overline{b} d car :
a overline{b} d + overline{b} d=(a+1) overline{b} d = overline{b} d

L'expression obtenue n'est pas simplifiée pour autant mais si on répète l'opération par rapport aux autres variable, on aboutit à l'expression simplifiée.
L'expression de la fonction devient:
H= overline{a} overline{b} overline{c} + b overline{c} overline{d} + overline{a} overline{c} d + overline{b} overline{c} d + overline{b} d

Cherchons les consensus de cette expression par rapport à la variable b, on obtient les termes suivants: overline{a} overline{c} overline{d} et overline{c} d. Ces consensus permettent de supprimer les 3ieme et 4ieme termes. L'expression de a fonction devient alors: H = overline{a} overline{b} overline{c} + b overline{c} overline{d} + overline{b} d + overline{a} overline{c} overline{d} + overline{c} d .

Répétons l'opération. Pour la variable c, nos e pouvons construire aucun consensus, puisque cette variable apparait uniquement sous forme complémentée.

Par rapport à la variable d, on a les consensus: b overline{c} et overline{a} overline{c}, ils autorisent la suppression des 1ier, second et 4ieme termes dans l'expression précédente, d'où l'expression de la fonction: H = overline{b} d + overline{c} d + b overline{c} + overline{a} overline{c}.

On répétera cette procedure tant qu'il est possible d'obtenir des consensus. Puisqu'on ne peut plus obtenir de consensus nouveau par rapport à aucune variable, alors la procédure s'arrête est la derniere expression obtenue est une expression simplifiée. Il reste une étape pour obtenir l'expression la plus simple de la fonction.

La méthode consiste donc à:
I. Chercher les consensus par rapport à une variable.
II. Supprimer le termes qui sont englobés dans les consensus précédents.
III. Chercher les consensus par rapport à la variable suivante et recommencer l'étape II.
IV. Répéter la procédure précédente jusqu'au moment où on ne peut plus obtenir de consensus nouveau.
V. Recherche des termes indispensables (ou essentiels).

L'expression obtenue à la fin de l'étape IV. représente une formule simplifiée de la fonction. Mais il n'est pas certain que ce soit l'expression la plus simple possible car l'un des termes peut être inclus dans la somme logique des autres. La dernière étape consiste donc à chercher les mintermes qui sont engobés dans chaque terme, pour déduire les simplifications encore possibles.

Pour chaque terme de la dernière expression obtenue de la fonction H, le tableau suivant donne les numéros des mintermes qu'il englobe:

N° des mintermesoverline{a} overline{c}b overline{c}overline{b} doverline{c} d
0X
1XXX
3X
4XX
5XXX
9XX
11X
12X
12X
13XX


Un produit logique est essentiel s'il est le seul à représenter au moins un minterme.

Dans notre cas: le produit overline{a} overline{c} est indispensable puisqu'il est le seul à représenter le minterme 0, c'est aussi le cas pour les termes b overline{c} (par rapport au minterme 12) et overline{b} d (par rapport au minterme 11). Par contre le terme overline{c} d ne représente aucun minterme à lui tout seul, il n'est donc pas essentiel et peut etre supprimer.

L'expression la plus simple possible de la fonction H est donc la suivante:
H = overline{b} d + b overline{c} + overline{a} overline{c}


Ce tutoriel touche sa fin, espérant que ces explications vont vous aidez a bien comprendre ces méthodes de simplification des fonctions logique, et par suite vous permettre de réaliser des schémas plus propres avec moins de composantes.

Warning: include(../footer.php) [function.include]: failed to open stream: Permission denied in /homepages/15/d248849740/htdocs/electronique/cour.php on line 303

Warning: include() [function.include]: Failed opening '../footer.php' for inclusion (include_path='.:/usr/lib/php5') in /homepages/15/d248849740/htdocs/electronique/cour.php on line 303