#### ENI: Électronique Numérique Intégrée

###

[Suivant] [Précédent] [Fin] [Niveau supérieur]

## Chapitre 2
Fonctions de base

2.1 Introduction
2.2 Variables et fonctions logiques, tables de vérité
2.3 Représentations des fonctions logiques
2.3.1 Formes algébriques
2.3.2 Forme disjonctive
2.3.3 Forme conjonctive
2.3.4 Équivalence entre la table de vérité et les formes canoniques
2.3.5 Forme canonique disjonctive
2.3.6 Forme canonique conjonctive
2.4 Description de méthodes de simplification
2.4.1 Utilisation des propriétés de l’algèbre de Boole
2.4.2 Simplification à partir de la forme algébrique
2.4.3 Méthode des tables de Karnaugh
2.4.4 Construction du tableau de Karnaugh
2.4.5 Règles de simplification
2.4.6 Fonctions non complètement définies
2.4.7 Pertinence de la méthode
2.5 Représentation schématique des fonctions logiques
2.6 Quelques fonctions combinatoires importantes
2.6.1 Fonctions d’aiguillage : multiplexeurs
2.6.2 Opérateurs de comparaison
2.7 Annexes
2.7.1 Exercice de consolidation
2.7.2 Bibliographie

### 2.1 Introduction

Nous évoquons, dans le chapitre 1, la possibilité de réaliser physiquement des fonctions de calcul utilisant une représentation binaire des données. Avant de poursuivre plus avant l’étude de la réalisation physique de ces fonctions, nous allons développer les bases mathématiques des fonctions logiques (Algèbre de Boole) ainsi que les méthodes de représentation et de manipulation associées.

Le choix d’une structure physique optimale pour construire une fonction logique est une opération complexe dépendant de nombreuses contraintes telles que l’optimisation de la vitesse de traitement, la minimisation de l’énergie dissipée par opération ou tout simplement le coût de fabrication.

Nous nous contenterons dans ce chapitre d’envisager le critère suivant qui pourra être remis en cause dans la suite du cours :

- La construction de fonctions combinatoires complexes est basée sur l’utilisation d’une bibliothèque de fonctions logiques (ou portes) élémentaires telles que l’inversion, le « ou » logique, et le « et » logique.
- L’optimisation des fonctions complexes est basée sur la minimisation du nombre des portes élémentaires utilisées qui correspond à une simplification des équations booléennes associées.

### 2.2 Variables et fonctions logiques, tables de vérité

Considérons l’ensemble E à 2 éléments (0,1).

1. Une variable logique est un élément de E et ne possède ainsi que 2 états 0 et 1. Elle est représentée par des lettres (A,b,e,X,).
2. Une fonction logique de plusieurs variables applique E × E ×E dans E. Elle associe à un n-uplet de variables booléennes (e0,e1,,en-1) une valeur F(e0,e1,,en-1).
3. Il existe différentes manières d’exprimer une fonction booléenne. Une fonction de n variables est entièrement décrite par l’énoncé des valeurs de cette fonction pour l’ensemble (ou le sous-ensemble de définition) des combinaisons du n-uplet de variables :

   Cet énoncé prend généralement la forme d’un tableau à n + 1 colonnes et au plus 2n lignes, chaque ligne exposant une combinaison des variables et la valeur correspondante de la fonction. Les tableaux 2.1 et 2.2 suivants donnent la forme générale de tables de v érit é de fonctions de trois variables totalement (fonction F) ou partiellement (fonction G) définies.

Ta b. 2.1: | Table de vérité d’une fonction de 3 variables.

Ta b. 2.2: | Table de vérité d’une fonction partiellement définie.

### 2.3 Représentations des fonctions logiques

#### 2.3.1 Formes algébriques

Nous associons, à l’ensemble E, l’algèbre de Boole basée sur trois opérateurs logiques :

- Opérateur NON : réalise la complémentation (ou inversion) représentée ici par une barre horizontale : « ».
- Opérateur OU : réalise l’union (ou addition logique) notée ici : « ».
- Opérateur ET : réalise l’intersection (ou multiplication logique) notée ici : « ».

