Corrige-TD04

8/3/2019 Corrige-TD04

1/7

Architecture des ordinateurs

Corrig du TD 4 : Circuits combinatoires

Arnaud Giersch, Benot Meister et Frdric Vivien

1. Exprimer la fonction xor comme un produit de sommes et raliser le circuit logique correspondant.

Correction : AB = (A +B) (A +B)

(A +B) (A +B)

A

B

Mme question en exprimant xor comme une somme de produits.

Correction : AB = A B +A BA

B

A B +A +B

2. La fonction nand formant un groupe logique complet, raliser, uniquement avec des portes nand, les circuits

logiques not, and, or et xor (les formules sont rappeles ci-dessous).

not(A) = nand(A,A) and(A,B) = nand(nand(A,B),nand(A,B))

or(A,B) = nand(nand(A,A),nand(B,B)) xor(A,B) = nand(nand(nand(A,A),B),nand(A,nand(B,B)))

Correction :

A A

B

AA B

A B = A B

A

B

A

B

A B = A +B

B

AA

B

A B

A B

A B A B = AB

3. Raliser un circuit logique qui implmente la fonction F.

F = (A +B +C) (A +B +C) (A +B +C)

Correction :

1


2/7

A

B

C

F

4. Un gnrateur de parit impaire est une fonction qui retourne 1 si le nombre de bits 1 est impair et 0 sinon.

Dfinir cette fonction pour un mot de 4 bits. Donner un circuit logique implmentant cette fonction.

Correction : La formule pour le gnrateur de parit impaire sur 4 bits (P) obtenue directement partir de la

table de vrit est :

P =A B CD +A B CD +A B CD +A B CD

+

+A B CD +A B CD +A B CD +A B CD

ce qui donnerait un circuit beaucoup trop compliqu !

On remarque que pour deux bits, P = AB :

A B P

0 0 0

0 1 1

1 0 1

1 1 0

On en dduit les circuits suivants :

A

B

C

D

P ou

A

B

C

D

P

5. Rappeler les principes dun demi-additionneur puis dun additionneur complet. Dduire de ces principes un

circuit logique qui implmente le complment 2 sur n bits.

Correction : Le demi-additionneur possde deux entres (x et y) et deux sorties (R et S). S correspond au bit de

rang zro du rsultat de laddition binaire de x et y, R au bit de rang 1 (retenue).

y x

R

S

HA

x y R S

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

S = xy

R = x y

Un additionneur complet sobtient en enchanant des demi-additionneurs de manire propager correctementla retenue.

On obtient selon le mme principe le circuit effectuant un complment deux :En

1

E0E1E2E3

Sn S3 S2 S1 S0

HA HAHAHAHA

2


3/7

6. Raliser un circuit pour un dcrmenteur n bits.

Correction : On pourrait imaginer utiliser un soustracteur avec le deuxime oprande gal 1 pour raliser

un dcrmenteur.

Or la dcrmentation (comme lincrmentation) est une opration frquente sur certains registres (compteur

ordinal, registre dindex, registre dadresse, . . .). Donc pour gagner du temps on souhaite construire un circuit

spcialis.Considrons An1 . . .A1A0 le nombre binaire dcrmenter. Appelons Sn1 . . .S1S0 le rsultat de la dcrmen-

tation.

On sait que S est obtenu par soustraction de 1 et propagation de la retenue (Ri). On a donc :

S0 = A0 1 :

A0 1 S0 R00 1 1 1

1 1 0 0

S0 = A0

R0 = A0

et Si = Ai Ri1 :

Ai Ri1 Si Ri0 0 0 0

0 1 1 1

1 0 1 0

1 1 0 0

Si = Ai Ri1

Ri = Ai Ri1

Do le circuit :An

Sn

A3

S3 S2

A2 A1

S1 S0

A0

Overflow

R0R1R2R3Rn1

7. Le soustracteur

(a) Raliser un demi-soustracteur (table de vrit et circuit).

Correction : Le demi-soustracteur est dfini par la table de vrit suivante (le bit B i est retranch au bit

Ai) :

