• 15 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 01/10/2019

Synthétisez des fonctions à partir de leur table de vérité

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Nous considérons dans ce chapitre le problème suivant : soit une fonction logique combinatoire décrite par sa table de vérité. La synthèse consiste à déterminer l'expression logique, si possible la plus économe possible, qui réalise la table de vérité. Nous allons étudier trois méthodes, essentiellement sur des exemples d'illustration. Nous nous limiterons à des fonctions de 3 ou 4 variables d'entrée.

Les deux premières méthodes se généralisent très aisément à un nombre d'entrées quelconque. La dernière, dite du tableau de Karnaugh, est une méthode graphique efficace, mais elle se généralise plus difficilement parce qu'elle utilise la géométrie de notre univers, qui est une géométrie 3D.

Somme de produits

La méthode dite de somme de produits est bien adaptée quand le nombre de combinaisons des entrées pour lesquelles la sortie est à 1 est faible. Pour décrire la méthode, nous allons traiter un exemple à 4 variables d'entrée notées respectivement a, b, c et d.

a

b

c

d

s

00000
000

1

1

00

1

00
00

1

1

0
0

1

000
0

1

0

1

0
0

1

1

00
0

1

1

1

0

1

0000

1

00

1

0

1

0

1

00

1

0

1

1

0

1

1

000

1

1

0

1

0

1

1

1

0

1

1

1

1

1

1

Comme vous pouvez le constater, la sortie notée s est à 1 pour 3 combinaisons des entrées, soit 0001, 1110 et 1111.

On montre que la fonction s s'exprime comme somme de produits des variables d'entrée, directes ou complémentées selon la recette suivante :

1. La somme comporte autant de termes qu'il y a de combinaisons à 1 de la sortie dans la table de vérité, en l’occurrence 3 termes dans cet exemple.

2. Chaque terme est le produit des 4 variables d'entrées, chaque variable apparaissant de façon directe ou complémentée, selon qu'elle est respectivement à 1 ou 0 dans la combinaison correspondante.

Sur notre exemple, il s'agit d’identifier les 3 combinaisons (cf. supra). Le terme correspondant à la combinaison 0001 est exprimé par $\(\bar a \bar b \bar c d\)$ puisque a, b et c y sont à 0, tandis que d est à 1. La combinaison 1110 conduit au produit $\(a b c \bar d\)$ et enfin, le produit correspondant à la combinaison 1111 s'exprime $\(a b c d\)$.

Ainsi, la fonction s'exprime par :

$\(s= \bar a \bar b \bar c d+abc \bar d + abcd\)$ 

Il reste ensuite à simplifier cette expression, autant que possible. Ici, la seule simplification possible est la mise en facteur de abc, dans les deux derniers termes, qui fait disparaître la variable d.

Finalement :

$\(s= \bar a \bar b \bar c d+abc \bar d + abcd = \bar a \bar b \bar c d + abc (\bar d + d)=\bar a \bar b \bar c d + abc\)$

Nous traitons un deuxième exemple à 3 variables d'entrée. Soit la fonction arbitraire suivante donnée par sa table de vérité :

a

b

c

s

0000
00

1

 0

0

1

0

 0

0

1

1

 1

1

00

 0

1

0

1

 0

1

1

0

 0

1

1

1

 1

Comme dans l'exemple précédent, on identifie les combinaisons pour lesquelles la fonction est à 1 (il y en a 2 ici, soit 011 et 111) et donc la fonction s'écrit comme somme de deux produits, soit par simplification :

$\(s=\bar a b c + abc = (\bar a +a)bc =bc\)$

Produit de sommes

La méthode dite produit de sommes est duale de la précédente. Elle est bien adaptée quand le nombre de combinaisons des entrées pour lesquelles la sortie est à 0 est faible. Pour décrire la méthode, comme plus haut, nous allons traiter un exemple à 4 variables d'entrée notées respectivement a, b, c et d.

a

b

c

d

s

0000

1

000

1

1

00

1

0

1

00

1

1

1

0

1

00

1

0

1

0

1

0
0

1

1

0

1

0

1

1

1

1

1

000

1

1

00

1

1

1

0

1

0

1

1

0

1

1

1

1

1

00

1

1

1

0

1

1

1

1

1

0

1

1

1

1

1

0

