Cours n°3 : Synthèse des systèmes logiques
I : Formes canoniques *
I.1.a : définition des mintermes *
I.1.b : Expression algébrique des mintermes *
I.1.c : Expression dune fonction à partir des mintermes *
I.2 : Deuxième forme canonique *
I.2.a : définition des maxtermes *
I.2.b : Expression algébrique des maxtermes *
I.2.c : Expression dune fonction à partir des maxtermes *
I.3 : Choix de la forme canonique *
II : Synthèse dun distributeur de café *
II.2 : Afficheur 7 segments *
II.3 : Table de vérité *
II.4 : Forme canonique des fonctions *
II-5 : Logigramme *
III : Tableaux de Karnaugh *
III.1.a : Définition *
III.1.b : Exemple dun tableau à 4 variables *
III.2 : Représentation dune fonction par tableau de Karnaugh *
III.2.a : Cas général *
III.2.b : Représentation dun minterme *
III.2.c : Représentation dun produit quelconque *
III.3 : Détermination de lexpression dune fonction daprès son tableau de Karnaugh *
III.3.a : Formes canoniques *
III.3.b Formes minimales *
III.4 : Circuit en " trois couches " *
III.5 : Exemple de synthèse en " trois couches " *
III.5.a : Table de vérité *
III .5.b : Tableau de Karnaugh *
III.5.c : Expression algébrique de la fonction *
III.5.d : Logigramme en trois couches *
Toute fonction logique peut sexprimer sous forme algébrique en nutilisant que la somme, le produit et la négation logiques.
Nous allons voir comment, à partir de sa table de vérité, toute fonction peut sécrire sous deux formes particulières appelées formes canoniques et utilisant des fonctions dénommées mintermes et maxtermes.
I.1 : Première forme canonique
I.1.a : définition des mintermes
Soit un mot binaire de n variables (un problème logique avec n variables dentrées logiques). Il existe 2n états binaires possibles pour ce mot binaire. Par conséquent, il existe 2n fonctions de ces n variables ne comportant quun seul 1 dans leur table de vérité.
On appelle ces fonctions des mintermes et on les note mi, i étant léquivalent décimal de lunique état binaire pour lequel le minterme vaut 1.
Exemple pour une entrée à trois variables :
I.1.b : Expression algébrique des mintermes
Dans notre exemple, choisissons le minterme m3.
On peut énoncer : m3=1 ssi %CBA=%011
Ou encore : m3=1 si ( C=0 ET B=1 ET A=1 ) ou m3=1 si (/C=1 ET B=1 ET A=1).
On obtient lexpression algébrique du minterme à partir de sa table de vérité.
Il faut noter que lexpression du minterme comprend toujours toutes les variables dentrées soit sous leur forme directe, soit sous leur forme complémentée.
I.1.c : Expression dune fonction à partir des mintermes
A partir de la table de vérité, on peut énoncer :
(S=1) ssi [ (m3=1) OU (m5=1) OU (m6=1) OU (m7=1) ]
Cest la première forme canonique.
Sous forme développée, on déduit S :
On peut donc, à partir de sa table de vérité et quelques soient la fonction et le nombre de variables dentrée, déterminer lexpression algébrique de cette fonction, et donc den déduire son logigramme.
Note : la première forme canonique dune fonction nest pas forcément son expression la plus simple.
I.2 : Deuxième forme canonique
I.2.a : définition des maxtermes
Soit un mot binaire de n variables (un problème logique avec n variables dentrées logiques). Il existe 2n états binaires possibles pour ce mot binaire. Par conséquent, il existe 2n fonctions de ces n variables ne comportant quun seul 0 dans leur table de vérité.
On appelle ces fonctions des maxtermes et on les note Mi, i étant léquivalent décimal de lunique état binaire pour lequel le maxterme vaut 0.
Exemple pour une entrée à trois variables :
I.2.b : Expression algébrique des maxtermes
On constate sur la table de vérité que
Cette relation permet dobtenir lexpression de Mi à partir de celle de mi.
Par application du théorème de De Morgan on obtient :
On obtient lexpression algébrique du maxterme à partir de sa table de vérité.
Il faut noter que lexpression du maxterme comprend toujours toutes les variables dentrées soit sous leur forme directe, soit sous leur forme complémentée.
I.2.c : Expression dune fonction à partir des maxtermes
A partir de la table de vérité, on peut énoncer :
(S=0) ssi (M0=0) OU (M1=0) OU (M2=0) OU (M4=0)
donc, par application de De Morgan,
La fonction sexprime donc sous la forme dun produit de maxtermes qui valent 0 pour un des états dentrée qui donnent à S la valeur 0.
Cest la deuxième forme canonique.
Sous forme développée, on déduit S :
On peut donc, à partir de sa table de vérité et quelles que soient la fonction et le nombre de variables dentrée, déterminer lexpression algébrique de cette fonction, et donc den déduire son logigramme.
Note : la deuxième forme canonique dune fonction nest pas forcément son expression la plus simple, elle nest pas non plus forcément plus simple ou plus complexe que la première forme.
Suivant la fonction, on aura intérêt à utiliser plutôt une forme que lautre.
Si la table de vérité de la fonction comporte une minorité de 1, mieux vaut utiliser la première forme canonique.
Si la table de vérité de la fonction comporte une majorité de 1, mieux vaut utiliser la deuxième forme canonique.
Dans la plupart des cas, on préférera utiliser la première forme.
II : Synthèse dun distributeur de café
On désire faire la synthèse dun distributeur (simplifié) de café.
Les informations disponibles en entrée sont :
Les informations à fournir en sortie sont :
Un afficheur " 7 segments "
regroupe 7 LEDs en bâtons, pouvant visualiser les chiffres
décimaux, quelques lettres, et en général un point décimal.
Si la variable binaire a est égale à 1, le segment correspondant est allumé.
On voit que pour afficher un chiffre donné, il suffit de correctement fixer le mot binaire %gfedcba.
II.4 : Forme canonique des fonctions
Il y a 8 fonctions logiques à déterminer : C, a,b,c,d,e,f,g
La table de vérité de C ne comportant quun seul 1, on prendra la première forme canonique :
C=P2.P1
Pour a, il vaut mieux prendre la seconde forme canonique :
Pour b, on remarque que
b=1
Même remarque que pour a pour c et d :
Pour e, f et g on utilisera la première forme canonique :
On remarque quil a été possible de simplifier les formes canoniques.
Cette réalisation ne demanderait que peu de boîtiers de type 74.
III.1 : Présentation des tableaux de Karnaugh
Un tableau de Karnaugh est constitué de cases (ou régions minimales) associées à chacune des combinaisons dentrée de la fonction représentée. Il possède donc 2n cases pour une fonction de n variables.
Un tableau de Karnaugh est conçu de manière à permettre deffectuer commodément des simplifications sur lexpression de la fonction.
Cest une forme particulière de la table de vérité.
III.1.b : Exemple dun tableau à 4 variables
La forme utilisée est la suivante :
%DC | %BA | 00 | 01 | 11 | 10 |
00 | |||||
01 | |||||
11 | |||||
10 |
Dans ce tableau, la case repérée * est associée à la combinaison %DCBA=%1101.
On remarque que les combinaisons correspondant à deux cases adjacentes ne différent que pour une seule des variables dentrée. Par exemple :
La case marquée dune * correspond à la combinaison %DCBA=%1101.
Les 4 cases marqués dun . lui sont toutes adjacentes. Leurs combinaisons associées sont :
%DCBA=%0101, %DCBA=%1001, %DCBA=%1100, %DCBA=%1111.
Chaque case possède 4 cases adjacentes, dont les combinaisons associées ne différent que par une et une seule variable.
On peut noter dans la case la combinaison dentrée associée. On indique alors quelle combinaison (ici %DCBA).
III.2 : Représentation dune fonction par tableau de Karnaugh
La représentation dune fonction par tableau de Karnaugh sobtient en dessinant un tableau de la dimension correspondant au nombre de variables de la fonction puis en hachurant (ou grisant, ) chacune des cases associées à une combinaison dentrée pour laquelle la fonction vaut 1.
Par exemple, pour la fonction majorité à trois variables :
%C | %BA | 00 | 01 | 11 | 10 |
0 | |||||
1 |
La construction du tableau peut être faite directement ou à partir de la table de vérité.
III.2.b : Représentation dun minterme
Un minterme nayant quun seul 1 dans sa table de vérité, il ny aura quune seule case hachurée dans son tableau de Karnaugh.
Inversement, un tableau de Karnaugh nayant quune seule case hachurée représente un minterme.
III.2.c : Représentation dun produit quelconque
Pour une fonction de n variables dentrées, les produits possibles de ces variables dentrée (sous forme directe ou complémentée) se répartissent en :
Produits de 1 variable, de 2 variables, de 3 . De n-1 variables, de n variables (mintermes).
Prenons lexemple de trois variables :
Les produits de deux variables : par exemple S=/A.B
Son tableau de Karnaugh est :
%C | %BA | 00 | 01 | 11 | 10 |
0 | |||||
1 |
Il est constitué de deux cases adjacentes. Une telle région est appelée région de taille 2.
Inversement, une région de taille 2 dans un tableau de Karnaugh à trois variables représente un produit de 2 variables.
Pour un produit dune seule variable, par exemple, S=B
Le tableau de Karnaugh de S est :
%C | %BA | 00 | 01 | 11 | 10 |
0 | |||||
1 |
Il est constitué de 4 cases hachurées adjacentes.
Une telle région est appelée région de taille 4.
Inversement, une région de taille 4 dans un tableau de Karnaugh à trois variables représente un produit dune seule variable.
De manière générale, avec n variables, on admettra :
Un produit de n variables représente un minterme, il correspond à une case hachurée unique.
Un produit de n-1 variables correspond à une région de taille 2.
Un produit de k variables (0<k<=n) correspond à une région de taille 2n-k.
III.3 : Détermination de lexpression dune fonction daprès son tableau de Karnaugh
La première sobtient directement : chaque case hachurée représentant un minterme, on effectue un OU des mintermes correspondants aux cases à 1.
Par exemple, pour la fonction majorité à trois variables :
%C | %BA | 00 | 01 | 11 | 10 |
0 | |||||
1 |
S=C.A./B + C.B.A + C.B./A +/C.B.A
Remarque : écrire /S revient à utiliser les cases non hachurée du tableau.
/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)
On cherchera à établir la fonction sous forme dune somme de produits les plus courts possible de variables dentrée sous forme simple ou complémentée.
Pour cela, on essaie à partir du tableau de Karnaugh, de déterminer les régions de taille maximum, en recouvrant toutes les cases hachurées. Une région de taille 4 donne un produit plus simple quune région de taille 2.
Note : si toutes les cases hachurées sont disjointes, la fonction ne sécrit que sous ses formes canoniques.
Si lon reprend lexemple de la fonction majorité à trois variables :
%C | %BA | 00 | 01 | 11 | 10 |
0 | |||||
1 |
Il faut trouver les régions de taille la plus grande possible. On peut réaliser les groupements ci-dessus :
On trouve 3 régions de taille 2 (aucune région de taille 4 possible). Toutes les cases hachurées sont contenues dans ces régions.
Or on a S1=A.C, S2=A.B, S3=B.C
On obtient donc la forme minimale pour S :
Remarques :
III.4 : Circuit en " trois couches "
Lorsquon synthétise une fonction combinatoire à laide des tableaux de Karnaugh, suivant la méthode décrite ci-dessus, on établit un logigramme dit en " trois couches ".
On a vu que cette méthode donnait comme expression algébrique de la fonction une somme de produits des variables dentrées ou de leur complément.
Quelle que soit la fonction et le nombre de variables dentrées, la structure du circuit sera toujours :
Cette structure présente plusieurs avantages :
III.5 : Exemple de synthèse en " trois couches "
Soit la fonction F(D,C,B,A) dont voici la table de vérité :
III .5.b : Tableau de Karnaugh
Construisons le tableau de Karnaugh de la fonction F à partir de sa table de vérité :
0000 | 0010 | 0011 | 0001 |
0100 | 0110 | 0111 | 0101 |
1100 | 1110 | 1111 | 1101 |
1000 | 1010 | 1011 | 1001 |
Il y a un groupement de taille 4 (donc un produit de 2 variables) et deux groupements de taille 2 (un produit de 3 variables).
Leurs expressions sont :
/A.C, B.C.D et D.A./C
III.5.c : Expression algébrique de la fonction
Daprès le tableau de Karnaugh, on déduit que lexpression minimale de F est :
F = /A.C + /D.A.C + B.C.D
III.5.d : Logigramme en trois couches