Circuits logiques

Un processeur récent compte des dizaines de milliards de transistors. Ce nombre décourage, et il ne devrait pas : la variété des briques, elle, tient sur une page. Quelques portes logiques, un additionneur, un multiplexeur, un décodeur, une bascule — et tout le reste est de la répétition et de l'assemblage.

Ce chapitre est la charnière du cours. Le chapitre 3 a donné l'algèbre ; on la câble ici. Le chapitre 5 posera l'architecture du processeur ; ses unités seront faites de ce qu'on construit maintenant. Et le TP prend tout son sens ici : monter un additionneur porte par porte dans Logisim, puis écrire la même addition en assembleur au chapitre 6, est ce qui relie concrètement les deux moitiés du semestre.

Les portes, et la seule qui compte vraiment

Une porte logique est un circuit qui réalise un opérateur booléen. Les trois de base — ET, OU, NON — se complètent de trois formes niées, NAND, NOR et XOR, plus utiles en pratique que leurs cousines directes.

Le fait remarquable du chapitre est que le NAND est universel : on construit toute fonction booléenne avec des NAND seuls. La démonstration tient en trois lignes, et De Morgan en est la clé.

1NON a    = NAND(a, a)2a ET b   = NON( NAND(a, b) )        = NAND( NAND(a,b), NAND(a,b) )3a OU b   = NAND( NON a, NON b )     par De Morgan

Ce n'est pas une curiosité théorique. En technologie CMOS, la porte naturelle est justement inverseuse : un NAND coûte quatre transistors, un ET en coûte six — un NAND suivi d'un inverseur. Les bibliothèques de cellules sont donc bâties sur NAND et NOR, et une conception qui les ignore paie ses portes plus cher qu'il ne faut.

Combinatoire : la sortie ne dépend que des entrées

Un circuit est combinatoire quand sa sortie est entièrement déterminée par ses entrées courantes. Pas de mémoire, pas d'histoire : mêmes entrées, même sortie, toujours.

Le demi-additionneur, puis l'additionneur complet

Additionner deux bits produit une somme et une retenue. La table est celle du chapitre 1 :

La colonne somme vaut 1 quand les entrées diffèrent : c'est un XOR. La colonne retenue vaut 1 quand les deux valent 1 : c'est un ET. Deux portes, et voilà le demi-additionneur — ainsi nommé parce qu'il lui manque l'essentiel : il ne sait pas recevoir la retenue de la colonne précédente.

L'additionneur complet prend trois entrées, $a$, $b$ et la retenue entrante $r_e$ :

Regardez la seconde expression : c'est exactement la fonction majorité simplifiée au Karnaugh du chapitre 3. Il y a une retenue sortante dès que deux des trois entrées valent 1, ce qui est intuitif — additionner trois bits donne 2 ou 3 dès que deux d'entre eux sont à 1.

De un bit à $n$ : l'additionneur à propagation

Pour additionner deux mots de 8 bits, on chaîne huit additionneurs complets, la retenue sortante de chacun alimentant la retenue entrante du suivant. C'est l'additionneur à propagation de retenue (ripple-carry), et c'est le circuit du TP.

Il a un défaut, et ce défaut gouverne toute l'architecture qui suit : la retenue doit traverser les huit étages avant que le dernier bit soit correct. Le temps de calcul est proportionnel au nombre de bits. Sur 64 bits, c'est intenable — d'où les additionneurs à anticipation de retenue, qui calculent les retenues en parallèle, plus rapides et plus gourmands en portes. C'est le premier compromis surface/vitesse du cours, et il ne sera pas le dernier.

Et la soustraction ? Le chapitre 2 a déjà répondu : $a - b = a + (-b)$, et $-b$ s'obtient en inversant les bits de $b$ puis en ajoutant 1. Concrètement, on place un XOR sur chaque bit de $b$ commandé par un signal $M$, et on injecte ce même $M$ comme retenue entrante du premier étage. $M = 0$ : le circuit additionne. $M = 1$ : il soustrait. Le même additionneur fait les deux, pour le prix de huit portes XOR — c'est là que le choix du complément à deux se paie en silicium économisé.

