ALGÈBRE DE BOOLE 02 : SIMPLIFICATION ET CIRCUITS

Chapitre 2 sur 2. Construire les formes canoniques, simplifier avec Karnaugh et réaliser des circuits utiles à l’ordinateur.

De la table aux formes canoniques

Ce deuxième cours suppose connus les portes, les propriétés et De Morgan. L’objectif est de transformer une spécification en circuit plus simple, puis de vérifier que la transformation conserve la fonction.

La chaîne de conception

Énoncé → variables et convention 0/1 → table de vérité → forme canonique → simplification → logigramme → vérification.

Minterme : sélectionner une ligne à 1

Un littéral est une variable ou son complément. Un minterme est un produit contenant une fois chacune des variables, complémentée ou non. Il vaut 1 sur une unique ligne de la table.

Sur la ligne 101, avec l’ordre $a,b,c$ , on obtient $a\overline b c$ . Une entrée à 1 donne la variable directe ; une entrée à 0 donne son complément.

m_5=a\overline b c,\qquad 5=(101)_2.

La forme canonique disjonctive est la somme des mintermes des lignes où la sortie vaut 1. À ordre de variables fixé, cet ensemble de mintermes est unique ; l’ordre d’écriture des termes est libre.

f=\sum m(i)\quad\text{pour les indices où }f=1.

Maxterme : sélectionner une ligne à 0

Un maxterme est une somme contenant chaque variable une fois. Il vaut 0 sur une unique ligne. La règle s’inverse : une entrée à 0 donne la variable directe ; une entrée à 1 donne son complément.

M_5=\overline a+b+\overline c.

La forme canonique conjonctive est le produit des maxtermes des lignes où la sortie vaut 0 :

f=\prod M(i)\quad\text{pour les indices où }f=0.

Ne pas confondre canonique et simplifiée.

$f=a+bc$ est une somme de produits, mais pas une forme canonique sur $a,b,c$ : chaque produit ne contient pas les trois variables. Une forme canonique décrit directement la table ; une forme simplifiée réduit le circuit.

Compléter une variable absente

b\overline c=(a+\overline a)b\overline c=ab\overline c+\overline a b\overline c.

La fonction vaut donc 1 aux indices 2 et 6, soit 010 et 110. Elle ne dépend pas réellement de $a$ , même si sa table est écrite avec trois variables.

Cas particuliers : la somme sans minterme vaut 0 ; le produit sans maxterme vaut 1. Il existe $2^{2^n}$ fonctions booléennes à $n$ variables, car chacune des $2^n$ sorties de la table se choisit indépendamment.

Un exemple complet : la fonction étudiée

Reprenons la table suivante. On fixe l’ordre $a,b,c$ , avec $a$ bit de poids fort.

Indice	a	b	c	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	1
3	0	1	1	0
4	1	0	0	1
5	1	0	1	1
6	1	1	0	1
7	1	1	1	0

1. Partir des cinq lignes à 1

F=\sum m(1,2,4,5,6).

F=\overline a\,\overline b c+\overline a b\overline c+a\overline b\,\overline c+a\overline b c+ab\overline c.

2. Partir des trois lignes à 0

F=\prod M(0,3,7)=(a+b+c)(a+\overline b+\overline c)(\overline a+\overline b+\overline c).

À l’indice 3, soit 011, le maxterme est $a+\overline b+\overline c$ : chacun de ses littéraux vaut 0 sur cette ligne. La forme conjonctive est parfois plus courte à construire lorsqu’il y a moins de 0 que de 1.

3. Simplifier algébriquement

Regroupons les indices (1,5), (2,6) et (4,5). Le minterme d’indice 5 est utilisé deux fois, ce qui est autorisé par $x+x=x$ .

\begin{aligned}F&=(\overline a+a)\overline b c+(\overline a+a)b\overline c+a\overline b(\overline c+c)\\&=\overline b c+b\overline c+a\overline b\\&=(b\oplus c)+a\overline b.\end{aligned}

Chaque paire élimine la variable qui change. On peut maintenant réaliser la fonction avec des portes à deux entrées.

Simplifier avec Karnaugh

Une carte de Karnaugh réorganise les lignes d’une table pour rendre les simplifications visibles. Les colonnes suivent le code de Gray : 00, 01, 11, 10. Entre deux cases voisines, une seule variable change.

Règles de regroupement

