Portes logiques

Le chapitre précédent a montré comment un signal analogique, une fois numérisé, se réduit à une suite d'entiers manipulés par le calculateur. Reste à comprendre comment une machine matérialise physiquement ces nombres et les opérations qu'on leur applique. La réponse tient en un principe d'une sobriété radicale : tout se ramène à deux états — présence ou absence de tension — et à quelques opérations élémentaires sur ces états. C'est l'objet de l'électronique logique, socle commun de tout ordinateur.

Ce chapitre, à la saveur informatique propre à la filière MPI, décrit d'abord la manière dont on encode un bit par une tension, puis l'interrupteur commandé — le transistor MOS en commutation — brique physique à partir de laquelle on construit les portes logiques. On établira ensuite l'algèbre qui gouverne ces portes, l'algèbre de Boole, avec ses lois de De Morgan et la remarquable universalité des portes NAND et NOR. On saura enfin passer d'une table de vérité — la description exhaustive d'une fonction — à un circuit combinatoire qui la réalise, et l'on illustrera cette démarche par deux composants emblématiques : le demi-additionneur et le multiplexeur.

Ce que demande le programme de physique de MPI. Il demande de déterminer la table de vérité d'une association d'interrupteurs commandés par une tension et d'identifier par sa table de vérité la porte logique réalisée, pour les portes NOT, AND, OR, NAND, NOR (à deux ou plusieurs entrées) et XOR, et, en travaux pratiques, de mettre en œuvre des montages utilisant des portes logiques. Il se limite à des systèmes comportant un nombre raisonnable de composants, et déclare hors programme la connaissance des circuits électroniques qui constituent les portes : l'étude reste au niveau du modèle idéal (interrupteur parfait, porte sans délai sauf mention contraire). Les lois de De Morgan et le lien entre table de vérité et forme normale disjonctive complète relèvent du programme d'informatique de MP2I-MPI : on les emploie comme des acquis. La simplification algébrique des expressions, le demi-additionneur et le multiplexeur sont des compléments, absents du programme de physique (et, pour les deux circuits, de celui d'informatique, qui exclut l'architecture des ordinateurs).

3.1 Signaux logiques

3.1.1 Codage d'un bit par une tension

Un signal logique ne prend que deux valeurs, notées $0$ et $1$. Physiquement, ces deux symboles correspondent à deux plages de tension séparées par une zone interdite, ce qui confère à l'information numérique son immunité au bruit : une petite perturbation ne fait pas basculer l'état lu.

3.1.2 Notion de front

L'information ne réside pas seulement dans le niveau instantané, mais aussi dans ses transitions.

3.2 L'interrupteur commandé

3.2.1 Le transistor MOS en commutation

Toutes les portes logiques se construisent à partir d'un unique composant élémentaire : un interrupteur commandé par une tension. Le transistor MOS (métal-oxyde-semiconducteur) joue ce rôle. On n'en retient ici qu'un modèle idéalisé, sans entrer dans la physique du semi-conducteur.

3.2.2 Association d'interrupteurs et logique câblée

En associant des interrupteurs commandés entre l'alimentation $V_{DD}$ et la masse, on impose au nœud de sortie un niveau haut ou bas selon les commandes : c'est le principe de toute porte. Le raisonnement typique consiste à établir la table de vérité d'une association série/parallèle.

3.3 Les portes logiques

Une porte logique réalise une fonction booléenne : à un ou plusieurs bits d'entrée elle associe un bit de sortie. On décrit chaque porte par trois éléments indissociables : son symbole normalisé, sa table de vérité et son expression booléenne.

3.3.1 La porte NOT (inverseur)

3.3.2 Les portes AND et OR

3.3.3 Les portes NAND et NOR

Ce sont les compléments des précédentes : on ajoute une bulle d'inversion en sortie.

3.3.4 Les portes XOR et XNOR

3.4 Algèbre de Boole