Les tables de vérité de ces trois fonctions logiques sont données dans les tableaux 2.3, 2.4 et 2.5.

Ta b. 2.3: | Opérateur NON.
Ta b. 2.4: | Opérateur OU.
Ta b. 2.5: | Opérateur ET.

Une fonction logique booléenne se présente comme une association des opérations algébriques précédentes sur un ensemble de variables. Elle peut s’écrire de plusieurs façons.

#### 2.3.2 Forme disjonctive

Elle correspond à une somme de produits logiques : , où ei représente une variable ou son complément. Exemple :

Si chacun des produits contient toutes les variables d’entrée sous une forme directe ou complémentée, alors la forme est appelée « premi ère forme canonique » ou « forme canonique disjonctive ». Chacun des produits est alors appelé minterme. Exemple de forme canonique disjonctive :

#### 2.3.3 Forme conjonctive

Elle fait référence à un produit de sommes logiques : . Voici un exemple :

Si chacune des sommes contient toutes les variables d’entrée sous une forme directe ou complémentée, alors la forme est appelée « deuxi ème forme canonique » ou « forme canonique conjonctive ». Chacune des sommes est alors appelée maxterme. Exemple de forme canonique conjonctive :

#### 2.3.4 Équivalence entre la table de vérité et les formes canoniques

Nous avons défini la table de vérité d’une fonction comme la correspondance entre chaque combinaison des variables (du domaine de définition de la fonction) et la valeur (0 ou 1) associée de cette fonction.

Chacune des combinaisons des variables définit un état des entrées, on peut donc associer un état à chaque ligne d’une table de vérité.

#### 2.3.5 Forme canonique disjonctive

Une fonction logique est représentée par l’ensemble des états pour lesquels la fonction est égale à « 1 ».

Considérons maintenant un état des entrées pour lequel une fonction booléenne vaut « 1 » : il existe un minterme unique prenant la valeur « 1 » dans cet état.

Il suffit donc d’effectuer la somme logique (ou réunion) des mintermes associés aux états pour lesquels la fonction vaut « 1 » pour établir l’expression canonique disjonctive de la fonction.

Exemple d’une fonction H à trois variables entièrement définie :

Ta b. 2.6: | Table de vérité de la fonction H : états associés et mintermes.

On remarque que H(A,B,C) = 1 pour les états 0, 1, 3, 5. On écrit la fonction ainsi spécifiée sous une forme dite numérique : H = R(0,1,3,5), Réunion des états 0, 1, 3, 5. La première forme canonique de la fonction H s’en déduit directement :

#### 2.3.6 Forme canonique conjonctive

Considérons maintenant un état des entrées pour lequel la fonction vaut « 0 ».

Il existe un maxterme unique prenant la valeur « 0 » en cet état. Ce maxterme prend donc la valeur « 1 » dans tous les autres états des entrées.

Il suffit donc d’effectuer le produit logique (ou intersection) des maxtermes associés aux états pour lesquels la fonction vaut « 0 » pour établir l’expression canonique conjonctive de la fonction.

Reprenons l’exemple de la fonction H :

Ta b. 2.7: | Table de vérité de la fonction H : états associés et maxtermes.

On remarque que H(A,B,C) = 0 pour les états 2, 4, 6, 7. On écrit la fonction ainsi spécifiée sous une forme dite numérique : H = I(2,4,6,7) Intersection des états 2, 4, 6, 7.

La deuxième forme canonique de la fonction H s’en déduit directement :

### 2.4 Description de méthodes de simplification

On cherche ici à obtenir une expression algébrique comportant un nombre minimal de termes, ainsi qu’un nombre minimal de variables dans chaque terme dans le but de simplifier la réalisation matérielle.

Attention : Comme nous l’avons indiqué en introduction, l’optimisation d’une fonction logique dépend de paramètres tels que la performance en vitesse désirée, la consommation maximale autorisée ou l’obligation d’utiliser des bibliothèques de fonctions élémentaires prédéfinies. La complexité de la représentation algébrique n’est donc qu’un critère d’optimisation parmi d’autres.

#### 2.4.1 Utilisation des propriétés de l’algèbre de Boole

