Chapitre 1012 minDébutant
Portes logiques, XOR, NAND et NOR
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- utiliser les propriétés du ou exclusif pour chiffrer et calculer une parité ;
- expliquer pourquoi NAND et NOR suffisent à tout construire ;
- reconnaître les symboles des portes et lire un logigramme ;
- comprendre comment un additionneur additionne deux bits.
5 exercices corrigés1 schéma
Une porte logique est un composant électronique qui réalise une opération booléenne sur des signaux binaires : NON, ET, OU, et leurs variantes OU exclusif (XOR), NON-ET (NAND) et NON-OU (NOR). Le programme du BTS demande de connaître l'intérêt de ces trois dernières opérations ; les portes et les circuits comme l'additionneur sont un complément, qui montre comment l'algèbre de Boole devient du matériel. Ce chapitre présente XOR, NAND et NOR, leurs propriétés et leurs usages en informatique, puis les portes et les logigrammes.
Le ou exclusif (XOR) et ses propriétés
Le ou exclusif a ⊕ b vaut 1 quand a et b sont différents. Le chapitre 7 a établi son expression :
| a | b | a ⊕ b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Le XOR est aussi l'addition modulo 2 : 1 ⊕ 1 = 0, comme 1 + 1 = 2 ≡ 0 (mod 2). Ses propriétés se vérifient toutes sur la table :
| Propriété | Formule |
|---|---|
| Commutativité | a ⊕ b = b ⊕ a |
| Associativité | (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) |
| Élément neutre | a ⊕ 0 = a |
| Inverseur | a ⊕ 1 = a̅ |
| Auto-annulation | a ⊕ a = 0 |
| Réversibilité | (a ⊕ k) ⊕ k = a |
La dernière découle des précédentes : (a ⊕ k) ⊕ k = a ⊕ (k ⊕ k) = a ⊕ 0 = a. Appliquer deux fois le même XOR redonne la valeur de départ. Trois usages en informatique en découlent directement.
1. Le chiffrement. On applique le XOR bit à bit entre un message et une clé : le résultat est illisible sans la clé, et refaire le XOR avec la même clé redonne le message.
| Bits | |
|---|---|
| Message m | 1011 0110 |
| Clé k | 0110 1100 |
| Chiffré c = m ⊕ k | 1101 1010 |
| Déchiffré c ⊕ k | 1011 0110 = m |
Avec une clé aléatoire aussi longue que le message et utilisée une seule fois (le masque jetable, ou chiffre de Vernam), ce chiffrement est inviolable. Les chiffrements par flot modernes, comme ChaCha20 (l'une des suites de TLS 1.3), et AES en mode GCM fabriquent une longue suite pseudo-aléatoire à partir d'une clé courte et la combinent au message par XOR. Le chiffrement symétrique est traité dans le cours cybersécurité.
2. Le contrôle de parité. Le XOR de tous les bits d'un mot vaut 1 si le mot contient un nombre impair de 1. Un bit de parité ajouté au mot permet de détecter une erreur de transmission sur un bit.
3. Le RAID 5. Sur trois disques de données D1, D2, D3, le RAID 5 stocke un bloc de parité P = D1 ⊕ D2 ⊕ D3 (réparti sur les disques). Si un disque tombe en panne, son contenu se recalcule à partir des autres : D2 = D1 ⊕ D3 ⊕ P. Exemple sur 4 bits : D1 = 1100, D2 = 1010, D3 = 0111 donnent P = 0001 ; si D2 est perdu, D1 ⊕ D3 ⊕ P = 1100 ⊕ 0111 ⊕ 0001 = 1010, la valeur de D2. Le RAID est détaillé dans le chapitre Le matériel serveur : redondance et RAID du cours Poste de travail.
NAND et NOR
NAND (non-et) est le complément du produit, NOR (non-ou) le complément de la somme.
| a | b | NAND : non(ab) | NOR : non(a + b) |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
Par De Morgan : NAND = non(ab) = a̅ + b̅ et NOR = non(a + b) = a̅ b̅.
Pourquoi NAND et NOR sont universelles
L'intérêt de ces deux opérations, que signale le programme : chacune suffit, à elle seule, pour exprimer toutes les autres. On dit qu'elles sont universelles. Notons a ↑ b = non(ab) le NAND.
- Le NON : a ↑ a = non(aa) = a̅.
- Le ET : (a ↑ b) ↑ (a ↑ b) = non(non(ab)) = ab.
- Le OU : (a ↑ a) ↑ (b ↑ b) = non(a̅ b̅) = a + b, par De Morgan.
Le NOR fonctionne de la même façon : avec a ↓ b = non(a + b), on a a ↓ a = a̅, (a ↓ a) ↓ (b ↓ b) = non(a̅ + b̅) = ab, et (a ↓ b) ↓ (a ↓ b) = a + b.
Conséquence pratique : un fabricant de puces peut construire n'importe quel circuit avec un seul type de porte, plus simple à produire en masse. Dans la technologie CMOS des processeurs, la porte NAND est d'ailleurs plus simple que la porte ET (une porte ET y est réalisée par une NAND suivie d'un inverseur).
Les portes logiques et leurs symboles
Chaque opération a son symbole graphique. Deux normes coexistent : les symboles rectangulaires de la norme internationale CEI 60617 (un rectangle avec un signe : & pour ET, ≥1 pour OU, =1 pour OU exclusif, un rond pour la négation), et les symboles à formes distinctives de la norme américaine ANSI/IEEE 91, très répandus dans les documentations et les simulateurs.
Logigrammes : de l'expression au circuit
Un logigramme est le schéma d'un circuit : les variables entrent à gauche, traversent des portes, et la fonction sort à droite. Pour dessiner le logigramme d'une expression, on suit les priorités : les compléments d'abord, puis les produits (portes ET), puis la somme (porte OU) en sortie.
Exemple : F = ab + c̅ demande une porte ET (pour ab), une porte NON (pour c̅) et une porte OU qui réunit les deux. Pour lire un logigramme, on fait l'inverse : on écrit la sortie de chaque porte de gauche à droite, jusqu'à la sortie finale.
Simplifier l'expression avant de construire le circuit réduit le nombre de portes : F = abc + abc̅ + ab̅c + ab̅c̅ demanderait quatre portes ET à trois entrées et une porte OU à quatre entrées ; simplifiée en F = a (exemple 4 du chapitre 7), elle se réduit à un simple fil.
L'additionneur : l'arithmétique en portes (complément)
Un processeur additionne des nombres binaires avec des portes logiques. Pour additionner deux bits a et b, il faut un bit de somme S et un bit de retenue R :
| a | b | R | S | Calcul |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 + 0 = 00 |
| 0 | 1 | 0 | 1 | 0 + 1 = 01 |
| 1 | 0 | 0 | 1 | 1 + 0 = 01 |
| 1 | 1 | 1 | 0 | 1 + 1 = 10 |
On lit sur la table : S = a ⊕ b et R = ab. Ce circuit (une porte XOR et une porte ET) s'appelle un demi-additionneur. Pour additionner des nombres de plusieurs bits, chaque rang doit aussi ajouter la retenue r venue du rang précédent : c'est l'additionneur complet, avec S = a ⊕ b ⊕ r et R = ab + r(a ⊕ b). En enchaînant 64 additionneurs complets, on additionne deux entiers de 64 bits. L'addition binaire elle-même, avec ses retenues, est expliquée dans le cours d'arithmétique (addition binaire et hexadécimale).
Exercices
Exercice 1 sur 5 Chiffrer et déchiffrer par XOR Réussi À revoir
On chiffre l'octet m = 0100 1101 (la lettre « M » en ASCII) avec la clé k = 1010 0110.
- Calcule le chiffré c = m ⊕ k.
- Déchiffre c avec la même clé et vérifie que tu retrouves m.
- Un attaquant connaît m et c, mais pas k. Comment retrouve-t-il la clé ?
Voir la réponseMasquer la réponse de l'exercice 1
- Bit à bit, 1 quand les bits diffèrent : 0100 1101 ⊕ 1010 0110 = 1110 1011.
- 1110 1011 ⊕ 1010 0110 = 0100 1101 = m.
- m ⊕ c = m ⊕ (m ⊕ k) = (m ⊕ m) ⊕ k = 0 ⊕ k = k. Il calcule m ⊕ c = 0100 1101 ⊕ 1110 1011 = 1010 0110, la clé. C'est pourquoi une clé de masque jetable ne doit jamais resservir.
Tu avais trouvé ?
Exercice 2 sur 5 Avec des NAND seulement Réussi À revoir
- Vérifie par une table de vérité que (a ↑ a) ↑ (b ↑ b) = a + b, où ↑ désigne le NAND.
- Combien de portes NAND faut-il pour réaliser un ET ? un OU ?
Voir la réponseMasquer la réponse de l'exercice 2
1. La table :
| a | b | a ↑ a = a̅ | b ↑ b = b̅ | a̅ ↑ b̅ = non(a̅b̅) | a + b |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
Les deux dernières colonnes sont identiques.
2. Un ET : 2 portes (une NAND, puis une NAND montée en inverseur). Un OU : 3 portes (deux NAND en inverseurs sur a et sur b, puis une NAND).
Tu avais trouvé ?
Exercice 3 sur 5 Parité RAID 5 Réussi À revoir
Trois disques de données contiennent, sur un même bloc, D1 = 0110, D2 = 1011 et D3 = 1110.
- Calcule le bloc de parité P = D1 ⊕ D2 ⊕ D3.
- Le disque 3 tombe en panne. Recalcule D3 à partir des autres blocs.
Voir la réponseMasquer la réponse de l'exercice 3
- D1 ⊕ D2 = 0110 ⊕ 1011 = 1101 ; puis 1101 ⊕ 1110 = 0011. P = 0011.
- D3 = D1 ⊕ D2 ⊕ P = 1101 ⊕ 0011 = 1110. On retrouve bien D3.
Tu avais trouvé ?
Exercice 4 sur 5 Lire un logigramme Réussi À revoir
Un circuit reçoit a, b et c. La sortie d'une porte NOR alimentée par a et b entre, avec c, dans une porte ET. Écris l'expression de la sortie F, puis donne les valeurs de (a, b, c) pour lesquelles F = 1.
Voir la réponseMasquer la réponse de l'exercice 4
La porte NOR donne non(a + b) = a̅b̅. La porte ET donne F = a̅b̅c. C'est un seul minterme : F = 1 seulement pour (a, b, c) = (0, 0, 1).
Tu avais trouvé ?
Exercice 5 sur 5 Additionneur complet Réussi À revoir
Vérifie sur les huit cas que S = a ⊕ b ⊕ r et R = ab + r(a ⊕ b) donnent bien le résultat de l'addition a + b + r écrit sur deux bits (R S).
Voir la réponseMasquer la réponse de l'exercice 5
| a | b | r | a + b + r | R | S |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 = 00 | 0 | 0 |
| 0 | 0 | 1 | 1 = 01 | 0 | 1 |
| 0 | 1 | 0 | 1 = 01 | 0 | 1 |
| 0 | 1 | 1 | 2 = 10 | 1 | 0 |
| 1 | 0 | 0 | 1 = 01 | 0 | 1 |
| 1 | 0 | 1 | 2 = 10 | 1 | 0 |
| 1 | 1 | 0 | 2 = 10 | 1 | 0 |
| 1 | 1 | 1 | 3 = 11 | 1 | 1 |
S vaut 1 quand le nombre de 1 parmi a, b, r est impair : c'est bien a ⊕ b ⊕ r. R vaut 1 quand au moins deux entrées valent 1 : si a = b = 1, ab = 1 ; si exactement une de a et b vaut 1 et r = 1, r(a ⊕ b) = 1. Les deux formules sont justes.
Tu avais trouvé ?