GELE2442 Chapitre 3 : Principes de la logique … · 2 Portes logiques 3 Cr eation des circuits logiques 4 Impl ementation NAND 5 Chronogrammes Gabriel Cormier (UdeM) GELE2442 Chapitre

GELE2442 Chapitre 3 :Principes de la logique combinatoire

Gabriel Cormier, Ph.D., ing.

Universite de Moncton

Hiver 2015

Gabriel Cormier (UdeM) GELE2442 Chapitre 3 Hiver 2015 1 / 33

Contenu

1 Algebre booleenne

2 Portes logiques

3 Creation des circuits logiques

4 Implementation NAND

5 Chronogrammes


Logique combinatoire

Deux types de logique: combinatoire et sequentielle

Combinatoire: logique ou la sortie depend seulement des entrees

Sequentielle: logique ou la sortie depend des entrees actuelle et de lasortie precedente

La logique combinatoire est la base du design de circuits logiques.


Algebre booleenne

Algebre booleenne

Algebre utilisee pour les systemes binaires

Seules deux valeurs: 0 (FAUX) et 1 (VRAI)

La mathematique est differente (un domaine complet)

On verra des postulats et theoremes de base


Algebre booleenne

Postulats importants

Tableau 1 : Postulats importants de l’algebre booleenne

(A1) X = 0 si X 6= 1 (A1’) X = 1 si X 6= 0(A2) Si X = 0⇒ X ′ = 1 (A2’) Si X = 1⇒ X ′ = 0(A3) 0 · 0 = 0 (A3’) 1 + 1 = 1(A4) 1 · 1 = 1 (A4’) 0 + 0 = 0(A5) 0 · 1 = 1 · 0 = 0 (A5’) 1 + 0 = 0 + 1 = 1


Algebre booleenne

Theoremes importants

Tableau 2 : Theoremes importants de l’algebre booleenne

Numero Nom Theoreme

T5 Complement X +X ′ = 1, ou X ·X ′ = 0T6 Idempotence X +X = X, ou X ·X = XT8 Distributivite X + (Y · Z) = (X + Y ) · (X + Z)T9 Absorption X + (X · Y ) = XT10 Combinaison X · Y +X · Y ′ = X


Algebre booleenne

Dualite

Dualite: si dans une expression on interchange l’operateur etl’element d’identite, l’egalite demeure (0↔ 1, · ↔ +)

DualiteX + 0 = X X · 1 = XX +X ′ = 1 X ·X ′ = 0


Algebre booleenne

Theoreme de Demorgan

Permet d’interchanger l’operateur + et ·, et l’operateur decomplement:

(X + Y + Z)′ = X ′ · Y ′ · Z ′

(X · Y · Z)′ = X ′ + Y ′ + Z ′

Figure 1 : Exemples du theoreme de Demorgan


Algebre booleenne Fonction booleenne

Fonction booleenne

Expression formee de variables binaires, comme F = X · Y + Z ′

Le symbole · represente ET (AND)

Le symbole + represente OU (OR)

Souvent representee par une table de verite: tableau qui representetoutes les combinaisons possibles d’entrees et de sortie(s)

Pour n variables d’entree, il y a 2n possibilites



Exemple de table de verite

X Y Z F

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

Figure 2 : Exemple de table de verite pour F = X · Y + Z ′



Complement d’une fonction

Le complement d’une fonction F s’ecrit F ′.

On l’obtient en changeant les 0 pour des 1 (et vice-versa) dans latable de verite.

On peut aussi l’obtenir en utilisant le theoreme de Demorgan.



Exemple

Calculer le complement de la fonction F = X ′Y Z ′ +X ′Y ′Z

F ′ = (X ′Y Z ′+X ′Y ′Z)′ = (X ′Y Z ′)′·(X ′Y ′Z) = (X+Y ′+Z)·(X+Y+Z ′)


Algebre booleenne Mintermes et maxtermes

Mintermes et maxtermes

Une fonction booleenne peut etre exprimee de l’une de deux facons:

une somme de produitsun produit de sommes

Terme multiplie: minterme

Somme de termes: maxterme




X Y Z Minterme Maxterme

0 0 0 0 X ′ · Y ′ · Z ′ X + Y + Z1 0 0 1 X ′ · Y ′ · Z X + Y + Z ′

2 0 1 0 X ′ · Y · Z ′ X + Y ′ + Z3 0 1 1 X ′ · Y · Z X + Y ′ + Z ′

4 1 0 0 X · Y ′ · Z ′ X ′ + Y + Z5 1 0 1 X · Y ′ · Z X ′ + Y + Z ′

6 1 1 0 X · Y · Z ′ X ′ + Y ′ + Z7 1 1 1 X · Y · Z X ′ + Y ′ + Z ′

Figure 3 : Mintermes et maxtermes a 3 bits




Generer les mintermes: utiliser le complement de la variable auxendroits ou on a un 0 dans la table de verite

Generer les maxtermes: utiliser le complement lorsqu’il y a un 1 dansla table de verite

