Simplification des fonctions logiques
n Table de Karnaugh
n Fonctions complètement définies
n Fonctions incomplètement définies
[Link]@[Link]
Simplification
Les diverses expressions algébriques qui représentent une même
fonction sont dites équivalentes ou égales
Une transformation d’une expression algébrique est le passage
de cette expression à une expression équivalente
On appelle simplification la transformation qui correspond au
passage de la forme canonique à un polynôme contenant le
nombre minimal de lettres
Ce polynôme minimal conduit à des réalisations matérielles qui
réduisent le nombre de portes logiques du circuit
1
Table de Karnaugh
La table de Karnaugh est un mode de représentation des fonctions
logiques qui permet d’effectuer des simplifications graphiques
La table de Karnaugh à quatre variables présente deux variantes
DC
D
BA 00 01 11 10
00
01
A
11
B
10
Table de Karnaugh
Dans les cases des deux variantes de la table, on a respectivement
représenté le numéro décimal de l’état D,C,B,A et son équivalent
binaire
DC
D
BA 00 01 11 10
0 4 12 8 00 0000 0100 1100 1000
1 5 13 9 01 0001 0101 1101 1001
A
3 7 15 11 11 0011 0111 1111 1011
B
2 6 14 10 10 0010 0110 1110 1010
2
Représentation des variables
La représentation d’une variable correspond à un bloc de 8 cases
On a ainsi représenté A et A’ dans les tables ci-dessous
D D
1 1 1 1
1 1 1 1
A A
1 1 1 1
B B
1 1 1 1
C C
Représentation des monômes
Les produits de deux variables correspondent à des blocs de
quatre cases ainsi que C’A’ et DC ci-dessous
D D
1 1 1
1
A A
1
B B
1 1 1
C C
3
Représentation des monômes
Les produits de 3 (resp. 4) variables correspondent à des blocs de
2 (resp. 1) cases ainsi que C’BA et D’CB’A ci-dessous
D D
1
A A
1 1
B B
C C
Représentation des polynômes
Tout polynôme, tel que Z = DA + DC, est représenté par la réunion
des blocs qui décrivent ses monômes
1 1
A
1 1
B
1
4
Impliquant premier
On appelle impliquant premier d’un polynôme tout monôme qui
n’est pas totalement inclus dans un monôme plus grand
Z = DC + DCA D
Z = DC (1 + A)
Z = DC . 1 1
Z = DC
1
Le monôme DCA qui est A
totalement inclus dans le 1
monôme DC peut être B
supprimé 1
Exemple de simplification
On cherche à simplifier la fonction Z(D,C,B,A)=Σ0,1,2,3,10,11
On trouve:
0 bloc de 8 cases D
2 blocs de 4 cases
7 blocs de 2 cases 1
6 blocs de 1 case
1
Seuls les blocs de 2 cases A
sont des impliquants 1 1
premiers et ils conduisent B
au polynôme: 1 1
z = D’C’ + C’B C
5
Exemple de simplification
On cherche à simplifier la fonction Z(D,C,B,A)=Σ0,1,3,7
On trouve 3 blocs de 2 cases:
D’C’B’, D’C’A, D’BA D
Ce sont tous des 1*
impliquants premiers
mais D’C’A qui est 1
contenu dans la réunion A
des deux autres peut 1 1*
être supprimé B
z = D’C’B’ + D’BA
C
Impliquant premier essentiel
On appelle impliquant premier essentiel un impliquant qui,
dans la table de Karnaugh, remplit une case au moins qui n’est
pas incluse dans un autre impliquant
On marque d’un astérisque (*) ce type de case
Les impliquants premiers essentiels sont des impliquants qui
sont inclus dans toutes les solutions minimales résultant de la
simplification
6
Méthode de simplification
La méthode de simplification des fonctions logiques s’effectue
en quatre étapes:
1) Introduire la fonction dans la table de Karnaugh
2) Trouver tous les blocs de 1 qui correspondent à des
impliquants premiers de la fonction
3) Marquer d’un astérisque (*) les impliquants premiers
essentiels
4) Déterminer le polynôme minimal qui se compose de tous les
impliquants premiers essentiels et d’un ensemble minimal
d’impliquants premiers non essentiels destinés à couvrir les
1 de la fonction qui ne sont pas couvert par les impliquants
premiers essentiels
Méthode de simplification
1) Introduction de la fonction Z(D,C,B,A)=Σ3,5,7,8,12,13 dans la
table de Karnaugh
1 1
1 1
A
1 1
B
7
Méthode de simplification
2) 5 impliquants premiers de la fonction (blocs de deux cases):
D’CA, D’BA, DCB’, DB’A’ et CB’A
1 1
1 1
A
1 1
B
Méthode de simplification
3) 2 impliquants premiers essentiels (*): D’BA et DB’A’
1 1*
1 1
A
1* 1
B
8
Méthode de simplification
4) 1 solution minimale: Z = D’BA + DB’A’ + CB’A
1 1*
1 1
A
1* 1
B
Méthode de simplification
1) Introduction de la fonction Z(D,C,B,A)=Σ1,5,6,7,11,12,13,15
dans la table de Karnaugh
1 1 1
A
1 1 1
B
1
9
Méthode de simplification
2) 5 impliquants premiers de la fonction (1 bloc de 4 cases et
4 blocs de 2 cases): CA, D’CB, DCB’, D’B’A et DBA
1 1 1
A
1 1 1
B
1
Méthode de simplification
3) 4 impliquants premiers essentiels (*): D’CB, DCB’,D’B’A
et DBA
1*
1* 1 1
A
1 1 1*
B
1*
10
Méthode de simplification
4) 1 solution minimale: Z = D’CB + DCB’ + D’B’A + DBA
1*
1* 1 1
A
1 1 1*
B
1*
Application
On dispose de l’affichage à 7 segments représenté ci-dessous
Il s’agit de calculer les fonctions des segments a, b, … , g de
manière à représenter le nombre binaire D,C,B,A sous forme
hexadécimale
f b
g
e c
d
11
Application
On commence par établir une table de Karnaugh générale
dans laquelle on représente les états de l’affichage
Application
Simplification du segment supérieur a (allumé=1):
1) Introduction de la fonction logique dans la table
1 1 1
1 1
A
1 1 1
B
1 1 1 1
12
Application
2) 7 impliquants premiers
3) 6 impliquants premiers essentiels (*)
1* 1* 1
1* 1*
A
1* 1 1*
B
1 1 1 1
Application
4) 1 solution minimale:
a = D’B + DA’ + C’A’ + CB + D’CA + DC’B’
1* 1* 1
1* 1*
A
1* 1 1*
B
1 1 1 1
13
Application
Simplification du segment supérieur droite b:
1) Introduction de la fonction logique dans la table
1 1 1
1 1 1
A
1 1
B
1 1
Application
2) 6 impliquants premiers
3) 4 impliquants premiers essentiels (*)
1 1* 1
1 1* 1
A
1 1*
B
1 1*
14
Application
4) 2 solutions minimales:
b = C’A’ + D’B’A’ + D’BA + DB’A + (D’C’ ou C’B’)
1 1* 1
1 1* 1
A
1 1*
B
1 1*
Application
Simplification du segment inférieur droite c:
1) Introduction de la fonction logique dans la table
1 1 1
1 1 1 1
A
1 1 1
B
1 1
15
Application
2) 7 impliquants premiers
3) 3 impliquants premiers essentiels (*)
1 1 1
1 1 1* 1
A
1 1 1
B
1* 1*
Application
4) 4 solutions minimales:
c = D’C + DC’ + B’A + (D’B’ ou C’B’) + (D’A ou C’A)
1 1 1
1 1 1* 1
A
1 1 1
B
1* 1*
16
Réalisation NAND
Il s’agit de déterminer le nombre minimal de porte NAND pour
implémenter les fonctions a, b et c de l’affichage:
a = D’B + DA’ + C’A’ + CB + D’CA + DC’B’
b = C’A’ + D’B’A’ + D’BA + DB’A + (D’C’ ou C’B’)
c = D’C + DC’ + B’A + (D’B’ ou C’B’) + (D’A ou C’A)
On a souligné les termes qui se retrouvent dans les expressions
Il convient d’y recourir car on ne les implémente qu’une fois
Bilan matériel:
- 9 portes NAND à 2 entrées
- 5 portes NAND à 3 entrées
- 2 portes NAND à 5 entrées
- 1 porte NAND à 6 entrées
Réalisation circuits intégrés
Sachant qu’on dispose des circuits intégrés suivants:
- circuit intégré 7430 (1 porte NAND à 8 entrées)
- circuit intégré 7420 (2 portes NAND à 4 entrées)
- circuit intégré 7400 (4 portes NAND à 2 entrées)
Pour implémenter:
- 9 portes NAND à 2 entrées
- 5 portes NAND à 3 entrées
- 2 portes NAND à 5 entrées
- 1 porte NAND à 6 entrées
On aura recours à:
- 3 circuits 7430 (1 NAND à 6, 2 NAND à 5)
- 3 circuits 7420 (5 NAND à 3, 1 NAND à 2)
- 2 circuits 7400 (8 NAND à 2)
17
Fonctions de deux variables
La table de Karnaugh d’une fonction de deux variables z(a,b)
comporte quatre cases numérotées de 0 à 3
0 2
b 1 3
Fonctions de deux variables
La simplification de la fonction OU z(a,b)=Σ1,2,3 fait apparaître
deux impliquants premiers essentiels a et b
On retrouve ainsi la relation z=a+b
b 1 1
18
Fonctions de trois variables
La table de Karnaugh d’une fonction de trois variables z(a,b,c)
comporte huit cases numérotées de 0 à 7
0 2 6 4
c 1 3 7 5
Fonctions de trois variables
La simplification de la fonction MAJ(a,b,c)=Σ3,5,6,7 fait apparaître
trois impliquants premiers essentiels ab, ac et bc
On retrouve ainsi la relation MAJ(a,b,c)=ab+ac+bc
c 1 1 1
19
Fonctions de cinq variables
La table de Karnaugh d’une fonction de cinq variables
Z(E,D,C,B,A) comporte 32 cases numérotées de 0 à 31
E
D D
0 4 12 8 16 20 28 24
1 5 13 9 17 21 29 25
A
3 7 15 11 19 23 31 27
B
2 6 14 10 18 22 30 26
C C
On trouve alors des blocs qui appartiennent à:
- la table E=0 uniquement tel que E’BA’
- la table E=1 uniquement tel que EC’B
- la table E=0 et la table E=1 simultanément tel que D’C’
E
D D
1 1
1 1
A
1 1 1
B
1 1 1 1 1 1
C C
20
Fonctions égalité et majorité
Considérons les fonctions égalité E et majorité M de quatre
variables a, b, c et d
a E(a,b,c,d)
b
c
d M(a,b,c,d)
Condition indifférente
En cas d’égalité E=1, la fonction majorité peut prendre
indifféremment la valeur 0 ou 1
Il s’agit d’une condition indifférente que nous symboliserons
par la lettre Φ
On est ainsi conduit à la notion de fonction incomplètement
définie (on dit aussi incomplètement spécifiée)
E M
Majorité de 0 0 0
Majorité de 1 0 1
Egalité 1 Φ
21
No a b c d E(a,b,c,d) M(a,b,c,d)
0 0 0 0 0 0 0
1 0 0 0 1 0 0
2 0 0 1 0 0 0
3 0 0 1 1 1 Φ
4 0 1 0 0 0 0
5 0 1 0 1 1 Φ
6 0 1 1 0 1 Φ
7 0 1 1 1 0 1
8 1 0 0 0 0 0
9 1 0 0 1 1 Φ
10 1 0 1 0 1 Φ
11 1 0 1 1 0 1
12 1 1 0 0 1 Φ
13 1 1 0 1 0 1
14 1 1 1 0 0 1
15 1 1 1 1 0 1
Condition indifférente
Les formes canoniques décimales des fonctions égalité E et
majorité M des quatre variables a, b, c et d s’écrivent:
E(a,b,c,d) = Σ 3,5,6,9,10,12
M(a,b,c,d) = Σ 7,11,13,14,15 + Φ 3,5,6,9,10,12
Comme chacune des six conditions indifférentes de M peut
prendre la valeur 0 ou 1, il y a 26=64 solutions possibles
pour cette fonction
En particulier, la fonction majorité de trois variables
MAJ(a,b,c) est une solution pour la fonction majorité de
quatre variables M(a,b,c,d)
22
Application
On dispose de l’affichage à 7 segments représenté ci-dessous
Il s’agit de calculer les fonctions des segments a, b, … , g de
manière à représenter sous forme décimale les nombres
binaires D,C,B,A compris entre 0000 et 1001 (0 et 9)
f b
g
e c
d
Application
La table de Karnaugh générale comporte des conditions indifférentes
pour tous les états de D,C,B,A compris entre 1010 et 1111 (10 et 15)
Φ
A
Φ Φ
B
Φ Φ
23
Application
Le segment inférieur gauche e(D,C,B,A)=Σ0,2,6,8+Φ10,…,15
correspond ainsi à la table de Karnaugh individuelle ci-dessous
1 Φ 1
Φ
A
Φ Φ
B
1 1 Φ Φ
Application
Pour trouver les plus grands blocs possibles, on recherche d’abord
les impliquants premiers de la fonction en considérant Φ=1
1 Φ 1
Φ
A
Φ Φ
B
1 1 Φ Φ
24
Application
On détermine ensuite parmi ces impliquants ceux qui sont
essentiels (*) en considérant cette fois Φ=0
1* Φ 1
Φ
A
Φ Φ
B
1 1* Φ Φ
Application
Les deux impliquants premiers essentiels (*) suffisent à couvrir
tous les 1 de la fonction: e = C’A’ + BA’
1* Φ 1
Φ
A
Φ Φ
B
1 1* Φ Φ
25
Méthode de simplification
La méthode de simplification des fonctions incomplètement
définies s’effectue en quatre étapes:
1) Introduire la fonction dans la table de Karnaugh
2) Trouver tous les blocs de 1 qui correspondent à des
impliquants premiers de la fonction (Φ=1)
3) Marquer d’un astérisque (*) les impliquants premiers
essentiels (Φ=0)
4) Déterminer le polynôme minimal qui se compose de tous les
impliquants premiers essentiels et d’un ensemble minimal
d’impliquants premiers non essentiels destinés à couvrir les
1 de la fonction qui ne sont pas couvert par les impliquants
premiers essentiels
Application
Simplification du segment supérieur a:
1) Introduction de la fonction logique dans la table
1 Φ 1
1 Φ 1
A
1 1 Φ Φ
B
1 Φ Φ
26
Application
2) 5 impliquants premiers (Φ=1)
3) 3 impliquants premiers essentiels (*, Φ=0)
1* Φ 1
1* Φ 1*
A
1 1 Φ Φ
B
1 Φ Φ
Application
4) 2 solutions minimales:
a = D + C’A’ + CA + (C’B ou BA)
1* Φ 1
1* Φ 1*
A
1 1 Φ Φ
B
1 Φ Φ
27
Application
L’analyse des six états non définis du segment a montre que pour
les deux solutions minimales ils correspondent tous à des 1
D D
1
A A
1 1
B B
1 1
C C
Application
L’analyse des six états non définis du segment e montre que seul
deux d’entre eux correspondent à des 1
D D
0
A A
0 0
B B
1 1
C C
28
Application
Pour l’ensemble des segments, l’analyse des six états non définis
conduit à l’affichage représenté ci-dessous
Comparateur
On se propose de calculer les fonctions supériorité S, égalité E
et infériorité I résultant de la comparaison de deux nombres
binaires A et B de n bits chacun
A B
S
E
I
A > B : (S,E,I) = 100
A = B : (S,E,I) = 010
A < B : (S,E,I) = 001
29
Comparateur
Pour le faire, on va concevoir un module qui compare les bits
de rang i des deux nombres A et B
Ce module fournit les comparaisons S, E et I pour le rang i+1
Ai Bi
Si+1 Si
Ei+1 Ei
Ii+1 Ii
(Si+1,Ei+1,Ii+1) = 100
(Si+1,Ei+1,Ii+1) = 010
(Si+1,Ei+1,Ii+1) = 001
Si Ei Ii Ai Bi Si+1 Ei+1 Ii+1
0 0 0 Φ Φ -
0 0 1 0 0 0 0 1
0 1 0 0 1
1 0 1 0 0
1 1 0 0 1
0 1 0 0 0 0 1 0
0 1 0 0 1
1 0 1 0 0
1 1 0 1 0
0 1 1 Φ Φ -
1 0 0 0 0 1 0 0
0 1 0 0 1
1 0 1 0 0
1 1 1 0 0
1 0 1 Φ Φ -
1 1 0 Φ Φ -
1 1 1 Φ Φ -
30
Comparateur
La simplification de la fonction Si+1 conduit à la relation:
Si+1 = SiAi + SiBi’ + AiBi’
Si
Ei Ei
- 0 - 0 1 - - -
- 0 - 0 0 - - -
Bi
- 0 - 0 1 - - -
Ai
- 1 - 1 1 - - -
Ii Ii
Comparateur
La simplification de la fonction Ii+1 conduit à la relation:
Ii+1 = IiAi’ + IiBi + Ai’Bi
Si
Ei Ei
- 1 - 0 0 - - -
- 1 - 1 1 - - -
Bi
- 1 - 0 0 - - -
Ai
- 0 - 0 0 - - -
Ii Ii
31
Comparateur
La simplification de la fonction Ei+1 conduit à la relation:
Ei+1 = EiAi’Bi’ + EiAiBi
Si
Ei Ei
- 0 - 1 0 - - -
- 0 - 0 0 - - -
Bi
- 0 - 1 0 - - -
Ai
- 0 - 0 0 - - -
Ii Ii
Comparateur
Les équations du module de comparaison vérifient ainsi les
trois relations:
Si+1 = SiAi + SiBi’ + AiBi’
Ii+1 = IiAi’ + IiBi + Ai’Bi
Ei+1 = EiAi’Bi’ + EiAiBi
Du fait du codage 1 parmi 3 utilisé, il est cependant possible
de remplacer n’importe laquelle de ces relations par une
combinaison des deux autres:
Si+1 = Ii+1’Ei+1’
Ii+1 = Si+1’Ei+1’
Ei+1 = Si+1’Ii+1’
32
Caractéristiques temporelles
Tout circuit logique qui réalise une somme de produits peut
engendrer un aléa statique (en anglais: static hazard) à sa
sortie si son schéma comporte trois niveaux de portes
Le circuit ci-dessous qui implémente la fonction logique
z = ab + b’c
présente un aléa statique lorsqu’on passe de l’état d’entrée
a,b,c=111 à l’état a,b,c=101
a x
b
z
c y
Caractéristiques temporelles
L’aléa statique engendré par le déclenchement de l’entrée b
se traduit par une impulsion indésirable (en anglais: glitch)
1->0->1 à la sortie z
33
Caractéristiques temporelles
Dans la table de Karnaugh, où la fonction z correspond aux
deux impliquants premiers ab et b’c, l’aléa statique produit
par le déclenchement de b résulte du passage de l’un à l’autre
de ces impliquants
Pour le supprimer, il convient d’ajouter l’impliquant ac, qui
couvre la transition, dans l’équation de z
c 1 1 1
Caractéristiques temporelles
On appelle aléas dynamiques (en anglais: dynamic hazards)
les séquences non désirables
z = 1 -> 0 -> 1 -> 0
ou
z = 0 -> 1 -> 0 -> 1
qui résultent de l’enclenchement ou du déclenchement d’une
variable d’entrée
Les aléas dynamiques peuvent survenir dans les circuits dont
le nombre de niveaux de portes logiques est supérieur à trois
34