Cours11

GPA 325 Introduction à l’électronique COURS 11 Chapitre 7 LOGIQUE COMBINATOIRE

Plan       

Systèmes de numérotation Codes Algèbre de Boole Évaluation d’une fonction logique Tables de vérité Diagrammes de Karnaugh Réduction

Systèmes de numérotation 

Tout nombre peut s'exprimer sous sa forme polynomiale :

N=

n

∑ ai

i=0

×b

i

■

Dans cette équation polynomiale: • • •

■

b = base du système de numérotation i = rang ou poids d'un nombre a = nombre appartenant à {0,1, ... , (b-1)}

Exemple: • • •

(1997)10 = 1 x103 + 9X102 + 9x101 + 7x100 Poids du chiffre 1 = 1000 Rang du chiffre 1 = 3

Les principales bases ■

Base Décimale (b = 10): •

■

Base Binaire (b = 2) •

■

a ∈ {0,1}

Base Octale (b = 8) •

■

a ∈ {0,1,2,3,4,5,6,7,8,9}

a ∈ {0,1,2,3,4,5,6,7}

Base Hexadécimale (b = 16) •

a ∈ {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

Changements de base 

Représentation de nombres décimaux  



De la base b à la base décimale De la base décimale à la base b

Représentation de nombres binaires    

De De De De

binaire à octal octal à binaire binaire à hexadécimal hexadécimal à binaire

De la base b à la base décimale ■

■

(base 10)

Ecrire simplement la forme polynomiale, puis calculer. Exemples: 

(237)8 = 2x82 + 3x81 + 7x80 = (159)10



(56A)16 = 5x162 + 6x161 + 10x160 = 1386



(101)2 = 1x22 + 0x21 + 1x20 = (5)10

De la base décimale à la base b ■

Deux techniques:  Soustractions successives  Divisions successives

■

Soustractions successives: 

■

(1386)10 = (?)16

Solution de l'exemple:   

■

Exemple:

1386 - 256 = 1130 ; 1130 - 256 = 874 874 - 256 = 618 ; 618 - 256 = 362 362 - 256 = 106

Donc le nombre commence par un 5

■

Poursuivons l'exemple: • • •

■ ■

■

106 - 16 = 90 ; 90 - 16 = 74 74 - 16 = 58 ; 58 - 16 = 42 42 - 16 = 26 ; 26 - 16 = 10

Donc, le second nombre est un 6 Et le troisième est un 10 ou un A Solution: (1386)10 = (56A)16

■

Divisions successives: •

■

(1386)10 = (?)16

Solution de l'exemple: • • •

■

Exemple:

1386 ÷ 16 = 86 reste 10 86 ÷ 16 = 5 reste 6 5 ÷ 16 = 0 reste 5

Donc le nombre est (56A)16

(ou A)

De la base binaire à la base octale ■

Conversion en groupant des ensembles de 3 bits. •

■

Rappel: • •

■

Exemple:

(10010110)2 = (?)8

000 = 0 ; 001 = 1 ; 010 = 2 ; 011 = 3 100 = 4 ; 101 = 5 ; 110 = 6 ; 111 = 7

Solution de l'exemple: •

(010 010 110)2 = (226)8

De la base octale à la base binaire ■ ■

■

Opération inverse à la précédente Exemple: (3452)8 = (?)2 Solution de l'exemple: •

(3452)8 = (011 100 101 010)2

De la base binaire à la base hexadécimale ■

■ ■

Conversion en groupant des ensembles de 4 bits. Exemple: (100101101)2 = (?)16 Solution de l'exemple: •

(0001 0010 1101)2 = (12D)8

De la base hexadécimale à la base binaire ■ ■

■

Opération inverse à la précédente Exemple: (3F5B)16 = (?)2 Solution de l'exemple: •

(3F5B)16 = (0011 1111 0101 1011)2

Nombres à virgule flottante  

Principe de la notation scientifique Permet de représenter:  

Des nombres entiers de très grande valeur Des nombres réels, possédant une partie entière et une partie fractionnaire (ex.: 23,5618)

Nombres à virgule flottante 

Composition:  



Mantisse: grandeur normalisée du nombre réel. Exposant: puissance de 10

Exemple:

2 4 1 5 0 6 8 0 0

⇒ 0 , 2 4 1 5 0 6 8

9 × 1 0

Nombres à virgule flottante 32 bits

S Exposant (E) Mantisse fractionnaire (F) 1

 

23

Norme ANSI/IEEE 754-1985 Précision:   



8

Simple: 32 bits Double: 64 bits Étendue: 80 bits

Composition:  

Mantisse: 24 bits (1 le + significatif pas compté) Exposant: polarisé (127 est ajouté à l’exposant réel)

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

⇒ 1 , 0 1 1 0 1 0 0 1 0 0 0 1

1 2 × 2

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

⇒ 1 , 0 1 1 0 1 0 0 1 0 0 0 1

1 2 × 2

32 bits

0 S

10001011 01101001000100000000000 E

F

Opérations mathématiques en binaire    

Addition Soustraction Multiplication Division

Opérations mathématiques en binaire 

Addition

La table d’addition : 0+0=0 0+1=1 1+0=1 1 + 1 = 0 et report de 1

Opérations mathématiques en binaire 

Soustraction

La table de soustraction : 0-0=0 0 - 1 = 1 et retenue de 1 1-0=1 1-1=0

Opérations mathématiques en binaire Soustraction (suite) Complément à 1 : S’obtient en complémentant le nombre binaire. Ex. A= 101101110010 Complément à 1 de A /A = 010010001101 

Complément à 2 : S’obtient en ajoutant 1 au complémentant à 1. Ex. A = 101101101000 /A = 010010010111 Complément à 2 de A = /A+1 = 010010011000 

Opérations mathématiques en binaire

Soustraction (suite) 

Soustraction par complémentation à 2 et addition

Ex.

-

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

1 0 1 1 1 0 1 1 1 0 1 + 1 1 0 1 0 0 1 1 0 0 1 + 1 -----------------------------------------1 1 0 0 0 1 1 1 0 1 1 1

On ajoute des 0s

Complément à 1 Complément à 2 On ignore le report

Opérations mathématiques en binaire

Soustraction (suite) 



Lorsque le bit le plus significatif = 1, le nombre est négatif Le complément à 2 du nombre négatif redonne le même nombre mais avec un signe positif

Opérations mathématiques en binaire Soustraction (suite & fin)  Exemples 

Addition de 2 nombre positifs

2 7 + 6 1 = 8 8 0 0 0 1 1 0 1 1 + 0 0 1 1 1 1 0 1 = 0 1 0 1 1 0 0 0







Soustraction de 2 nombres avec résultat positif

6 1 − 2 7 = + 3 4 0 0 1 1 1 1 0 1 + 1 1 1 0 0 1 0 1

= 0 1 0 0 0 1 0

2 7 − 6 1 = − 3 4 0 0 0 1 1 0 1 1 + 1 1 0 0 0 0 1 1

= 1 1 0 1 1 1 0

6 1 + 8 8 = 1 4 9 0 0 1 1 1 1 0 1 + 0 1 0 1 1 0 0 0

= 1 0 0 1 0 1 0 1

Soustraction de 2 nombres avec résultat négatif

Addition de 2 nombres positifs ( détection du changement de signe) -> débordement

Codes 

BCD « Binary Coded Decimal »



Gray ou binaire réfléchi



ASCII « American Standard Code for Information Interchange »



Unicode

Code BCD Décimal Codé Binaire : Chaque chiffre d'un nombre est codé sur 4 bits 0 0000 1 0001 2 0011 ………… 10 0001 0000 11 0001 0001 Ce code simplifie la conversion décimal binaire

Code BCD (Binary coded decimal) ■ ■

■

■

Souvent utilisé par les machines à calculer. Combine les avantages du décimal et du binaire. Les chiffres de 0 à 9 suivent le code binaire naturel. Par contre, les valeurs de A à F ne sont pas utilisées. Opérations arithmétiques + complexes.

Code Gray Distance de 1 entre deux mots de code consécutif 0 1 2 3 4 5 6 7

000 001 011 010 110 111 101 100

Ce code évite le changement simultané de 2 bits, et donc les états transitoires indésirables.

Code ASCII ■

■

(American Standard Code for International Interchange). Norme universelle pour la transmission de données.  

ASCII normal: 128 caractères sur 7 bits; ASCII étendu: 256 caractères sur 8 bits. Norme ISO Latin 1

Code Unicode (ISO 8859-1) ■

■

■

Le code ASCII est limité à 256 caractères. Pour dépasser cette limite, une nouvelle norme sur 16 bits fut créée. Donc, plus de 65 000 caractères disponibles: •

Japonais, Mandarin, Grec, Russe, Hébreux, Arabe, Coréen, ...

Encodage, décodage et affichage

Algèbre de Boole     

Opérations de base Lois fondamentales Théorèmes de Morgan Tables de vérité Tables de Karnaugh

Opérations de base 

Reposent sur 3 opérateurs de base:  

ET, OU, NON Toutes les équations logiques sont formées de ces 3 opérateurs

Fonction logique NON  

En anglais: NOT Représentation: F=A



ou

F = /A

T a b le d e v é r it é E n tré e

S o r t ie

A

F

0

1

1

0

A

F

S y m b o le g r a p h iq u e

Fonction logique ET  

En anglais: AND Représentation: 

F = A * B ou A • B ou AB

T a b le d e v é r it é E n tré e

S o r tie

B

A

F

0

0

0

0

1

0

1

0

0

1

1

1

A

F

B S y m b o le g r a p h iq u e

Application de la porte ET

Fonction logique OU  

En anglais: OR Représentation: 

F=A+B

T a b le d e v é r it é E n tré e

S o r t ie

B

A

F

0

0

0

0

1

1

1

0

1

1

1

1

A

F

B S y m b o le g r a p h iq u e

Application de la porte OU

Fonction logique NON-ET  

En anglais: NAND Représentation: 

F=A*B

T a b le d e v é r it é E n tr é e

S o r t ie

B

A

F

0

0

1

0

1

1

1

0

1

1

1

0

A

F

B S y m b o le g r a p h iq u e

Application de la porte NON ET

Fonction logique NON-OU  

En anglais: NOR Représentation: 

F=A+B

T a b le d e v é r it é E n tré e

S o r tie

B

A

F

0

0

1

0

1

0

1

0

0

1

1

0

A

F

B S y m b o le g r a p h iq u e

Application

Fonction OU-EXCLUSIF  

En anglais: EXOR Représentation:  F = A ⊕ B

B*A+B*A

T a b le d e v é r it é E n tré e

S o r t ie

B

A

F

0

0

0

0

1

1

1

0

1

1

1

0

/B*A B*/A A

F

B S y m b o le g r a p h iq u e

Fonction NON OU-EXCLUSIF  

En anglais: EXNOR Représentation:  F = A ⊕ B

/B*/A + B*A

T a b le d e v é r it é E n tré e

/B*/A S o r tie

B

A

F

0

0

1

0

1

0

1

0

0

1

1

1

B*A A

F

B S y m b o le g r a p h iq u e

Lois fondamentales de l’algèbre booléenne 

Règles, postulats et théorèmes 

Utiles pour la simplification des équations logiques !

Règles, postulats et théorèmes 

Fermeture: 



Si A et B sont des variables Booléennes, alors A+B, A*B sont aussi des variables Booléennes.

Commutativité  

A+B= B+A A*B = B*A

Règles, postulats et théorèmes 

Associativité  



A + (B + C) = (A + B) + C A * (B * C) = (A * B) * C

Distributivité  

ET/OU: A(B + C) = AB + AC OU/ET: A+(B*C) = (A+B)*(A+C)

Règles, postulats et théorèmes 

Idempotence  



A+A = A A*A=A

Complémentarité  

A+A=1 A*A=0

Règles, postulats et théorèmes 

Identités remarquables  



1+A=1 0+A=A

et et

1*A=A 0*A=0

Distributivité interne  

A + (B + C) = (A + B) + (A + C) A * (B * C) = (A * B) * (A * C)

Règles (ou propriétés) de l’algèbre booléenne

Postulats

Théorèmes

Théorèmes de De Morgan X+Y+Z = XYZ

1) X

