Download pdf - Chapitre 4 - e-monsitegenie-indus.e-monsite.com/medias/files/logique-combinatoire.pdf · Pour N=4 ÎSoustracteur Complet 4-bits La logique hardware réalisant « le complément à2»,

(c) Hiver 2003, Rachid Beguenane DSA-UQAC 1

Chapitre 4 : 2ème Partie

Chapitre 4 : Logique Combinatoire

4.4 Additionneurs et Soustracteurs Binaires

4.4.1 Semi-Additionneur4.4.2 Addition Multi-Binaire4.4.3 Additionneur Complet 1-bit4.4.4 Additionneur Complet N-bit4.4.5 Soustracteur Complet N-bit4.4.6 Circuit Additionneur/Soustracteur 4.4.7 Le problème de Dépassement 4.4.8 Additionneur BCD4.4.9 Additionneur « LookAhead »

4.5 Multiplicateur Binaire


4.4 Additionneurs et Soustracteurs Binaires

L’Addition et la Soustraction des données binaires sont des opérations fondamentales dans les circuits digitaux

D’ou le besoin de déterminer leur implémentation hardware

Représenter les entrées et les sorties. Par exemple pour l’additionneur:

Entrées : Bits singuliers à ajouter, Retenue d’entrée (Carry in)Sorties : Somme, Retenue de sortie (Carry out)

Caractéristiques HardwareCréer des Additionneurs/Soustracteurs (à 1-bit) et enchaîner l’ensemble

Cas de dépassement (overflow) pour l’additionComment prendre en considération le cas des nombres longs?


4.4.1 Semi-Additionneur Ou Demi-Additionneur (Sans Retenue d’entrée)

A 0 B 0

S 0

C 1

C A B S 0 0 0 1

0 0 0 00 1 1 01 0 1 01 1 0 1

Dec Binary1 1+1 +12 10

Ajouter 2 digits binairesA0 , B0 -> les bits singuliers d’entréeS0 -> la Somme (un bit singulier)C1 -> La Retenue de sortie (carry out)


4.4.2 Addition Multi-Binaire

Considérer un additionneur 1-bit pour chaque position binaire.

A3 A2 A1 A00 1 0 1A 0 1 1 1B3 B2 B1 B0

B

Ai+Bi

Ci

Si

Ci+1

0 1 0 10 1 1 1

AB

0

1

0

1

1

1

1

C

SChaque position binaire crée une Somme et une Retenue (Carry)


4.4.3 Additionneur Complet à 1-bit

Un additionneur complet (à 1-bit) inclut la Retenue d’entrée Ci.Donc il possède deux sorties (Ci+1, Si).Le positionnement des ‘1’ dans le Tableau-K pous Si, rappelle quelque chose. C’est quoi?

XOR

0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

Ci Ai Bi Si Ci+1

1 1

1 1

Ci

AiBi 00 01 11 10

0

1

Si

Si

AiBi

Ci


Maintenant considérant l’implémentation de Ci+1 ‘Carry out’.

Ci+1= Ai.Ci + Bi.Ci + Ai.Bi

11 11

Ci

AiBi 00 01 11 10

0

1

Bi

Ai

Ci+1

Ci0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

Ci Ai Bi Si Ci+1

Ou bien

Ci+1= Ai.Bi + Ci.(Ai + Bi)+

11 11

CiAiBi 00 01 11 10

0

1

Bi

AiCi+1

Ci


Un Additionneur Complet (à 1-bit) peut ainsi être fait à partir de plusieurs 2 Semi-Additionneurs 1-bit, en plus d’une porte OU.

Ci+1= Ai.Bi + Ci.(Ai + Bi)Si = Ai + Bi + Ci

A B

S C

C i+1

ii

i

i

Semi-Additionneur Semi-Additionneur

Note Importante: Une répétition Hardware simplifie énormément la conception des circuits digitaux.


Un Additionneur Complet (à 1-bit) est une pièce essentielle dans lesconceptions de systèmes digitaux.

AdditionneurComplet

(1-bit)

A B

C C

S

i i

i+1 i

iBlock Diagramme


4.4.4 Additionneur Complet N-bits

Pour obtenir un Additionneur Complet (à N-bit), il suffit d’enchaîner ‘N’ Additionneur Complet (à 1-bit) en série. Par exemple, pour N=4:

A B

0 C

S

0 0

1

0

A B

C

S

1 1

2

1

A B

C

S

2 2

3

2

AdditionneurComplet(1-bit)

A B

C S

3 3

4 3


AdditionneurComplet

(1-bit)

AdditionneurComplet

(1-bit)

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


Additionneur Complet 8-bitsPour N=8

A B

C

S

4 4

5

4

A B

C

S

5 5

6

5

A B

C

S

6 6

7

6


A B

C S

7 7

87

AdditionneurComplet

(1-bit)

AdditionneurComplet

(1-bit)


A B

0 C

S

0 0

1

0

A B

C

S

1 1

2

1

A B

C

S

2 2

3

2


A B

C

S

3 3

4

3

AdditionneurComplet

(1-bit)

AdditionneurComplet

(1-bit)


Conséquence: Le temps de propagation (ou le retard) est proportionnel à la taille (n) de l’Additionneur Complet.Par exemple: Un Additionner Complet 8-bits est plus lent à s’exécuter par rapport à un Additionner Complet 4-bits, car le temps de la propagation de la Retenue Ci est deux fois plus pour obtenir le résultat final.

Ce type d’Additionneur s’appelle Additionner à Propagation de Retenue. Il existe d’autres types d’additionneur plus rapide, tel que « Look-Ahead Adder ».


