En 1937, un étudiant du MIT de vingt et un ans rend un mémoire de maîtrise. Claude Shannon y remarque que l'algèbre publiée par George Boole en 1854 pour formaliser le raisonnement décrit exactement le comportement des circuits à relais des centraux téléphoniques : un relais ouvert ou fermé, une proposition fausse ou vraie, même algèbre. Le mémoire a été appelé le plus important du siècle, et il n'exagère qu'un peu — c'est lui qui autorise à calculer un circuit au lieu de le bricoler.

Ce chapitre est cette algèbre. Le chapitre 4 la câblera en portes ; ici, on apprend à poser une fonction logique, à la simplifier, et à savoir quand deux écritures différentes désignent le même circuit. La simplification n'est pas une coquetterie : chaque terme éliminé est une porte en moins, donc de la surface de silicium, de la consommation et du délai en moins.

Trois opérateurs, trois tables

Une variable booléenne ne prend que deux valeurs, 0 et 1. Trois opérateurs suffisent à tout décrire.

Les notations empruntent à l'arithmétique — produit pour le ET, somme pour le OU — et le parallèle tient tant qu'on ne l'étire pas : $1 + 1 = 1$ en logique, pas 2. Le OU booléen est inclusif : « l'un, l'autre, ou les deux ». Le « ou bien » exclusif du langage courant est un quatrième opérateur, le OU exclusif noté $a \oplus b$, vrai quand les entrées diffèrent. On le retrouvera partout au chapitre 4 : c'est la somme de l'additionneur, et le détecteur d'égalité du comparateur.

Une fonction booléenne de $n$ variables associe 0 ou 1 à chacune des $2^n$ combinaisons d'entrée. Sa table de vérité est donc de taille finie, ce qui a une conséquence forte : deux expressions sont équivalentes si et seulement si elles ont la même table, et cela se vérifie exhaustivement. Aucune autre branche des mathématiques n'offre un test d'égalité aussi brutal.

Les propriétés, et les deux qui surprennent

Beaucoup de règles sont celles de l'arithmétique : commutativité, associativité, distributivité du ET sur le OU, éléments neutres ($a \cdot 1 = a$, $a + 0 = a$) et absorbants ($a \cdot 0 = 0$, $a + 1 = 1$).

Trois s'en écartent, et ce sont celles qui font tout le travail.

L'idempotence : $a + a = a$ et $a \cdot a = a$. Un terme répété ne compte qu'une fois.

La distributivité du OU sur le ET : $a + (b \cdot c) = (a+b) \cdot (a+c)$. Elle n'a aucun équivalent arithmétique — $2 + (3 \times 4) \neq (2+3) \times (2+4)$ — et c'est elle qui rend l'algèbre de Boole duale : toute identité reste vraie en échangeant simultanément ET avec OU et 0 avec 1.

L'absorption : $a + (a \cdot b) = a$. Si $a$ suffit, préciser « $a$ et $b$ » n'apporte rien. C'est la règle qui élimine le plus de termes à la main.

Restent les théorèmes de De Morgan, les plus utiles du chapitre :

En français : la négation d'un ET est le OU des négations, et réciproquement. « Il est faux que la porte soit fermée et l'alarme active » équivaut à « la porte est ouverte ou l'alarme est inactive ». La faute classique consiste à distribuer la barre sans changer l'opérateur, et elle donne un circuit faux — pas seulement inélégant.

De Morgan a une conséquence pratique majeure, exploitée au chapitre 4 : le NON-ET (NAND) est universel. Toute fonction booléenne se construit avec des NAND seuls, et c'est pourquoi les technologies de fabrication en font leur brique de base.

Les formes canoniques

Toute fonction, si tordue soit son énoncé, s'écrit mécaniquement à partir de sa table de vérité. C'est ce qui permet de partir d'un cahier des charges en français et d'arriver à un circuit sans intuition.

La forme canonique disjonctive, dite somme de produits, se lit sur les lignes où la fonction vaut 1. Pour chacune, on écrit le produit de toutes les variables — barrées si elles valent 0 sur cette ligne — puis on fait le OU de ces produits. Chaque produit s'appelle un minterme.

Prenons la fonction « majorité » de trois variables, vraie dès que deux entrées au moins valent 1 — c'est le vote majoritaire des systèmes redondants, et la retenue sortante de l'additionneur du chapitre 4.

La forme conjonctive, ou produit de sommes, est la duale : elle se lit sur les lignes à 0, chaque ligne donnant une somme dont les variables sont barrées si elles valent 1. On la préfère quand la fonction est majoritairement vraie — il y a alors moins de lignes à écrire.