Y

X

Z

Y

Z

X

Y

Z

Y

Z

X

Théorèmes de De Morgan XYZ = X+Y+Z

2) X

Y

X

Z

Y

Z

X

Y

Z

Y

Z

X

Tables de vérité E n tré e s

S o rtie

C

B

A

S

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1 1

0 0

0 1

0 1

1

1

0

1

1

1

1

0

Exemple 

E n tré e s

S o rtie

C 0

B 0

A 0

S 0

0 0 0 1 1 1 1

0 1 1 0 0 1 1

1 0 1 0 1 0 1

0 1 1 0 1 1 0

Solution: 



On construit l’équation de S en écrivant tous les termes donnant S=1. Ainsi, S = 1:    

si C=0 et B=1 et A=0; ou si C=0 et B=1 et A=1; ou si C=1 et B=0 et A=1; ou si C=1 et B=1 et A=0.

Exemple E n tré e s

S o r tie

C

B

A

S

0 0 0

0 0 1

0 1 0

0 0 1

0

1

1

1

1 1 1

0 0 1

0 1 0

0 1 1

1

1

1

0



Solution pour S=1.    



si C=0 et B=1 et A=0; ou si C=0 et B=1 et A=1; ou si C=1 et B=0 et A=1; ou si C=1 et B=1 et A=0.

