Utilisateur:Regards sur sciences/agreg/leçons/19. Fonctions et circuits booléens en architecture des ordinateurs.

Modèle:Voir homonymes Il existe deux grands types de fonctions logiques :

• les fonctions logiques dites « combinatoires », bases du calcul booléen, elles résultent de l'analyse combinatoire des variations des grandeurs d'entrées uniquement
• les fonctions logiques dites « séquentielles » ou bascules, qui résultent de l'association de plusieurs fonctions logiques « combinatoires » dont les résultats ne dépendent pas seulement des données en train d'être traitées, mais aussi des données traitées précédemment.

Les fonctions logiques combinatoires directement issues des mathématiques (algèbre de Boole) sont les outils de base de l'électronique numérique. Elles sont mises en œuvre en électronique sous forme de portes logiques. Ainsi les circuits électroniques calculent des fonctions logiques de l'algèbre de Boole. Ces portes électroniques sont construites à partir de plusieurs transistors connectés de manière adéquate.

Dans d'autres applications, on peut trouver des portes logiques à base de relais, de fluides ou d'éléments optiques ou mécaniques. Selon la modélisation utilisée, on prendra en compte les temps de retard ou pas dans les calculs.

L'automatisme et l'informatique utilisent la logique combinatoire mais surtout la logique séquentielle.

Classification

Niveaux logiques

En algèbre de Boole, une donnée, qu'elle soit en entrée ou en sortie, n'a que deux niveaux possibles. Selon les applications, ces deux niveaux peuvent porter des noms différents : marche / arrêt, haut / bas, un (1) / zéro (0), vrai / faux, positif / négatif, positif / nul, circuit ouvert / circuit fermé, différence de potentiel / pas de différence, oui / non.

Dans le cas de circuits électroniques, les deux niveaux sont représentés par deux niveaux de tension, « haut » et « bas ». Chaque type de circuit possède ses propres niveaux de tension, pour s'assurer de la connectivité entre les entrées et sorties des circuits. Habituellement, deux niveaux bien distincts (ne risquant pas de se chevaucher) sont définis ; la différence entre les deux niveaux varie entre 0,7 V et 28 V (ce dernier dans le cas des relais).

Pour harmoniser la notation, ces deux niveaux seront notés ici 1 et 0.

Fonctions logiques élémentaires

Les portes peuvent être classées suivant leur nombre d'entrées :

• « portes » sans entrée : VRAI, FAUX ;
• portes à une entrée : NON (NOT), OUI ;
• portes à deux entrées : ET (AND), NON-ET (NAND), OU (OR), NON-OU (NOR), OU exclusif (XOR), Coïncidence (informatique) dite aussi NON-OU exclusif ou équivalence (XNOR), implication ;
• À partir de trois entrées, le nombre de fonctions commence à subir l'influence de l'explosion combinatoire. On note toutefois l'existence de : ET, OU, etc. à plus de deux entrées.

Il est possible de reconstituer les fonctions NON, ET et OU en utilisant uniquement soit la fonction NON-ET, soit la fonction NON-OU. On évoque cette caractéristique sous la notion d'universalité des opérateurs NON-OU et NON-ET (cf. le connecteur binaire d'incompatibilité, appelé aussi barre de Sheffer).

Lorsqu'on associe deux portes logiques compatibles, on peut connecter deux entrées ensemble, ou une entrée sur une sortie. Il ne faut en aucun cas connecter deux sorties différentes car elles peuvent produire des données différentes ; dans le cas de portes électroniques, cela équivaudrait à un court-circuit.

Représentation

Pour définir chacune des fonctions logiques, nous donnerons plusieurs représentations :

• une représentation algébrique : équation ;
• une représentation arithmétique : table de vérité ;
• une représentation graphique : symbole logique.

Dans le cas de portes électroniques, un niveau logique est représenté par un voltage défini (selon le type de composant utilisé). Chaque porte logique doit donc être alimentée pour délivrer la tension de sortie appropriée. Dans la représentation en symboles logiques, cette alimentation n'est pas représentée, mais elle doit l'être dans un schéma électronique complet.

La représentation d'un système combinatoire incluant plusieurs fonctions logiques peut aussi se faire grâce à un schéma à contact, une équation, une table de vérité et un schéma graphique. Dans ce dernier cas on parlera d'un logigramme.

Représentation graphique

Deux ensembles de symboles sont utilisés pour représenter les fonctions logiques ; les deux sont définis par la norme ANSI/IEEE 91-1984 et son supplément 91a-1991. La représentation par « symboles distinctifs », basée sur les schématisations classiques, est utilisée pour les schémas simples et est plus facile à tracer à la main. Elle est parfois qualifiée de « militaire », ce qui reflète ses origines, sinon son usage actuel.

