Logique (sciences de l'ingénieur)/Exercices/TD3

Simplification par Karnaugh

Une équation obtenue à partir d’une table de vérité s’appelle une forme disjonctive ou somme de produits. Les tableaux de Karnaugh permettent de simplifier ces formes disjonctives en regroupant des termes.

Pour obtenir un terme à partir d’un regroupement, on se « balade » dans le regroupement et on regarde toutes les variables qui changent : elles sont alors éliminées. L'objectif d’une simplification par tableaux de Karnaugh est de réaliser les regroupements les plus grands possibles et en nombre le plus petit possible. Voir ( Table de Karnaugh)

La forme simplifiée obtenue à l'aide d’un tableau de Karnaugh est une forme disjonctive simplifiée. Celle obtenue à partir de la table de vérité est dite disjonctive canonique.

Exercice 1

Trouver la forme disjonctive simplifiée correspondante au tableau de Karnaugh.

Parfois il arrive que pour une fonction donnée, une ou plusieurs combinaisons des entrées ne peut se produire. Dans ce cas ce qui se passera en sortie n'a aucune importance : on dit que l’on a des cas indéterminés. Ils sont notés x ou X ou Ø. On les choisit alors comme cela nous arrange.

Implantation d’une forme disjonctive

Une forme disjonctive, qu'elle soit simplifiée ou non, s'implante de manière naturelle en une structure ET-OU (les ET d’abord pour finir par les OU). Cette forme ET-OU conduit directement, en utilisant De Morgan, à un schéma en ET-NON (NAND). Prenons comme exemple la forme simplifiée du tableau de Karnaugh.

La figure ci-dessous explique la démarche pour obtenir un schéma en ET-NON (NAND).

On part d’une forme disjonctive si possible simplifiée et on fait une schéma en trois couches ET/OU (d’abord les ET puis le OU) puis on transforme le OU final en ET-NON en faisant glisser les inverseurs de ses entrées. Le schéma obtenu est alors en trois couches ET-NON qui utilise des portes à nombre d'entrées illimité. Si on limite le nombre d'entrées des ET-NON on ne limite alors plus le nombre de couches à trois. On peut partir d’un schéma à trois couches et utiliser les équivalences suivantes.

Remarque : tout serait très simple si la règle suivante était vraie : à toute meilleure simplification d’une forme disjonctive correspond le meilleur schéma (celui qui utilise le moins de portes possible). Montrons sur deux exemples que ce n’est pas vrai, qu’il faut parfois éviter les formes disjonctives.

Cette figure nous montre le gain de deux portes en partie supérieure et le gain d’une porte en partie inférieure. Après toute synthèse en ET-NON, il faudra chercher si une des deux optimisations ci-dessus n’est pas applicable.

Exercice 2

Pour chacune des équations ci-dessous, trouver la forme disjonctive simplifiée, réaliser la synthèse trois couches avec des portes ET-NON.

$y_{1}=a.(b+c)$ avec 3 portes

$y_{2}=a.b+{\bar {c}}$ avec 2 portes

$y_{3}={\bar {a}}.b+a.c$ avec 4 portes

$y_{4}={\bar {a}}.b+a.{\bar {b}}$ avec 4 portes

$y_{5}=(({\bar {a}}+b).(a+c)+b.c).(a+b+c)$ avec 4 portes

$y_{6}={\bar {a}}.b.{\bar {c}}+a.{\bar {b}}.c$ avec 5 portes