ICT104 – Computer Systems

Fiche de TD numéro 1

Partie 1 – Circuits combinatoires

Exercice 1 – additionneur/soustracteur

On construit un circuit qui a deux entrées (a et b) et deux sorties (s et r) et une ligne de commande F tel
que :
• Si F = 0, le circuit effectue une addition (a + b avec une sortie s et une retenue r).
• Si F = 1, le circuit effectue une soustraction (a – b avec une sortie s et une retenue r).

1. Donnez la table de vérité de ce circuit demi-additionneur/soustracteur. Montrez que s se calcule facilement

avec une porte et r avec deux.
2. On construit maintenant un additionneur/soustracteur complet, c’est-à-dire un circuit à trois entrées (a, b et
r), deux sorties (s et r’) et une ligne de commande F tel que :
• Si F = 0, le circuit effectue une addition (a + b + r avec une sortie s et une retenue r’).
• Si F = 1, le circuit effectue une soustraction (a – (b + r) avec une sortie s et une retenue r’)
Écrivez la table de vérité de s pour la soustraction et comparez-la à celle de l’additionneur complet.
Donnez l’expression logique de s. Écrivez la table de Karnaugh ainsi qu’une expression logique de r’.
3. À partir des deux circuits précédents, proposez une construction pour un additionneur/soustracteur sur n bits,
c’est-à-dire un circuit avec deux fois n bits en entrée et qui effectue l’addition ou la soustraction de ces deux
nombres suivant la valeur d’une ligne de commande.

Exercice 2 – multiplicateur

1. On souhaite construire un multiplicateur 2 bits par 1 bit (représentant des nombres entiers positifs), c’est-à-dire
un circuit à trois entrées a0, a1 et b, et deux sorties s0 et s1, tel que si b = 0, s0 = s1 = 0 et si b = 1, s0 = a0 et s1
= a1. Donnez le schéma d’un tel circuit (appelé M) en utilisant deux portes ET.
2. On veut maintenant construire un multiplicateur 2 bits par 2 bits. En décomposant cette multiplication en
multiplications plus simples et en additions, montrez que l’on peut le construire avec deux circuits M et deux
demi-additionneurs.
3. Donnez le schéma d’un multiplicateur 2 bits par n bits utilisant des circuits M, demi-additionneurs et
additionneurs complets.

Exercice 3 – additionneur à retenue anticipée

1. On suppose que le passage d’un signal électrique dans une porte « coûte » 10 nanosecondes (c’est un ordre de
grandeur réaliste compte tenu des technologies actuelles). On dit alors qu’un circuit travaille en p ns si tous les
signaux en sortie sont disponibles en un maximum de p ns. En combien de temps un demi-additionneur, un
additionneur complet et un additionneur 4 bits travaillent-ils ?
2. On va construire un additionneur 4 bits à retenue anticipée, c’est-à-dire un circuit où le calcul des retenues
intermédiaires se fait plus rapidement. Soit une fonction de génération de retenue G = ab et une fonction de
propagation de retenue P = a + b. Montrez que la retenue de sortie d’un additionneur complet peut se calculer
par la formule r’ = Pr + G, où a et b sont les entrées et r la retenue d’entrée.
3. Dans l’additionneur 4 bits, on note Gi = aibi et Pi = ai + bi, et ri la retenue intermédiaire d’un étage, normalement
calculée à partir des entrées ai, bi et de la retenue précédente ri – 1. Exprimez r0, r1, r2 et r3 = r en fonction de
G0, G1, G2, G3, P0, P1, P2 et P3.
4. Supposons que l’on dispose de plusieurs portes OU et ET à deux, trois ou quatre entrées, et que chacune travaille
Computer Systems – ICT1
 en 10 ns. En combien de temps se fait le calcul des Gi, Pi et ri ? Est-ce intéressant ? Quelle différence y a-t-il
entre le temps de travail d’un additionneur 8 bits normal et d’un additionneur 8 bits à retenue anticipée (avec les
bonnes portes OU et ET) ?

Exercice 4 – bascules équivalentes

Comment peut-on utiliser une bascule JK pour construire une bascule T, et une bascule RS pour construire une
bascule T ?

Partie 2 – ordinateur et processeur

Exercice 5 – compilation ou interprétation

Vous écrivez un programme qui peut être soit compilé, soit interprété. Le compilateur peut compiler dix mille lignes
de code par seconde, puis il nécessite deux secondes pour l’édition des liens. Votre programme exécutable final
contient vingt fois plus de lignes d’instructions processeur que le programme de départ en langage évolué et
s’exécute à la vitesse de cent mille instructions par seconde.
Pour l’exécuter, vous avez aussi le choix de passer par un interpréteur travaillant à la vitesse de cent mille
instructions par seconde. Malheureusement, l’interprétation est compliquée et nécessite deux cents fois plus
d’instructions que votre programme de départ.
1. Une fois le programme écrit (mille lignes de code), en combien de temps s’exécute-t-il s’il est compilé (temps
de compilation inclus) ? Et s’il est interprété ?
2. Quels sont les deux temps d’exécution s’il contient un million de lignes de code ?
3. Quand doit-on choisir la compilation plutôt que l’interprétation, ou l’inverse ?

Exercice 6 – débit d’informations