Ai Bi Di Ri0 0 0 0

0 1 1 1

1 0 1 0

1 1 0 0

Di contient la diffrence Ai BiRi contient la retenue ventuelle

On a donc :

Di = Ai Bi

Ri = Ai Bi

Do le circuit logique :

3


4/7

Di = Ai Bi

Ri = Ai Bi

Ai

Bi

(b) Raliser un soustracteur binaire complet (ou tage de soustracteur) selon deux modes :

i. avec deux demi-soustracteurs ;

Correction : Pour obtenir un soustracteur binaire complet il faut prendre en compte lventuelle

retenue prcdente Ri1. La table de vrit est :

Ri1 Ai Bi Di Ri0 0 0 0 0

0 0 1 1 1

0 1 0 1 0

0 1 1 0 0

1 0 0 1 1

1 0 1 0 1

1 1 0 0 0

1 1 1 1 1

Di = Ri1 (Ai Bi) +Ri1 (Ai Bi)

= (AiBi)Ri1

Ri = Ri1 Ai Bi +Ri1 Ai Bi

+Ri1 Ai Bi +Ri1 Ai Bi

= Ai Bi (Ri1 +Ri1)

+ (Ai Bi +Ai Bi) Ri1

= Ai Bi + (Ai Bi) Ri1

do le circuit :Ai Bi

Ai Bi

Ai

Bi

Ri1

Di = Ai Bi Ri1

Ri = Ai Bi +(Ai Bi ) Ri1

HSHS

Ce schma correspond au fait que le soustracteur est ralis en

(1) retranchant Bi de Ai (1er demi-soustracteur) ;

(2) puis en retranchant Rii de la diffrence obtenue.

ii. avec un demi-additionneur et un demi-soustracteur.

Correction : Une autre manire de procder consiste :

(1) additionner Bi et Ri1 avec un demi-additionneur (cette opration peut videmment engendrerune retenue);

(2) puis en retrancher le rsultat obtenu de Ai.

Cela est obtenu par transformation des fonctions logiques :

Di = Ai (Bi Ri1)

Ri = Ai (Bi Ri1 +Bi Ri1) + (Ai +Ai) Bi Ri1

= Ai (Bi Ri1) +Bi Ri1

do le circuit :

Bi Ri1

Ai

Ri1

Bi

Ri = Ai (Bi Ri1)+ Bi Ri1

Di = Ai Bi Ri1

Bi Ri1

Ai (Bi Ri1)

HA

HS

(c) Raliser un soustracteur parallle pour mots de 8 bits.

Correction : On utilise 8 soustracteurs complets :A0B0

D0

R0

A1B1

D1

R1

A2B2

D2

R2

A3B3

D3

R3

A4B4

D4

R4

A5

D5

B5

R5

A6B6

D6

R6

A7B7

D7

R7

Overflow

0FS FS FS FS FS FS FS FS

4


5/7

8. Le (d)multiplexeur

Un multiplexeurest un circuit logique qui dispose de 2n entres, dune unique sortie et de n lignes de slection.

Son principe de fonctionnement consiste connecter, selon la configuration binaire prsente sur les n lignes de

slection, lune des entres la sortie. Les n lignes de slection diffrencient 2n configurations binaires, chacune

de ces configurations correspondant lentre du multiplexeur qui doit tre connecte la sortie.

Un dmultiplexeur, pour sa part, est un circuit logique qui dispose dune unique entre, de 2 n sorties et de n

lignes de slection. Son principe de fonctionnement, linverse de celui du multiplexeur, consiste connecter,

selon la configuration binaire prsente sur les lignes de slection, lentre lune des sorties.

(a) Raliser un multiplexeur quatre voies (cest--dire un multiplexeur quatre entres).

Correction : Soit S0,S1 les lignes de slection, I0, . . . ,I4 les entres et O la sortie (cf. fig. 1).

(b) Raliser un dmultiplexeur quatre voies (cest--dire un dmultiplexeur quatre sorties).

Correction : Soit S0,S1 les lignes de slection, I lentre et O0, . . . ,O3 les sorties (cf. fig. 2).

