Portes logiques et langage machine

Le ou exclusif (xor)

Tu connais déjà and, or et not. Il manque une opération très utilisée en informatique : le ou exclusif, noté $\oplus$ (en Python : ^ sur les entiers). Il vaut 1 lorsque les deux bits sont différents. Le « ou » ordinaire (or) accepte que les deux soient à 1 ; le xor, non.

Essaie les entrées de la porte XOR :

Deux propriétés à connaître, elles servent partout :

Sur des entiers, ^ agit bit à bit, colonne par colonne.

Le xor est la base du masque jetable (chiffrement de Vernam). On chiffre un message $m$ avec une clé $k$ de même longueur : $c = m \oplus k$. Pour déchiffrer, on refait le même xor, car $c \oplus k = m \oplus k \oplus k = m$.

Évaluation séquentielle paresseuse

En mathématiques, $a \land b$ et $b \land a$ sont la même chose. En Python, l'ordre compte : les opérateurs and et or évaluent leurs opérandes de gauche à droite, et s'arrêtent dès que le résultat est connu.

• A and B : si A est faux, le résultat est faux, B n'est pas évalué.

• A or B : si A est vrai, le résultat est vrai, B n'est pas évalué.

C'est ce qu'on appelle l'évaluation paresseuse (ou séquentielle).

t = [1, 2]

x = 0

print(x == 0 or t[5] == 1)    # True : t[5] n'est jamais lu

print(x != 0 and t[5] == 1)   # False : t[5] n'est jamais lu

print(t[5] == 1 or x == 0)    # IndexError : t[5] est évalué en premier

On en tire un réflexe très utile : placer en premier le test qui « protège » le second.

if a != 0 and b // a > 2:

    print("quotient supérieur à 2")

Pour $a = 0$, le premier test est faux : b // a n'est jamais calculé et il n'y a pas de ZeroDivisionError. Si on écrit b // a > 2 and a != 0, l'erreur se produit.

Les lois de De Morgan permettent de transformer une condition :

Pourquoi ? $A \land B$ est faux dès qu'au moins un des deux est faux : c'est exactement (not A) or (not B).

Additionner avec des portes logiques

Additionnons deux bits $a$ et $b$ comme à l'école, avec une retenue :

• $0 + 0 = 0$ ; $0 + 1 = 1$ ; $1 + 0 = 1$ ;

• $1 + 1 = (10)_2$ : on écrit 0 et on retient 1.

On repère les deux colonnes de la table : le bit de somme $s$ vaut 1 quand $a \ne b$ (c'est un xor), et la retenue $r$ vaut 1 quand les deux bits sont à 1 (c'est un and).

Ce circuit à deux portes s'appelle le demi-additionneur :

Le demi-additionneur ne sait pas prendre en compte une retenue entrante. Pour additionner les colonnes suivantes, on utilise l'additionneur complet, qui a trois entrées : $a$, $b$ et la retenue $r_{in}$.

Pour additionner deux nombres de $n$ bits, on chaîne $n$ additionneurs complets : la retenue sortante de la colonne $i$ devient la retenue entrante de la colonne $i+1$.

Dérouler un programme en langage machine

Un processeur n'exécute pas du Python, mais des instructions machine très simples. Elles sont stockées dans la mémoire, avec les données (modèle de von Neumann). Le processeur contient :

• des registres (R0, R1, …) : de toutes petites mémoires très rapides ;

• une UAL (unité arithmétique et logique) qui fait les calculs, construite avec des portes comme celles de la section précédente ;

• une unité de contrôle et un compteur ordinal (PC) qui contient l'adresse de la prochaine instruction.

Pour chaque instruction, le processeur répète le même cycle : chercher l'instruction à l'adresse PC, la décoder, l'exécuter, puis passer à la suivante (PC augmente de 1, sauf en cas de branchement).

Voici le jeu d'instructions simplifié utilisé dans les exercices :

Pour les boucles, le branchement modifie PC : au lieu de passer à l'instruction suivante, on « saute » à une autre adresse. Pour être sûr qu'une boucle se termine, on cherche son variant : une quantité entière, positive, qui diminue strictement à chaque tour. Elle ne peut pas diminuer indéfiniment, donc la boucle s'arrête.

Par exemple, dans while n > 0: n = n - 1, la valeur de n est un entier positif ou nul qui diminue de 1 à chaque tour : c'est un variant, donc la boucle se termine.

Pour prouver qu'une boucle calcule le bon résultat, on utilise un invariant de boucle : une propriété vraie avant la boucle et conservée à chaque tour. Dans s = 0 puis for i in range(1, n + 1): s = s + i, l'invariant est « après $k$ tours, s vaut $1 + 2 + \dots + k$ ». À la fin, il donne le résultat voulu.

0: LDR R0, 10

1: LDR R1, 11

2: ADD R0, R1

3: CMP R0, #20

4: BGT 6

5: STR R0, 12

6: HALT

Retour au début : le processeur calcule $6 + 7$ en chaînant des additionneurs complets (xor, and, or) et en exécutant des instructions comme LDR, ADD et STR.

L'essentiel

• Le xor ($\oplus$, ^ en Python) vaut 1 quand les bits sont différents : $a \oplus a = 0$, $a \oplus 0 = a$, donc $(m \oplus k) \oplus k = m$.

• En Python, and et or sont évalués de gauche à droite et paresseusement : on place le test protecteur en premier (a != 0 and b // a > 2).

• De Morgan : $\lnot(A \land B) = \lnot A \lor \lnot B$ et $\lnot(A \lor B) = \lnot A \land \lnot B$.

• Demi-additionneur : $s = a \oplus b$, $r = a \land b$. Additionneur complet : $s = a \oplus b \oplus r_{in}$, $r_{out} = (a \land b) \lor (r_{in} \land (a \oplus b))$. On les chaîne pour additionner des nombres de $n$ bits.

• Un processeur exécute le cycle chercher-décoder-exécuter ; le compteur ordinal PC désigne la prochaine instruction et les branchements le modifient.

• Pour montrer qu'une boucle se termine, on exhibe un variant.