Comme vous pouvez le constater, la sortie notée s est à 0 pour 2 combinaisons des entrées, soit 0101 et 1111.

On montre que la fonction s s'exprime comme produit de sommes des variables d'entrée, directes ou complémentées selon la recette suivante :

1. Le produit comporte autant de facteurs qu'il y a de combinaisons à 0 de la sortie dans la table de vérité, en l’occurrence 2 facteurs dans cet exemple.

2. Chaque facteur est la somme des 4 variables d'entrée, chaque variable apparaissant de façon directe ou complémentée, selon qu'elle est respectivement à 0 ou 1 dans la combinaison correspondante.

Sur notre exemple, il s'agit d’identifier les 2 combinaisons (cf. supra).

Ainsi, la fonction s'exprime : $\(s=(a \bar b c \bar d).(\bar a \bar b \bar c \bar d)\)$

Tableau de Karnaugh

La méthode du tableau de Karnaugh est dans une certaine mesure l'extension graphique de la méthode de somme de produits pour faire apparaître graphiquement les simplifications qui peuvent résulter de la mise en facteur de variables. Dans les faits, la méthode du tableau de Karnaugh fonctionne bien à 3 ou 4 variables. Elle est en principe extensible à 5, voire 6 variables, mais nous ne ferons qu'évoquer cette extension à 5 et 6 variables, sans toutefois traiter aucun exemple. La méthode est basée sur plusieurs étapes dont la première est la transformation de la table de vérité vers le tableau de Karnaugh.

De la table de vérité au tableau de Karnaugh

Pour effectuer cette transformation, nous allons utiliser l'exemple de la fonction à 4 variables traité dans le paragraphe "Somme de produits". Les 16 combinaisons de la table de vérité sont transformées en un tableau carré de 4 fois 4 cases.

La figure ci-dessous montre la transformation de la table de vérité vers le tableau de Karnaugh :

Tableau de Karnaugh de la fonction logique du paragraphe
Tableau de Karnaugh de la fonction logique du paragraphe "Somme de produits"

Il convient de faire les commentaires suivants :

a. Les poids forts (a et b) sont mis en ligne tandis que les poids faibles (c et d) sont mis en colonne.

b. Les 16 combinaisons des entrées sont organisées en 4 fois 4 cases.

c. Les deux groupes (poids forts et poids faibles) sont organisés en code de Gray (00, 01, 11 et 10).

d. Les 16 états de la sortie occupent les 4 fois 4 cases du tableau de Karnaugh.

Identification de groupes de 1

La méthode de synthèse est basée sur l'identification de groupes de 1, les plus gros possibles. Dans l'exemple que nous traitons, il y en a peu et ils ne sont pas bien gros. Nous verrons plus loin de nombreux exemples qui conduisent à des simplifications très efficaces. Mais pour l'instant, nous revenons à notre exemple qui est adapté pour un tout premier contact.

Le 1 de la toute première ligne est totalement isolé. En fait, il a 4 cases adjacentes, respectivement à gauche, à droite, en-dessous et au-dessus. Au-dessus ? Mais vous direz, c'est la première ligne, il n'y a rien au-dessus. En fait, si ! La toute dernière ligne est "adjacente", en ce sens qu'elle correspond aux entrées 10, tandis que la première ligne correspond aux entrées 00. Il n'y a donc que a qui ait changé d'état. La case "au-dessus" du 1 de la première ligne est donc la deuxième case de la dernière ligne.

Revenons à notre exemple. Le 1 de la première ligne est donc isolé puisque toutes ses cases adjacentes sont remplies de 0. Dans la fonction logique que nous nous efforçons de synthétiser, il y aura donc un produit des variables d'entrées directes ou complémentées, en fonction de l'état des entrées correspondant à cette case. En l'occurrence, le terme s'écrit $\(\bar a \bar b \bar c d\)$  puisque dans la case, a, b et c sont à 0 et d à 1.

Dans la troisième ligne, il y a un groupe de deux 1 puisque les deux cases sont adjacentes. Dans l'expression de la fonction finale (sous forme de somme de produits), ce groupe correspond à un terme mais non pas des 4 variables d'entrée, seulement de 3 d'entre elles. Vous observez que dans ce groupe, une variable d'entrée a changé d'état. Il s'agit de d qui passe de 0 à 1 au sein du groupe. À ce titre, d disparaît du produit et il reste $\(abc\)$ parce qu'ils sont tous trois à 1 au sein du groupe.