I0

I1

I2

I3

S1 S0

O

FIG . 1 Multiplexeur 4 voies.

S1 S0I

O0

O1

O2

O3

FIG . 2 Dmultiplexeur 4 voies.

9. Les hasards logiques

Le temps de passage dune porte logique est la dure entre linstant o les signaux sont appliqus lentre et

celui o leur effet se rpercute en sortie. Jusqu prsent, ce temps de passage a t ignor dans un souci de

simplification. Toutefois, le temps de passage dune porte logique nest jamais nul (de lordre de 5 25 ns).

Si un tage logique est construit laide de portes logiques (cest--dire si la sortie dune porte logique attaque

lune des entres de la porte logique suivante) alors le temps de passage de ltage est au moins gal la somme

des temps de passage des portes logiques qui le composent : dans ce cas, les temps de passage sajoutent. Il

en rsulte quun changement des donnes en entre dun montage, non seulement mettra un certain temps

se rpercuter en sortie, mais pourra en plus provoquer des changements dtat (impulsions) non souhaits la

sortie. De telles impulsions parasites sont appeles hasards logiques.

(a) Mise en vidence dun hasard logique.

i. Exprimer la valeur de la sortie S du circuit ci-dessous en fonction de son entre E.

S2

S1E

S

5


6/7

Correction :

S1 = E

S2 = EE = 1

S = S2 = 1 = 0

ii. Complter le chronogramme suivant de ce circuit (on considre que toutes les portes logiques mises

en jeu ont un mme temps de passage t).

1

0

0

0

0

1

1

1

t

Entre E

Sortie S1

Sortie S2

Sortie S

Correction :

1

0

0

0

0

1

1

1

t

Entre E

Sortie S1

Sortie S2

Sortie S

Ce circuit se comporte comme un dtecteur de transitions. Il peut tre simplifi en remplaant le nand

et le deuxime not par un and, carnot(nand(a,b)) = and(a,b).

(b) Exemples de mise profit des hasards logiques : dtecteur de transitions.

i. Exprimer la valeur de la sortie S du circuit ci-dessous en fonction de son entre E.

S

S10

E

Correction :

S1 = E0 = E (cest la fonction identit, mais avec un dlai)

S = EE = 0

La sortie de ce circuit devrait donc toujours valoir 0. Mais le retard introduit par le premier xor

implique que tout changement dun tat de E entrane une impulsion positive de S comme le montre

le chronogramme ci-dessous.

ii. Complter le chronogramme suivant de ce circuit (on considre que toutes les portes logiques mises

en jeu ont un mme temps de passage t).

1

0

0

1

Entre E

Sortie S1

1

0Sortie S

t

6


7/7

Correction :

1

0

0

1

Entre E

Sortie S1

1

0Sortie S

t

iii. Raliser un dtecteur de transitions pour lequel la dure des impulsions en S est de 3t.

Correction : Il suffit davoir un dlai de 3t entre les deux entres du xor. Ce dlai peut tre obtenu

en ajoutant au circuit prcdent deux portes xor, ou laide dun autre circuit ralisant lidentit

avec un dlai de 3t, comme par exemple un xor et deux not.

S4

32

1E

0

31E

S

0 2

4

(c) Raliser un dtecteur de front montant, cest--dire un dtecteur de transitions qui ne rpond que lorsque

le signal dentre passe dun niveau bas un niveau haut.

Correction : On se base toujours sur un dlai entre deux entres dune porte logique. Les portes logiques

choisies filtrent ensuite les cas souhaits. Ici, on utilise une porte not etand.

S1

SE 1

2

1

0

0

1

Entre E

Sortie S1

1

0Sortie S

t

(d) Raliser un dtecteur de front descendant, cest--dire un dtecteur de transitions qui ne rpond que lorsquele signal dentre passe dun niveau haut un niveau bas.

Correction : Ici on utilise une porte logique not etnor.

S1

SE

1

0

0

1

Entre E

Sortie S1

1

0Sortie S

t

7

Documents

Corrige-TD04