Pour une somme de produits, regrouper les 1 en rectangles de 1, 2, 4, 8… cases.
Chaque groupe contient uniquement des 1, éventuellement des états indifférents explicitement autorisés.
Les bords opposés sont voisins ; les diagonales ne le sont pas.
Les groupes peuvent se chevaucher. Chaque 1 doit être couvert.
Privilégier les grands groupes et une couverture sans groupe inutile. Comparer les couvertures s’il en existe plusieurs.
Dans un groupe, garder les variables constantes : directe si elle vaut 1, complémentée si elle vaut 0. Éliminer celles qui changent.

Carte de la fonction étudiée

Les cellules portent la sortie et, en petit, leur indice. Les encadrements indiquent les trois paires retenues.

Groupes de Karnaugh : bleu (1,5), ocre (4,5), vert (2,6). Chaque contour entoure une paire entière.

Bleu : (1,5)Ocre : (4,5)Vert : (2,6)

\{1,5\}\to\overline b c,\quad\{4,5\}\to a\overline b,\quad\{2,6\}\to b\overline c.

Les indices 1, 2 et 4 ne peuvent être couverts que par ces paires dans cette carte. Les trois termes sont donc nécessaires pour une couverture minimale en somme de produits :

\boxed{F=\overline b c+a\overline b+b\overline c}.

Exemple à quatre variables : les quatre coins

Pour $G=\sum m(0,2,8,10)$ , lignes $ab$ et colonnes $cd$ sont toutes deux dans l’ordre Gray. Les quatre coins forment un seul groupe, grâce à l’adjacence des bords.

ab \ cd	00	10
00	1	1
01	0	0
11	0	0
10	1	1

Dans ces quatre cases, $a$ et $c$ changent, tandis que $b=0$ et $d=0$ . Ainsi $G=\overline b\,\overline d$ .

Regrouper les 0 pour un produit de sommes

La même méthode fonctionne avec les 0. Pour chaque groupe de 0, écrire une somme qui s’annule sur le groupe : variable directe si elle est constamment à 0 ; complémentée si elle est constamment à 1. Multiplier ensuite les sommes obtenues.

États indifférents

Un état noté X n’est ni un 0 imposé, ni un 1 imposé. On peut l’utiliser comme 0 ou 1 pour agrandir les groupes. Exemple : $H=\sum m(1,3)$ , avec $d=\{5,7\}$ , sur trois variables. Les quatre indices impairs donnent le groupe $c=1$ , donc $H=c$ respecte tous les états imposés.

Un X doit venir de la spécification.

On ne déclare pas une ligne indifférente pour simplifier un calcul. Si une combinaison peut réellement survenir et que sa sortie est exigée, sa valeur doit être respectée.

NAND et NOR : des portes universelles

Un ensemble de portes est fonctionnellement complet s’il permet de réaliser toute fonction booléenne. ET, OU et NON suffisent. NAND seule ou NOR seule suffisent aussi, car elles permettent de reconstruire ces trois opérations.

Avec NAND uniquement

On note $a\uparrow b=\overline{ab}$ .

\begin{aligned}\overline a&=a\uparrow a,\\ab&=(a\uparrow b)\uparrow(a\uparrow b),\\a+b&=(a\uparrow a)\uparrow(b\uparrow b).\end{aligned}

Pour la dernière ligne : $\overline{\overline a\,\overline b}=a+b$ , par De Morgan. Une porte NAND dont les deux entrées sont reliées ensemble joue le rôle d’un inverseur.

Avec NOR uniquement

On note $a\downarrow b=\overline{a+b}$ .

\begin{aligned}\overline a&=a\downarrow a,\\a+b&=(a\downarrow b)\downarrow(a\downarrow b),\\ab&=(a\downarrow a)\downarrow(b\downarrow b).\end{aligned}

Deux niveaux NAND–NAND

Pour une somme de produits $S=p+q$ , une double négation puis De Morgan donnent :

S=\overline{\overline{p+q}}=\overline{\overline p\cdot\overline q}.

Si $p=ab$ et $q=cd$ , deux NAND calculent $\overline{ab}$ et $\overline{cd}$ , puis une troisième NAND produit $S=ab+cd$ . Le principe dual NOR–NOR réalise naturellement un produit de sommes.

NAND et NOR ne sont pas associatives.

On ne peut pas remplacer une porte NAND à trois entrées par une cascade arbitraire de deux NAND : $\overline{abc}\ne\overline{\overline{ab}\,c}$ . Pour $a=b=c=1$ , le premier membre vaut 0 et le second vaut 1.

Construire XOR avec quatre NAND

Le circuit suivant réalise une porte XOR à partir de quatre NAND. Les quatre portes sont des NAND à deux entrées ; les fils marqués d’un point sont connectés.

XOR réalisé avec quatre portes NAND.

Suivre les quatre NAND sans confondre leurs sorties