On peut donc écrire: 

S = /C.B./A + /C.B.A + C./B.A + C.B./A

S = C B A + C B A + C B A + C B A

Exemple  

S = /C.B./A + /C.B.A + C./B.A + C.B./A On peut simplifier: 

S = /C.B./A + C.B./A + /C.B.A + C./B.A



S = B./A.(/C+C) + /C.B.A + C./B.A



S = B./A.(1) + /C.B.A + C./B.A

 

S = B./A + /C.B.A + C./B.A S = B./A + A.(C ⊕ B) "ou-exclusif"

Exemple Inspection visuelle ? E n tré e s

C 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

S o rtie

A 0 1 0 1 0 1 0 1

S 0 0 1 1 0 1 1 0

S = /C.B + C./B.A + C.B./A S = /C.B + C.(A ⊕ B) S = B./A + /C.B.A + C./B.A S = B./A + A.(C ⊕ B)

La simplification des équations 

La simplification est essentielle. 





On veut avoir le circuit le plus simple possible...

La simplification peut être un processus long si le système est complexe. Heureusement, il existe des techniques simples pour simplifier.

Méthodes de simplification 



Il est possible d ’obtenir directement une équation sous sa forme simplifiée en utilisant une méthode de simplification graphique. Méthode de simplification graphique: 

