Exercices: portes logiques et langage machine

1. a) Donner la table de vérité de l'opération xor (ou exclusif) sur deux variables $a$ et $b$.

1. b) Calculer 0b1100 ^ 0b1010 en binaire.

1. c) Quelle est la valeur de $a$ xor $a$ ? De $a$ xor 0 ?

On considère les expressions Python avec x = 0 et t = [1, 2].

1. a) Donner la valeur de x == 0 or t[5] == 1.

1. b) Donner la valeur de x != 0 and t[5] == 1.

1. c) Expliquer pourquoi aucune erreur ne se produit dans ces deux cas (évaluation séquentielle paresseuse).

Un processeur simplifié possède des registres R0 à R3 et exécute les instructions : MOV Rd, #n (Rd reçoit n), ADD Rd, Rs (Rd reçoit Rd + Rs), SUB Rd, Rs.

On exécute : MOV R0, #5, MOV R1, #8, ADD R0, R1, SUB R1, R0.

Donner le contenu de R0 et R1 après chaque instruction.

Un additionneur un bit calcule la somme $s$ et la retenue $r$ de deux bits $a$ et $b$.

1. a) Exprimer $s$ et $r$ à l'aide de xor et de and.

1. b) Compléter la table de vérité pour les quatre cas possibles.

1. c) Expliquer comment chaîner des additionneurs complets pour additionner deux nombres de 4 bits.

Un programme en assembleur simplifié est stocké en mémoire aux adresses 0 à 6 :

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

On suppose que les cases 10 et 11 contiennent 7 et 9, et que la case 12 contient initialement 0. BGT branche à l'adresse indiquée si le résultat est strictement supérieur.

1. a) Suivre l'exécution et donner le contenu final de la mémoire à l'adresse 12.

1. b) Même question si les cases 10 et 11 contiennent 15 et 9.

1. c) Décrire en une phrase ce que fait ce programme.

Dans le chiffrement par masque jetable, on calcule $c = m \oplus k$ bit à bit.

1. a) Chiffrer $m = (1011\,0010)_2$ avec la clé $k = (0110\,1100)_2$.

1. b) Montrer que $c \oplus k = m$.

1. c) Pourquoi la clé ne doit-elle jamais être réutilisée ?

On veut construire un additionneur complet à partir des opérations xor, and et or. Il reçoit deux bits $a$ et $b$ à additionner et une retenue entrante $r_{in}$ ; il fournit le bit de somme $s$ et la retenue sortante $r_{out}$.

1. a) Écrire $s$ et $r_{out}$ en fonction de $a$, $b$ et $r_{in}$.

1. b) Vérifier le résultat par la table de vérité complète (huit lignes).

1. c) En n'utilisant que des portes xor, and et or à deux entrées et un additionneur complet pour chaque bit, déterminer le nombre de portes nécessaires pour additionner deux nombres de 8 bits et justifier pourquoi le temps de propagation de la retenue limite la rapidité.

Écrire un programme assembleur simplifié (instructions LDR, STR, ADD, SUB, CMP, BNE, BRA, HALT) qui calcule dans R0 la somme $1 + 2 + \dots + n$, où $n$ est lu à l'adresse 20.

1. a) Écrire le programme en commentant chaque instruction.

1. b) Dérouler l'exécution pour $n = 3$ en donnant les registres à chaque étape.

1. c) Identifier le variant de la boucle et justifier la terminaison.

Soit une fonction f(a, b) qui, dans le cas où a est un entier non nul, calcule b // a. On écrit : if a != 0 and b // a > 2: ....

1. a) Montrer que cette expression ne provoque pas d'erreur pour $a = 0$.

1. b) Que se passe-t-il si on inverse l'ordre des deux conditions ?

1. c) Donner une expression équivalente avec or et la négation, et vérifier son équivalence par les lois de De Morgan.