L'algèbre de Boole et les portes logiques
Partie 2 sur 4
4Le chronogramme : le temps en plus
Une table de vérité décrit ce que fait une porte, mais elle ignore le temps. Or un circuit réel vit dans le temps : ses entrées changent, ses sorties réagissent. Le chronogramme est un diagramme qui montre l’évolution des entrées et des sorties en fonction du temps. On y dessine, l’un sous l’autre, les signaux A, B et S : chacun est une ligne qui passe de bas (0) à haut (1) et inversement. Pour une porte ET, on voit la sortie S monter à 1 uniquement pendant les intervalles où A et B sont tous deux à 1.
4.1Le chronogramme idéal
Le chronogramme classique est un chronogramme idéal : les transitions de 0 à 1 y sont verticales et la sortie réagit instantanément. Il est parfait pour comprendre la logique d’un circuit, et c’est ainsi qu’on le dessine la plupart du temps.
4.2Le chronogramme réel
En réalité, les signaux électriques ne passent pas instantanément de 0 à 1 : les pentes (verticales sur le schéma idéal) sont obliques, car il faut un temps pour charger les petites capacités électriques du circuit. Et le traitement des entrées cause un retard sur les sorties : le temps de propagation de la porte. Ce retard, de l’ordre de quelques dizaines de picosecondes (millièmes de milliardième de seconde) dans les circuits actuels, a une conséquence énorme : plus un circuit enchaîne de portes, plus la sortie est tardive. C’est ce qui limite la vitesse d’un processeur. Sa fréquence (le nombre de cycles par seconde, mesuré en gigahertz) est fixée pour que le chemin le plus long, de portes en portes, ait le temps de se stabiliser avant le cycle suivant.
On touche ici à une raison pratique de simplifier les formules : moins de portes en chaîne, c’est un circuit plus rapide, plus petit, moins gourmand en énergie. Les lois de la partie 7 ne sont pas un jeu d’écriture, elles ont des conséquences concrètes.
4.3Les aléas
Un effet plus subtil existe : si deux chemins de longueurs différentes aboutissent à une même porte, la sortie peut afficher brièvement une valeur fausse, avant de se stabiliser, comme un feu qui passe un instant au vert au mauvais moment. Les ingénieurs appellent cela un aléa (en anglais glitch). On s’en protège en lisant la sortie seulement à des instants précis, cadencés par une horloge, après que tout s’est stabilisé. C’est l’origine de la distinction entre circuits « combinatoires » (partie 8) et circuits « séquentiels ».
5Les expressions algébriques
Le but de l’algèbre de Boole est de décrire le traitement de signaux sous forme d’expression algébrique. Les signaux y sont représentés par des noms de variables, les fonctions logiques par des opérateurs. Voici la notation usuelle :
- la fonction OU est représentée par un plus : A + B ;
- la fonction ET est représentée par un point : A . B (ou simplement AB, comme en algèbre où l’on écrit 2x) ;
- la fonction NON est représentée par une barre au-dessus de la variable inversée ; elle est parfois représentée par un / devant la variable : /A (c’est la notation utilisée dans cet article, parce qu’elle s’écrit au clavier) ;
- la fonction OU EXCLUSIF est représentée par un plus encerclé : A ⊕ B.
Une expression algébrique sera donc une expression du type : (A + B) . /C, qui se lit « (A ou B) et non C ». Comme en arithmétique, le point (ET) est prioritaire sur le plus (OU) : A + B . C signifie A + (B . C), et les parenthèses lèvent toute ambiguïté.
5.1Évaluer une expression
Pour évaluer une expression, on remplace les variables par leurs valeurs et on calcule de l’intérieur vers l’extérieur. Exemple : (A + B) . /C avec A = 0, B = 1, C = 0. On calcule A + B = 0 + 1 = 1 ; puis /C = 1 ; puis 1 . 1 = 1. La sortie vaut donc 1. Avec A = 0, B = 0, C = 0 : A + B = 0, donc le produit est 0 quel que soit /C.
5.2Les mots du langage courant
Traduire une phrase en expression est un excellent exercice. « La porte s’ouvre si le badge est valide et qu’il est entre 8 h et 18 h, ou si le gardien appuie sur le bouton » devient : (B . H) + G. Le même raisonnement sert à écrire une condition dans un programme, un filtre de messagerie ou une recherche : les moteurs de recherche, les logiciels de messagerie et les langages de requête (voir le SQL) offrent tous des opérateurs ET, OU et NON qui obéissent exactement à ces règles.
Un piège de la langue : « ou » a deux sens en français (inclusif et exclusif), « et » peut vouloir dire « puis ». La logique de Boole tranche : OU est toujours inclusif ; si l’on veut l’exclusif, on écrit XOR.
Pour s’exercer
Exercice 2 : évaluer une expression
Calculez S = (A + /B) . C pour A = 0, B = 1, C = 1, puis pour A = 1, B = 1, C = 0.
Voir la réponse
Premier cas : /B = 0 ; A + /B = 0 + 0 = 0 ; S = 0 . 1 = 0. Second cas : /B = 0 ; A + /B = 1 + 0 = 1 ; S = 1 . 0 = 0. Dans les deux cas, S vaut 0. (S vaut 1 seulement quand C = 1 et que A vaut 1 ou B vaut 0.)
6De la table de vérité à l’expression
Il est possible, à partir de la table de vérité d’une fonction, d’écrire l’expression algébrique de celle-ci. La méthode est mécanique : on regarde les lignes où la sortie vaut 1, on écrit pour chacune un produit (ET) qui « reconnaît » exactement cette ligne, et on additionne (OU) ces produits.
6.1Un premier exemple, à deux entrées
Soit la table suivante :
| A | B | S |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
La sortie vaut 1 lorsque A vaut 1 et B vaut 0. On écrit donc : S = A . /B (A et non B).
6.2Un deuxième exemple, à trois entrées
Prenons maintenant une fonction de trois variables :
| A | B | C | S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
La sortie vaut 1 dans deux cas : lorsque A vaut 0, B vaut 1 et C vaut 0 ; ou lorsque A vaut 1, B vaut 1 et C vaut 0. L’expression algébrique est donc : S = /A . B . /C + A . B . /C.
Cette formule est correcte, mais on peut la simplifier. Les deux termes ont en commun B . /C ; on le met en facteur : S = B . /C . (/A + A). Or /A + A vaut toujours 1 (une variable ou son contraire : l’un des deux vaut forcément 1), donc S = B . /C. Cette fonction, qui avait l’air de dépendre de trois variables, ne dépend en fait que de deux : A ne change rien. Voilà ce que font les lois de composition de la partie suivante.
6.3La méthode en trois temps
Pour écrire la formule d’une fonction à partir de sa table : (1) repérer les lignes où S vaut 1 ; (2) pour chaque ligne, écrire le produit des variables, en barrant (en faisant précéder d’un « / ») celles qui valent 0 sur cette ligne ; (3) faire la somme de ces produits ; puis (4) simplifier. On obtient toujours une formule exacte, même si elle est longue. Cette méthode s’appelle la forme normale disjonctive (somme de produits) ; c’est la formule « brute » dont part tout concepteur de circuit.
Pour s’exercer
Exercice 3 : de la table à la formule
S vaut 1 pour (A, B, C) = (1, 0, 1) et (1, 1, 1), et 0 ailleurs. Écrivez l’expression, puis simplifiez-la.
Voir la réponse
S = A . /B . C + A . B . C. On met A.C en facteur : S = A.C.(/B + B) = A.C.1 = A.C. La fonction ne dépend pas de B : S vaut 1 si, et seulement si, A et C valent 1.