Les propriétés, lois et théorèmes fondamentaux de l’algèbre de Boole sont à notre disposition pour manipuler les équations :

Remarque : Deux termes sont dits adjacents logiquement s’ils ne diffèrent que par une variable.

Th éor ème de De Morgan :

Premier th éor ème d’expansion :

Second th éor ème d’expansion :

#### 2.4.2 Simplification à partir de la forme algébrique

Les méthodes algébriques employées se rapportent aux relations fondamentales d’absorption, d’adjacence, de mise en facteur et aux théorèmes de De Morgan. On distingue plusieurs procédés permettant d’aboutir au but recherché :

##### Regroupement des termes et mises en facteur

Nous avons successivement utilisé une mise en facteur, la complémentarité, une deuxième mise en facteur et enfin le théorème d’absorption.

##### Réplication de termes existants

La réplication du terme a.b.c permet de simplifier chacun des trois premiers termes en utilisant une mise en facteur et la complémentarité.

##### Suppression de termes superflus

Nous avons ici réintroduit la variable b dans le troisième terme par l’intermédiaire de la propriété de complémentarité, nous avons ensuite utilisé la propriété d’absorption pour simplifier les produits.

##### Simplification par utilisation des formes canoniques

Si l’on dispose de la table de vérité de la fonction, on prend pour équation algébrique de départ la forme canonique comportant le minimum de termes. Cette équation sera ensuite simplifiée en utilisant les méthodes décrites précédemment. En effet, pour une fonction à N entrées, la forme canonique disjonctive comportera P mintermes (avec P < 2N), alors que la forme conjonctive comportera 2N - P maxtermes.

#### 2.4.3 Méthode des tables de Karnaugh

Les tables de Karnaugh sont des représentations sous forme d’un tableau à deux dimensions de la table de vérité. Elles sont construites de façon à ce que les termes logiquement adjacents soient g éom étriquement adjacents. Chaque ligne de la table de vérité est représentée par une case du tableau de Karnaugh dans laquelle on indique la valeur de la fonction.

La contrainte d’adjacence géométrique est réalisée par un ordonnancement des lignes (resp. colonnes) du tableau pour lequel le nombre de bits modifiés d’un code au suivant est constant et égal à un. Cette propriété est respectée entre le code de la dernière ligne (resp. colonne) et celui de la première ligne (resp. colonne). Prenons par exemple le cas d’une fonction F de trois variables, spécifiée dans le tableau 2.8.

Ta b. 2.8: | Table de vérité de la fonction F : états associés et mintermes.
Ta b. 2.9: | Table de Karnaugh de la fonction F.
Ta b. 2.10: | Correspondance des mintermes.

Nous constatons que la fonction F est égale à « 1 » pour :

- les 4 cases (adjacentes) qui constituent la ligne « a = 1 » (Fig. 2.11) ;
- les 4 cases (adjacentes) qui constituent le carré « c = 1 » (Fig. 2.12).

Ta b. 2.11: | Adjacence : a = 1

Ta b. 2.12: | Adjacence : c = 1

Les deux zones déterminées « recouvrant » exactement les cases du tableau où la fonction F vaut 1, nous pouvons en déduire directement que : F = a + c.

Nous allons maintenant généraliser la méthode exposée dans l’exemple.

#### 2.4.4 Construction du tableau de Karnaugh

- Il y a 2n cases pour n variables.
- A chaque case est associé un minterme égal à 1 pour la combinaison considérée.
- Le passage d’une case à sa voisine se fait par changement d’une seule variable à la fois.

#### 2.4.5 Règles de simplification

Il s’agit de « paver » le tableau de Karnaugh en regroupant les « 1 » adjacents de telle manière que :

- l’ensemble des « 1 » de la fonction appartiennent au moins à un pavé,
- les pavés soient rectangulaires,
- le nombre de « 1 » regroupés dans un pavé soit une puissance de 2.

Chaque pavé ainsi constitué représente un terme produit de la fonction ne contenant que les variables « stables » (par rapport au codage des lignes et des colonnes du tableau).

Attention !

- De même qu’il n’y a pas unicité de la représentation algébrique d’une fonction booléenne, il n’y a pas unicité des regroupements géométriques dans le tableau de Karnaugh.
- Il ne faut pas oublier les adjacences possibles entre colonnes et lignes extrêmes du tableau de Karnaugh.

