Logique Combinatoirepoukie8.free.fr/ESIL/2%E8me%20semestre/Archi/Cours/… · · 2007-03-15additionneur-soustracteur un nombre codØ sur n bits peut prendre toutes les valeurs comprises

F. Touchard ESIL Département d'Informatique 1ère année 2006-2007 Cours Architecture Logique combinatoire 1

Logique Combinatoire


Introduction

� famille de circuits logiques pour lesquels la sortie dépend uniquement des états des entrées � par opposition à la logique séquentielle où le temps va

intervenir)

� aspect logique et fonctionnel uniquement� pas d'aspect matériel


Addition

� demi-additionneur� addition de 2 bits en base 2

0 + 0 = 000 + 1 = 011 + 0 = 011 + 1 = 10

� il faut éventuellement tenir compte de la retenue (carry)

a3 a

2 a

1 a

0 nombre A

+ b3 b

2 b

1 b

0 nombre B

s3 s

2 s

1 s

0 résultat D

r3 r

2 r

1 r

0 retenue C


Addition

� circuit demi-additionneur (half-adder)

HA

A B

C D

A B C D

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0


Addition


HA

A B

C D

A B C D

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

D = AB + ABC = AB

D = A � BC = AB


Addition


HA

A B

C D

A B C D

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

D = AB + ABC = AB

D = A � BC = AB


Addition

� additionneur� 3 entrées :

� les 2 bits des nombres à ajouter� la retenue de l'étage précédent

� 2 sorties :� le résultat de l'addition� la retenue A B R

S CF. Touchard ESIL Département d'Informatique 1ère année 2006-2007 Cours Architecture Logique combinatoire 8

Addition

� additionneur� 3 entrées :

� les 2 bits des nombres à ajouter� la retenue de l'étage précédent

� 2 sorties :� le résultat de l'addition� la retenue A B R

S C


Addition

� table de vérité

S = ABR + ABR + ABR + ABR

C = ABR + ABR + ABR + ABR

A B R S C0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1


ABR

00 01 11 10

0 11 1 1 1

Addition� tableau de Karnaugh pour simplifier C


ABR

00 01 11 10

0 11 1 1 1


C = AB + AR + BR


ABR

00 01 11 10

0 11 1 1 1


C = AB + AR + BR

ensuite pour simplifier S :C = AB + AR + BR


ABR

00 01 11 10

0 11 1 1 1


C = AB + AR + BR


AC = ABR

BC = ABR

RC = ABR


ABR

00 01 11 10

0 11 1 1 1


C = AB + AR + BR


AC = ABR

BC = ABR

RC = ABR

et enfinS = ABR + ABR + ABR + ABR

= (A + B + R) C + ABR


Addition

� exemple d'implémentation d'un additionneur 1 bit

C = AB + AR + BR

S = (A+B+R)C + ABR


Addition

� addition en parallèle� l'addition de nombres comportant plusieurs bits peut se

faire en série (bit après bit) ou en parallèle (tous les bits simultanément)


Addition

� implémentation possible d'un additionneur parallèle (Philips 74F283)


Addition

� addition séquentielle� chaque nombre à additionner est représenté par un

train d'impulsions synchrone par rapport à un signal d'horloge

� l'ordre chronologique d'arrivée des impulsions correspond à l'ordre croissant des poids des bits


� les impulsions sont injectées sur les entrées d'un additionneur

� à chaque cycle d'horloge, la retenue provenant des bits de poids inférieurs doit être mémorisée par une bascule D

� un additionneur parallèle est plus rapide mais nécessite davantage de composants

Addition


Soustraction

� demi-soustracteur� table de vérité

D = A-B C : retenue

A B D C0 0 0 0

0 1 1 1

1 0 1 0

1 1 0 0


Soustraction


D = A-B C : retenue

� D = A.B + A.B = A � BC = A.B

A B D C0 0 0 0

0 1 1 1

1 0 1 0

1 1 0 0


Soustraction


D = A-B C : retenue

� D = A.B + A.B = A � BC = A.B

A B D C0 0 0 0

0 1 1 1

1 0 1 0

1 1 0 0


Soustraction� additionneur-soustracteur

� un nombre codé sur n bits peut prendre toutes les valeurs comprises entre 0 et 2n

� le complémentaire d'un mot de n bits est obtenu en prenant le complément de chacun des n bits

� A + A = 2n - 1� -A = A + 1 - 2n

