Digital Works - Université Lavalmarchand/ift17583/Acetates/17583-Acetates04.pdfcircuits combinatoires simples tels que le dé codeur, le multiplexeur et le démultiplexeur; ... La

1

©Pierre Marchand, 2001 111

Objectifs :À la fin de cette unité, vous comprendrez le fonctionnement desprincipaux éléments d'un ordinateur : d écaleur, additionneur, unitélogique et arithmétique. Pour y arriver, vous devrez avoir atteint lesobjectifs suivants :

- décrire le fonctionnement et les propriétés des portes logiques, decircuits combinatoires simples tels que le décodeur, le multiplexeuret le démultiplexeur;

- utiliser les théorèmes et les identités de l'algèbre de Boole poursynthétiser un circuit à partir de sa table de vérité et simplifier lerésultat obtenu.

Unité 4: Logique combinatoire


Digital Works

Pour mieux profiter des unités 4 à 6, nous vous encourageons à utiliserle logiciel Digital Works, disponible gratuitement à l’adresse :

http://www.mecanique.co.uk/digital-works/

Le logiciel est également disponible dans les laboratoires 3910 et 3966.

Ce logiciel permet non seulement de dessiner les circuits, mais égale-ment de les faire fonctionner.

Vous trouverez sur le site du cours à la page :

http://www.ift.ulaval.ca/~marchand/ift17583/Exemples/Exemples2.html

des fichiers implantant pratiquement tous les circuits du cours ainsi quequelques autres.

2


5.1 Notion de circuit logiqueFonctions logiques

Une fonction logique est une fonction qui agit sur une ou plusieursvariables logiques.

Une variable logique est une variable qui peut prendre l’une dedeux valeurs : vrai ou faux, 1 ou 0.



5.1 Notion de circuits logiquesLes circuits logiques sont des circuits électroniques servant àeffectuer physiquement des fonctions logiques.

Circuits combinatoires

Les signaux de sortie ne dépendent que des signaux d’entréeprésents.

Circuits séquentiels

Circuits dans lesquels les signaux de sortie dépendent des signauxd’entrée appliqués antérieurement en plus des signaux d’entréeprésents.


3


5.2 Circuits combinatoires5.2.1 Algèbre booléenne

Georges Boole, en 1847, a défini une algèbre qui s’applique à desfonctions logiques de variables logiques. Nous verrons que toutefonction logique peut être réalisée à l’aide d’un petit nombre defonctions logiques de base aussi appelées opérateurs logiques ouportes (gates).

La fonction logique d’un circuit combinatoire peut se définir par letableau de correspondance entre les états d’entrée et les états desortie. Un tel tableau est appelé table de vérité.



5.2 Circuits logiques5.2.1 Algèbre booléenne

La table de vérité d’une fonction de n variables a autant de lignesque d’états d’entrée possibles, soit 2n. Pour chacun de ces états,la sortie peut prendre la valeur 0 ou 1.

Donc, pour n variables, on a fonctions possibles.


22n

4


5.2 Circuits logiques5.2.2 Fonctions d’une variable

Soit a une variable logique. On a quatre fonctions possibles :

a Z0 Z1 Z2 Z3

0 0 0 1 1

1 0 1 0 1

Z0 = 0 : constante

Z1 = a: identité

Z2 = a : complément

Z3 = 1 : constante

La seule fonction non triviale est le complément, qu’on réalise aumoyen de l’opérateur NON ou inverseur Z = a.



5.2 Circuits logiques5.2.2 Fonctions d’une variable

L’opérateur NON ou inverseur

Table de vérité :

a a0 11 0


a a

5


5.2 Circuits logiques5.2.3 Fonctions de deux variables

Il y a 16 fonctions possibles de deux variables

00 01 10 11 ab

0 0 0 0 F0 = 0 Constante 0

0 0 0 1 F1 = a.b Fonction ET

0 0 1 0 F2 = a.b

0 0 1 1 F3 = a

0 1 0 0 F4 = a.b

0 1 0 1 F5 = b0 1 1 0 F6 = a⊕b Fonction XOR