Multiplexeur, décodeur, comparateur

Trois autres briques reviennent partout.

Le multiplexeur est un aiguillage : $2^k$ entrées de données, $k$ entrées de commande, une sortie qui recopie l'entrée désignée. Le plus simple, à deux entrées, s'écrit $s = \bar{c}\,e_0 + c\,e_1$. C'est le composant qui, au chapitre 5, choisira si l'unité de calcul reçoit un registre ou une valeur immédiate.

Le décodeur fait l'inverse : $k$ entrées, $2^k$ sorties, et une seule sortie active, celle dont le numéro est écrit en binaire sur les entrées. C'est ainsi qu'une adresse sélectionne une case mémoire, et qu'un code d'opération active la bonne commande.

Le comparateur teste l'égalité de deux mots. Deux bits sont égaux quand leur XOR vaut 0 ; deux mots sont égaux quand tous leurs XOR valent 0, ce qui s'écrit avec un NOR final. La comparaison d'ordre demande davantage de logique, et se ramène souvent à une soustraction dont on lit le signe — encore le même additionneur.

Séquentiel : quand le circuit se souvient

Tout ce qui précède oublie instantanément. Or un processeur doit retenir : le contenu d'un registre, la valeur d'un compteur, l'adresse de la prochaine instruction. Il faut un circuit dont la sortie dépende aussi de son état passé. On l'obtient par un moyen simple et troublant : reboucler une sortie sur une entrée.

La bascule RS est le cas fondateur : deux portes NOR croisées, chacune recevant la sortie de l'autre. Trois comportements. Mettre $S$ (set) à 1 force la sortie à 1. Mettre $R$ (reset) à 1 la force à 0. Et laisser les deux à 0 conserve l'état — c'est là qu'il y a mémoire, dans le simple fait que la boucle s'auto-entretient. La combinaison $R = S = 1$ est interdite : elle produit un état incohérent, et l'issue dépend de qui retombe à 0 en premier.

Une bascule RS réagit dès que ses entrées bougent, ce qui est ingérable dans un circuit complexe. On la discipline avec une horloge, signal carré qui rythme tout le système, et l'on obtient la bascule D : une entrée de donnée, une entrée d'horloge, et la sortie qui recopie l'entrée au moment décidé par l'horloge.

Ce moment fait toute la différence. Une bascule sur niveau (latch) est transparente tant que l'horloge est haute : la sortie suit l'entrée, ce qui peut faire traverser plusieurs étages en un seul cycle. Une bascule sur front ne prend en compte l'entrée qu'à l'instant précis où l'horloge monte, puis se verrouille. C'est celle qu'on emploie partout, parce qu'elle rend le circuit prévisible : à chaque front, tout l'état bascule d'un coup vers sa valeur suivante, et ce qui se passe entre deux fronts n'a aucune importance.

D'où la contrainte qui fixe la fréquence d'une machine, et que le chapitre 5 reprendra : entre deux fronts, il faut que le plus long chemin combinatoire — le chemin critique, la propagation de la retenue par exemple — ait eu le temps de se stabiliser. La période d'horloge est dictée par le circuit le plus lent, pas par le plus rapide.

Registres et compteurs

À partir de la bascule D, deux assemblages suffisent.

Un registre de $n$ bits est un paquet de $n$ bascules D partageant la même horloge et le même signal d'écriture. Tous les bits basculent ensemble, ce qui est indispensable : un registre dont les bits changeraient à des instants différents laisserait lire des valeurs qui n'ont jamais existé. Un registre à décalage relie en plus la sortie de chaque bascule à l'entrée de la suivante, et décale son contenu d'un rang à chaque front — c'est le décalage qui multiplie ou divise par deux du chapitre 1, réalisé en fils plutôt qu'en calcul.

