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 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 0 |
1 | 1 | 0 | 0 | 0 |
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 ˉaˉbˉcd puisque a, b et c y sont à 0, tandis que d est à 1. La combinaison 1110 conduit au produit abcˉd et enfin, le produit correspondant à la combinaison 1111 s'exprime abcd.
Ainsi, la fonction s'exprime par :
s=ˉaˉbˉcd+abcˉ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=ˉaˉbˉcd+abcˉd+abcd=ˉaˉbˉcd+abc(ˉd+d)=ˉaˉbˉcd+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 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
1 | 0 | 0 | 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=ˉabc+abc=(ˉ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 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 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+b¯+c+d¯).(a¯+b¯+c¯+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 :
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 ˉaˉbˉcd 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.
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.
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 ˉbˉd. Comme pour cette fonction, c'est le seul groupe de 1. La fonction totale s'écrit s=ˉbˉd
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 ˉbd, tandis que le groupe des deux colonnes extrêmes conduit à bˉd. Comme il n'y a pas d'autre groupe dans le tableau, la fonction s'écrit s=bˉd+ˉbd
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
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+ˉbd
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" :
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 !