0 1 1 1 F7 = a+b Fonction OU




00 01 10 11 ab

1 0 0 0 F8 = a+b = a.b Fonction NOR1 0 0 1 F9 = a⊕b Fonction égalité

1 0 1 0 F10 = b

1 0 1 1 F11 = a+b

1 1 0 0 F12 = a

1 1 0 1 F13 = a+b

1 1 1 0 F14 = a.b = a + b Fonction NAND

1 1 1 1 F15 = 1 Constante 1


6



Fonction ET (AND)

Table de vérité

a b a.b

0 0 00 1 01 0 01 1 1


ETab

a.b

0 10 0 01 0 1

ab

a.b



Fonction OU (OR)

Table de vérité

a b a+b

0 0 00 1 11 0 11 1 1


OUab

a+b

0 10 0 11 1 1

ab

a+b

7



Application.

Masquage d’un registre :

Avec des portes ET, on

peut mettre des bits à 0

de façon sélective.

Avec des portes OU, on

pourrait mettre des bits

à 1 de façon sélective.


1 1 0 1 1 1 0 0

Masque

Registre

0 0 1 1 1 1 1 1

0

0

1

1

1

0

0

0



On peut généraliser les fonctions logiques à trois variables oudavantage :


a b c a+b+c0 0 0 00 0 1 10 1 0 10 1 1 11 0 0 11 0 1 11 1 0 11 1 1 1

a b c a.b.c0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 01 1 0 01 1 1 1

8



Théorèmes fondamentaux de l’algèbre de Boole

Identités a + 0 = a a . 0 = 0

a + 1 = 1 a . 1 = a

Commutativité a + b = b + a a . b = b . a

Distributivité a+(b.c) = (a+b).(a+c) a.(b+c) = a.b + a.c

Associativité a+(b+c) = (a+b)+c = a+b+c a.(b.c) = (a.b).c = a.b.c

Idempotence a + a = a a . a = a

Complémentation a + a = 1 a . a = 0

De Morgan a.b = a + b a + b = a . b

Autres a = a

Absorption a + (a . b) = a a.(a + b) = a

a + (a . b) = a + b (a + b).(a + b) = a




La fonction XOR (OU-exclusif ou OU-disjonctif) ou fonction inégalité

Table de véritéa b a ⊕ b

0 0 00 1 11 0 11 1 0


ab

a ⊕ b

0 10 0 11 1 0

ab

a⊕b

9



La fonction XOR. Propriétés :

a ⊕ b = a.b + a.b a ⊕ b = a.b + a.b

a ⊕ 0 = a a ⊕ a = 0

a ⊕ 1 = a a ⊕ a = 1