Un compteur est un registre bouclé sur un incrémenteur : à chaque front, il ajoute 1 à son propre contenu. Sur $n$ bits, il compte modulo $2^n$ et revient à zéro — le tour de compteur du chapitre 2, sous sa forme matérielle. C'est directement le compteur ordinal du chapitre 5, celui qui contient l'adresse de la prochaine instruction et qui s'incrémente à chaque cycle.

À vous

L'exercice construit l'additionneur du TP, mais en JavaScript et à partir des portes seules : un additionneur complet, puis huit en cascade, puis l'astuce du XOR commandé qui transforme l'additionneur en soustracteur.

Le jeu de tests reprend volontairement les cas du chapitre 2 — $100 + 50$ et $-128$ — pour que le circuit reproduise, à la porte près, les débordements que le codage annonçait.

// Les portes. On ne s'autorise rien d'autre : pas de +, pas de -.
const NON = (a) => a ^ 1;
const ET  = (a, b) => a & b;
const OU  = (a, b) => a | b;
const XOR = (a, b) => a ^ b;

// Additionneur complet : trois bits en entrée, somme et retenue en sortie.
function additionneurComplet(a, b, re) {
  const s = XOR(XOR(a, b), re);
  const rs = 0;              // ← à écrire : la fonction majorité de a, b, re
  return { s, rs };
}

const N = 8;
const versBits = (n) => Array.from({ length: N }, (_, i) => (n >> i) & 1); // [poids faible…]
const versNombre = (bits) => bits.reduce((n, b, i) => n + b * (1 << i), 0);