La représentation « rectangulaire » se base sur la norme CEI 60617-12 ; toutes les portes y sont représentées avec des bords rectangulaires et un symbole, ce qui permet la représentation d'un plus grand nombre de types de circuits. Ce système a été repris par d'autres standards comme EN 60617-12:1999 en Europe et BS EN 60617-12:1999 au Royaume-Uni.

Symboles et tables de vérités de portes logiques

Type	Symbole américain	Symbole européen	Notation	Opération booléenne	Table de vérité	Diagramme de Venn
ET			$A\land B$	$A\cdot B$	Entrée Sortie A B A ET B 0 0 0 0 1 0 1 0 0 1 1 1
OU			$A\lor B$	$\textstyle A+B$	Entrée Sortie A B A OU B 0 0 0 0 1 1 1 0 1 1 1 1
NON			$\neg A$	${\overline {A}}$	Entrée Sortie A NON A 0 1 1 0
NON-ET (NAND)			$\neg (A\land B)$	${\overline {A\cdot B}}$	Entrée Sortie A B A NAND B 0 0 1 0 1 1 1 0 1 1 1 0
NON-OU (NOR)			$\neg (A\lor B)$	${\overline {A+B}}$	Entrée Sortie A B A NOR B 0 0 1 0 1 0 1 0 0 1 1 0
OU exclusif (XOR)			$A\oplus B$	$A\oplus B$	Entrée Sortie A B A XOR B 0 0 0 0 1 1 1 0 1 1 1 0
Coïncidence, NON-OU exclusif			$A\odot B$	$A\odot B$	Entrée Sortie A B A XNOR B 0 0 1 0 1 0 1 0 0 1 1 1
FAUX			$\perp$		Entrée Sortie A B FAUX 0 0 0 0 1 0 1 0 0 1 1 0