C'est le principe de la méthode. Au sein d'un groupe de 1, seules les variables qui ne changent pas d'état subsistent dans le produit correspondant au groupe. Celles qui changent d'état disparaissent.

Groupes de tailles supérieures

Dans les figures qui suivent, nous montrons des groupes classiques et écrivons les termes correspondants. Dans une synthèse quelconque, nous les retrouverons souvent, ou, bien sûr, des variantes.

Un groupervertical de 8
Un groupe vertical de 8

On constate qu'au sein de ce groupe, les variables a et b changent d'état puisqu'on parcourt toutes les lignes. En ce qui concerne les variables c et d, d change d'état mais pas c. Finalement, le produit qui correspond à ce groupe est réduit à c, les 3 autres variables d'entrée ont disparu.

Le groupe de 4 en coin.
Le groupe de 4 en coin

C'est étonnant pour un débutant mais ce groupe fonctionne : les 4 cases en "coin" sont adjacentes. Au sein du groupe, a et c changent d'état. Il reste, pour ce groupe, le produit $\(\bar b \bar d\)$. Comme pour cette fonction, c'est le seul groupe de 1. La fonction totale s'écrit $\(s=\bar b \bar d\)$ 

Deux groupes de 4
Deux groupes de 4

En vertu du code de Gray, les deux lignes extrêmes et les deux colonnes extrêmes sont adjacentes. On peut donc former deux groupes de 4. Le groupe formé des deux lignes extrêmes conduit au terme $\(\bar b d\)$, tandis que le groupe des deux colonnes extrêmes conduit à $\(b \bar d\)$. Comme il n'y a pas d'autre groupe dans le tableau, la fonction s'écrit $\(s=b \bar d + \bar b d\)$ 

Deux groupes de 4 qui partagent des cases à 1
Deux groupes de 4 qui partagent des cases à 1

Dans cet exemple, on identifie deux groupes de 4 qui partagent une même case à 1, ce qui est parfaitement autorisé. Le groupe de 4 vertical conduit à $\(cd\)$, tandis que le groupe de 4 horizontal conduit à $\(ab\)$. La fonction s'écrit $\(s=ab + cd\)$ 

Un dernier exemple
Un dernier exemple

Dans ce dernier exemple, on reconnaît l'exemple précédent, mais il y a deux groupes supplémentaires de 4. La fonction s'écrit $\(s=ab+cd+ad+\bar b d\)$ 

Sauriez-vous identifier à quel groupe correspond chaque terme de la somme de produits ?

Fonction de 3 variables d'entrée

Nous allons nous intéresser uniquement à la transformation de la table de vérité en tableau de Karnaugh. Ensuite, la synthèse de la fonction est obtenue par l'identification de groupes et à une fonction qui s'écrit comme somme de produits, chaque groupe conduisant à un terme de la somme.

Les 8 combinaisons des 3 variables d'entrée sont organisées en un tableau de 2 fois 4 colonnes, selon la figure ci-dessous qui utilise l'exemple à 3 entrées du paragraphe "Somme de produits" :

Tableau de Karnaugh pour une fonction à trois entrées
Tableau de Karnaugh pour une fonction à trois entrées

Saurez-vous écrire rapidement la fonction comme expression des variables d'entrée ? Comparez votre résultat à celui établi dans le paragraphe "Somme de produits" !

Extension des tableaux de Karnaugh à 5 ou 6 variables d'entrée

Une solution consiste à exploiter la troisième dimension. Le tableau de Karnaugh devient un "cube" de Karnaugh pour 6 variables d'entrée. D'autres variantes, pour rester en 2D, existent.

En résumé

Félicitations ! Vous êtes arrivé à la fin de ce premier cours ! Vous avez à présent toutes les clés en main pour :

  • définir le concept de codage de l’information ;

  • décrire le code binaire et ses variantes ;

  • décrire les fonctions élémentaires ;

  • reconnaître les portes logiques CMOS ;

  • utiliser un logiciel de conception et de simulation ;

  • faire la synthèse d’une fonction logique combinatoire. 

N'oubliez pas de réaliser les quiz à la fin de chaque partie pour valider ces compétences. Nous vous souhaitons une très bonne continuation !

Exemple de certificat de réussite
Exemple de certificat de réussite