Architecture des Ordinateurs, corrigé TD 4

Exercice 1. Réalisation d’un additionneur/soustracteur (portes logiques disponibles : ET, OU,

NON, OU EXCL)
1. Réaliser un demi-soustracteur (1 bit A avec 1 bit B sans retenue d’entrée) :
– Ecrire la table de vérité.
– Donner les équations de sortie.
– Etablir le schéma logique.
2. En comparant le circuit du demi-soustracteur avec celui d’un demi-additionneur, concevoir
le plus simplement possible un circuit, appelé demi-additionneur/soustracteur, qui à partir
d’un signal de commande C et des entrées A et B, simule le demi-additionneur sur A et B
lorsque la commande C est à 0, et le demi-soustracteur sur A et B lorsque la commande
C est à 1 (suggestion : appliquer le signal de commande à une des entrées d’une porte OU
EXCL).
3. A partir du demi-additionneur/soustracteur qui vient d’être réalisé, concevoir un addition-
neur/soustracteur complet (1 bit A avec un bit B avec retenue d’entrée).
4. Donner le schéma d’un additionneur/soustracteur quatre bits par quatre bits.

Correction.
1. Un demi-soustracteur est un circuit qui soustrait simplement un bit d’un autre. Le résultat
est obtenu sur deux bits, S pour le poids faible (la différence), R pour le poids fort (la
retenue). A partir de la table de vérité suivante :

A B R S
0 0 0 0
0 1 1 1
1 0 0 1
1 1 0 0

on obtient :

S = A.B + A.B
= A⊕B

R = A.B

Le demi-soustracteur est réalisé par le circuit suivant :

A
=1 S
B

& R

2. On constate que la seule différence entre un demi-soustracteur et un demi-additionneur

tient à la présence d’une négation sur l’entrée A de la porte ET qui génère la retenue.

1
 L’ajout d’une porte OU EXCL dont une des entrées est la commande C doit donc permettre
de simuler la négation présente dans le demi-soustracteur lorsque C = 1, et l’absence de
cette négation dans le demi-additionneur lorsque C = 0. Il est aisé de vérifier partir de la
table de vérité de OU EXCL qu’il suffit de prendre directement A pour l’autre entrée de la
porte OU EXCL : lorsque C = 0, la sortie de la porte est équivalente à A, lorsque C = 1
cette sortie prend la valeur de A.

C A C ⊕A
0 0 0
0 1 1
1 0 1
1 1 0

Bien entendu, une étude systématique des sorties à partir de toutes les entrées permet de
retrouver les équations booléennes attendues :

C A B R S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 0
1 0 1 1 1
1 1 0 0 1
1 1 1 0 0

on obtient :

S = C.A.B + C.A.B + C.A.B + C.A.B

= C.(A ⊕ B) + C.(A ⊕ B)
= (C + C).(A ⊕ B)
= A⊕B

R = C.A.B + C.A.B
= (C.A + C.A).B
= (C ⊕ A).B

Le schéma d’un demi-additionneur/soustracteur est donc :

A
=1 S
B

& R

=1
C
3. La table de vérité de l’additionneur/soustracteur est (avec Re , retenue en entrée et Rs

2
retenue en sortie) :
C Re A B Rs S
0 0 0 0 0 0
0 0 0 1 0 1
0 0 1 0 0 1
0 0 1 1 1 0
0 1 0 0 0 1
0 1 0 1 1 0
0 1 1 0 1 0
0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 1 1 1
1 0 1 0 0 1
1 0 1 1 0 0
1 1 0 0 1 1
1 1 0 1 1 0
1 1 1 0 0 0
1 1 1 1 1 1
on obtient :

S = C.Re .A.B + C.Re .A.B + C.Re .A.B + C.Re .A.B +

C.Re .A.B + C.Re .A.B + C.Re .A.B + C.Re .A.B
= (C + C).Re .A.B + (C + C).Re .A.B + (C + C).Re .A.B + (C + C).Re .A.B
= Re .(A.B + A.B) + Re .(A.B + A.B)
= Re .(A ⊕ B) + Re .A ⊕ B
= Re ⊕ A ⊕ B