� 2n � 0 (pour une variable codée sur n bits)� -A = A + 1

� A - B = A + B + 1 - 2n

= A + B + 1 (pour des variables codées sur n bits)


Soustraction� additionneur-soustracteur

� un nombre codé sur n bits peut prendre toutes les valeurs comprises entre 0 et 2n

� le complémentaire d'un mot de n bits est obtenu en prenant le complément de chacun des n bits

� A + A = 2n - 1� -A = A + 1 - 2n

� 2n � 0 (pour une variable codée sur n bits)� -A = A + 1

� A - B = A + B + 1 - 2n

= A + B + 1

code opération O : 0 : addition 1 : soustraction


Comparaison

� A=B, A>B, A<B� table de vérité

A B C(A>B) D(A<B) E(A=B)

0 0 0 0 1

0 1 0 1 0

1 0 1 0 0

1 1 0 0 1


Comparaison


� on en déduit :

C = A.B

D = A.B

E = AB + AB = C + D


0 0 0 0 1

0 1 0 1 0

1 0 1 0 0

1 1 0 0 1


Comparaison


� on en déduit :

C = A.B

D = A.B

E = AB + AB = C + D


0 0 0 0 1

0 1 0 1 0

1 0 1 0 0

1 1 0 0 1


Contrôle de parité

� la parité d'un mot binaire est définie comme la parité de la somme des n bits qui le composent

� le OU EXCLUSIF donne la parité d'un sous-ensemble de 2 bits

A B Y = A�B0 0 0

0 1 11 0 11 1 0



� principe du contrôle de parité :� partant d'un mot de n bits� le mot de n+1 bits formé en adjoignant au mot de n bits

son bit de parité est toujours de parité nulle

� si P' est maintenue à 0, P donne la parité du mot de 4 bits



� utilisation du contrôle de parité pour valider la transmission de données

� P2 doit être nul pour valider la transmission


Décodage

� l'opération de décodage permet d'identifier un objet parmi N à partir d'un code l'identifiant de façon unique

� exemple :� N=2n instructions numérotées de 0 à N-1� il faut n bits pour représenter le numéro de chaque

instruction� un décodeur va prendre en entrée les n bits permettant

d'identifier une instruction et en sortie va activer (mettre à un niveau 1) la ligne correspondant à l'instruction


Décodage

� exemple : 8 instructions codées sur 3 bits

01234

56

7


Décodage


0

0

0

01234

56

7

10000000


Décodage


0

0

1

01234

56

7

01000000


Décodage


0

1

0

01234

56

7

00100000


Décodage


1

1

0

01234

56

7

00000010


Décodage


1

1

1

01234

56

7

000000

10


Décodage

� Représentation BCD� la représentation Binary Coded Decimal (décimale

codée binaire) remplace chacun des chiffres décimaux par 4 chiffres binairesCette représentation conserve la structure décimale (unités, dizaines, centaines, etc...)

� chaque chiffre est codé sur 4 bits selon la table suivante :

Décimal BCD

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001


Décodage

� Représentation BCD� la représentation Binary Coded Decimal (décimale

codée binaire) remplace chacun des chiffres décimaux par 4 chiffres binairesCette représentation conserve la structure décimale (unités, dizaines, centaines, etc...)

� chaque chiffre est codé sur 4 bits selon la table suivante

le chiffre 294 sera codé :0010 1001 0100

Décimal BCD

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001


Décodage

� utilisation pour un afficheur

� le rôle des transcodeur est de positionner à 1 les lignes correspondant aux segments à allumer

10 10 10


Décodage

� Décodeur BCD-décimal� table de vérité

D C B A L0 L1 L2 L3 L4 L5 L6 L7 L8 L9

0 0 0 0 1

0 0 0 1 1

0 0 1 0 1

0 0 1 1 1

0 1 0 0 1

0 1 0 1 1

0 1 1 0 1

0 1 1 1 1

1 0 0 0 1

1 0 0 1 1


Décodage

� Décodeur BCD-décimal� table de vérité

la ligne 5 correspond à ABCD

D C B A L0 L1 L2 L3 L4 L5 L6 L7 L8 L9

0 0 0 0 1

0 0 0 1 1

0 0 1 0 1

0 0 1 1 1

0 1 0 0 1

0 1 0 1 1

0 1 1 0 1

0 1 1 1 1

1 0 0 0 1

1 0 0 1 1