// Additionneur n bits à propagation de retenue, avec entrée de commande M.
// M = 0 : calcule a + b.  M = 1 : doit calculer a − b.
function additionner(a, b, M) {
  const A = versBits(a), B = versBits(b);
  const S = [];
  let retenue = 0;           // ← que doit valoir la retenue entrante si M = 1 ?
  for (let i = 0; i < N; i++) {
    const bi = B[i];         // ← et que doit devenir ce bit si M = 1 ?
    const { s, rs } = additionneurComplet(A[i], bi, retenue);
    S.push(s);
    retenue = rs;
  }
  return { motif: versNombre(S), retenueSortante: retenue };
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez rs dans additionneurComplet (majorité : ab + a·re + b·re).
// 2. Faites soustraire le circuit : inverser chaque bit de B par un XOR
//    commandé par M, et injecter M comme retenue entrante initiale.

const signe = (m) => (m >= 128 ? m - 256 : m);
const CAS = [
  { a: 11,  b: 7,   M: 0 },
  { a: 100, b: 50,  M: 0 },
  { a: 5,   b: 5,   M: 1 },
  { a: 3,   b: 10,  M: 1 },
  { a: 255, b: 1,   M: 0 },
];

for (const c of CAS) {
  const r = additionner(c.a, c.b, c.M);
  const attendu = c.M === 0 ? c.a + c.b : c.a - c.b;
  const lu = signe(r.motif);
  const ok = lu === attendu || r.motif === (attendu & 255) ? "  ok" : "  X";
  console.log(
    (c.a + (c.M ? " - " : " + ") + c.b).padEnd(12) +
    "motif " + r.motif.toString(2).padStart(8, "0") +
    "  non signé " + String(r.motif).padStart(3) +
    "  signé " + String(lu).padStart(4) + ok
  );
}

const NON = (a) => a ^ 1;
const ET  = (a, b) => a & b;
const OU  = (a, b) => a | b;
const XOR = (a, b) => a ^ b;

function additionneurComplet(a, b, re) {
  const s = XOR(XOR(a, b), re);
  // La retenue sortante est la fonction majorité des trois entrées : il y a
  // report dès que deux d'entre elles valent 1. C'est l'expression obtenue
  // au tableau de Karnaugh du chapitre 3.
  const rs = OU(OU(ET(a, b), ET(a, re)), ET(b, re));
  return { s, rs };
}

const N = 8;
const versBits = (n) => Array.from({ length: N }, (_, i) => (n >> i) & 1);
const versNombre = (bits) => bits.reduce((n, b, i) => n + b * (1 << i), 0);

function additionner(a, b, M) {
  const A = versBits(a), B = versBits(b);
  const S = [];
  // M sert deux fois : il inverse B et il fournit le « + 1 » du complément
  // à deux, gratuitement, par la retenue entrante du premier étage.
  let retenue = M;
  for (let i = 0; i < N; i++) {
    const bi = XOR(B[i], M);
    const { s, rs } = additionneurComplet(A[i], bi, retenue);
    S.push(s);
    retenue = rs;
  }
  return { motif: versNombre(S), retenueSortante: retenue };
}

const signe = (m) => (m >= 128 ? m - 256 : m);
const CAS = [
  { a: 11,  b: 7,   M: 0 },
  { a: 100, b: 50,  M: 0 },
  { a: 5,   b: 5,   M: 1 },
  { a: 3,   b: 10,  M: 1 },
  { a: 255, b: 1,   M: 0 },
];

for (const c of CAS) {
  const r = additionner(c.a, c.b, c.M);
  const attendu = c.M === 0 ? c.a + c.b : c.a - c.b;
  const lu = signe(r.motif);
  const ok = lu === attendu || r.motif === (attendu & 255) ? "  ok" : "  X";
  console.log(
    (c.a + (c.M ? " - " : " + ") + c.b).padEnd(12) +
    "motif " + r.motif.toString(2).padStart(8, "0") +
    "  non signé " + String(r.motif).padStart(3) +
    "  signé " + String(lu).padStart(4) + ok
  );
}

// 100 + 50 : le motif tient sur 8 bits, aucune retenue ne sort, et pourtant
// la lecture signée donne −106. 255 + 1 : la retenue sort, et le motif
// retombe à 0. Deux débordements de natures différentes, comme au ch. 2.

En travaux pratiques

demi-additionneur          additionneur complet
S = A XOR B                S = A XOR B XOR Cin
C = A ET  B                Cout = (A ET B) + (A ET Cin) + (B ET Cin)
                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                la fonction MAJORITÉ du TP 3

15 + 1 :  1111 + 0001 = 0000, Cout = 1

profondeur : le bit de poids fort attend la retenue du rang 2,
qui attend celle du rang 1, qui attend celle du rang 0
→ 4 × 2 = 8 portes traversées, en série

entrée SUB (0 = addition, 1 = soustraction)

chaque bit de B passe par :  Bi XOR SUB
                               SUB=0 → Bi inchangé
                               SUB=1 → Bi inversé
retenue initiale Cin = SUB

SUB=1 : A + (non B) + 1 = A + (-B) = A - B

Z = NON(S3 + S2 + S1 + S0)        résultat nul
V = C3 XOR C4                      débordement SIGNÉ

7 + 1 sur 4 bits signés :
0111 + 0001 = 1000 = -8
Cout = 0   (aucune retenue sortante)
V    = 1   (retenue entrante du dernier rang ≠ sortante)

bascule D : recopie D sur Q au FRONT MONTANT de l'horloge,
          et la conserve entre deux fronts

registre 4 bits = 4 bascules D partageant la même horloge

compteur : entrée du registre ← UAL(sortie du registre, 1, ADD)
         la sortie revient en entrée : une BOUCLE

Ce que la suite en fait

Les briques de ce chapitre se retrouvent une à une dans le processeur du chapitre 5. Le registre devient le banc de registres et le compteur ordinal ; le décodeur devient la sélection d'une case mémoire et le décodage du code d'opération ; le multiplexeur choisit les entrées de l'unité arithmétique et logique, qui n'est elle-même qu'un additionneur entouré de quelques portes ; et l'horloge devient la fréquence affichée sur la fiche technique.

Le chemin critique, lui, ressortira deux fois : au chapitre 5 pour expliquer pourquoi un cycle dure ce qu'il dure, et au chapitre 8 pour expliquer ce que le pipeline gagne en le découpant.

À retenir