Une porte NON-ET (NAND) peut également être représentée en utilisant le symbole OU avec des bulles (inverseurs) sur les entrées, et une porte NON-OU (NOR) peut être représentée par un symbole ET avec des bulles sur les entrées. Cela reflète les lois d'équivalence de De Morgan ; cela permet de rendre également un diagramme plus lisible, ou de fabriquer un circuit facilement avec des portes préfabriquées, car un circuit qui a des bulles des deux côtés peut être remplacé par un circuit non-inversé en changeant la porte. Si une porte NON-ET est représentée par un OU avec des entrées inversées, ou qu'un NON-OU est représenté par un ET avec des entrées inversées, le remplacement se fait automatiquement dans le schéma (les bulles « s'annulent »). C'est courant dans les diagrammes logiques réels — si bien que le lecteur ne doit pas s'habituer à associer les symboles aux portes OU et ET automatiquement, mais doit aussi prendre en compte les inverseurs pour déterminer la bonne fonction représentée. Les entrées inversées sont particulièrement utiles dans le cas de signaux « actifs à l'état bas ».

Les deux autres portes fréquemment rencontrées sont la fonction OU exclusif et son inverse. Un OU exclusif à deux entrées ne renvoie un 1 que quand les deux entrées sont différentes, et un 0 quand elles sont égales, quelle que soit leur valeur. S'il y a plus de deux entrées, la porte renvoie 1 si le nombre d'entrées égales à 1 est impair. Dans la pratique, ces portes sont souvent réalisées à partir de combinaisons de portes logiques plus simples.

Convention d'écriture

La notation surlignée exprimant l'opérateur NON n'est pas facile à utiliser dans des systèmes informatiques. On la remplace souvent par la notation à l'aide d'une apostrophe « ' » et si nécessaire un parenthésage. Ainsi :

• NON(x) = x', d'où (x')' = x.
• NON·ET(x, y)= (x·y)' = x'+y'.
• NON·OU(x, y)= (x+y)' = x'·y'.
• NON·ET(NON·ET(a, b, c), NON·ET(d, f)) = ((a·b·c)')'+((d·f)')' = a·b·c + d·f.
• NON·OU(NON·OU(a, b, c), NON·OU(d, f)) = ((a+b+c)')'·((d+f)')' = (a+b+c)·(d+f)

Les opérateurs physiques NON·ET/NON·OU étant peu commodes dans les calculs, les deux dernières relations (dites de double couche) facilitent la liaison entre calcul et dessin ; ainsi :

• une double couche NON·ET réalise toute fonction donnée sous forme d'une somme de monômes booléens ;
• de même, une double couche NON·OU réalise toute fonction donnée sous forme d'un produit de clauses booléennes.

Autres fonctions logiques

Multiplexeurs

Pour aller plus loin, voir : Multiplexeur.

Soient 8 entrées binaires x0 à x7, et 3 entrées de commande a, b, c, permettant d'afficher un nombre de 0 à 7. Un multiplexeur aligne sa sortie s sur l'entrée dont le numéro est affiché. Pour cela, s = a'·b'·c'·x0 + a'·b'·c·x1 + a'·b·c'·x2 + a'·b·c·x3 +....+ a·b·c·x7.

Commande			Sortie
a	b	c	s
0	0	0	x0
0	0	1	x1
0	1	0	x2
0	1	1	x3
*	*	*	*
1	1	0	x6
1	1	1	x7

Additionneurs

Pour aller plus loin, voir : Additionneur.

C'est l'exemple type de cellules logiques, regroupements de fonctions des mêmes variables, utilisables comme briques ou boîtes noires dans des ensembles complexes.

simple

Soient a et b deux bits à additionner ; le résultat est un couple (r, s) tel que, arithmétiquement a + b = 2r + s. En termes booléens, r = a·b et s = $a\oplus b$.

complet

L'addition de deux bits a et b sera le plus souvent une addition intermédiaire recevant un report r. Le résultat est alors un couple (R, S) tel que, arithmétiquement, a+b+r = 2R+S. En termes booléens, S = $a\oplus b\oplus r$ et R = MAJ(a, b, r), où la porte MAJ(orité) a pour définition MAJ(x, y, z)= xy + yz + xz.

soustracteur

Un additionneur complet peut devenir additionneur/soustracteur en complément à un ou complément à deux s'il fait la somme des bits a, $b\oplus \$$ et r, où r est un report, et $ une commande valant 0 pour une addition et 1 pour une soustraction. Alors, le résultat est un couple (R, S) où S = $a\oplus b\oplus \$\oplus r$ et R = MAJ(a, $b\oplus \$$, r).

multiplicateur

Un additionneur complet peut devenir une cellule de multiplicateur s'il fait la somme des bits a, b·m et r, où a est un bit d'une somme partielle de produits, b un bit du multiplicande, m un bit du multiplicateur, et r un report. Alors S = $a\oplus b$·$m\oplus r$ et R = MAJ(a, b·m, r).

Unités de stockage

Au-delà des fonctions logiques purement combinatoires, se pose le problème du stockage d'un bit d'information. Les portes logiques présentées plus haut ne stockent pas de données : quand une entrée change, la sortie réagit immédiatement (au temps de propagation près). Il est possible de créer des éléments de stockage soit avec des condensateurs, soit en utilisant le feedback. En connectant la sortie d'une porte à son entrée, on renvoie la sortie dans le circuit logique ; elle peut ainsi être conservée ou modifiée en utilisant les autres entrées. En connectant des portes de cette manière, on crée un verrou (latch en anglais). D'autres circuits un peu plus complexes utilisent des signaux d'horloge (des signaux qui oscillent à une fréquence connue) et changent quand le signal d'horloge passe à 1 ; on les appelle des bascules ou bistables (flip-flops en anglais). En combinant plusieurs bascules en parallèle pour stocker une valeur de plusieurs bits, on crée un registre.

Les registres et autres circuits de stockage sont regroupés sous le terme de « mémoires électroniques ». Leurs performances varient en termes de vitesse, de complexité et de fiabilité de la mémoire. Leurs types peuvent être très différents selon les applications.

Automates à nombre fini d'états

Ils comprennent :

• un ensemble défini E de variables d'entrée,
• un ensemble défini I de variables d'état internes, stockées dans un registre,
• un ensemble défini S de variables de sortie,
• un réseau combinatoire T : (E, I) → I assurant l'évolution de l'automate en fonction des entrées successives,
• un réseau combinatoire R : (E, I) → S assurant la définition de la sortie, conformément aux entrées actuelles, et à la mémoire que I a gardé des situations antérieures.

Dès lors que toutes les variables se présentent sous forme binaire, ils sont réalisables à l'aide de circuits logiques.

Ils peuvent être simples, ou fédérés en automates plus complexes.

Unités fonctionnelles

Les circuits logiques peuvent également réaliser des éléments comme des multiplexeurs, des unités arithmétiques et logiques (en anglais : Arithmetic and Logic Unit ou ALU), des mémoires, ou les automates animant un processeur. Les microprocesseurs rassemblent de tels éléments, et peuvent contenir plus de 100 millions de portes logiques.

Les composants de microprocesseurs sont à base de transistors à effet de champ, en particulier des MOSFET.

Voir aussi

Articles connexes

• Bascule
• Algèbre de Boole (logique)
• Sortance
• Table de Karnaugh
• Logique pneumatique

Bibliographie

• Jean Kuntzmann, Algèbre de Boole, Dunod, 1965 ,PPN 004867440