1. Un processeur exécute une instruction de 4 octets toutes les nanosecondes. De plus, 20 % de ces instructions
font référence à une donnée de 4 octets en mémoire. Quel est le débit nécessaire entre le processeur et la
mémoire ?
2. Une carte vidéo doit afficher vingt-quatre images par seconde sur un écran de 1 600 × 1 200 pixels, un pixel
étant une combinaison de trois couleurs, chacune codée sur 8 bits. Quel est le débit nécessaire entre la carte
vidéo et le moniteur ?

Exercice 7 - Instructions à une, deux ou trois données

Un processeur possède les registres r0 à r9. On veut calculer l’expression ((r1× r2- r3)/(r1+ r4+ r5))+ r6+ r2 et
mettre le résultat dans r0.
1. Le processeur possède des instructions à trois données qui sont :

ADD rX,rY,rZ (rX <- rY+rZ)

SUB rX,rY,rZ (rX <- rY-rZ)
MUL rX,rY,rZ (rX <- rY×rZ)
DIV rX,rY,rZ (rX <- rY/rZ)
MOVE rX,rY (rX <- rY)
Écrivez la suite d’instructions correspondant au calcul voulu.

2. Le processeur possède des instructions à deux données qui sont :

ADD rX,rY (rX <- rX+rY)
Computer Systems – ICT1
 SUB rX,rY (rX <- rX-rY)
MUL rX,rY (rX <- rX×rY)
DIV rX,rY (rX <- rX/rY)
MOVE rX,rY (rX <- rY)
Écrivez la suite d’instructions correspondant au calcul voulu.

3. Le processeur possède un registre accumulateur qui est source et destination de toutes les opérations. Les
instructions à une donnée sont :
ADD rX (Acc <-Acc+rX)
SUB rX (Acc <- Acc-rX)
MUL rX (Acc <- Acc×rX)
DIV rX (Acc <- Acc/rX)
LOAD rX (Acc <- rX)
STORE rX (rX <- Acc)
Écrivez la suite d’instructions correspondant au calcul voulu. On veut toujours avoir le résultat dans r0, qui n’est
pas l’accumulateur.

Exercice 8 – divers modes d’adressage

Pour accéder à une donnée en mémoire, un processeur ne possède que le mode d’adressage indirect : MOVE r1,(r2),
qui récupère la donnée se trouvant à l’adresse mémoire indiquée dans r2 et la met dans r1. On souhaite simuler les
autres modes d’adressage accédant à la mémoire. En distinguant à chaque fois deux cas (instruction à deux ou trois
données), écrivez les instructions correspondant aux exemples suivants utilisant d’autres modes d’adressage :
1. Adressage indirect avec déplacement : MOVE r1,8(r2).
2. Adressage indirect avec pré-incrémentation : MOVE r1,(r2)+.
3. Adressage indirect avec post-décrémentation : MOVE r1,-(r2).
4. Adressage indirect indexé : MOVE r1,(r2,r3).
5. Adressage indirect indexé avec déplacement : MOVE r1,8(r2,r3).

Partie 3 – le langage assembleur

Exercice 9 – trouver la longueur d’une chaine

Dans r0 se trouve l’adresse d’une chaîne de caractères terminée par l’octet nul. Écrivez une suite d’instructions
assembleur qui, lorsqu’elle se termine, permet de récupérer le nombre de caractères de la chaîne dans r1.

Exercice 10 – parcourir un tableau

1. Un tableau d’entiers est stocké en mémoire. Chaque élément a une valeur de 1 à 127 et est donc stocké sur 1
octet. L’octet qui suit le dernier élément du tableau est nul. L’adresse du premier élément du tableau se trouve
dans le registre r0. Écrivez une suite d’instructions assembleur qui, lorsqu’elle se termine, permet de récupérer
le plus grand élément du tableau dans le registre r1.
2. Ajoutez au programme précédent le calcul de la somme de tous les éléments du tableau dans le registre r2.

Exercice 11 – remplacer des caractères dans une chaine

Une chaîne de caractères est stockée en mémoire. Chaque élément occupe 1 octet et aucun n’est nul. L’octet qui suit

Computer Systems – ICT1

le dernier élément de la chaîne est nul. L’adresse du premier élément de la chaîne se trouve dans le registre r0. On
souhaite effectuer une opération de remplacement de certains caractères de la chaîne. Le registre r1 contient le
caractère à remplacer. Il s’agit de substituer à chaque occurrence de ce dernier dans la chaîne, le caractère se trouvant
dans le registre r2.

Écrivez une suite d’instructions assembleur qui, lorsqu’elle se termine, assure que toutes les occurrences (dans la
chaîne) du caractère contenu dans r1 sont remplacées par le caractère contenu dans r2. On souhaite également avoir
à la fin, dans le registre r3, le nombre de remplacements effectués.

Exercice 12 – renverser une chaine

Une chaîne de caractères est stockée en mémoire. Chaque caractère occupe 1 octet et l’octet qui suit le dernier
caractère de la chaîne est nul. L’adresse du premier élément de la chaîne se trouve dans le registre r0. On souhaite
renverser la chaîne, c’est-à-dire l’écrire en commençant par le dernier caractère et stocker cette nouvelle chaîne en
mémoire à une adresse contenue dans le registre r1. (Ainsi, si la première chaîne est truc, on souhaite écrire la chaîne
curt en mémoire avec le premier élément à l’adresse qui se trouve dans r1 et avec l’octet nul final.)

Écrivez une suite d’instructions assembleur qui renverse la chaîne pointée par r0 et la stocke à l’adresse pointée par
r1.

Computer Systems – ICT1