Ces formes ont une vertu et un défaut. La vertu : elles sont automatiques, donc jamais fausses. Le défaut : elles sont grosses. Quatre mintermes de trois variables, c'est quatre portes ET à trois entrées plus une porte OU à quatre entrées — là où la fonction majorité s'écrit en réalité $ab + ac + bc$, trois portes ET à deux entrées.

Simplifier par tableau de Karnaugh

On peut simplifier à l'algèbre, mais c'est long et l'on ne sait jamais si l'on a fini. Le tableau de Karnaugh rend la simplification visuelle et permet de la mener jusqu'au bout.

Le tableau est une table de vérité repliée en deux dimensions, dont les en-têtes suivent un code de Gray : 00, 01, 11, 10. Ce n'est pas une coquetterie d'ordre — c'est le cœur de la méthode. Dans cet ordre, deux cases voisines ne diffèrent que par une seule variable, donc leur regroupement élimine cette variable : $ab + a\bar{b} = a(b + \bar{b}) = a$.

Voici la fonction majorité, avec $a$ en ligne et $bc$ en colonne :

La méthode tient en quatre règles.

1. On entoure des rectangles de 1 dont la taille est une puissance de 2 : 1, 2, 4, 8 cases. Jamais 3, jamais 6.
2. On les prend aussi grands que possible : un groupe de $2^k$ cases élimine $k$ variables.
3. Les groupes peuvent se chevaucher — l'idempotence l'autorise, $a + a = a$.
4. Le tableau est torique : les bords gauche et droit sont adjacents, de même que le haut et le bas. C'est l'oubli le plus fréquent, et il coûte systématiquement un terme.

Sur la majorité, trois groupes de deux cases suffisent : la colonne 11 donne $bc$, la paire (1,01)-(1,11) donne $ac$, la paire (1,11)-(1,10) donne $ab$. D'où :

On est passé de quatre termes de trois variables à trois termes de deux. Il faut couvrir tous les 1 et aucun 0 ; un groupe entièrement recouvert par les autres est inutile et se retire.

Deux remarques de terrain. Le Karnaugh reste lisible jusqu'à quatre variables, tolérable à cinq, inutilisable au-delà — les outils de synthèse emploient alors des algorithmes comme Quine-McCluskey. Et lorsque certaines combinaisons d'entrée ne peuvent pas se produire, on note leur sortie « indifférente » et on s'autorise à les compter comme des 1 quand cela agrandit un groupe, comme des 0 sinon : c'est gratuit, et cela simplifie beaucoup.

À vous

L'exercice construit la table de vérité d'une expression, puis compare deux écritures. C'est l'outil qui manque le plus en TD : il transforme « je crois que c'est équivalent » en preuve, puisque l'exhaustivité sur $2^n$ lignes est un test complet.

Vous vérifierez d'abord De Morgan, puis la simplification de la fonction majorité obtenue au Karnaugh — et enfin une simplification volontairement fausse, pour voir la table diverger.

// Une fonction booléenne de n variables est ici une fonction JS qui reçoit
// un tableau de 0/1. On énumère les 2^n entrées et on compare les sorties.

function table(f, n) {
  const lignes = [];
  for (let m = 0; m < (1 << n); m++) {
    // Bit de poids fort = première variable, pour lire comme au tableau.
    const e = [];
    for (let i = n - 1; i >= 0; i--) e.push((m >> i) & 1);
    lignes.push({ e, s: f(e) ? 1 : 0 });
  }
  return lignes;
}

function equivalentes(f, g, n, nom) {
  const tf = table(f, n), tg = table(g, n);
  const ecarts = tf.filter((l, i) => l.s !== tg[i].s);
  console.log(nom + " : " + (ecarts.length === 0 ? "équivalentes" : "DIFFÉRENTES"));
  for (const l of ecarts) {
    console.log("   contre-exemple " + l.e.join("") + " -> " +
                l.s + " contre " + tg[table(g, n).indexOf(l)]);
  }
  return ecarts.length === 0;
}

// ── De Morgan ─────────────────────────────────────────────────────────────
const gauche = ([a, b]) => !(a && b);
const droite = ([a, b]) => !a || !b;
equivalentes(gauche, droite, 2, "De Morgan  non(a.b) = na + nb");

// ── Majorité : forme canonique contre forme simplifiée ────────────────────
// Vraie dès que deux entrées au moins valent 1.
const canonique = ([a, b, c]) =>
  (!a && b && c) || (a && !b && c) || (a && b && !c) || (a && b && c);