Diagrammes de Karnaugh

Diagrammes de Karnaugh 



Représentation de la table de vérité sous forme graphique. Nombre de cases = nombre de lignes de la table de vérité. 

Multiple de 2n (1, 2, 4, 8, 16, ...) 

n = Nombre d ’entrées

Diagrammes de Karnaugh 

Avec n = 2:  

Entrées B et A 4 cases

B

A 0

1

0 0 .

1 .

2 .

3 .

1

Diagrammes de Karnaugh 

Avec n = 3:  

Entrées C, B et A 8 cases

BA

C

00

01

11

10

0 0

1

3

2

4

5

7

6

1

Diagrammes de Karnaugh 

Avec n = 4:  

Entrées D, C, B et A 16 cases

BA

D C

00

01

11

10

00 0

1

3

2

4

5

7

6

12

13

15

14

8

9

11

10

01

11

10

Exemple (Karnaugh)

BA

C 0

1

TABLE DE VÉRITÉ

00

01

11

10

0

0

1

1

0

0

4

1

1

5

0

3

7

1

2

6

DIAGRAMME DE KARNAUGH

Diagrammes de Karnaugh 







À partir de la table, on simplifie en groupant les 1 adjacents. Les 1 adjacents sont mis en évidence par l'ordre utilisé pour former la table La taille d’un groupe est un multiple de 2k (1, 2, 4, 8, ...). Le groupe est soit rectangulaire ou carré.

Exemple (Karnaugh) 

Simplification: S = /C.B + B./A + C./B.A /C.B.A+/C.B./A = /C.B

BA

C 0

1

00

01

11

10

0

0

1

1

0

0

4

C./B.A

1

1

5

0

3

7

1

2

6

/C.B./A+C.B./A=B./A

Table de Karnaugh 

Former les plus gros groupes possibles. 



Termes plus simples.

Un 1 peut faire partie de plusieurs groupes.

Exemple (Karnaugh) 

Les 1 des bords extrêmes sont adjacents. 

La table se referme sur elle même.

/C./A

BA

DC 00

00

01

11

10

1

0

1

1

1

0

/D.C./B.A

01

0

1 4

11

0

10

0 5

0

12

1

13

7

15

1 9

2

0

0

0 8

3

11

6

0 14

1 10

/C.B

Ex. Décodeur BCD – 7 Segment

Circuits intégrés d’implantation de fonctions logiques 

Floyd, p. 127 - 138