On exprime ensuite comme somme de mintermes ou produit demaxtermes

Mintermes: on utilise les termes ou la fonction est 1

Maxtermes: on utilise les termes ou la fonction est 0

On simplifie ensuite avec l’algebre booleenne



Exemple

Exprimer la fonction ayant la table de verite de la figure suivante a l’aidede mintermes et maxtermes.

X Y Z F

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

Figure 4 : Table de verite pour une fonction



Exemple (suite...)

Les mintermes sont exprimes avec des m minuscules; les termes ou lafonction est 1 sont: 0, 3, 4, 6 et 7.

F =∑

m0,m3,m4,m6,m7

= X ′ · Y ′ · Z ′ +X ′ · Y · Z +X · Y ′ · Z ′ +X · Y · Z ′ +X · Y · Z

Les maxtermes sont exprimes avec des M majuscules; les termes ou lafonction est 0 sont: 1, 2 et 5.

F =∏

M1,M2,M5

= (X + Y + Z ′) · (X + Y ′ + Z) · (X ′ + Y + Z ′)


Portes logiques

Portes logiques

Selon les equations booleennes, on a trois fonctions de base:

ET (AND), represente par le symbole ·OU (OR), represente par +NON (NOT; complement), represente par ′ ou

Chaque fonction est associee a une porte logique

Le cercle a la sortie de la porte NON indique que la porte logique aun comportement d’inversion

La porte NON s’appelle aussi un inverseur


Portes logiques

Portes logiques

X Y X·Y0 0 00 1 01 0 01 1 1

ET

XY

X·Y

X Y X+Y0 0 00 1 11 0 11 1 1

OU

XY

X+Y

X X′

0 11 0

NON

X X′

Figure 5 : Trois fonctions logiques de base


Portes logiques

Portes logiques

Trois autres portes communes:

NAND: NOT-AND

NOR: NOT-OR

XOR: eXclusively-OR


Portes logiques

Portes logiques

X Y X · Y0 0 10 1 11 0 11 1 0

NAND

XY

X · Y

X Y X + Y0 0 10 1 01 0 01 1 0

NOR

XY

X + Y

X Y X⊕Y0 0 00 1 11 0 11 1 0

XOR

XY

X⊕Y

Figure 6 : Trois fonctions logiques communes


Creation des circuits logiques


Comment creer des circuits a partir des fonctions?

Chaque minterme est cree a partir des portes logiques de base



Exemple

F1 = X + Y ′Z

YY ′Z

Z

XF1



Exemple

On a trois juges qui controlent le depart d’une course. La course a lieu siau moins deux des trois juges sont prets. Creer le circuit logique quirepresente le depart d’une course.


Implementation NAND

Implementation NAND

Les circuits logiques sont souvent realises avec des portes NAND etNOR plutot que des portes AND et OR

Les portes NAND et NOR necessitent moins de transistors pourl’implementation

On utilise souvent des portes NAND et NOR pour faire le design,plutot que AND et OR


Implementation NAND Creation des portes NAND

Creation des portes NAND

Deux options:

Ajouter une bulle d’inversion a la sortie d’une porte ANDAjouter des bulles d’inversion a l’entree d’une porte OR (verifier avecDeMorgan)


Implementation NAND Creation des portes NAND

Creation des portes NAND

XYZ

(X + Y + Z)′

XYZ

X ′ · Y ′ · Z ′

= (X + Y + Z)′

Figure 7 : Portes AND et OR transformees en porte NAND


Implementation NAND Transformation AND-OR a NAND

Transformation AND-OR a NAND

Il faut que le circuit (ou la fonction logique) soit de la forme d’unesomme de produits

Seulement possible avec des mintermes

On ajoute des bulles d’inversion a la sortie des portes AND et al’entree des porte OR



Exemple

F = AB + CD

Le circuit correspondant a cette fonction est montre a la figure suivante,sous la forme d’un circuit AND-OR.

AB

CD

F

Figure 8 : Fonction F = AB + CD implantee en logique AND-OR



Exemple: transformation a NAND

AB

CD

F

AB

CD

F

Figure 9 : Portes AND-OR transformees en portes NAND


Chronogrammes

Chronogramme

Representation graphique des ondes synchronisees franchissant une oudes portes logiques

Permet de representer l’evolution d’un signal (une sortie) dans letemps

Permet d’identifier les relations cause-a-effet


Chronogrammes

Exemple: porte ET

A

B

Ftd

Figure 10 : Chronogramme pour une porte ET


Chronogrammes

Chronogramme

La fleche rouge montre la relation entre l’entree et l’activation de lasortie

La porte a aussi un delai: les portes logiques reelles auront toujoursun delai; ce delai peut avoir une grande importance lorsque qu’on aplusieurs portes en cascade


Documents

GELE2442 Chapitre 3 : Principes de la logique … · 2 Portes logiques 3 Cr eation des circuits logiques 4 Impl ementation NAND 5 Chronogrammes Gabriel Cormier (UdeM) GELE2442 Chapitre