const simplifiee = ([a, b, c]) => (a && b) || (a && c);   // ← il manque un terme

equivalentes(canonique, simplifiee, 3, "Majorité");

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Le Karnaugh donnait ab + ac + bc. Corrigez simplifiee et relancez.
// 2. Écrivez le OU exclusif a XOR b de deux façons — (a et non b) ou
//    (non a et b), puis a différent de b — et vérifiez leur équivalence.

function table(f, n) {
  const lignes = [];
  for (let m = 0; m < (1 << n); m++) {
    const e = [];
    for (let i = n - 1; i >= 0; i--) e.push((m >> i) & 1);
    lignes.push({ e, s: f(e) ? 1 : 0 });
  }
  return lignes;
}

function equivalentes(f, g, n, nom) {
  const tf = table(f, n), tg = table(g, n);
  const ecarts = [];
  for (let i = 0; i < tf.length; i++) {
    if (tf[i].s !== tg[i].s) ecarts.push({ e: tf[i].e, f: tf[i].s, g: tg[i].s });
  }
  console.log(nom + " : " + (ecarts.length === 0 ? "équivalentes" : "DIFFÉRENTES"));
  for (const x of ecarts) {
    console.log("   contre-exemple " + x.e.join("") + " -> " + x.f + " contre " + x.g);
  }
  return ecarts.length === 0;
}

const gauche = ([a, b]) => !(a && b);
const droite = ([a, b]) => !a || !b;
equivalentes(gauche, droite, 2, "De Morgan  non(a.b) = na + nb");

const canonique = ([a, b, c]) =>
  (!a && b && c) || (a && !b && c) || (a && b && !c) || (a && b && c);

// Les trois groupes de deux cases lus au Karnaugh : ab, ac et bc. Le terme
// bc est celui que l'oubli de la colonne 11 fait sauter.
const simplifiee = ([a, b, c]) => (a && b) || (a && c) || (b && c);

equivalentes(canonique, simplifiee, 3, "Majorité");

// Le OU exclusif, deux écritures.
const xorPortes = ([a, b]) => (a && !b) || (!a && b);
const xorDiff = ([a, b]) => a !== b;
equivalentes(xorPortes, xorDiff, 2, "XOR");

En travaux pratiques

A B C | S            S = A'BC + AB'C + ABC' + ABC
0 0 0 | 0
0 0 1 | 0            4 termes de 3 littéraux
0 1 0 | 0            → 4 portes ET à 3 entrées
0 1 1 | 1            → 1 porte OU à 4 entrées
1 0 0 | 0            → 3 portes NON
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

S = A'BC + AB'C + ABC' + ABC

on duplique ABC (car X + X = X) :
S = (A'BC + ABC) + (AB'C + ABC) + (ABC' + ABC)
= BC(A' + A) + AC(B' + B) + AB(C' + C)
= BC + AC + AB

3 portes ET à 2 entrées, 1 porte OU à 3 entrées, 0 porte NON

for (int a = 0; a < 2; a++)
for (int b = 0; b < 2; b++)
  for (int c = 0; c < 2; c++) {
    int canonique = (!a&&b&&c) || (a&&!b&&c) || (a&&b&&!c) || (a&&b&&c);
    int simplifie = (b&&c) || (a&&c) || (a&&b);
    if (canonique != simplifie)
        printf("DIFFÉRENCE en %d%d%d\n", a, b, c);
  }

X + Y = (X' · Y')'      (De Morgan)
X · Y = ((X · Y)')'      (double négation)
X'    = (X · X)'         (une NON-ET à entrées reliées)

S = BC + AC + AB
= ( (BC)' · (AC)' · (AB)' )'
→ 3 NON-ET pour les produits, 1 NON-ET à 3 entrées pour la somme

A·B + A·B' + A'·B  =  A + B    (2 portes → 1 porte)

mais si A et B n'arrivent pas au même instant, la forme simplifiée
peut produire une impulsion parasite pendant la transition —
un ALÉA que la forme redondante n'avait pas.

Ce que la suite en fait

Chaque objet de ce chapitre a un équivalent matériel immédiat, et le chapitre 4 ne fera guère que traduire. Une expression devient un assemblage de portes ; une somme de produits devient deux étages de portes ; De Morgan devient la possibilité de tout construire en NAND ; et le nombre de termes après Karnaugh devient un nombre de transistors.

La fonction majorité étudiée ici n'a rien d'un exemple gratuit : c'est exactement la retenue sortante de l'additionneur complet. Vous l'avez déjà simplifiée, il ne restera qu'à la câbler.

À retenir

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