Les fonctions logiques obéissent à une algèbre à deux éléments $\{0,1\}$, introduite par George Boole. Sa maîtrise permet de simplifier les expressions et donc de réduire le nombre de portes d'un circuit. Les lois de De Morgan sont un acquis du programme d'informatique de MP2I-MPI (qui note $\wedge$, $\vee$, $\neg$ ce que l'on note ici $\cdot$, $+$ et la barre) ; la simplification systématique des expressions est un complément.

3.4.1 Les lois de De Morgan

Démonstration (Vérification par table de vérité)

On dresse la table des deux membres de la première loi :

$a$	$b$	$\overline{a\cdot b}$	$\overline{a}+\overline{b}$
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

Les deux colonnes coïncident ligne à ligne : l'égalité est établie. La seconde loi s'obtient en échangeant les rôles de $+$ et $\cdot$ (principe de dualité).

3.4.2 Universalité de NAND et de NOR

Démonstration (NOT, AND et OR à partir de NAND)

Notons $\text{NAND}(x,y)=\overline{x\cdot y}$.

• NOT : en reliant les deux entrées, $\text{NAND}(a,a)=\overline{a\cdot a}=\overline{a}$.
• AND : $a\cdot b=\overline{\overline{a\cdot b}}=\text{NOT}(\text{NAND}(a,b))$, soit une NAND suivie d'une NAND-inverseur : deux portes.
• OR : par De Morgan, $a+b=\overline{\overline{a}\cdot \overline{b}}=\text{NAND}(\overline{a},\overline{b})$. On inverse d'abord $a$ et $b$ (deux NAND-inverseurs), puis on applique une NAND : trois portes.

Toute expression booléenne, écrite comme somme de produits, se traduit donc en un réseau de NAND. Le résultat pour NOR s'obtient de la même façon, en échangeant les rôles de $\cdot$ et $+$ : $\overline{a}=\overline{a+a}$, $a+b=\overline{\overline{a+b}}$ et $a\cdot b=\overline{\overline{a}+\overline{b}}$.

Ce n'est pas l'universalité qui fait préférer NAND et NOR dans les circuits intégrés, mais la structure des montages : une association d'interrupteurs reliée à une résistance de rappel, ou à un réseau complémentaire, réalise naturellement une fonction inverseuse (voir les exercices résolus) ; une porte AND s'obtient en ajoutant un inverseur à une NAND, ce qui coûte un étage et un délai de plus.

3.5 Synthèse d'une fonction logique combinatoire

Un circuit combinatoire produit une sortie qui ne dépend que de l'état présent des entrées (sans mémoire). Sa spécification complète est sa table de vérité ; le problème de synthèse consiste à en déduire un circuit de portes.

Démonstration

La table de vérité : $m=1$ pour $(a,b,c)\in \{(0,1,1),(1,0,1),(1,1,0),(1,1,1)\}$. La forme canonique somme de produits est

$$m=\overline{a}bc+a\overline{b}c+ab\overline{c}+abc.$$

On regroupe astucieusement en réutilisant $abc$ (idempotence : $abc=abc+abc+abc$) :

$$m=(ab\overline{c}+abc)+(a\overline{b}c+abc)+(\overline{a}bc+abc)=ab(\overline{c}+c)+ac(\overline{b}+b)+bc(\overline{a}+a).$$

Comme $x+\overline{x}=1$, il vient la forme minimale

$$\boxed{m=ab+bc+ca.}$$

Trois portes AND et une porte OR à trois entrées suffisent, au lieu des quatre AND à trois entrées de la forme canonique.

3.6 Exemples de circuits combinatoires

Cette section est un complément : ni le demi-additionneur ni le multiplexeur ne figurent au programme. Le multiplexeur 2 vers 1 se rencontre pourtant naturellement comme association d'interrupteurs : un aiguillage commandé par $c$ relie la sortie à l'entrée $e_0$ si $c=0$, à l'entrée $e_1$ si $c=1$.

3.6.1 Le demi-additionneur

Démonstration

L'addition binaire d'un bit : $0+0=0$, $0+1=1$, $1+0=1$, $1+1=10$ (somme $0$, retenue $1$). D'où la table :

$a$	$b$	$s$ (somme)	$r$ (retenue)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

On reconnaît immédiatement

$$\boxed{s=a\oplus b,r=a\cdot b.}$$

La somme est un OU exclusif, la retenue un ET. Le circuit est donc une porte XOR et une porte AND partageant les mêmes entrées :

3.6.2 Le multiplexeur

Démonstration

La sortie recopie $e_0$ quand $c=0$ et $e_1$ quand $c=1$. On sélectionne chaque voie par un ET avec $c$ (ou son complément), puis on combine par un OU :

$$\boxed{s=\overline{c}{e}_0+c{e}_1.}$$

Vérification : si $c=0$, $\overline{c}=1$ donc $s=e_0$ ; si $c=1$, $s=e_1$. Le multiplexeur est le composant d'aiguillage universel : associé à des mémoires, il fonde le routage des données dans un processeur.