Décodage

� activation des lignes en présence seulement d'un signal de commande global (strobe)


Multiplexage

� pour transmettre sur une seule ligne des informations en provenance de plusieurs sources possibles à destination de plusieurs cibles� analogie mécanique


Multiplexage

� Démultiplexeur� circuit avec une entrée et N sorties, mettant en relation

l'entrée avec une seule des sorties� sélection de la sortie à l'aide de lignes d'adressage

� très proche d'un décodeur� exemple

� 1 ligne d'entrée portant les données D� 4 lignes de sortie Y0, Y1, Y2, Y3

� 2 lignes d'adressage A et B� validation de l'adressage par un strobe E (Enable) à 0


Multiplexage

� table de correspondance

E B A Y0 Y1 Y2 Y3 Produit

0 0 0 D 0 0 0 A B E D

0 0 1 0 D 0 0 A B E D

0 1 0 0 0 D 0 A B E D

0 1 1 0 0 0 D A B E D1 0 0 0 0 0 01 0 1 0 0 0 01 1 0 0 0 0 01 1 1 0 0 0 0


Multiplexage

� implémentation correspondante

� il se fabrique des démultiplexeurs avec 2, 4 ou 16 lignes de sortie


Multiplexage

� mise en cascade de plusieurs démultiplexeurs� démultiplexeur à 32 sortie réalisé avec un "tronc" de 4

sorties et 4 "branches" de 8 sorties


Multiplexage� multiplexeur

� réalise l'opération inverse : sélectionne une entrée parmi N et transmet l'information à une sortie unique

