Architecture des Ordinateurs, corrigé TD 1

Fonctions booléennes
Remarque : Les schémas des circuits logiques sont réalisés à partir de la notation IEEE :

Porte IDENTITÉ 1

Porte NON 1 ou

Porte OU ≥1

Porte ET &

Porte OU-EXCL =1

Exercice 1. 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

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

1
&
&

&
1 Z
1

&
&
&

Exercice 2. On considère un ascenceur desservant un rez-de chaussée et trois étages. L’unité

logique de contrôle de cet ascenceur reçoit en entrée des requêtes de déplacement d’un étage vers
un autre, et génère en sortie les commandes correspondantes destinées au moteur de la cage. Il
s’agit de réaliser les circuits qui composent l’unité de contrôle. Pour cela :
— La valeur de l’étage d’où part la requête (de 0 à 3) est codée par deux variables booléennes
x1 et x2. La valeur courante de l’étage où se trouve la cage de l’ascenceur est codée de
façon similaire par deux variables booléennes x3 et x4.
— La sortie de l’unité de contrôle est constituée de trois fonctions booléennes Haut, Bas,
Stop des quatre variables d’entrée x1, x2, x3, et x4. Haut(x1, x2, x3, x4) est vraie quand
la position courante de la cage est au-dessous de l’étage d’où part la requête et fausse
autrement. Inversement, Bas(x1, x2, x3, x4) est vraie quand la position courante de la
cage est au-dessus de l’étage d’où part la requête et fausse autrement. Finalement,
Stop(x1, x2, x3, x4) est vraie quand l’étage d’où part la requête et la position courante
de l’ascenceur sont les mêmes, et fausse autrement.
On vous demande de :
1. représenter chacune des fonctions de l’unité de contrôle par une table de Karnaugh ;
2. simplifier ces fonctions ;
3. dessiner les schémas des circuits correspondant à chacune des fonctions simplifiées, en
utilisant le plus petit nombre possible de portes.

Correction. La valeur de l’étage d’où part la requête est représentée par la table binaire sui-
vante :

x1 x2 Etage
0 0 Rez-de-chaussée
0 1 1er
1 0 2d
1 1 3ème

2
De même, la valeur courante de l’étage où se trouve la cage de l’ascenceur est représenté par la
table binaire :

x3 x4 Etage
0 0 Rez-de-chaussée
0 1 1er
1 0 2d
1 1 3ème

Pour la fonction booléenne Haut(x1, x2, x3, x4) par exemple, il suffit de remplir une table de
Karnaugh à quatre variables de telle façon que pour chaque case un “1” y est placé si la valeur
courante de l’étage où se trouve la cage de l’ascenceur est plus basse que la valeur de l’étage d’où
part la requête, et un “0” y est placé sinon :

x3 x4

x1 x2 00 01 11 10

00 0 0 0 0

01 1 0 0 0

11 1 1 0 1

10 1 1 0 0

L’expression booléenne résultante après simplification est :

Haut(x1, x2, x3, x4) = x1.x3 + x2.x3.x4 + x1.x2.x4

Bien que cette expression soit une forme normale disjonctive minimale, il est possible de pousser
la simplification plus loin :

x1.x3 + x2.x3.x4 + x1.x2.x4 = x1.x3 + x2.x4.(x3 + x1)

Le circuit obtenu a exactement sept portes logiques :

x1
&

x2
Haut (x1, x2, x3, x4)
1 1
x3 1 &

&
x4 1

3
Les autres fonctions booléennes sont établies de la même manière.

Exercice 3. On désire réaliser le système inclus dans une calculette qui à un digit décimal fait
correspondre l’allumage de segments représentant ce digit. Le digit étant codé sur quatre valeurs
A, B, C, D, calculer les sept fonctions a, b, c, d, e, f, g commandant l’éclairement des segments
correspondants :
a

f b
g

e c

Correction.
A B C D a b c d e f g
0 0 0 0 1 1 1 1 1 1 0
0 0 0 1 0 1 1 0 0 0 0
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1
0 1 1 0 1 0 1 1 1 1 1
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 x x x x x x x
1 0 1 1 x x x x x x x
1 1 0 0 x x x x x x x
1 1 0 1 x x x x x x x
1 1 1 0 x x x x x x x
1 1 1 1 x x x x x x x

C D

A B 00 01 11 10

00 1 0 1 1

01 0 1 1 1

11 X X X X

10 1 1 X X

4
 a = A + C + B.D + B.D
. . .
. . .

g = A + B.C + B.C + C.D

Exercice 4. 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, conce-
voir 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 addi-
tionneur/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

5
 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 rete-
nue. 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

6
 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
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 = [Link] .A.B + [Link] .A.B + [Link] .A.B + [Link] .A.B +

[Link] .A.B + [Link] .A.B + [Link] .A.B + [Link] .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 = [Link] .A.B + [Link] .A.B + [Link] .A.B + [Link] .A.B +

[Link] .A.B + [Link] .A.B + [Link] .A.B + [Link] .A.B
= [Link] .(A.B + A.B) + [Link] .(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

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

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

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

8
Exos supplémentaires
Exercice 5.
1. Exprimer les opérateurs NON, ET, OU en fonction de l’unique opérateur NON-OU,
résultant de la composition de NON et OU, et vu comme un opérateur booléen à part
entière défini par :
NON − OU (x, y) = x + y

2. Exprimer avec des NON-OU uniquement l’expression booléenne suivante :

((x1 + x2 ).(x3 + x4 .x5 )).x6

3. Dessiner ensuite le schéma logique correspondant.

Correction.
NON x=x+x
ET x.y = x.y = x + y = x + x + y + y
OU x+y =x+y = x+y+x+y

f (x1 , x2 , x3 , x4 , x5 , x6 ) = ((x1 + x2 ).(x3 + x4 .x5 )) .x6

| {z }
x7

= x7 + x7 + x6
= x7 + x7 + x6

x7 = (x1 + x2 ).(x3 + x4 .x5 ))

= (x1 + x2 ) + (x1 + x2 ) + (x3 + x4 .x5 ) + (x3 + x4 .x5 )
= (x1 + x2 ) + (x3 + x4 .x5 )
x4 .x5 = x4 + x4 + x5 + x5

d’où :

x7 = x1 + x2 + x3 + x4 + x4 + x5 + x5

x1
1
x2
x7
x3 1
1
x 1
4 1 1
1
x5 1

x6

9
Exercice 6. Réalisation d’un multiplicateur 2 bits par 2 bits :
— Réaliser un circuit qui effectue la multiplication 1 bit par 1 bit.
— Réaliser un multiplicateur 2 bits par 2 bits
— directement à l’aide de portes ET, OU, NON, NON–ET, NON–OU . . .
— 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

10
(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

11