Électronique numérique : logique/Simplification et implantation de formes disjonctives

Nous avons vu au chapitre précédent que les formes algébriques différentes pouvaient être équivalentes. Nous allons à partir de maintenant essayer de faire un peu le tri parmi les formes algébriques intéressantes.

Simplification par Karnaugh

Revenons sur quelques définitions, même si elles ont déjà été utilisées au chapitre précédant. Une équation obtenue à partir d'une table de vérité s'appelle une forme disjonctive ou somme de produits (notée parfois "Σ Π"). Elle est canonique, c'est à dire unique ou non simplifiée.

Les Tableau de Karnaugh permettent de simplifier ces formes disjonctives en regroupant des termes : elles deviennent des formes disjonctives simplifiées (elles sont aussi appelées formes normales disjonctives). Si la forme disjonctive canonique est unique, il peut, par contre, y avoir plusieurs formes disjonctives simplifiées (en fait plus ou moins bien simplifiées). Les tableaux de Karnaugh ont comme objectifs de permettre une simplification facile par des regroupements. Les regroupements sont des carrés ou des rectangles de une, deux, quatre, huit ou seize cases contenants des '1'.

Il y a un exemple de dans Tableau de Karnaugh, mais nous allons en utiliser un autre ici qui a comme intérêt de présenter toutes les spécificités des tableaux de Karnaugh.

Principe : 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. La "ballade" peut être romantique ou pas, au clair de lune ou en plein soleil.... rien n'y changera on appliquera toujours ce principe à la lettre.

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. Attention les regroupements peuvent ne pas être contigus géométriquement. Regardez la forme des regroupements bleu et vert pour comprendre ce que l'on veut dire par là.

Exemple : appliqué à l'exemple ci-contre on obtient facilement

regroupement rouge : $s_{2}=x_{1}\cdot x_{2}\cdot x_{4}$ où x3 s'en va lors d'une "ballade" dans le regroupement rouge.
regroupement vert : $s_{1}={\bar {x_{1}}}\cdot {\bar {x_{4}}}$ car x2 et x3 s'en vont lors d'une ballade dans le rectangle vert
regroupement bleu : $s_{3}={\bar {x_{2}}}\cdot {\bar {x_{4}}}$ car x1 et x3 s'en vont lors d'une ballade dans le rectangle bleu

Le résultat final donnera donc $y=S_{1}+S_{2}+S_{3}=x_{1}\cdot x_{2}\cdot x_{4}+{\bar {x_{1}}}\cdot {\bar {x_{4}}}+{\bar {x_{2}}}\cdot {\bar {x_{4}}}$ .

Remarque : le fait que le résultat final soit un OU entre tous les termes simplifiés est toujours vrai.

Quelques exemples de Tableaux de Karnaugh

Il existe quelques images toutes faites de tableaux de Karnaugh que je ne résiste pas à vous présenter.

Évidemment les regroupements sont déjà montrés. Mais il n'est pas inutile de transformer chacun des regroupements en équations.

premier tableau de Karnaugh :
- rouge ${\bar {B}}\cdot {\bar {D}}$
- vert ${\bar {C}}\cdot D$
- violet ${\bar {A}}\cdot C$
- bleu A.B
- Premier tableau : $y={\bar {B}}\cdot {\bar {D}}+{\bar {C}}\cdot D+A\cdot B+{\bar {A}}\cdot C$
Deuxième tableau de karnaugh
- bleu : ${\bar {A}}$
- rouge : ${\bar {B}}\cdot C$
- vert : ${\bar {B}}\cdot D$
- Deuxième tableau : $y={\bar {A}}+{\bar {B}}\cdot C+{\bar {B}}\cdot D$

Pour le troisième tableaux de Karnaugh on vous demande de trouver l'expression simplifiée correspondante.

Exercice 1

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

Solution de l'exercice 1

$y=c.{\bar {b}}+{\bar {c}}.a$

Traitement des cas indéterminés

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.