� exemple :� 4 entrées (2 lignes d'adressage et 1 strobe)

Y = ABEX0 + ABEX1 + ABEX2 + ABEX3

E B A Y

0 0 0 X0

0 0 1 X1

0 1 0 X2

0 1 1 X3

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 0


Multiplexage� multiplexeur

� réalise l'opération inverse : sélectionne une entrée parmi N et transmet l'information à une sortie unique

� exemple :� 4 entrées (2 lignes d'adressage et 1 strobe)

Y = ABEX0 + ABEX1 + ABEX2 + ABEX3

E B A Y

0 0 0 X0

0 0 1 X1

0 1 0 X2

0 1 1 X3

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 0


Multiplexage

� mise en cascade de plusieurs multiplexeurs


Multiplexage� Réalisation d'une conversion parallèle-série

� mot de n bits présent sur les n entrées d'un multiplexeur :Xj correspondant au bit 2j

� si les lignes d'adresses sont connectées aux sorties d'un compteur de période T

� table de vérité en fonction du temps

� les bits X0, X1, X2, X3, se retrouvent en série dans le temps sur la sortie du multiplexeur

t B A Y[0, T] 0 0 X0

[T, 2T] 0 1 X1

[2T, 3T] 1 0 X2

[3T, 4T] 1 1 X3

[4T, 5T] 0 0 X0


Multiplexage

� Réalisation d'une fonction logique� exemple d'une fonction F de 4 variables définie par sa

table de vérité :x y z t F

0 0 0 0 1

0 0 0 1 0

0 0 1 0 1

0 0 1 1 0

0 1 0 0 0

0 1 0 1 1

0 1 1 0 0

0 1 1 1 0

1 0 0 0 1

1 0 0 1 1

1 0 1 0 1

1 0 1 1 1

1 1 0 0 0

1 1 0 1 1

1 1 1 0 0

1 1 1 1 0


Multiplexage


table de vérité :x y z t F Multiplexeur

0 0 0 0 1 X0

0 0 0 1 0 X1

0 0 1 0 1 X2

0 0 1 1 0 X3

0 1 0 0 0 X4

0 1 0 1 1 X5

0 1 1 0 0 X6

0 1 1 1 0 X7

1 0 0 0 1 X8

1 0 0 1 1 X9

1 0 1 0 1 X10

1 0 1 1 1 X11

1 1 0 0 0 X12

1 1 0 1 1 X13

1 1 1 0 0 X14

1 1 1 1 0 X15


Multiplexage


table de vérité :x y z t F Multiplexeur

0 0 0 0 1 X0

0 0 0 1 0 X1

0 0 1 0 1 X2

0 0 1 1 0 X3

0 1 0 0 0 X4

0 1 0 1 1 X5

0 1 1 0 0 X6

0 1 1 1 0 X7

1 0 0 0 1 X8

1 0 0 1 1 X9

1 0 1 0 1 X10

1 0 1 1 1 X11

1 1 0 0 0 X12

1 1 0 1 1 X13

1 1 1 0 0 X14

1 1 1 1 0 X15

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

X0

X15

1

x y z t

F

X1


Encodage

� opération inverse du décodage� N = 2n lignes en entrée� n lignes en sortie� lorsque une des lignes est activée en entrée,

l'encodeur fournit en sortie un mot de n bits correspondant au codage de l'information identifiée par la ligne d'entrée

� exemple d'une conversion décimal-BCD� 10 entrées (de 0 à 9)� 4 sorties (codes BCD)


Encodage


� expressions logiquesY0 = W1 + W3 + W5 + W7 + W9

Y1 = W2 + W3 + W6 + W7

Y2 = W4 + W5 + W6 + W7

Y4 = W8 + W9

W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 Y3 Y2 Y1 Y0

1 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 1

0 0 1 0 0 0 0 0 0 0 0 0 1 0

0 0 0 1 9 0 0 0 0 0 0 0 1 1

0 0 0 0 1 0 0 0 0 0 0 1 0 0

0 0 0 0 0 1 0 0 0 0 0 1 0 1

0 0 0 0 0 0 1 0 0 0 0 1 1 0

0 0 0 0 0 0 0 1 0 0 0 1 1 1

0 0 0 0 0 0 0 0 1 0 1 0 0 0

0 0 0 0 0 0 0 0 0 1 1 0 0 1


Encodage

� implémentation possible de la fonction de décodage avec des portes OU réalisées par des diodes


Encodage

� justification� le circuit :

correspond à la table de vérité :

qui est celle d'un OU inclusif

A B S

0 0 0

0 1 1

1 0 1

1 1 1


Encodage

� le bon fonctionnement du montage suppose qu'une seule ligne d'entrée peut être à 1 à un instant donné

� le prolème de l'activation simultanée de plusieurs lignes se résoud par un encodeur prioritaire :

� si plusieurs lignes sont activées simultanément en entrée, une seule sortie (la plus prioritaire) sera activée en sortie


Encodage

� table de vérité d'un encodeur prioritaire où la ligne prioritaire est celle qui a l'indice le plus élevé

� les croix indiquent que le code de sortie est indépendant de l'entrée correspondante

W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 Y3 Y2 Y1 Y0

1 0 0 0 0 0 0 0 0 0 0 0 0 0

X 1 0 0 0 0 0 0 0 0 0 0 0 1

X X 1 0 0 0 0 0 0 0 0 0 1 0

X X X 1 0 0 0 0 0 0 0 0 1 1

X X X X 1 0 0 0 0 0 0 1 0 0

X X X X X 1 0 0 0 0 0 1 0 1

X X X X X X 1 0 0 0 0 1 1 0

X X X X X X X 1 0 0 0 1 1 1

X X X X X X X X 1 0 1 0 0 0

X X X X X X X X X 1 1 0 0 1


Encodage

� pour écrire les expressions logiques définissant les lignes de sortie en fonction des entrées, il faut maintenant tenir compte des 0exemple : Y0 = W1 W2 W3 W4 W5 W6 W8 W8 W9 + W3 W4 W5 W6 W7 W8 W9 + W5 W7 W8 W9 + W7 W8 W9 + W9

= W9 + W8(W7 + W6(W5 + W4(W3 + W2W1)))


Encodage

� les encodeurs à priorité sont fréquemment utilisés pour la gestion des interruptions

� souvent plusieurs périphériques veulent accéder à un même système

� utilisent une ligne d'interruption qui leur est propre� mais une seule interruption peut être satisfaite à la fois� nécessaire d'établir un ordre de priorité :

A > B > C > D

ABCD

Z

XY

X Y Demandeur

0 0 D

0 1 C

1 0 B

1 1 A


Les encodeurs


� équations logiques� Z = A + B + C + D� X = A + B� Y = A + BC

A B C D X Y Z

0 0 0 0 Ø Ø 0

0 0 0 1 0 0 1

0 0 1 X 0 1 1

0 1 X X 1 0 1

1 X X X 1 1 1

Documents

Logique Combinatoirepoukie8.free.fr/ESIL/2%E8me%20semestre/Archi/Cours/… · · 2007-03-15additionneur-soustracteur un nombre codØ sur n bits peut prendre toutes les valeurs comprises