L’exemple suivant (Tab. 2.13) illustre ces deux principes :

Ta b. 2.13: | Table de Karnaugh
Ta b. 2.14: | Premier pavage
Ta b. 2.15: | Deuxième pavage

Selon le premier pavage (Tab. 2.14), l’expression obtenue est :

Le second pavage (Tab. 2.15), qui utilise une adjacence entre deux cases extrêmes, donne :

#### 2.4.6 Fonctions non complètement définies

Certaines combinaisons peuvent ne pas se produire : elles n’ont pas d’effet sur la valeur de la fonction. Ces états indifférents, notés X ou -, peuvent être utilisés partiellement ou totalement pour simplifier la fonction, comme illustré dans l’exemple de la Fig. 2.16.

Ta b. 2.16: | Table de Karnaugh
Ta b. 2.17: | Premier pavage
Ta b. 2.18: | Deuxième pavage

On profite du fait que les états indifférents peuvent être interprétés au choix comme des 1 ou des 0 pour réaliser les regroupements les plus pertinents permettant d’aboutir à une expression logique minimale. Ici, les deux regroupements en carrés retenus dans les tableaux 2.17 et 2.18 s’imposent naturellement.

L’expression obtenue finalement est :

#### 2.4.7 Pertinence de la méthode

Dans une représentation à 2 dimensions, chaque case a au plus 4 cases géométriquement adjacentes. Pour une fonction logique de plus de 4 variables, le nombre d’adjacences logiques pour un minterme (égal au nombre de variables) devient supérieur aux possibilités dans le plan. Les groupements deviennent alors moins naturels, et la méthode n’est plus aussi utile.

### 2.5 Représentation schématique des fonctions logiques

Notre bibliothèque de fonctions ou portes logiques élémentaires n’est pour l’instant constituée que des trois opérateurs inversion (NOT), « et » logique (AND) et « ou » logique (OR). Nous allons compléter cette bibliothèque par quelques éléments supplémentaires dont l’objectif est de mettre en place une représentation schématique des fonctions logiques.

Nous distinguerons ainsi :

- la fonction NON-ET ou NAND dont la sortie vaut 0 si et seulement si toutes les entrées sont à 1,
- la fonction NON-OU ou NOR dont la sortie vaut 1 si et seulement si aucune entrée n’est à 1.

Ces deux fonctions sont la simple complémentation des fonctions AND et OR.

Nous associons maintenant à chacune des fonctions NOT, OR, AND, NAND et NOR un symbole graphique. La complémentation sera représentée systématiquement par un cercle :

AND | OR | NOT | NAND | NOR
Fi g. 2.1: | Symboles des portes élémentaires.

Exemple de schéma et équation algébrique correspondante :

Fi g. 2.2: | Un exemple de schéma.

### 2.6 Quelques fonctions combinatoires importantes

#### 2.6.1 Fonctions d’aiguillage : multiplexeurs

La fonction « multiplexeur à N entrées » consiste à aiguiller vers la sortie de la fonction une entrée parmi N. Le multiplexeur à 2 entrées est le multiplexeur le plus simple à concevoir. Son équation algébrique est de la forme :

où (E0 , E1 ) sont les entrées à multiplexer et A est une entrée de sélection.

La fonction multiplexeur est une traduction directe d’une instruction de type « if then else » dans le cadre de langages informatiques. Elle permet aussi de décomposer une fonction booléenne complexe en utilisant les théorèmes d’expansion.

Le multiplexeur à deux entrées est souvent symbolisé de la façon suivante :

Fi g. 2.3: | Multiplexeur à deux entrées (Mux2).

Le multiplexeur à 2N entrées nécessite N entrées de sélection pour distinguer les 2N configurations des entrées.

Nous allons tenter maintenant de construire un multiplexeur à 4 entrées à partir des portes de base définies dans le chapitre précédent. L’expression algébrique de la sortie est de la forme :

