Des portes logiques aux additionneurs
Les ordinateurs ne « font pas d'arithmétique » — ils ne font que construire des blocs couche par couche avec des portes logiques. Dans cette leçon, nous allons construire à la main un circuit capable d'additionner des nombres en utilisant des portes XOR, AND et OR, du demi-additionneur à l'additionneur complet puis à l'additionneur 4 bits, en construisant étape par étape.
L'addition dans la vie quotidienne — Inspirée par l'addition posée
Rappelez-vous le processus pour faire une addition sur papier. Calculez37 + 58:
Calculez d'abord le chiffre des unités :7 + 8 = 15, écrivez5,, retenez 1。
Calculez ensuite le chiffre des dizaines :3 + 5 + retenue 1 = 9, écrivez9, le résultat est95。
Ce processus révèle trois points clés :
1. Calcul bit par bit: Chaque bit ne se soucie que de ses deux opérandes et de la retenue provenant du bit inférieur.
2. Propagation de la retenue: Après le calcul du bit inférieur, une retenue peut être générée, et cette retenue doit être transmise au bit supérieur.
3. Bit de poids faible particulier: Le bit le plus bas n'a pas de retenue provenant d'un bit inférieur ; il doit seulement traiter les deux opérandes.
Les ordinateurs effectuent l'addition avec la même idée : décomposer un grand problème (addition multi-bits) en de nombreux petits problèmes (addition 1-bit), puis les résoudre un par un.
Demi-additionneur — addition 1-bit pour le bit le plus bas
Le bit le plus bas n'a pas d'entrée de retenue ; il doit seulement additionner deux nombres binaires de 1 bit. Un circuit capable de gérer cette situation est appelé unDemi-additionneur。
Un demi-additionneur a deux entrées A et B, et deux sorties :Bit de sommeetRetenue。
Table de vérité du demi-additionneur :
| A | B | Somme (somme) | Retenue |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
En regardant la table de vérité, une coïncidence surprenante apparaît :
Sum = A XOR B. Lorsque A et B sont différents, Sum=1 ; lorsqu'ils sont identiques, Sum=0 — c'est exactement la table de vérité d'une porte XOR.
Carry = A AND B. Une retenue est générée uniquement lorsque les deux entrées valent 1 — c'est exactement la table de vérité d'une porte AND.
Un demi-additionneur ne nécessite que1 porte XOR + 1 porte ANDCela peut être implémenté. George Boole n'aurait probablement jamais imaginé que le système algébrique qu'il a inventé deviendrait un jour le fondement mathématique des additionneurs.
Additionneur complet — Addition complète avec gestion de retenue
Le demi-additionneur présente un défaut fatal :Il ne peut pas recevoir de retenue provenant du bit inférieur.. Hormis le bit le plus bas, chaque bit doit traiter trois nombres : A, B, et la retenue d'entrée Cin provenant du bit inférieur.
Un circuit capable de traiter simultanément deux termes à additionner et une entrée de retenue est appelé unAdditionneur complet。
Table de vérité de l'additionneur complet :
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Une conception astucieuse :On peut construire un additionneur complet avec deux demi-additionneurs。
Étape 1 : le demi-additionneur 1 traite A et B, produisant la somme intermédiaire S1 et la retenue C1.
Étape 2 : le demi-additionneur 2 traite S1 et Cin, produisant la somme finale Sum et la retenue C2.
Étape 3 : retenue finaleCout = C1 OR C2(Si l’un ou l’autre des demi-additionneurs génère une retenue, la sortie finale est une retenue.)
La structure de circuit d’un additionneur complet :2 demi-additionneurs + 1 porte OU. Superposés l’un sur l’autre, chaque demi-additionneur est intérieurement XOR + AND. Cette idée de construction hiérarchique traverse toute l’architecture informatique.
Mise en cascade d’additionneurs complets — additionneur à propagation de retenue 4 bits
Avec les additionneurs complets, l’addition multi-bits devient simple :Connecter plusieurs additionneurs complets en série, avec la sortie de retenue du bit inférieur reliée à l’entrée de retenue du bit supérieur。
La structure en cascade d’un additionneur 4 bits :
Bit 0 (bit de poids faible) : l’additionneur complet traite A0, B0, retenue d’entrée = 0, produisant la somme S0 et la retenue C0.
Bit 1 : l’additionneur complet traite A1, B1, retenue d’entrée = C0, produisant la somme S1 et la retenue C1.
Bit 2 : l’additionneur complet traite A2, B2, retenue d’entrée = C1, produisant la somme S2 et la retenue C2.
Bit 3 (bit de poids fort) : l’additionneur complet traite A3, B3, retenue d’entrée = C2, produisant la somme S3 et la retenue C3 (retenue finale).
La retenue se propage comme des vagues d’eau du bit de poids faible vers le bit de poids fort niveau par niveau, c’est pourquoi cette structure porte le nom deRipple Carry Adder (additionneur à propagation de retenue)。
L’additionneur à propagation de retenue est simple et intuitif, mais présente un goulot d’étranglement de performance : dans le pire des cas, la retenue doit se propager du bit 0 jusqu’au bit le plus élevé, en traversant N étages de délais d’additionneur complet. Les CPU modernes utilisent des techniques comme l’anticipation de retenue (carry lookahead) pour optimiser, mais comprendre la propagation de retenue est un prérequis pour comprendre toutes les optimisations d’additionneurs.
Démo de code Python
Exemple
# Leçon 8 : Des portes logiques aux additionneurs - Démo Python
# série de tutoriels d'exemple
# ============================================
def half_adder(a, b):
"""
Demi-additionneur : additionne deux nombres binaires de 1 bit, en ignorant l'entrée de retenue.
Paramètres :
a, b : chacun vaut 0 ou 1
Retourne :
(sum_bit, carry_out) : bit de somme et retenue sortante
Implémentation du circuit :
sum_bit = a XOR b (porte XOR)
carry_out = a AND b (porte AND)
"""
sum_bit = a ^ b # XOR : même = 0, différent = 1
carry_out = a & b # AND : retenue uniquement lorsque les deux valent 1
return sum_bit, carry_out
def full_adder(a, b, carry_in):
"""
Additionneur complet : additionner deux nombres binaires de 1 bit, en tenant compte de l'entrée de retenue.
Paramètres :
a, b, carry_in : chacun vaut 0 ou 1
Retourne :
(sum_bit, carry_out) : bit de somme et retenue sortante
Astuce d'implémentation — cascader deux demi-additionneurs :
Étape 1 : half_adder(a, b) → (s1, c1)
Étape 2 : half_adder(s1, carry_in) → (sum_bit, c2)
Retenue finale : carry_out = c1 OR c2
"""
s1, c1 = half_adder(a, b)
sum_bit, c2 = half_adder(s1, carry_in)
carry_out = c1 | c2 # Porte OU : si l'un ou l'autre a une retenue, la retenue finale est mise à 1
return sum_bit, carry_out
def adder_4bit(a_bits, b_bits):
"""
Additionneur à propagation de retenue de 4 bits : 4 additionneurs complets en cascade.
Paramètres :
a_bits : liste binaire de 4 bits, a_bits[0] est le bit de poids faible (LSB)
b_bits : liste binaire de 4 bits, b_bits[0] est le bit de poids faible (LSB)
Retourne :
(sum_bits, final_carry) : somme sur 4 bits (bit de poids faible en premier) et retenue finale
Afficher le processus complet de propagation de la retenue, en démontrant comment fonctionne la retenue propagée.
"""
carry_in = 0
sum_bits = []
print("=" * 55)
print(Additionneur à retenue propagée 4 bits — processus de propagation de la retenue)
print("=" * 55)
# Afficher d'abord les bits de poids fort, pour faciliter la lecture
print(f" Terme A : {list(reversed(a_bits))} (bits de poids fort en premier)")
print(f" Terme B : {list(reversed(b_bits))} (bits de poids fort en premier)")
print()
for i in range(4):
s, carry_out = full_adder(a_bits[i], b_bits[i], carry_in)
sum_bits.append(s)
print(f" [bit {i}] (le bit de poids faible est le bit 0)")
print(f" Entrée : A[{i}]={a_bits[i]}, B[{i}]={b_bits[i]}, bits d'entrée={carry_in}")
print(fSortie : bit de somme={s}, retenue sortante={carry_out})
if carry_out:
print(f>> Retenue générée ! La retenue={carry_out} sera transmise au bit {i+1})
carry_in = carry_out # La retenue courante devient l'entrée de retenue du bit suivant
print()
print(fRésultat du calcul : {list(reversed(sum_bits))} (bits de poids fort en premier))
print(fRetenue finale : {carry_in})
print("=" * 55)
return sum_bits, carry_in
def decimal_to_4bit(n):
"""Convertit les nombres décimaux 0-15 en listes binaires de 4 bits (bit de poids faible en premier)"""
return [(n >> i) & 1 for i in range(4)]
def bits_to_decimal(bits):
"""Convertir une liste de bits binaires (bit de poids faible en premier) en un entier décimal"""
return sum(bit * (2 ** i) for i, bit in enumerate(bits))
# ============================================
# Cas de test
# ============================================
print(>>> exemple de test de demi-additionneur <<<)
for a in (0, 1):
for b in (0, 1):
s, c = half_adder(a, b)
print(f" half_adder({a}, {b}) => somme={s}, retenue={c}")
print()
print(>>> exemple de test d'additionneur complet <<<)
test_cases = [
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)
]
for a, b, cin in test_cases:
s, c = full_adder(a, b, cin)
print(f" full_adder({a}, {b}, carry_in={cin}) => somme={s}, retenue={c}")
print()
print(>>> exemple de test d'additionneur 4 bits: 7 + 5 <<<)
a_dec, b_dec = 7, 5
a_bits = decimal_to_4bit(a_dec)
b_bits = decimal_to_4bit(b_dec)
result_bits, final_carry = adder_4bit(a_bits, b_bits)
result_dec = bits_to_decimal(result_bits)
print(fAttendu : {a_dec} + {b_dec} = {a_dec + b_dec})
print(fRésultat : {result_dec} (retenue={final_carry}))
print(f" vérification d'exemple : {'Réussi !' if result_dec == a_dec + b_dec else 'échec !'}")
print()
print(>>> exemple de test supplémentaire : 10 + 6 (débordement possible) <<<)
a_bits2 = decimal_to_4bit(10)
b_bits2 = decimal_to_4bit(6)
result_bits2, carry2 = adder_4bit(a_bits2, b_bits2)
result_dec2 = bits_to_decimal(result_bits2)
full_result = result_dec2 + (carry2 * 16)
print(f" Attendu : 10 + 6 = 16")
print(f" Résultat 4 bits : {result_dec2}, bits d'entrée : {carry2}, Valeur complète 5 bits : {full_result}")
print(fvérification de l'exemple : {'Pass!' if full_result == 16 else 'Fail!'})
Exécutez le code et observez comment la retenue se propage entre chaque bit — le bit de poids faible est calculé en premier, et après la génération d'une retenue, elle est transmise au bit suivant ; le bit suivant est alors calculé, et si une retenue est générée, elle est transmise plus loin. C'est l'origine du nom « ripple carry ».
Démo interactive : animation en cascade d'un additionneur 4 bits (exemple de démo de propagation de retenue)
Ci-dessous, un additionneur 4 bits à retenue propagée (ripple carry) est simulé en pur div+SVG.Cliquez sur le bouton pour avancer pas à pas dans la propagation de la retenue du bit 0 (bit de poids faible) au bit 3 (bit de poids fort)., ou vous pouvez utiliser « Auto Demo » pour regarder tout le processus.