Première porte : a et b produisent n. La bulle inverse tout le produit : n est nul uniquement pour a = b = 1.
Deuxième niveau : n se divise en deux branches au point plein. La porte du haut reçoit a et n ; celle du bas reçoit n et b. Elles donnent les deux signaux p et q.
Dernière porte : p et q sont réunis par NAND. Sa bulle inverse leur produit, et non chacune des entrées séparément.

Exemple 01 : n = 1, p = 1 et q = 0 ; la dernière NAND fournit 1. Exemple 11 : n = 0, puis p = q = 1 ; la sortie finale vaut 0. Les entrées différentes donnent donc 1, les entrées égales donnent 0.

Les points pleins à gauche partagent a ou b entre deux portes. Le point au centre partage le même signal n : il ne crée pas deux variables différentes. Les lettres intermédiaires servent à vérifier le circuit porte par porte.

n=\overline{ab},\quad p=\overline{an},\quad q=\overline{bn},\quad S=\overline{pq}.

Pourquoi obtient-on XOR ?

\begin{aligned}S&=\overline p+\overline q=an+bn\\&=a(\overline a+\overline b)+b(\overline a+\overline b)\\&=a\overline b+\overline a b=a\oplus b.\end{aligned}

a	b	n	p	q	S
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

Ce circuit utilise quatre portes et trois niveaux sur le plus long chemin. Le nombre de portes et le nombre de niveaux sont deux critères distincts : réduire une expression ne suffit pas à estimer son délai réel.

Applications en architecture des ordinateurs

Le demi-additionneur : additionner deux bits

La somme arithmétique de deux bits produit un bit de somme $s$ et une retenue $r$ .

s=a\oplus b,\qquad r=ab.

a	b	Somme s	Retenue r	Résultat rs
0	0	0	0	00
0	1	1	0	01
1	0	1	0	01
1	1	0	1	10

Un XOR calcule le bit de somme ; un ET calcule la retenue.

Pourquoi deux sorties pour additionner deux bits ?

Les deux portes reçoivent les mêmes entrées, grâce aux dérivations indiquées par des points pleins. Le XOR du haut fournit le bit de poids faible s ; le ET du bas fournit la retenue r, qui occupe le poids suivant.

Pour a = b = 1, le XOR donne s = 0 et le ET donne r = 1. La lecture du résultat se fait dans l’ordre r puis s : on obtient 10 en binaire, soit 2. Pour 01 ou 10, on obtient r = 0 et s = 1, soit 01.

Rappel sur les fils : un point plein relie les branches. Dans ce dessin, un croisement sans point ne relie pas les deux signaux ; a et b restent indépendants. Le demi-additionneur ne possède pas d’entrée de retenue, d’où son nom.

L’additionneur complet : tenir compte d’une retenue entrante

Pour additionner $a,b$ et une retenue d’entrée $c_{in}$ , on relie deux demi-additionneurs :

p=a\oplus b,\quad s=p\oplus c_{in},\quad c_{out}=ab+p\,c_{in}.

La retenue vaut aussi $ab+ac_{in}+bc_{in}$ : elle vaut 1 si au moins deux des trois entrées valent 1. Plusieurs additionneurs complets en chaîne permettent l’addition de mots binaires. Le délai de propagation de la retenue limite la vitesse d’une chaîne simple.

Le multiplexeur 2 vers 1 : choisir une donnée

Avec les entrées de données $d_0,d_1$ et la sélection $s$ :

Y=\overline s\,d_0+s\,d_1.

Si $s=0$ , le premier produit transmet $d_0$ et le second est nul. Si $s=1$ , on obtient $d_1$ . Des multiplexeurs choisissent, par exemple, la donnée envoyée à une entrée d’une unité arithmétique et logique.

Décomposition de Shannon

F(a,b,c)=aF(1,b,c)+\overline a F(0,b,c).

Pour $a=1$ , seul le premier terme reste. Pour $a=0$ , seul le second reste. Cette décomposition montre qu’une fonction peut être réalisée par un multiplexeur commandé par $a$ , dont les données sont les deux fonctions obtenues en fixant $a$ .

Exercices d’application corrigés

Application 1 · Simplifier pas à pas

Simplifier :

S_1=\overline a b+a\overline b+ab,\qquad S_2=b+ab+bc+c.

S_3=(b+\overline b a)c+ab\overline c,\qquad S_4=(a+c)(a+\overline b)(a+\overline c).

Voir le corrigéMasquer le corrigé