R = C.Re .A.B + C.Re .A.B + C.Re .A.B + C.Re .A.B +

C.Re .A.B + C.Re .A.B + C.Re .A.B + C.Re .A.B
= C.Re .(A.B + A.B) + C.Re .(A.B + A.B) + C.(Re + Re ).A.B + C.(Re + Re ).A.B
= (C.(A ⊕ B) + C.(A ⊕ B)).Re + (C.A + C.A).B
= (C ⊕ A ⊕ B).Re + (C ⊕ A).B
| {z } | {z }
R2 R1

Le schéma de l’additionneur/soustracteur est immédiat :

Re S
1/2-a-s R2
A
1/2-a-s R1 ≥1 Rs
B
C

3
 4. Le schéma d’un additionneur/soustracteur quatre bits par quatre bits s’obtient de façon
toute aussi immédiate :

C
B3 B2 B1 B0
A3 A2 A1 A0

R2 R1 R0
Add/Sou Add/Sou Add/Sou Add/Sou 0
Dépassement

S3 S2 S1 S0

Exercice 2. Etudier un circuit combinatoire à quatre entrées a0, a1, a2, a3, et une sortie Z tel
que Z = 1 chaque fois que le numéro codé par l’entier a3a2a1a0 est divisible entièrement par 4
ou 5.

Correction.
a1 a0
a3 a2 00 01 11 10

00 1

01 1 1

11 1 1

10 1 1

Z = a1.a0 + a3.a2.a1 + a3.a2.a0 + a3.a2.a1.a0