Cette formulation fait apparaître tous les mintermes possibles à partir des entrées de sélection (A0,A1). Le schéma de la Fig. 2.4 présente un multiplexeur à 4 entrées muni de plus une entrée supplémentaire V permettant de valider ou d’invalider (S = 0) la sortie de la fonction.

Fi g. 2.4: | Schéma interne d’un multiplexeur à 4 entrées avec entrée de validation.

Remarque : Il est possible de construire un multiplexeur à 4 entrées à partir de 3 multiplexeurs à 2 entrées. On se base pour cela sur la reformulation suivante, illustrée dans la Fig. 2.5.

Fi g. 2.5: | Reformulation du multiplexeur à 4 entrées.

#### 2.6.2 Opérateurs de comparaison

Les fonctions de comparaison les plus simples sont le test de l’égalité de deux variables booléennes ainsi que le test de complémentarité de deux variables booléennes. Ces deux fonctions ont pour équations algébriques respectives :

Ces fonctions étant très souvent utilisées, il a été jugé utile de définir un nouvel opérateur booléen pour les représenter. Il s’agit de l’opérateur « OU exclusif » que nous représenterons par le symbole suivant : .

Les relations précédentes deviennent :

Les tables de vérité et symboles associés à ces fonctions sont donnés dans les tableaux 2.19 et 2.20.

Ta b. 2.19: | Table de vérité et symbole des opérateurs XNOR

Ta b. 2.20: | Table de vérité et symbole des opérateurs XOR

Disposant du comparateur d’égalité à deux entrées, il est possible de généraliser l’opérateur à la comparaison de deux mots de N bits. L’exemple suivant montre un comparateur opérant sur 2 mots de 4 bits.

Nous disposons de 2 nombres codés sur 4 bits : et .

Alors A = B si et seulement si et et et , ce qui justifie le montage de la Fig. 2.6.

Fi g. 2.6: | Test d’égalité de deux mots de 4 bits.

### 2.7 Annexes

#### 2.7.1 Exercice de consolidation

L’expérience a montré que parmi les notions qui viennent d’être exposées, celle dans laquelle on se prend le plus fréquemment les « pieds dans le tapis » et qui par ailleurs sert le plus dans le cadre du module est la simplification des tables de Karnaugh. L’exercice suivant constitue en conséquence un petit entraînement qui pourrait s’avérer salutaire afin d’être au point sur ce sujet.

On désire réaliser un afficheur 7 segments (a,b,c,d,e,f,g, voir Fig. 2.7) traduisant un nombre binaire exprimé sur 4 bits A, B, C, D en un symbole hexadécimal (0,,9,A,b,C,d,E,F).

Fi g. 2.7: | Afficheur 7 segments. Un segment = une diode électro-luminescente.

La transcription de cette réalisation en tables de vérité si l’on considère que l’on travaille en logique positive (segment allumé = « 1 ») donne une table par segment.

Pour vous aider, il vous est proposé de vous donner directement le tableau de Karnaugh correspondant au segment « a » ainsi que le résultat obtenu après simplification.

Fi g. 2.8: | Tableau de Karnaugh de a = F(A,B,C,D).

Le résultat à trouver est :

Comment l’obtient-on ? Détaillons pour les sceptiques !

Regroupement : |
Regroupement : |
Regroupement : |
Regroupement : . Les extr émit és sont logiquement adjacentes ! |
Regroupement : |
Enfin, Regroupement : . |

L’équation du premier segment a est ainsi obtenue à l’aide des 6 regroupements précédents. A vous de les effectuer pour les autres segments…

Si vous arrivez au bout de cet exercice dans un temps raisonnable, vous pouvez considérer que vous ne rencontrerez pas beaucoup de problèmes dans le futur !

#### 2.7.2 Bibliographie

- Groupe numérique Polycopi é Composants et fonctions de l’électronique num érique, ENST
- Ronald Tocci « Digital Systems », Prentice Hall
- Eugene D. Fabricius, « Modern Digital Design and Switching Theory », CRC Press, 1992.
- Barry Wilkinson, « Digital System Design », Prentice Hall, 1992.

[Suivant] [Précédent] [Début] [Niveau supérieur]

Pour revenir au sommaire des supports du cours ENI.

Page maintenue par Jean Provost
Dernière modification:2 décembre 2004