Portes logiques et langage machine

Les opérateurs booléens et le xor

Une valeur booléenne vaut 0 ou 1 (en Python : False ou True). Trois opérateurs de base :

Un quatrième opérateur est très utile : le ou exclusif, noté xor ou $\oplus$. Il vaut 1 quand les deux entrées sont différentes.

Calculons 0b1100 ^ 0b1010 : on applique le xor colonne par colonne.

Résultat : $0110$. En refaisant le xor avec $1010$, on retrouve $1100$.

Évaluation séquentielle en Python

En Python, and et or évaluent leurs opérandes de gauche à droite et s'arrêtent dès que le résultat est connu. C'est l'évaluation séquentielle paresseuse.

• 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é.

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 !

Cette propriété sert à se protéger d'une erreur : if a != 0 and b // a > 2: ne divise jamais par zéro, car si a vaut 0 la première condition est fausse.

Les lois de De Morgan permettent de réécrire une condition : $\overline{a \land b} = \bar a \lor \bar b$ et $\overline{a \lor b} = \bar a \land \bar b$. Ainsi a != 0 and C équivaut à not (a == 0 or not C).

Additionner avec des portes

Additionne deux bits $a$ et $b$ : $0+0=0$, $0+1=1$, $1+0=1$, $1+1=10_2$. Il faut donc deux sorties : la somme $s$ et la retenue $r$.

On reconnaît : $s = a \oplus b$ et $r = a \land b$. C'est le demi-additionneur.

Pour additionner des nombres de plusieurs bits, chaque colonne doit aussi absorber la retenue entrante $r_{in}$ : c'est l'additionneur complet, avec trois entrées $a$, $b$, $r_{in}$.

Pourquoi ? La somme vaut 1 s'il y a un nombre impair de 1 parmi les trois entrées (propriété du xor). Il y a une retenue sortante dès que deux bits au moins valent 1 : soit $a$ et $b$ valent 1, soit un seul des deux vaut 1 et $r_{in}$ aussi.

Colonne 3 : $s=1$, $r_{out}=0$. Résultat : $1010_2 = 10$. ✓

On chaîne les additionneurs : la retenue sortante de la colonne $i$ est la retenue entrante de la colonne $i+1$. Pour $n$ bits, il faut $n$ additionneurs complets. Chacun contient 2 xor, 2 and et 1 or, soit 5 portes : 40 portes pour 8 bits. Comme chaque colonne attend la retenue de la précédente, le temps de calcul croît avec $n$ : c'est le temps de propagation de la retenue.

Dérouler un programme en langage machine

Dans le modèle de von Neumann, la mémoire contient à la fois les instructions et les données. Le processeur répète sans cesse le cycle :

1. chercher l'instruction dont l'adresse est dans le compteur ordinal (PC) ;

2. décoder cette instruction (unité de contrôle) ;

3. exécuter (UAL, registres, mémoire) et mettre à jour le PC (PC + 1, sauf saut).

Voici quelques instructions d'un langage machine simplifié :

R1 = 8 − 13 = −5. Une bonne méthode : tracer un tableau avec une ligne par instruction et une colonne par registre (et par case mémoire utile).

Une boucle se construit avec un saut en arrière.

Tour 3 : R0 = 5 + 1 = 6, R1 = 0, le saut n'est pas pris, PC = 5 puis HALT. Résultat : R0 = 6 = 3 + 2 + 1. Ici, le variant est R1 : il vaut 3, 2, 1 tant que la condition de la boucle est vraie, puis 0 à la sortie. Pour qu'une boucle se termine, il faut un variant (un entier naturel, c'est-à-dire positif ou nul, qui décroît strictement à chaque tour tant que la condition de la boucle est vraie) : par exemple un compteur décrémenté de 1 et comparé à 0 avec BNE.

# équivalent Python de la somme 1 + 2 + ... + n

r0 = 0

r1 = n

while r1 != 0:     # variant : r1, entier décroissant, borné par 0

    r0 += r1

    r1 -= 1

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 : un processeur ne manipule que des 0 et des 1, mais avec des portes xor et and il additionne des bits, et en répétant le cycle chercher-décoder-exécuter, il déroule n'importe quel programme.

L'essentiel