= a1.(a0 + a3.a2) + a3.(a2.a0 + a2.a1.a0

d’où le schéma :
a3 a2 a1 a0

1
&
&

&
1 Z
1

&
&
&

4
Exercice 3. Réalisation d’un multiplicateur 2 bits par 2 bits :
1. Réaliser un circuit qui effectue la multiplication 1 bit par 1 bit.
2. Réaliser un multiplicateur 2 bits par 2 bits
(a) directement à l’aide de portes ET, OU , NON, NON–ET, NON–OU. . .
(b) alternativement, à l’aide du multiplicateur 1 bit par 1 bit réalisé ci-dessus et de demi-
additionneurs.

Correction.
1. Circuit qui effectue la multiplication 1 bit par 1 bit : a et b étant les deux bits à multiplier,
la fonction booléenne P = a.b
2. On note a1a0 les deux bits du premier nombre, et b1b0 les deux bits du deuxième nombre ;
le résultat s’écrit sur 4 bits p3p2p1p0.
(a)
b1 b0 a1 a0 p3 p2 p1 p0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 0 0 0 0 0
0 1 0 1 0 0 0 1
0 1 1 0 0 0 1 0
0 1 1 1 0 0 1 1
1 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0
1 0 1 0 0 1 0 0
1 0 1 1 0 1 1 0
1 1 0 0 0 0 0 0
1 1 0 1 0 0 1 1
1 1 1 0 0 1 1 0
1 1 1 1 1 0 0 1

p3 = b1.b0.a1.a0
p2 = b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0
= b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0
= b1.b0.a1 + b1.a1.a0
= b1.a1.(b0 + a0)
= b1.a1.b0.a0
p1 = b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0
= b1.b0.a1 + b1.b0.a0 + b1.b0.(a1 ⊕ a0)
= b1.b0.a1 + b1.(b0.a0 + b0.(a1 ⊕ a0))
p0 = b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0 + b1.b0.a1.a0
= b1.b0.a0 + b1.b0.a0
= b0.a0

5
(b) Remarquons que (développement polynômial d’un nombre en base 2) :

a1a0 = a1 × 21 + a0 × 20
b1b0 = b1 × 21 + b0 × 20

Rappelons que l’exposant associé à la base correspond au rang de chacun des bits qui
codent le nombre. On a alors :

a1a0 × b1b0 = (a1 × 21 + a0 × 20 ) × (b1 × 21 + b0 × 20 )

= a1 × b1 × 22 + (a1 × b0 + a0 × b1) × 21 + a0 × b0 × 20

Dans cette équation

p0 = a0 × b0
p1 = a1 × b0 + a0 × b1 qui représente une somme de deux bits réalisée avec
un demi–additionneur, et donc génère une retenue R1 de rang supérieur
d’où :
p2 = a1 × b1 + R1 qui représente une somme de deux bits réalisée avec
un demi–additionneur, et donc génère une retenue R2 de rang supérieur
d’où :
p3 = R2

Autrement dit,

p3p2p1p0 = R2 × 23 + (a1 × b1 + R1 ) × 22 + (a1 × b0 + a0 × b1) × 21 + (a0 × b0) × 20

Exemple :
11 a1a0 = 11
x 11 b1b0 = 11
----
11
11
----
1001 p3 = 1, p2 = 0, p1 = 0, p0 = 1

A partir des équation de p3, p2, p1, p0 obtenues ci-dessus, on obtient le schéma :

a1 b1 a1 b0 a0 b1 a0 b0

Mult 1−1 Mult 1−1 Mult 1−1 Mult 1−1

Add 1−1

Add 1−1

p3 p2 p1 p0

6
Exercice 4. Réalisation d’un multiplicateur 4 bits par 4 bits :
1. A l’aide du multiplicateur 2 bits par 2 bits de l’exercice précédent et d’additionneurs 2
bits par 2 bits, réaliser un circuit multiplicateur 4 bits par 4 bits.
Indication : A et B étant des entiers codés sur quatre bits, on considère les nombres écrits
par groupes de deux bits dont la place est, comme dans l’exercice précédent, indiquée
par une notation puissance ; par exemple, A = M N et B = P Q, tels que M , N , P , Q
s’écrivent sur deux bits. On note alors (par exemple) {M P } le résultat (sur quatre bits)
de la multiplication M × P , résultat qui se décompose en {M P }F (les deux bits de poids
fort de {M P }) et {M P }f (les deux bits de poids faible de {M P }), d’où :

M × P = {M P }F × b1 + {M P }f × b0 (où b désigne la base)

Question subsidiaire : quelle est la valeur de b ici ?

2. Simuler la multiplication 1110 × 1101 sur le multiplicateur 4 bits par 4 bits ainsi réalisé.

Correction. Question subsidiaire : puisque les nombres sont pris par groupes de 2 bits, b = 4.
Comme dans l’exercice précédent, on pose A = M N, B = P Q où M, N, P, Q sont des couples
de bits. Le produit A × B s’écrit alors :

A × B = MN × PQ
= (M × b1 + N × b0 ) × (P × b1 + Q × b0 )
= {M P } × b2 + ({N P } + {M Q}) × b1 + {N Q} × b0
= ({M P }F × b1 + {M P }f × b0 ) × b2 +
({N P }F × b1 + {N P }f × b0 ) × b1 +
({M Q}F × b1 + {M Q}f × b0 ) × b1 +
({N Q}F × b1 + {N Q}f × b0 ) × b0
= {M P }F × b3 +
R2 × b3 + ({M P }f + {N P }F + {M Q}F ) × b2 +
R1 × b2 + ({N P }f + {M Q}f + {N Q}F ) × b1 +
{N Q}f × b0

On obtient le schéma et la multiplication 1110 × 1101 :

M P N P M Q N Q

11 11 10 11 11 01 10 01

Mult 2−2 Mult 2−2 Mult 2−2 Mult 2−2

F f F f F f F f

01 00 11 00

00 00
Add 2−2 Add 2−2

10 00 01 01 10 11

dépassement Add 2−2 Add 2−2 Add 2−2 00

10 11 01 10

7
Exercice 5. A partir de quatre bascules JK utilisée en mode T (J = K ), réaliser un compteur
binaire asynchrone modulo 16 sur quatre bits.

Correction. Voir la réalisation d’un compteur binaire asynchrone dans le cours.

Exercice 6. Soit le circuit séquentiel synchrone suivant, composé de bascules D :

≥1

I =1 D Q1 D Q2 =1 Y
Q1 Q2

Ce circuit se caractérise par :

– I = {0, 1}, l’ensemble des entrées ;
– Y = {0, 1}, l’ensemble des sorties ;
– Q = {(Q1 , Q2 ) | Qi ∈ {0, 1}, i = 1, 2} = {(0, 0), (0, 1), (1, 0), (1, 1)} = {q0 , q1 , q2 , q3 },
l’ensemble des états du circuits.
– une fonction de transition δ(I, Q) qui permet de déterminer l’état du circuit à l’instant
t + 1 en fonction de son état à l’instant t ;
– une fonction ω(I, Q) qui permet de déterminer les valeurs de la variable de sortie.
On veut déterminer le comportement du circuit, c’est-à-dire, à partir des fonctions δ et ω,
déterminer la table de transition et le diagramme de transition :
1. Donner les équations des sorties Q1 et Q2 des bascules à l’instant t + 1 en fonction des
valeurs de ces sorties et des valeurs d’entrée du circuit à l’instant t ;
2. donner l’équation de la sortie Y du circuit à l’instant t en fonction de l’état et des valeurs
d’entrée du circuit à l’instant t ;
3. donner les équations des fonctions δ et ω ;
4. à partir des équations de δ et ω, construire la table de transition et le diagramme de
transition du circuit.

Correction. Notons par Q1 (t) et Q2 (t) les états actuels des bascules, et par A1 (t+1) et A2 (t+1)
leurs états suivants. A partir du schéma, on obtient les équations suivantes :

Q1 (t + 1) = I(t) ⊕ (Q1 (t) + Q2 (t))

Q2 (t + 1) = Q1 (t)
Y (t) = I(t) ⊕ Q2 (t)

Par conséquent, les deux fonctions de transition s’expriment par :

δ(I, Q) = {I(t) ⊕ (Q1 (t) + Q2 (t)), Q1 (t)}

ω(I, Q) = {I(t) ⊕ Q2 (t)}

La table de transition est construite à partir de ces relations : par exemple lorsque le circuit se
trouve dans l’état q2 = (1, 0), caractérisé par Q1 (t) = 1 et Q2 (t) = 0, l’état suivant est

8
 – pour I(t) = 0,

Q1 (t + 1) = 0 ⊕ (1 + 0)
= 1
Q2 (t + 1) = 1

donc l’état suivant est q3 = (1, 1) ;

– pour I(t) = 1,

Q1 (t + 1) = 1 ⊕ (1 + 0)
= 0
Q2 (t + 1) = 1

donc l’état suivant est q1 = (0, 1).

En même temps, les sorties se caractérisent
– pour I(t) = 0, par Y (t) = 0 ⊕ 0 = 0,
– pour I(t) = 1, par Y (t) = 1 ⊕ 0 = 1.
Par conséquent, la troisième ligne de la table de transitions, qui correspond à l’état initial q2 , doit
contenir les informations suivante : q3 /0 pour I = 0, q1 /1 pour I = 1. On obtient en définitive :

0 1
q0 q0 /0 q2 /1
q1 q2 /1 q0 /0
q2 q3 /0 q1 /1
q3 q3 /1 q1 /0

Le diagramme de transitions découle directement de la table de transition : par exemple, en

partant du même état q2 = (1, 0), la flèche qui effectue la transition vers l’état q3 = (1, 1) doit
porter l’information 0/0, et la flèche qui effectue la transition vers l’état q1 = (0, 1) doit porter
l’information 1/1 :

0/0 1/0

q0 q1

0/1
1/1 1/0
1/1

q2 q3
0/0 0/1

En utilisant l’une des méthodes d’analyse exposées, on peut définir le comportement du circuit
séquentiel pour chaque séquence assignées aux entrées. Supposons que la séquence 01001 ait été
assignée à l’entrée unique et que le circuit se trouve dans l’état q2 = (1, 0). Le comportement du
circuit se caractérise par :
– séquence à l’entrée : 0 1 0 0 1 ;
– séquence des états : q2 q3 q1 q2 q3 q1 ;
– séquence à la sortie : 0 0 1 0 0.