SOMME DE PRODUITS (SOP) 

À partir d’une table de Karnaugh, nous générons une somme de produits minimale en formant la sortie en encerclant les 1’s YZ 00 01 11 10

WX

00 0

1

0

0

01

1

1

0

0

11

1

1

1

1

10

0

1

1

0

SOP F = W*X + /Y*Z + X*/Y + W*Z

SOMME DE PRODUITS (SOP) WX

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

SOP, F = W*X + /Y*Z + X*/Y + W*Z En appliquant De Morgan, on peut transformer la somme de produits (SOP) en produit de sommes (POS)

POS, /F = (/W+/X) * (Y+/Z) * (/X+Y) * (/W+/Z) Réalisation de SOP et de POS avec portes NON, ET et OU. Il ne faut pas oublier d’inverser la sortie si on réalise POS

PRODUIT DE SOMMES (POS) 

À partir d’une table de Karnaugh, nous générons un produit de sommes minimal en : 



Formant la somme de produits (SOP) de la sortie complémentée en encerclant les 0’s Transformant cette SOP par De Morgan pour former le produit de somme (POS) de la sortie non complémentée

WX

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

SOP, /F = /W*Y + /X*/Z

PRODUIT DE SOMMES (POS)

WX

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

SOP, /F = /W*Y + /X*/Z En appliquant De Morgan, on peut transformer la somme de produits (SOP) en produit de sommes (POS) POS F = (W+/Y) * (X+Z)

Réalisation de SOP et de POS avec portes NON, ET et OU. Il ne faut pas oublier d’inverser la sortie si on réalise SOP

SOP à POS et POS à SOP 





Les théorèmes de De Morgan permettent de transformer une somme de produits (SOP) en un produit de sommes (POS) et vice-versa. Si une fonction logique F s’exprime par une somme de produits, on peut la représenter par le complément d’un produit de sommes réalisé avec des portes NON-ET et NON-OU Si une fonction logique F s’exprime par un produit de sommes, on peut la représenter par le complément d’une somme de produits réalisé avec des portes NON-ET et NON-OU

Réalisation d’une fonction F exprimée en somme de produits avec des portes NON-ET SOP, F = (W*X) + (/Y*Z) + (X*/Y) + (W*Z) /{ /[F] } = /{ /[(W*X) + (/Y*Z) + (X*/Y) + (W*Z)] }

F = /{ /(W*X) * /(/Y*Z) * /(X*/Y) * /(W*Z) } À partir de SOP, on obtient une réalisation avec seulement des portes NON-ET

Réalisation d’une fonction F exprimée en produit de sommes avec des portes NON-OU POS F = (W+/Y) * (X+Z) /{ /[F] } = /{ /[(W+/Y) * (X+Z)] } F = /{ /(W+/Y) + /(X+Z)] } À partir de POS, on obtient une réalisation avec seulement des portes NON-OU

C’est la réalisation la plus simple : 1 X Quad 2-Input NOR

MULTIPLEXEUR 4 à 1 I0 I1

4 -1

I2

MUX

Out

I3

S1

S0

Out

0

0

I0

0

1

I1

1

0

I2

1

1

I3

S1

S0

Écrivez l’équation de sortie

DÉMULTIPLEXEUR 1 à 4 O0

In

4 -1

O1

MUX

O2

Écrivez l’équation de sortie

O3

S1

-:

S0

non utilisé

S1

S0

O0

O1

O2

O3

0

0

In

-

-

-

0

1

-

In

-

-

1

0

-

-

In

-

1

1

-

-

-

In

DÉCODEUR 2 à 4 O0

I0

Décodeur

O1

2 - 4 I1

O2

O3

Écrivez l’équation de sortie

I1

I0

0 0 1 1

0 1 0 1

O0 O1 O2 O3

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

ENCODEUR 4 à 2 I0

I1

Encodeur

O0

4 - 2 I2

O1

I3

Écrivez l’équation de sortie

I0

I1

I2

I3

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

O1 O0

0 0 1 1

0 1 0 1

ENCODEUR DE PRIORITÉ 4 à 2 I0

I1

Encodeur de

O0

Priorité I2

4 - 2

O1

I3

Écrivez l’équation de sortie

I0

I1

I2

I3

1 0 0 0

X 1 0 0

X X 1 0

X X X 1

O1 O0

0 0 1 1

0 1 0 1