4.4.5 Soustracteur Complet N-bits

Un Soustracteur Complet (à N-bit) peut aisément se réaliser en ayant en tête cette propriété, démontrée au chapitre 1:

Soustraire un nombre est la même chose que:1. Performer le complément à 2 (C’2) de ce nombre …2. … et faire l’addition ensuite.

+12 00001100- +(C’2 de +33)+33 11011111-----------------------------21 0 11101011

110 = 0116 = 00000001-110 = FF16 = 1111111112710 = 7F16 = 0111 1111

-12710 = 8116 = 1000 0001

Ainsi si on ajoute à un additionner complet (à n-bit) une logique hardware réalisant « le complément à 2 », le Soustracteur Complet (à n-bit), se déduit directement de l’additionner en question.


Soustracteur Complet 4-bitsPour N=4

La logique hardware réalisant « le complément à 2 », ne peut être qu’une porte XOR. Ainsi, en analysant de plus prêt ce circuit:

A 3 3 A B 2 2 A B 1 1 A B 0 B 0

C 1 C 2 C 3





S

SD 0 SD 1 SD 2 3 C SD4

Ce circuit réalise, dans le cas ou le signal de control S = ‘1’, l’addition de A (A3A2A1A0) avec B’ , qui est le Complément de ‘1’ de B (B3B2B1B0) + 1.

C’est à dire, l’addition de A avec le Complément de ‘1’ de B

Ce qui revient à effectuer l’opération: D = A - B


4.4.6 Circuit Additionneur/Soustracteur (Complet 4-bits)

En réalité le circuit précédent réalise à la fois une addition et une soustraction, suivant que le signal de control S prend la valeur ‘0’ ou ‘1’ respectivement.

S

C4 SD3 SD2 SD1 SD0

B3 A3 B2 A2 B1 A1 B0 A0

A_C 1-b

A_C 1-b

A_C 1-b

A_C 1-b

Note:

S sert àsélectionnerle typed’opérationà effectuerl’Addition ou la Soustraction.MAIS aussiil permet d’effectuerle C’2 dansle cas d’unesoustraction.


4.4.7 Le problème de Dépassement (Overflow)

Définition: Quand deux valeurs de même signe sont ajoutées:Le résultat ne rentre pas dans la bande du nombre de bits réservée aux opérandes.Le Résultat aura donc un signe opposé, de ce qu’il doit être.

Cn-1Cn Cn-1

Cn

1011011010

--------0111

1111101101

--------1011

0100110110

--------1001

0000100011

--------0101

0000101100

--------1110

1111100100

--------0010

DPS

235

36

-7

-2-3-5

-3-67

2-4-2

-242

DPS


Circuit de Dépassement

Il existe des circuits permettant de prévoir quand il y’a de dépassement. Comme:

Dépassement si ‘1’

CN

BN-1

AN-1

CN-1


4.4.8 Additionneur BCD A l’aide de 2 additionneurs 4-bits et 3 portes logiques

191001111001

180001101001

171110110001

160110100001

151010111110

140010101110

131100110110

120100100110

111000111010

100000101010

91001010010

80001000010

71110011100

60110001100

51010010100

40010000100

31100011000

20100001000

11000010000

00000000000

S0S2S4S8CZ0Z2Z4Z8K

DECIMALSomme BCDSomme Binaire


(Mano)

C

S8 S4 S2 S1


C’est un Additionneur ParallèlePermettant de réduire l’effet de propagation de la Retenue.

4.4.9 Additionneur «LookAhead»

A partir du circuit de la page 7:

A B

S C

C i+1

ii

i i

Semi-Additionneur Semi-Additionneur

Pi= Ai+Bi

Gi =Ai.Bi

Si= Pi + Ci Ci+1 =Gi+ Pi.Ci

Carry GenerateCar produit ‘1’ quand Ai et Bi sont ‘1’

Carry PropagateCar elle permet de propager la retenue de Ci vers Ci+1


Ainsi:

C0 =Retenue d’entrée

C1 =G0+ P0.C0

C2 = G1+ P1.C1 = G1+ P1.(G0+ P0.C0) = G1+ P1.G0 + P1.P0.C0

C3 =G2+ P2.C2 = G2+ P2.(G1+ P1.C1) = … = G2+ P2.G1 + P2.P1.G0 + P2.P1.P0.C0

… etc. SdP Implémentation 2 niveauxMAIS beaucoup de Portes logiques

NOTE: Chaque Retenue Ci (i = 0,1,2, …) est générée séparément Pas de propagation de Retenue Moins de retard MAIS beaucoup de Portes

logiques par rapport au type d’addition à Propagation de Retenue Compromis Vitesse/Densité. (bien connu dans la conception des systèmes VLSI)


Réalisation Hardware D’un Additionneur type « Carry LookAhead » Mano

(Mano)


(Mano)


4.5 Multiplicateur Binaire

(Mano)


(Mano)


En Résumé

L’Addition et la Soustraction sont des opérations fondamentales dans les systèmes digitaux, et des ordinateurs en particulier.

Leur réalisation se fait à partir d’une chaîne de circuits Additionneur/Soustracteur complet 1-bit.

Cette approche est appelé Addition à propagation de retenue (Ripple-Carry Addition)

Son inconvénient, c’est sa lenteur dans les systèmes de conception larges. Toutefois, il existe d’autres approches plus rapides (Look-AheadAddition).

Le Dépassement est une issue importante pour les ordinateurs.

En général, les processeurs numériques sont munis de circuit Hardware adéquat pour détecter les cas de dépassement.