\begin{aligned}S_1&=\overline a b+a(\overline b+b)=\overline a b+a=a+b,\\S_2&=(b+ab)+(c+bc)=b+c,\\S_3&=(a+b)c+ab\overline c=ac+bc+ab\overline c\\&=bc+a(c+b\overline c)=bc+a(b+c)=ab+ac+bc,\\S_4&=(a+c)(a+\overline c)(a+\overline b)\\&=(a+c\overline c)(a+\overline b)=a(a+\overline b)=a.\end{aligned}

Pour $S_3$ , les deux identités utilisées sont $b+\overline b a=a+b$ et $c+\overline c b=c+b$ . La sortie simplifiée est la fonction majorité de trois bits.

Application 2 · Deux formes canoniques d’une même fonction

Pour $H=\overline a b+\overline b\,\overline c+ab\overline c$ , établir la table, les deux formes canoniques, puis simplifier.

Voir le corrigéMasquer le corrigé

a	b	c	H
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

La sortie vaut 1 aux indices 0, 2, 3, 4 et 6 ; elle vaut 0 aux indices 1, 5 et 7.

H=\sum m(0,2,3,4,6)=\prod M(1,5,7).

H=\overline a\,\overline b\,\overline c+\overline a b\overline c+\overline a bc+a\overline b\,\overline c+ab\overline c.

H=(a+b+\overline c)(\overline a+b+\overline c)(\overline a+\overline b+\overline c).

Les indices 0, 2, 4 et 6 forment le groupe $\overline c$ . Les indices 2 et 3 forment le groupe $\overline a b$ . On obtient :

H=\overline c+\overline a b.

Une forme canonique conjonctive est toujours un produit de maxtermes. Remplacer un des produits par une somme modifie la fonction.

Application 3 · Universalité de NOR

Exprimer NON, OU et ET uniquement avec NOR. Justifier chaque construction.

Voir le corrigéMasquer le corrigé

Notons $N(x,y)=\overline{x+y}$ .

N(a,a)=\overline a.

N(N(a,b),N(a,b))=\overline{\overline{a+b}+\overline{a+b}}=a+b.

N(N(a,a),N(b,b))=\overline{\overline a+\overline b}=ab.

NON utilise une NOR, OU en utilise deux et ET en utilise trois. Comme toute fonction peut s’écrire avec ET, OU et NON, NOR seule est fonctionnellement complète.

Application 4 · Une simplification symétrique

G=(a+b)(a+c)+(b+c)(b+a)+(c+a)(c+b).

Voir le corrigéMasquer le corrigé

Appliquer trois fois $(x+y)(x+z)=x+yz$ :

G=(a+bc)+(b+ac)+(c+ab)=a+b+c+ab+ac+bc=a+b+c.

Les produits sont absorbés : $a+ab=a$ , $a+ac=a$ , $b+bc=b$ . La sortie ne vaut 0 que si les trois entrées valent 0.

Application 5 · Une lampe automatique

Une lampe doit s’allumer si le mode automatique est actif, s’il fait sombre et si une personne est présente. On note $a=1$ pour le mode automatique, $l=1$ pour une forte luminosité et $p=1$ pour une présence. Écrire son équation et l’indice de son minterme.

Voir le corrigéMasquer le corrigé

L=a\overline l p.

La seule combinaison favorable, dans l’ordre $a,l,p$ , est 101. Donc $L=\sum m(5)$ . La forte luminosité doit être inversée ; le mode automatique et la présence restent directs. Le circuit utilise un inverseur sur $l$ , puis un ET à trois entrées, ou deux ET à deux entrées en cascade.

Vérifier la fonction et son circuit

Deux expressions sont équivalentes si elles ont la même sortie pour toutes les combinaisons d’entrées. Pour trois variables, on compare les huit lignes ; pour quatre, les seize lignes.

Fixer l’ordre des variables et le bit de poids fort avant toute numérotation.
Écrire les sorties intermédiaires du circuit ; une bulle inverse toute la fonction de sa porte.
Contrôler la portée des barres avant d’appliquer De Morgan.
Comparer la table de la spécification, la formule simplifiée et le circuit.
Pour une fonction incomplète, comparer tous les états imposés ; les X peuvent différer.

Mesurer la simplicité avec un objectif clair

Une somme de produits minimale n’est pas nécessairement le meilleur circuit pour une bibliothèque donnée. Comptez les portes, les entrées par porte et les niveaux successifs. Une porte XOR peut réduire le dessin, mais son coût réel dépend de la technologie. Les délais et les transitions physiques ne sont pas représentés par une table de vérité statique.

À retenir

La table définit la fonction. La forme canonique traduit la table. Les propriétés et Karnaugh réduisent l’expression. Le logigramme réalise l’expression. La vérification exhaustive garantit leur accord sur les états spécifiés.