Définition
On appelle un cas indéterminé un cas pour lequel la valeur de la sortie nous importe peu. La raison peut être que la combinaison correspondante des entrées n'arrive jamais ou une autre raison. Ils sont ici notés ɸ. On les choisit alors comme cela nous arrange lors des regroupements dans notre tableau de Karnaugh.

En français, cela veut dire que l'on réalise les regroupements les plus grands à partir des 1 en englobant éventuellement un ou plusieurs ɸ. Tout se passe alors comme si les ɸ englobés étaient des '1' et les ɸ laissés de côté étaient des '0'. Et c'est comme cela que réagira le circuit réalisé : pour l'exemple ci-dessous, vous pouvez vous rendre compte à partir de l'équation simplifiée que pour des entrées d=1, c=0, b=0 et a=0 on aura bien y=0 (la case n'est pas dans un regroupement) et non pas y=ɸ.

Pour comprendre ce que l'indétermination n'est pas : y=ɸ voudrait-il dire ici que les jours pluvieux on a y=0 et que les jours de beaux temps on a y=1 et qu'on laisse de côté les jours de brouillard où le circuit ne sait plus quoi faire ! Si vous avez un circuit qui fonctionne comme cela, mettez-le à la poubelle. Si vous en êtes le concepteur, vous n'arriverez jamais à le vendre, sauf peut être à la météo.

Exemple : Voici un tableau de Karnaugh présentant un exemple.

$y=a.c+a.{\bar {b}}.{\bar {d}}+{\bar {a}}.b.{\bar {c}}$ est la forme algébrique simplifiée obtenue à partir du tableau de Karnaugh.

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).

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). À ce stade on utilise les inverseurs comme on le veut et on ne se pose pas de question sur le nombre d'entrées des portes. Ce schéma est absolument naturel et ne demande pas de profonde réflexion.
On transforme le OU final en ET-NON (c'est de Morgan schématique) en faisant glisser les inverseurs de ses entrées (du nouveau ET-NON) vers l'étage précédant. Cela a comme conséquence de transformer les ET de l'étage précédant en ET-NON.
On transforme pour finir les inverseurs en ET-NON en reliant les deux entrées ensembles.

Le schéma obtenu est alors en trois couches ET-NON qui utilise des portes à nombre d'entrées illimité. Pourquoi trois couches ? Parce que si vous partez des entrez pour aller vers la sortie vous traversez parfois deux portes parfois trois. Le nombre de couches est le plus grand de ces nombres.

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 :

qui vous permettront de réaliser le schéma qui aura, sauf cas exceptionnel, plus de trois couches.

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). Mais, comme chacun sait, la simplicité ne fait pas partie du monde technique.

Montrons sur deux exemples que ce n'est pas toujours vrai, qu'il faut parfois éviter les formes disjonctives :

Cette figure montre qu'en partie supérieure, un gain de deux portes peut être obtenu si au lieu de faire le schéma à partir de la forme disjonctive simplifiée $a.{\bar {b}}+a.{\bar {c}}$ on le fait à partir d'une forme simplifiée mais qui n'est pas disjonctive $a.({\overline {b.c}})$ . Le gain d'une porte en partie inférieure se produit si au lieu d'implanter la forme disjonctive ${\bar {a}}.b+a.{\bar {b}}.c$ on implante $a.({\overline {a.b}})+a.({\overline {a.b}}).c$ .

Remarque : Après toute synthèse en ET-NON, il faudrait chercher si une des deux optimisations ci-dessus est applicable.

Conclusion : Gardez en tête que toute forme disjonctive simplifiée conduit au schéma le plus simple même si, comme on l'a montré, ce n'est pas toujours vrai. Il ne faut pas oublier, qu'à notre époque, l'informatique peut aider à résoudre ce genre de problèmes. On laissera donc tomber les optimisations, sauf pour l'exercice qui suit. Il sera toujours temps de revenir sur ces optimisations si votre métier est de réaliser, à longueur de journée, des schémas en portes ET-NON.