a ⊕ b = b ⊕ a (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

Réalisation :


ba

a ⊕ b



Minterm

Un minterm est le produit logique de toutes les variables d’entréeapparaissant chacune sous la forme vraie (si la variable vaut 1) ousous la forme complémentée (si la variable vaut 0).

Ainsi, dans la table de vérité suivante, il y a quatre minterms :

a b a ⊕ b

0 0 0 a . b0 1 1 a . b1 0 1 a . b1 1 0 a . b


10



Maxterm

Un maxterm est la somme logique de toutes les variables d’entréeapparaissant chacune sous la forme vraie (si la variable vaut 0) ousous la forme complémentée (si la variable vaut 1).

Ainsi, dans la table de vérité suivante, il y a quatre maxterms :

a b a ⊕ b

0 0 0 a + b0 1 1 a + b1 0 1 a + b1 1 0 a + b




Théorème

Un circuit logique peut être représenté par la somme logique de tousles minterms pour lesquels la sortie est 1 ou par le produit logique detous les maxterms pour lesquels la sortie est 0.

Exemple :

Le XOR peut être exprimé para ⊕ b = a.b + a.b

oua ⊕ b = (a + b).(a + b)


11



Les fonctions NAND et NOR

Le théorème précédent montre que tout circuit logique peut êtreréalisé avec trois types de portes : ET, OU et NON. On peut aussiles réaliser avec un seul type de porte si on utilise les portescomplètes NAND ou NOR.

NAND NOR


0 10 1 11 1 0

ab

a.b

ab

a.b

0 10 1 01 0 0

ab

a+b

a+bab



Les fonctions NAND et NOR

En effet :

a.b = a.b = a+b

et

a+b = a+b = a.b

Aussi, puisque a.a = a et a+a = a


= =

=

=

a a

12


5.2 Circuits logiques5.2.4 Synthèse d’un circuit combinatoire

Pour effectuer la synthèse d’un circuit combinatoire, on part de satable de vérité.

On en extrait les minterms des valeurs pour lesquelles la fonctionest vraie (1) et on réalise cette fonction en faisant la sommelogique de ces minterms,

ou encore, on en extrait les maxterms des valeurs pour lesquellesla fonction est fausse (0) et on réalise cette fonction en faisant leproduit logique de ces maxterms.

Cette réalisation n’est pas toujours optimale. On aura donc laplupart du t emps à simplifier les expressions au moyen del’algèbre booléenne.




Exemple : soit la table de vérité suivante :

a b c f minterms

0 0 0 00 0 1 1 a.b.c0 1 0 00 1 1 01 0 0 01 0 1 1 a.b.c1 1 0 1 a.b.c1 1 1 1 a.b.c

f = a.b.c + a.b.c + a.b.c + a.b.c


13



Simplification

f = (a + a).b.c + a.b.(c + c) = b.c + a.b

Circuit


ab

c

f



Simplification

La simplification des équations logiques au moyen de l’algèbrebooléenne n’est pas toujours simple, et on ne sait pas toujours sion a atteint une solution optimale.

Les tables de Karnaugh permettent de systématiser ce processus.


14



Tables de Karnaugh

a b c f

0 0 0 00 0 1 10 1 0 00 1 1 11 0 0 01 0 1 01 1 0 11 1 1 1 Donc f = a.b + a.c


00 0 101 0 111 1 110 0 0

abc

0 1

a.b

a.c



Chaque boucle doit être rectangulaire et doit contenir le maximumpossible de 1 qui soit une puissance de 2 : 1, 2, 4, 8, 16, etc. et necontenir aucun 0.

La boucle est caractérisée par les combinaisons qui sont vraiespour tous les éléments de la boucle.

Les recouvrements sont possibles.


00 01 11 1000 0 0 0 001 0 1 1 011 0 1 1 110 1 0 0 0

abcd

b.d

a.b.c

00 0 001 1 111 1 110 1 0

abc

0 1

ba.c

a.b.c.d

15



Les boucles peuvent «faire le tour» de la table

a b c f

0 0 0 00 0 1 10 1 0 00 1 1 01 0 0 01 0 1 11 1 0 01 1 1 0 Donc f = b.c


00 0 101 0 011 0 010 0 1

abc

0 1

b.c



Les boucles peuvent «faire le tour» de la table


abcd

b.d

00 01 11 1000 1 0 0 101 0 0 0 011 0 0 0 010 1 0 0 1

abcd

b.d

00 01 11 1000 0 1 1 001 1 0 0 111 1 0 0 110 0 1 1 0

b.d

16



États indifférents

Dans certains cas, la sortie pour un état d’entrée donné estindifférente, soit parce que cet état d’entrée ne peut jamais seproduire, soit parce que la sortie correspondante ne nous inté-resse pas. On inscrit alors un x dans la table de Karnaugh. Onpeut s’en servir pour minimiser le circuit comme si c’étaient des 1.


abcd

00 01 11 1000 0 0 0 001 0 0 0 011 1 x x x10 x 0 1 x

a.b + a.c au lieu dea.b.c.d + a.b.c.d



Synthèse d’un demi-additionneur binaire

Table de vérité du demi-additionneur (qui ne tient pas compted’une retenue antérieure)

a b S R R = a.b0 0 0 0 S = a.b + a.b = a ⊕ b0 1 1 0 a.b1 0 1 0 a.b1 1 0 1 a.b


ab S

R

17



Synthèse d’un additionneur binaire de 1 bit

Table de vérité de l’additionneur 1 bit

a b R S R’ R’ = a.b.R + a.b.R + a.b.R + a.b.R

0 0 0 0 0 S = a.b.R + a.b.R + a.b.R + a.b.R0 0 1 1 0 On simplifie :0 1 0 1 0 R’ = (a.b + a.b).R + a.b0 1 1 0 1 R’ = (a ⊕ b).R + a.b1 0 0 1 0 S = (a.b + a.b).R + (a.b + a.b).R1 0 1 0 1 S = (a ⊕ b).R + (a ⊕ b).R1 1 0 0 1 S = (a ⊕ b) ⊕ R1 1 1 1 1




Synthèse d’un additionneur binaire

Réalisation au moyen de 2 demi-additionneurs

Réalisation complète

d’un additionneur 1 bit


a

b

S

R

a

b

S

RS

R’a

b

R

a.b

a⊕b

a⊕b⊕R

(a⊕b)R

R

R’

ab

S

(a⊕b)R

a⊕b

a⊕b⊕R

a.b

18



Additionneur à plusieurs bits


a b R

R’ S

A0 B0

a b R

R’ S

A1 B1

a b R

R’ S

A2 B2

a b R

R’ S

A3 B3

S3 S2 S1 S0

0

Additionneur1 bit



Additionneur/soustracteur 4 bits


a b R

R’ S

A0

a b R

R’ S

A1

a b R

R’ S

A2

a b R

R’ S

A3

S3 S2 S1 S0

Additionneur1 bit

B0B1B2B31 = soustraction0 = addition

19


5.2 Circuits logiques5.2.6 Multiplexeurs et démultiplexeurs

Démultiplexeur 4 bits ou 1 vers 4

Ce circuit est utile pour choisir la destination d’un signal.


a

b

xa.b.x

a.b.x

a.b.x

a.b.x



Multiplexeur 2 bits ou 2 vers 1

Ce circuit est utile pour choisir la source d’un signal.


S

a

b

S.a

S.b z

z = S.a + S.b

20



Multiplexeur 4 bits ou 4 vers 1


a

b

x0

x1

x2

x3

a.b.x0

a.b.x3

a.b.x1

a.b.x2z



Décaleur de 1 bit vers la gauche


a bS z

0D0

S0

a bS z

D0D1

S1

a bS z

D1D2

S2

a bS z

D2D3

S3

a bS z

D3D4

S4

a bS z

D4D5

S5

a bS z

D5D6

S6

a bS z

D6D7

S7

C

21



Décaleur à barillet


D0-D31

S0-S31

Décaleur 1 bit

Décaleur 2 bits

Décaleur 4 bits

Décaleur 8 bits

S

S

S

S

1 0 1 1Nb. de décalages

Registre decommande


5.2 Circuits logiques5.2.6Multiplexeurs et démultiplexeurs

Utilisation d’un multiplexeur pour réaliser n’importe quelle fonctionlogique. Exemple :

Table de vérité

a b c f

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


MUX f

c01c

a b

0

1

2

3

22


5.2 Circuits logiques5.2.7 Décodeurs, codeurs, transcodeurs

Codeur : code en binaire le numéro de la ligne activée.


0 1 2 3 4 5 6 7 8 9

S1

S2

S4

S8



Décodeur 3 vers 8


c c b b a a

0

1

2

3

4

5

6

7

Une seule sortie à la foisest 0 et est choisie par lecode abc.

a.b.c = 4

23



Transcodeur BCD-excédent-3

Table de vérité:


A B CD X Y Z T I0 0 0 0 0 0 1 1 00 0 0 1 0 1 0 0 00 0 1 0 0 1 0 1 00 0 1 1 0 1 1 0 00 1 0 0 0 1 1 1 00 1 0 1 1 0 0 0 00 1 1 0 1 0 0 1 00 1 1 1 1 0 1 0 01 0 0 0 1 0 1 1 01 0 0 1 1 1 0 0 0

A B CD X Y Z T I1 0 1 0 x x x x 11 0 1 1 x x x x 11 1 0 0 x x x x 11 1 0 1 x x x x 11 1 1 0 x x x x 11 1 1 1 x x x x 1



Transcodeur BCD-excédent-3


00 01 11 1000 1 0 1 001 1 0 1 011 x x x x10 1 0 x x Z

00 01 11 1000 0 1 1 101 1 0 0 011 x x x x10 0 1 x x Y

00 01 11 1000 0 0 0 001 0 1 1 111 x x x x10 1 1 x x X

00 01 11 1000 0 0 0 001 0 0 0 011 1 1 1 110 0 0 1 1 I

ABCD

ABCD

ABCD

ABCD

ABCD

T = DZ = CD + CD = C⊕DY = BCD+BC +BDX = A + BC +BDI = AB + AC

00 01 11 1000 1 0 0 101 1 0 0 111 x x x x10 1 0 x x T

24


5.2 Circuits logiques

UAL élémentaire


Additionneur

Décodeur 2-4

ABR

S

R’

AB

R

F0

F1

0123

R’

A.B

A+B

B

AB

Sortie

Unité logique

Unité arithmétiqueUnité de commande



Logique à trois états

Il faut souvent appliquer à un même fil la sortie de l’une ou l’autre d’unensemble de sorties. Pour éviter l’interférence entre les différentscircuits, par exemple une sortie qui tenterait d’appliquer 1 à une lignealors qu’une autre sortie tenterait d’y appliquer 0, on utilise la logiquetrois états, dans laquelle la sortie peut être 0, 1, ou haute impédance(comme si elle n’état pas connectée). On ajoute une entrée OutputEnable (OE) à chaque circuit et on n’en active qu’un à la fois.


OE OE

=

25



Logique programmable

Les circuits de logique programmable PLA (Programmable LogicArray), PLD (Programmable Logic Devices), EPLD (Eraseble PLD),etc. sont basés sur le fait que toute fonction logique peut être expriméecomme une somme de minterms.

Le circuit contient un réseau de portes logiques ET à n variables, et unréseau de portes logiques OU, suivi, le cas échéant, d’une couche debistables. Des appareils spécialisés permettent la programmation duréseau.




Logique programmable combinatoire


I1

I2

In

F0

F2

F0

F1

F2

F1

Les jonctions en rougesont éliminées (brûlées)sélectivement lors de laprogrammation.

26



Logique avec ROM

Il est possible de réaliser des circuits logiques au moyen de mémoiresROM (Read-Only Memory). Aucune simplification n’est nécessaire.Les entrées de la table de vérité servent d’adresse dans la ROM et lecontenu de chaque adresse est la sor t ie désirée pour cettecombinaison de variables d’entrée, la sortie pouvant avoir un ouplusieurs bits.




Logique avec ROM

Exemple : transcodeur binaire à code Gray


ABCD

0000

0001

0010

0011

0100

0101

0110

0111

EFGH

0000

0001

0011

0010

0110

0111

0101

0100

ABCD

1000

1001

1010

1011

1100

1101

1110

1111

EFGH

1100

1101

1111

1110

1010

1011

1001

1000

ABCD

ROM16 x 4

EFGH

Table de vérité

27


Technologie des semiconducteursTransistors

Transistors bipolaires


NPN PNP+ -

Transistors unipolaires (à effet de champ)

MOSFET ou MOS,CMOS

E

B

C

S

G

Dp-channeln-channel

E

B

C

S

G

D+ -


Technologie des semiconducteursInverseur TTL Inverseur CMOS


+5 V

5 kΩ

10 kΩentréesortie

+5 V à +15 V

entrée sortie

28


Technologie des semiconducteursNAND TTL NOR CMOS

Unités 4 et 5 : Logique combinatoire

AB

+5 V

A.B

+5 V+5 V à +15 V

sortie

A

B

Documents

Digital Works - Université Lavalmarchand/ift17583/Acetates/17583-Acetates04.pdfcircuits combinatoires simples tels que le dé codeur, le multiplexeur et le démultiplexeur; ... La