Circuits Logiques

Michel Billaud

2000

1 Eléments de Technologie

Nous avons vu comment coder l’information par des suites de valeurs binaires. Nous allons voir maintenant comment représenter ces valeurs binaires par des signaux électriques afin de les manipuler par des circuits électroniques.

1.1 Représentations de la logique binaire

1.1.1 Représentation des signaux

Il existe plusieurs façons de coder les valeurs 0 et 1. La plus simple, que nous adopterons dans la suite, est appelée logique positive et consiste à représenter 1 par la présence d’une tension (par exemple +5v) et 0 par une tension nulle.1

1.1.2 Génération d’un signal

Il est facile de fournir de tels signaux à un circuit: il suffit d’un interrupteur à deux positions (utilisé pour les va-et-vient); dans une position la sortie de l’interrupteur transmettra la tension +V, dans l’autre 0v (voir figure [fig1])

Génération d’un signal d’entrée
Génération d’un signal d’entrée

En pratique, on utilise plutôt (figure [fig2]) un interrupteur simple dont la sortie est reliée à une résistance de rappel R assez forte. Lorsque l’interrupteur est fermé (il fat contact) la sortie est à +V, lorsqu’il est ouvert la résistance ramène la tension de sortie vers 0. De plus ceci évite d’avoir une entrée “en l’air” quand l’interrupteur est entre deux positions.

Génération d’un signal d’entrée (2)
Génération d’un signal d’entrée (2)

1.1.3 Observation d’un signal

Pour observer la sortie d’un circuit on peut utiliser (figure [ampoule]) une ampoule du voltage voulu (5v = lampe de poche).

Ampoule témoin
Ampoule témoin

On préfèrera généralement employer des diodes électro-luminescentes (LED = Light Emitting Diode), qui coûtent moins cher et nécessitent un courant moindre (voir figure [temoin-led]). 0

LED témoin
LED témoin

Encore mieux, pour éviter de trop “tirer” sur la sortie du circuit observé, on pourra utiliser un transistor en amplification (voir plus loin [trans-ampli]).

1.2 Notions rudimentaires d’électronique

Quelques notions sommaires d’électronique sont nécessaires pour la compréhension des circuits logiques de base. Le lecteur est supposé connaître la loi d’Ohm et des rudiments d’électricité.

1.2.1 La diode

La diode à semi-conducteurs est un composant électronique muni de deux bornes: l’anode et la cathode (voir [diode]).

La diode: apparence physique et symbole
La diode: apparence physique et symbole

La propriété fondamentale de la diode est d’opposer qu’une résistance très faible lorsqu’elle est traversée par un courant de l’anode vers la cathode (sens passant), et une résistance très forte dans le sens inverse. Voir figure [diode-on-off].

Diodes passante (D1) et bloquée (D2)
Diodes passante (D1) et bloquée (D2)

Pour analyser les circuits logiques nous considérerons que les diodes sont parfaites, c’est-à-dire ayant une résistance nulle dans l’état passant, et infinie dans l’état bloqué.

Remarque importante. Lorsque nous construirons des circuits nous aurons soin d’éviter de faire traverser les diodes par des courants trop forts (risque de claquage). Il faudra donc de les monter en série avec des résistances pour limiter le courant.

1.2.2 La diode électro-luminescente

Les diodes électro-luminescentes (LED = Light Emitting Diod, voir fig. [fig9]) émettent de la lumière quand elles sont traversées par un courant de l’ordre de 10 à 20 mA dans le sens passant. Ces diodes offrant une résistance très faible, il conviendra de les monter en série avec une résistance limitatrice de courant d’une valeur suffisante (R = U/I = 5v/10mA = 500Ω).

LED: apparence physique et schéma
LED: apparence physique et schéma

1.2.3 Le transistor

Le transistor2 est un composant à 3 pattes: l’émetteur, le collecteur et la base (voir figure [transistor]).

Transistor NPN: boitier, broches (vues de dessous), schéma
Transistor NPN: boitier, broches (vues de dessous), schéma

Dans les montages usuels, le collecteur est relié à la tension d’alimentation  + V au travers d’une résistance Rc, l’émetteur étant relié à la masse (0v). Le courant Ib qui traverse la base permet de contrôler l’intensité de celui qui traverse l’émetteur et le collecteur.

Polarisation d’un transistor
Polarisation d’un transistor

Lorsque le transistor est utilisé en amplification, les courants sont liés par les équations

Les deux constantes β et Ice dépendent du transistor: le gain β est de l’ordre de 100, le courant Ice vaut quelques micro-ampères pour les transistors au silicium, et quelques nano-ampères pour les transistors au germanium. En général on le néglige pour les calculs.

Les montages logiques utilisent le mode de fonctionnement bloqué-saturé, en débordant largement de la plage de valeurs où les formules ci-dessus sont valides: si on applique une tension assez forte (proche de +V) à la base, l’intensité Ib est maximum et le transistor n’oppose qu’une résistance très faible entre émetteur et collecteur: le transistor est saturé. Si on applique une tension nulle à la base, le courant Ic sera négligeable : le transistor est alors dit bloqué.

[trans-ampli]

LED amplifiée par un transistor
LED amplifiée par un transistor

Ceci justifie le montage de la figure [ampli-diode] : lorsque l’entrée est à +V, le transistor est saturé, donc il laisse passer le courant à travers la LED qui s’éclaire. Lorsque l’entrée est au niveau bas (0v), le transistor est bloqué et la LED reste éteinte. En raison des propriétés amplificatrices du transistor, le courant de base n’a pas besoin d’être très élevé (de l’ordre de Ic/β), par conséquent on peut mettre une résistance limitatrice sur la base. Cette résistance évite de trop “tirer de courant” du signal que l’on observe, ce qui risquerait de perturber son fonctionnement.

1.3 Portes logiques

En assemblant ces composants on obtient des portes logiques qui combinent les signaux.

1.3.1 Porte OU

1.3.1.1 Montage à diodes

Deux diodes et une résistance suffisent pour réaliser une porte OU selon le schéma de la figure [porte-ou].

Porte logique OU à diodes
Porte logique OU à diodes

1.3.1.2 Analyse du montage

Supposons que les deux entrées A et B soient portées au potentiel +V. Les deux diodes sont dans le sens passant, et laissent donc passer le courant. Tout se passe alors comme si la sortie S était reliée à la même tension +V.

Si A et B sont reliées à la masse (0v), les diodes ne conduisent pas le courant. La sortie S est donc ramené à 0v par la résistance de rappel.

Si une des entrées est à +V et l’autre à la masse, la diode passante suffit, comme dans le premier cas, à amener la tension +V sur S.

1.3.1.3 Table de vérité

Si nous prenons la convention de logique positive, la tension +V correspond à la valeur logique “vrai” (notée 1) et 0v à “faux” (0). La table de vérité de l’opération “+” ainsi obtenue est celle de l’opérateur “OU logique”:
$$\begin{array}{|cc|c|} \hline A & B & A+B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \\ \hline \end{array}$$

La sortie est à 1 si au moins une des entrées est à 1.

1.3.1.4 Porte OU multiple

En reliant plusieurs entrées de la même façon on obtient une porte OU multiple. Son fonctionnement se résume en une phrase: la sortie est à 1 si au moins une des entrées est à 1.

Dans les schémas logiques, on représente les portes logiques par un symbole (figure [log2])

Symboles des portes OU
Symboles des portes OU

1.3.1.5 Montage à transistors

Le montage de la figure [log8] remplit la même fonction. L’analyse en est laissée au lecteur.

Porte OU à transistors en parallèle
Porte OU à transistors en parallèle

1.3.2 Porte ET

1.3.2.1 Montage à diodes

Le schéma (figure [log3]) n’est pas sans rappeler celui de la porte OU.

Porte ET à diodes
Porte ET à diodes

1.3.2.2 Analyse du montage

Chaque diode ne peut être passante que si l’entrée associée est à 0. Si une des entrées est à 0, la sortie sera donc également à 0. Par contre si les deux entrées sont à +V, la sortie S sera à +V au travers de la résistance de rappel.

1.3.2.3 Table de vérité

L’opération logique “ET” (noté “”) correspondant à ce montage possède donc la table de vérité suivante:
$$\begin{array}{|cc|c|} \hline A & B & A \cdot B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \hline \end{array}$$

La sortie est à 1 si les deux entrées sont à 1.

On représente les portes ET (à deux ou plusieurs entrées) par un symbole (figure [log4])

Symboles des portes ET
Symboles des portes ET

1.3.2.4 Montage à transistors

Le montage de la figure [log7] remplit la même fonction. L’analyse en est laissée au lecteur.

Porte ET à transistors en série
Porte ET à transistors en série

1.3.3 Porte NON

1.3.3.1 Montage

Dans la figure [log5] on utilise un transistor en mode bloqué/saturé.

Porte NON à transistor
Porte NON à transistor

1.3.3.2 Analyse du montage

Lorsque l’entrée est au niveau haut, le transistor est saturé. La sortie est alors reliée à la masse par l’intermédiaire de la résistance interne très faible du transistor : la sortie S est au niveau bas.

Lorsque l’entrée est au niveau bas, le transistor est bloqué. La résistance de rappel ramène donc la sortie au niveau haut.

1.3.3.3 Table de vérité

La table de l’opérateur NON “¬” ainsi obtenu est
$$\begin{array}{|c|c|} \hline A & \neg A \\ \hline 0& 1 \\ 1& 0 \\ \hline \end{array}$$
La sortie est à 1 si et seulement si l’entrée est à 0.

On symbolise cet opérateur (figure [log10]) par un triangle (indiquant par convention l’amplification) suivi d’un rond (négation).

Symbole de la Porte NON
Symbole de la Porte NON

1.3.4 Porte NON-ET (NAND)

Porte NAND
Porte NAND

Le montage de la figure [log9] réalise une fonction dont la table de vérité est:
$$\begin{array}{|cc|c|} \hline A & B & S\\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \hline \end{array}$$

On remarque aisément que l’on a $S = \overline{A.B}$, et on appelle cet opérateur le NON-ET (ou “nand”).

Exercice Donnez un schéma de cet opérateur utilisant 2 diodes, une résistance et un transistor.

On le représente par un symbole “ET” suivi du rond qui indique la négation (figure [log11]).

Porte NON-ET
Porte NON-ET

La porte NAND a un intérêt pratique évident: elle permet de reconstituer tous les autres types de portes.

1.3.5 Porte NON-OU (NOR)

La fonction “non-ou” (symbolisée fig. [log14]) est définie de la même façon, par l’équation
$$nor(A,B) = \overline{A + B}$$

Symbole de la porte NOR (non-ou)
Symbole de la porte NOR (non-ou)

Exercice Proposez une porte NOR à transistors.

1.3.6 Porte OU-exclusif (XOR)

La fonction XOR “ou-exclusif” (fig. [log15]) est souvent notée . On la définit par:
$$A \oplus B = \overline{A}B +A\overline{B}$$

Symbole de la porte XOR (ou-exclusif)
Symbole de la porte XOR (ou-exclusif)

Exercice Proposez une porte XOR à transistors.

1.3.7 Le circuit intégré CMOS 4011

Les circuits intégrés logiques sont des boîtiers qui renferment plusieurs portes logiques inter-connectées. Il existe une grande quantité de circuits intégrés logiques, renfermant des portes ET, OU, NAND, etc. Pour des petits montages, il est économique d’utiliser un seul type de circuit, comme le circuit CMOS 4011, qui contient 4 portes NAND.

1.3.7.1 Brochage

Le circuit 4011 se présente sous forme d’un boîtier DIL (Dual in line) à 14 broches (voir figure [log12]). Une encoche sur le côté gauche permet de reconnaître le sens du circuit.

Circuit CMOS 4011 vu de dessus
Circuit CMOS 4011 vu de dessus

Les broches 14 (en haut à gauche) et 7 (en bas à droite) servent à l’alimentation du circuit (14: +V, 7: masse). Les autres sont les entrées et sorties des 4 portes NAND:

La figure [log13] montre comment réaliser une porte OU avec ce circuit.

Porte OU avec CMOS 4011
Porte OU avec CMOS 4011

Exercice Fonctions binaires usuelles Montrez comment réaliser les expressions A.B, A ⊕ B, $A+\overline{B}$ à l’aide d’un circuit 4011.

Exercice Fonction majorité Réalisez la fonction maj(A, B, C), dont le résultat est 1 si au moins deux entrées sont à 1, à l’aide d’un circuit 4011 (ou plusieurs).

Exercice Réalisez la fonction $f(A,B,C)= $.

1.3.7.2 Conditions d’emploi des circuits CMOS

Les circuits de type CMOS présentent certains avantages pour les montages expérimentaux:

Par contre, ces circuit sont sensibles à l’électricité statique3. De plus, la propagation des signaux de l’entrée à la sortie d’une porte est plus lente (20-40 ns) qu’avec d’autres familles de circuits, comme les TTL.

1.3.7.3 Emploi des circuits TTL

Les circuits TTL (transistor-transistor-logic) sont très utilisés pour les réalisations professionnelles. A titre d’exemple, les caractéristiques de la série SN74 sont:

2 Algèbre de Boole et circuits logiques

En combinant les portes logiques, et en prenant garde de ne pas faire de boucles dans les circuits4, on réalise des circuits dont les sorties ne dépendent que des valeurs des entrées. On pourra alors décrire la fonction réalisée par ce circuit par sa table de vérité.

L’étude des “tables de vérité” a été entreprise il y a plus d’un siècle, et constitue ce qu’on appelle l’algèbre de Boole5.

Les propriétés de cette algèbre nous permettront de raisonner sur les circuits, et donc de les construire rigoureusement, plutôt que par la (coûteuse) méthode des essais et erreurs. En particulier nous verrons des méthodes systématiques pour simplifier les circuits.

2.1 Définitions

On appelle fonction booléenne toute fonction de {0, 1}n dans {0, 1}.

Il y a 22n fonctions booléennes à n variables: en effet pour décrire une fonction booléenne à n variables il suffit de remplir les 2n cases de sa table de vérité, chaque case pouvant contenir 0 ou 1.

Une expression booléenne est un terme construit à partir de variables (prises dans un ensemble V), de constantes 0 ou 1, et d’opérateurs ET, OU, et NON. Exemple : $a + \overline{a . \overline{b}} + b$.

Une expression booléenne représente une fonction booléenne ; nous dirons que deux expressions sont équivalentes si elles dénotent la même fonction.

Exemple Si nous construisons la table de vérité de l’expression ci-dessus, et de l’expression $\overline{a}+b$:
$$\begin{array}{|cc|ccc||c||c||c|} \hline a &b & \overline{b}& a.\overline{b}& \overline{a.\overline{b}} & \overline{a.\overline{b}} + b & \overline{a} & \overline{a}+b \\ \hline 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1\\ \hline \end{array}$$
nous constatons qu’elles coïncident : les deux expressions représentent la même fonction.

Par commodité, on appelle somme toute expression de la forme t1 + t2 + … + tn. Elle peut se réduire à un seul terme, ou aucun (dans ce cas c’est 0). Un produit est de la forme t1.t2tn. Le produit vide est 1.

Un monôme est un produit de variables ou de négations de variables, chaque variable n’apparaissant qu’au plus une fois.

Exemple de monômes: $x, \overline{y}, x.\overline{y}.z, 1$

Remarque À partir d’un ensemble de n variables on peut construire Cnk.2k monômes distincts à k variables : pour choisir un tel monôme il suffit de sélectionner k variables parmi n (d’où le coefficient binomial), et d’attribuer ou non à chacune d’entre elles une barre (2k possibilités).

Il y a en tout 3n monômes, puisqu’il suffit de décider, pour chacune des variables, de la faire figurer telle quelle, avec une barre, ou pas du tout. Ceci prouve l’égalité:
$$\sum_{k=0}^n C^k_n.2^k = 3^n$$
que l’on peut d’ailleurs retrouver en développant (1 + 2)n à l’aide des formules connues.

Un monôme est complet par rapport à un ensemble donné de variables si toutes les variables de cet ensemble apparaissent une fois. Il y a 2n monômes complets sur un ensemble de n variables, chaque monôme complet correspondant à une des cases d’une table de vérité à n variables.

Une expression est en forme canonique si elle est écrite sous forme d’une somme sans répétition de monômes complets.

2.1.0.0.1 Proposition

Toute fonction booléenne peut être construite par composition d’opérations OU, ET et NON.

2.1.0.0.2 Preuve

Toute fonction booléenne f(a, b, c…) peut être décrite par sa table de vérité. Chaque case de cette table correspond à un monôme complet. Une expression de la fonction f s’obtient en faisant la somme des monômes complets dont la valeur est 1.

Exemple Considérons une fonction maj (majorité) à trois variables a, b, c, qui vaut 1 quand au moins deux des entrées sont à un. On dresse la table de vérité de maj, en faisant figurer dans la marge les monômes correspondants:
$$\begin{array}{|ccc|c|l} \cline{1-4} a & b & c & maj(a,b,c) & \mbox{mon\^ome} \\ \cline{1-4} 0 & 0 & 0 & 0 & \overline{a}\overline{b}\overline{c} \\ 0 & 0 & 1 & 0 & \overline{a}\overline{b}c \\ 0 & 1 & 0 & 0 & \overline{a}b\overline{c} \\ 0 & 1 & 1 & 1 & \overline{a}bc \\ 1 & 0 & 0 & 0 & a\overline{b}\overline{c} \\ 1 & 0 & 1 & 1 & a\overline{b}c \\ 1 & 1 & 0 & 1 & ab\overline{c} \\ 1 & 1 & 1 & 1 & abc \\ \cline{1-4} \end{array}$$
et on obtient l’expression en forme canonique
$$maj(a,b,c)= \overline{a}bc + a\overline{b}c + ab\overline{c} + abc$$

2.2 Propriétés des algèbres de Boole

Les operations ET, OU, NON définies sur l’ensemble {0, 1} possèdent les propriétés suivantes:
$$\begin{array}{rclrcll} \overline{\overline{A}} &=& A& && & \mbox{double négation} \\ \overline{0} &=& 1 & \overline{1} &=& 0 & \mbox{constantes} \\ \overline{A+B} &=& \overline{A}.\overline{B} & \overline{A.B} &=& \overline{A}+\overline{B} & \mbox{dualité} \\ (A+B)+C &=& A+(B+C) & (AB)C &=& A(BC) & \mbox{associativité} \\ A+B &=& B+A & AB &=& BA & \mbox{commutativité} \\ (A+B)C &=& AC+BC & AB+C &=& (A+C)(B+C) & \mbox{distributivité} \\ A+A &=& A & AA &=& A & \mbox{idempotence} \\ A+0 &=& A & A.1 &=& A & \mbox{éléments neutres} \\ A+1 &=& 1 & A.0 &=& 0 & \mbox{absorption} \\ A+\overline{A} &=& 1 & A.\overline{A} &=& 0 & \mbox{complémentaires} \\ \end{array}$$

2.2.0.0.1 Remarques

2.2.0.1 Algèbre de Boole

On appelle algèbre de Boole tout ensemble qui possède deux éléments 0 et 1 et des opérations +,⋅,¬ qui satisfont les équations ci-dessus.

Exercice Montrez qu’il n’y a pas d’algèbre de Boole à 3 éléments {0, 1, 2}. (Indication : que vaut $\overline{2}$ ?).

On voit facilement que le produit A × B de deux algèbres de Boole est également une algèbre de Boole. Les opérations sur le produit sont définies par $\overline(a,b)=(\overline{a},\overline{b})$, (a, b) + (a′, b′) = (a + a′, b + b′), (a, b).(a′, b′) = (a.a′, b.b′).

Dans le sens inverse, un résultat mathématique (théorème de Stone) dit que toute algèbre de Boole se ramène en fait à un produit d’algèbres de Boole à 2 éléments7.

2.3 Simplification des expressions

À partir d’une expression booléenne, on pourra facilement fabriquer un circuit. Pour réaliser une même fonction, on aura tout intérêt à avoir des circuits qui utilisent le moins possible de portes logiques, pour des raisons de simplicité, de coût, de taille du circuit et de consommation de courant.

On peut essayer de simplifier les circuits en utilisant les équations vues plus haut. Par exemple, pour la fonction maj :
$$\begin{array}{rcll} maj(a,b,c)&=& \overline{a}bc + a\overline{b}c + ab\overline{c} + abc \\ &=& \overline{a}bc + a\overline{b}c + ab\overline{c} + abc + abc + abc & \mbox{(idempotence)} \\ &=& \overline{a}bc + abc + a\overline{b}c +abc + ab\overline{c} + abc & \mbox{(commutativité)} \\ &=& (\overline{a}+a)bc + a(\overline{b}+b)c + ab(\overline{c}+c) & \mbox{(distributivité)} \\ &=& 1.bc + a.1.c + ab.1 & \mbox{(complémentarité)} \\ &=& bc + ac + ab & \mbox{(éléments neutres)} \end{array}$$

Mais la difficulté est alors de mener le calcul vers une expression simple que l’on ne connaît pas a priori.

Problème Donnez une expression aussi simple que possible de chacune des 222 = 16 fonctions à deux variables.

Déterminez celles qui sont croissantes, c’est à dire telles que x ≤ x et y ≤ y entraîne f(x, y) ≤ f(x′, y′). Pour chacune d’elles montrez qu’elle peut s’exprimer (sans utiliser de négation) par une somme de produits de variables.

Réciproquement, montrez que toute fonction dont l’expression contient des ET et des OU mais pas de NON est nécessairement croissante.

Généralisez au cas des fonctions ayant un nombre quelconque de variables.

2.4 Méthode de Karnaugh

La méthode de Karnaugh est une méthode visuelle pour trouver une expression simple d’une fonction booléenne de quelques variables (jusqu’à 6).8.

Elle repose sur une présentation particulière de la table de vérité de la fonction étudiée. Voici la disposition adoptée pour les fonctions de 3 et 4 variables:


$$\begin{array}{|r|cc|} \cline{1-3} ab\ c& 0 & 1 \\ \cline{1-3} 00 & & \\ 01 & & \\ 11 & & \\ 10 & & \\ \cline{1-3} \end{array} \hspace{.5in} \begin{array}{|r|cccc|} \cline{1-5} ab\ cd& 00 & 01 & 11 & 10 \\ \cline{1-5} 00 & & &&\\ 01 & & &&\\ 11 & & &&\\ 10 & & &&\\ \cline{1-5} \end{array}$$

On remarque que dans ces tables, deux cases adjacentes ne diffèrent que le changement de valeur d’une seule variable. Comme chaque case correspond à un monôme complet, un groupement de 2 cases adjacentes représentera un monôme à n − 1 variables.

Exemple Les deux cases du bas de la première table correspondent respectivement à $a\overline{b}\overline{c}$ et $a\overline{b}c$, qui diffèrent par la variable c. En les regroupant on obtient $a\overline{b}\overline{c} + a\overline{b}c = a\overline{b}(\overline{c}+c) = a\overline{b}$

Attention : il faut également considérer les bords opposés comme étant adjacents, par exemple les cases $\overline{a}\overline{b}\overline{c}$ (en haut à gauche) et $a\overline{b}\overline{c}$ (en bas à gauche) se regroupent en $b\overline{c}$.

Les monômes à n − 2 variables sont visualisés sous forme de carrés, ou de rectangles 1 × 4.

Exemple On a $bd = (a + \overline{a})b(c +\overline{c})d$. En développant cette expression on trouve une somme de 4 monômes complets qui occupent le milieu de la seconde table. Les 4 coins de cette même table forment (virtuellement) un carré dont l’expression est $\overline{a}\overline{d}$. La colonne de droite correspond à $c\overline{d}$, etc.

De même les produits de n − 3 variables occupent 8 cases disposées en rectangles 2 × 4.

La méthode de Karnaugh consiste à écrire la table de vérité de la fonction dans la table, puis procéder à des regroupements que l’on entoure et dont on écrit l’expression au fur et à mesure.

2.4.0.0.1 Algorithme

L’algorithme est le suivant:

La figure [boole1] illustre le déroulement possible de la méthode sur l’exemple de la fonction majorité. Le résultat obtenu est BC + AB + AC.

Méthode de Karnaugh : exemple
Méthode de Karnaugh : exemple

Exercice Le vote Une commission est composé d’un président P et trois membres A,B,C. Cette commission doit se prononcer sur un vote par oui ou non à la majorité. Personne ne peut s’abstenir. En cas d’égalité entre les oui et les non, la voix du président est prépondérante. En utilisant la méthode de Karnaugh, donnez une expression simple de la fonction vote(A, B, C, P).

Exercice Décodage 7 segments hexadécimal Un afficheur 7 segments est composé de 7 diodes électro-luminescentes notés a,b,…g (voir figure [boole2]). Un nombre est fourni, codé en binaire sur 4 bits x3x2x1x0, qui devra être affiché. Donnez l’expression des 7 fonctions a(x3, x2, x1, x0), b(x3, x2, x1, x0), …

Afficheur 7 segments, chiffres
Afficheur 7 segments, chiffres

La méthode de Karnaugh est également applicable dans le cas des fonctions incomplètement spécifiées, c’est-à-dire qui ont des “cases vides” dans lesquelles on peut mettre ce que l’on veut, parce que cela correspond à des situations qui ne peuvent pas se produire.

La méthode est alors la suivante: former les plus gros paquets possibles contenant au moins un 1 non entouré et aucun 0.

Exercice Le dé électronique (fig. [boole3]) possède trois entrées, par lesquelles arrivent des nombres de 1 à 6 codés en binaire. Donnez une fonction pour chacune des lampes qui indiquera si elle doit être allumée ou éteinte.

Le dé électronique
Le dé électronique

Exercice Décodage 7 segments décimal Reprendre l’exercice de l’afficheur 7 segments, en supposant que les valeurs d’entrée vont toujours de 0000 à 1001.

Exercice Multiples de 3 Proposez un circuit qui prendra en entrée un nombre N entre 0 et 15 (codé en binaire évidemment) et dont la sortie indiquera si N est un multiple de 3.

3 Quelques circuits combinatoires

Dans ce chapitre nous étudions brièvement quelques circuits combinatoires qui interviennent dans la réalisation des composants logiques d’un ordinateur.

Nous présenterons l’étude de ces circuits sous une forme commune : la spécification énonce rapidement le rôle du circuit, la fonction de tranfert indique précisément (en général par des tables de vérité) la valeur des sorties pour toutes les entrées possibles, la réalisation montre un des circuits possibles.

3.1 Demi-additionneur

3.1.0.0.1 Spécification

C’est un circuit (voir fig. [combi1]) à deux entrées a, b et deux sorties r, s. Les entrées représentent les nombres 0 et 1, et rs est l’expression en binaire de leur somme. (s est la somme, r la retenue).

Demi-additionneur
Demi-additionneur
3.1.0.0.2 Fonction de transfert


$$\begin{array}{|cc|cc|} \hline a& b& r & s\\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \hline \end{array} \begin{array}{rcl} \multicolumn{3}{c}{\mbox{Équations:}} \\ r &=& a b \\ s &=& a\overline{b} + b\overline{a} \\ &=& a \oplus b \end{array}$$

3.1.0.0.3 Réalisation:

Le schéma de la figure [combi2] se déduit immédiatement des équations.

Schéma d’un demi-additionneur
Schéma d’un demi-additionneur

3.2 Additionneur élémentaire

Le demi-additionneur que nous venons de voir ne suffit pas pour réaliser des additions “chiffre par chiffre” parce qu’il produit des retenues, mais ne sait pas les utiliser.

3.2.0.0.1 Spécification

L’additionneur élémentaire (Fig. [combi3]) est un circuit à 3 entrées a, b, c et deux sorties r, s. Le nombre rs indique, en binaire, le nombre d’entrées qui sont à 1.

Additionneur
Additionneur
3.2.0.0.2 Fonction de transfert


$$\begin{array}{|ccc|cc|} \hline a& b& c& r & s\\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \hspace{1cm} \begin{array}{rcl} \multicolumn{3}{l}{\mbox{Equations:}} \\ r &=& a b + bc +a c\\ s &=& a \oplus b \oplus c \\ &= & abc + \overline{a}\overline{b}c + a\overline{b}\overline{c} + \overline{a}b\overline{c} \end{array}$$

Exercice Montrez qu’un additionneur peut être réalisé à partir de trois demi-additionneurs

Exercice Montrez qu’un additionneur peut être réalisé à partir de deux demi-additionneurs et une porte OU.

3.3 Circuit additionneur 2 × n bits

En mettant côte à côte n additionneurs on peut réaliser un additionneur n bits.

3.3.0.0.1 Spécification

Circuit à 2n + 1 entrées (a0an − 1, b0bn − 1, c) et n + 1 sorties (s0sn − 1, r). Les entrées an − 1an − 2a1a0 représentent un nombre A codé en binaire (et de même pour B sur les entrées bj), et c est la retenue entrante. Les sorties rsn − 1sn − 2…s1s0 expriment la valeur de A + B + c.

3.3.0.0.2 Réalisation

Une réalisation directe (par étude des tables de vérité et recherche d’expressions minimales) n’est envisageable que pour de très petites valeurs de n (si n = 3 il y a 7 entrées, donc des tables de vérité à 128 cases …).

On procède donc par décomposition du problème : il suffit de mettre en parallèle n additionneurs élémentaires identiques. La figure [combi4] montre un additionneur 2 × 4 bits.

Additionneur en tranches
Additionneur en tranches

Remarque Ces additionneurs “en tranches” peuvent eux-mêmes être juxtaposés pour former des additionneurs capables de traiter des nombres plus grands : il suffit de relier la retenue sortante de chaque circuit à la retenue entrante du suivant.

3.4 Décodeur

Ce circuit permet d’envoyer un signal à une sortie choisie.

3.4.1 Décodeur simple

3.4.1.0.1 Spécification

Ce circuit possède n entrées a0an − 1 et 2n sorties s0s2n − 1. Les entrées ai codent un nombre A en binaire. La sortie sA est mise à 1, les autres à 0.

3.4.1.0.2 Fonction de transfert

Pour n = 2 on a la table :
$$\begin{array}{|cc|cccc|} \hline a_1 & a_0 & s_0 & s_1 & s_2 & s_3 \\ \hline 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ \hline \end{array}$$

3.4.1.0.3 Réalisation

On voit facilement qu’à chaque sortie correspond un monôme complet sur a0, a1, et réciproquement. Voir figure [combi5] pour le schéma d’un décodeur “2 vers 4”.

Décodeur “2 vers 4”
Décodeur “2 vers 4”

Exercice Dessinez un décodeur “3 vers 8”

3.4.2 Décodeur avec validation

Ce décodeur possède une entrée supplémentaire V, qui sert à “activer” le circuit. Si cette entrée est à 1, le décodeur fonctionne comme précédemment. Si V = 0, toutes les sorties sont à 0.

On obtient (fig. [combi6]) ce circuit par une simple modification du schéma précédent.

Décodeur “2 vers 4” avec validation
Décodeur “2 vers 4” avec validation

Remarque Les décodeurs avec validation peuvent être assemblés entre eux pour former des décodeurs plus gros. Le montage de la figure [combi7] montre un décodeur “maître” pilotant 4 décodeurs esclaves, le tout formant un décodeur “4 vers 16” avec validation.

Montage de décodeurs en maître-esclaves
Montage de décodeurs en maître-esclaves

Exercice Quelles doivent être les valeurs des entrées pour avoir s13 = 1 ?

3.5 Multiplexeur

Autre circuit très utile, le multiplexeur permet de sélectionner une entrée parmi plusieurs. C’est un circuit à une seule sortie S. Il prend comme entrées un nombre N sur k bits, et 2k entrées ei. La valeur de la N-ième entrée est copiée sur la sortie S.

Multiplexeur 4 voies
Multiplexeur 4 voies

La figure [combi8] montre un multiplexeur 4 voies. On remarquera que le multiplexeur contient un décodeur 2 vers 4.

Exercice Multiplexeur 16 voies Montrez comment réaliser un multiplexeur 16 voies par un montage maître-esclaves.

3.6 Exercices

3.6.1 Test d’égalité

Concevoir un circuit qui prendra en entrée deux nombres binaires A et B de 4 chiffres, et indiquera si ces deux nombres sont égaux.

3.6.2 Comparateur

Concevoir un circuit qui prendra en entrée deux nombres binaires A et B de 4 chiffres, et indiquera si A < B, A = B ou A > B. Essayez d’obtenir un circuit “cascadable” pour comparer des nombres plus grands.

3.6.3 Additionneur à retenue anticipée

Dans l’additionneur classique la retenue se propage de chiffre en chiffre, ce qui induit un délai de calcul proportionnel au nombre N de bits des nombres à traiter. Evaluez ce délai en fonction de N et du temps de traversée des portes ET, NON, OU.

La première retenue sortante r0 vaut a0b0 + a0c0 + b0c0 (c0 est la première retenue entrante). Pour la seconde retenue on a r1 = a1b1 + a1c1 + b1c1. Comme c1 = r = 0, on peut donc exprimer r1 en fonction de a0, a1, b0, b1, c0 (donnez la formule). C’est ce qu’on appelle le pré-calcul de r1. Or cette formule s’exprime avec deux étages de portes (faites le schéma).

En suivant la même technique, donnez une formule pour r2, puis r3. Que dire du temps de traversée d’un tel additionneur N bits ? Quelle est la contrepartie de ce gain de temps ?

3.6.4 Compteur

Réaliser un circuit à 3 entrées e1, e2, e3 et 2 sorties s0, s1. Le nombre binaire s1s0 indiquera le nombre d’entrées qui sont à 1.

3.6.5 Encodeur de priorités

Réaliser un circuit à 3 entrées e1, e2, e3 et 2 sorties s0, s1. Le nombre binaire s1s0 indiquera le plus grand indice des entrées qui sont à 1, ou 00 si toutes les entrées sont à 0.

4 Circuits séquentiels

4.1 Définition

Un circuit séquentiel possède des entrées E et des sorties S, mais aussi un état interne Q qui sert à mémoriser de l’information. On peut résumer un tel circuit par deux fonctions. L’une (fonction de sortie f) indique la valeur des sorties en fonction des entrées et de l’état actuel :


S = f(E, Q)

L’autre (fonction de transition g) indique l’état que le circuit prendra à l’instant suivant:


Q′ = g(E, Q)

4.2 Du bistable à la bascule RS

Une expérience simple consiste à monter (fig. [seq1]) deux portes NON tête-bêche, la sortie de l’une servant d’entrée à l’autre. Soient Q1 et Q2 les deux sorties.

Bistable à deux portes NON
Bistable à deux portes NON

On constate que ce circuit prend l’un des deux eétats suivants:

et qu’il y reste indéfiniment: on dit que le circuit est stable. (C’est un bistable, car il y a deux positions de stabilité).

En revanche si on boucle l’entrée avec la sortie d’une seule porte NON, (fig. [seq2]) c’est un circuit astable qui oscille continuellement (et très rapidement) entre 0 et 1.

Circuit astable
Circuit astable

Reprenons notre bistable à 2 portes NON. Supposons qu’il soit dans l’état (0), c’est-à-dire Q1 = 0, Q2 = 1. Pour le faire basculer dans l’autre état, il faudrait forcer l’entrée E2 à 1. Mais pour l’instant l’entrée E2 n’est reliée qu’à Q1. On intercale donc (fig. [seq3]) une porte OU avec une entrée de commande S (Set).

Bistable avec commande S (set)
Bistable avec commande S (set)

Dans l’état (0) avec S=0, la situation est stable. L’arrivée d’une impulsion sur S provoque le passage de E2 à 1, puis Q2 prend la valeur 0 et Q1 passe à 0. Le bistable est donc dans la situation (1) qui est stable, et il y reste désormais quel que soit le signal d’entrée sur S. Ceci est résumé par le chronogramme de la figure[seq4].

Chronogramme
Chronogramme

Pour permettre le retour à l’état (0) on peut ajouter -par symétrie- une autre entrée de commande R (reset) et une autre porte OU (fig. [seq5]).

Bascule RS: schéma et symbole
Bascule RS: schéma et symbole

Le circuit résultant (que l’on réalise avec des portes NOR) est appelé bascule RS. Son fonctionnement normal se résume comme suit:

La figure [seq6] montre, sous forme de chronogramme, l’effet d’une séquence de “tops” envoyés successivement sur les entrées de commande d’une bascule RS.

Chronogramme d’une bascule RS
Chronogramme d’une bascule RS
4.2.0.0.1 Remarque

Si R et S sont simultanément à 1 les deux sorties sont à 1. Si S et R repassent simultanément à 0 le résultat est alors imprévisible (dépend des vitesses de réaction des différentes portes).

4.3 Bascules dérivées

4.3.1 Bascule RS à portes NAND

En mettant des portes NAND au lieu des portes NOR, on obtient une bascule RS à signaux de commande inversés. On désigne alors les entrées de commande par $\overline{R}$ et $\overline{S}$ (voir figure [seq7]).

Bascule RS à portes NAND
Bascule RS à portes NAND

4.3.2 Bascule RS avec horloge

Les commandes R et S ne sont actives que lorsque l’entrée d’horloge est à 1. Il suffit (fig. [seq8]) de valider les signaux R et S par l’entrée H au moyen de deux portes ET.

Bascule RSH: schéma et symbole
Bascule RSH: schéma et symbole

4.3.3 Bascule D

On la réalise à partir de la bascule RSH (figure [seq9]) Lorsque son entrée H est à 1, elle mémorise la valeur de son entrée D. Quand H=0, elle reste insensible aux changements sur D (voir chronogramme de la figure [seq10])

Bascule D
Bascule D
Chronogramme d’une Bascule D
Chronogramme d’une Bascule D

La bascule D est utilisée pour la constitution des mémoires.

4.4 La conception de circuits séquentiels

Considérons par exemple une commande d’éclairage par bouton-poussoir. Il y a une entrée B (l’état du bouton : appuyé ou pas), une sortie L (la lampe allumée ou éteinte), mais il est clair que la sortie ne dépend pas seulement de l’entrée, mais aussi de ce qui s’est passé avant, que l’on représente par un état Q.

Ici on pourra décider que Q mémorise simplement l’état de la lampe. Si Q=0, la lampe est éteinte. Si Q=1, la lampe est allumée

La sortie est fonction de l’entrée et de l’état
L = f(B, Q)

Ici on prendra par exemple L = Q.

Une autre fonction indique comment l’état interne évolue au cours du temps. Pour simplifier le raisonnement on découpe le temps en “instants”. L’état Q’ “à l’instant suivant” dépend des entrées ainsi que de l’ancien état:
Q′ = g(B, Q)
Dans l’exemple on dira que si B=0 l’état reste stable et si B=1 l’état s’inverse, d’où la table:


$$\begin{array}{|cc|l|} \hline B & Q & Q'=g(B,Q) \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \hline \end{array}$$

A partir de là on pourrait en conclure qu’il suffit (fig. [seq11]) d’une bascule D pour représenter l’état, qui serait activée par B et dont la sortie serait rebouclée sur l’entrée à travers un NOT.

Un montage naïf
Un montage naïf

Mais attention ça ne marche pas ! En effet l’impulsion sur le bouton dure “plusieurs instants”, ce qui fait clignoter (trop vite pour que l’oeil le perçoive) la sortie pendant l’appui du bouton : c’est un état instable. La vitesse élevée d’oscillation fait alors qu’à la fin de l’impulsion le résultat est imprévisible.

Pour s’en sortir on emploiera le montage de la figure [seq12], (appelé maître-esclave).

Bascule RSH maître-esclave
Bascule RSH maître-esclave

la bascule 1 (maître) est validée par H1 = B et la 2 (esclave) par $H_2=\overline{B}$, mais on utilise (et c’est là toute l’astuce) une porte NON dont le seuil de déclenchement est plus bas que la normale, ce qui fait qu’une impulsion sur B correspond à deux impulsions décalées sur H1 et H2, comme le montre le chronogramme de la figure [seq13].

Seuils de déclenchement
Seuils de déclenchement

Donc à l’arrivée d’une impulsion (front montant) la bascule esclave se verrouille en mémorisant l’état du maître, puis le maître change d’état. A la fin de l’impulsion (front descendant de l’impulsion sur B) le maître se verrouille, et l’esclave change d’état.

Exercice : vérifier le fonctionnement de ce circuit à l’aide d’un chronogramme (dessiner l’arrivée de 2 impulsions sur B).

Problème Bascule JK En utilisant le même principe (maître-esclave) concevoir une bascule JK. Comme son nom l’indique une bascule JK possède 3 entrées J,K et H et deux sorties Q et $\overline{Q}$. La bascule ne peut changer d’état que pendant une impulsion sur H. Si J=K=0 l’état reste inchangé. Si J=1 K=0 l’état devient 1. Si J=0 et K=1 l’état devient 0. Si J=K=1 l’état s’inverse.

4.4.0.0.1 Circuits Synchrones

On appelle circuit synchrone un circuit séquentiel dont l’état interne ne change qu’à l’arrivée d’une impulsion sur une entrée spéciale appelée “Horloge”. On suppose en général que les autres signaux ne varient pas pendant l’arrivée d’un top d’horloge.

L’intérêt de cette horloge est de donner une définition précise de “l’instant suivant”. C’est l’horloge qui rythme les transitions d’état.

4.5 Application à la synthèse de compteurs

On appelle compteur un dispositif séquentiel qui passe périodiquement par une suite d’états. Par exemple le compteur binaire sur deux bits suivra la séquence 00, 01, 10, 11, 00, 01, 10, 11, 00, etc. à chaque top d’horloge.

Nous allons voir comment réaliser, de manière systématique, n’importe quel compteur, d’abord avec des bascules D maître-esclave, puis avec des bascules JK qui permettent d’obtenir des circuits plus simples.

4.5.1 Réalisation à l’aide de bascules D

Exemple compteur binaire 2 bits

Les deux bits de l’état sont stockés dans deux bascules D.

4.5.1 Réalisation à l’aide de bascules JK

Le principe est légèrement différent : à partir de l’ancien état nous ne faisons plus calculer le nouvel état pour l’injecter dans les bascules, mais nous déterminons les commandes à envoyer aux bascules (sur les entrées J et K) pour que l’état change.

Avant de reprendre l’exemple du compteur 2 bits, quelques remarques sur les bascules JK. Regardons la table de transition :
$$\begin{array}{|c|cc||c|} \hline \mbox{ancien} & & & \mbox{nouvel} \\ \mbox{état} & J & K & \mbox{ état} \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \hline \end{array}$$

En regardant cette table d’une façon différente, on obtient
$$\begin{array}{|cc|c|} \hline \multicolumn{2}{|c|}{\mbox{pour passer}} & \mbox{il faut} \\ \mbox{de} & \mbox{à} & \mbox{avoir} \\ \hline 0 & 0 & J=0 \\ 0 & 1 & J=1 \\ 1 & 0 & K=1 \\ 1 & 1 & K=0 \\ \hline \end{array}$$

Ceci va nous servir pour construire le compteur 2 bits, à l’aide de 2 bascules JK.


$$\begin{array}{|cc|cc|cc|} \hline \multicolumn{2}{|c|}{\mbox{ancien}} & \multicolumn{2}{c|}{\mbox{nouvel}} & \multicolumn{2}{c|}{\mbox{commandes}} \\ \multicolumn{2}{|c|}{\mbox{état}} & \multicolumn{2}{c|}{\mbox{état}} & \multicolumn{2}{c|}{\mbox{à envoyer}} \\ Q_1 &Q_0& Q'_1& Q'_0& & \\ \hline 0& 0& 0& 1& J_1=0 &J_0=1 \\ 0& 1& 1& 0& J_1=1 &K_0=1 \\ 1& 0& 1& 1& K_1=0 &J_0=1 \\ 1& 1& 0& 0& K_1=1& K_0=1 \\ \hline \end{array}$$

Il ne reste plus qu’à trouver des expressions convenables pour J0, K0, J1 et K1 en fonction de Q1 et Q0. En remplissant les tableaux de Karnaugh :
$$\begin{array}{|r|cc|} \hline J_0(Q_0,Q_1) & 0 & 1 \\ \hline 0 & 1 & . \\ 1 & 1 & 1 \\ \hline \end{array} \hspace{0.5cm} \begin{array}{|r|cc|} \hline K_0(Q_0,Q_1) & 0 & 1 \\ \hline 0 & . & 1 \\ 1 & . & 1 \\ \hline \end{array}$$

$$\begin{array}{|r|cc|} \hline J_1(Q_0,Q_1) & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & . & . \\ \hline \end{array} \hspace{0.5cm} \begin{array}{|r|cc|} \hline K_1(Q_0,Q_1) & 0 & 1 \\ \hline 0 & . & . \\ 1 & 0 & 1 \\ \hline \end{array}$$
L’abondance de cas indéterminés nous permet d’obtenir des expressions très simples: J0 = 1, K0 = 1, J1 = Q1, K1 = Q1.

Exercice compteur modulo 3 La séquence à effectuer est 00, 01, 10, 00, 01, 10, etc.

Exercice compteur binaire sur 3 bits 000, 001, 010, 011, ...111, 000, ...

Exercice Compteur modulo 10 Séquence 0000,0001,.…,1000,1001,0000...

Exercice Compteur/décompteur 3 bits Une entrée supplémentaire C indique s’il faut compter (C=1) ou décompter (C=0).

Exercice Compteurs rampants 0000, 1000, 1100, 1110, 1111, 0111, 0011, 0001, 0000, .…

Exercice Compteurs de gray


  1. Une logique négative aura des signaux inversés: 0v représente la valeur 1, +5v la valeur 0.

  2. Pour simplifier l’exposé nous n’évoquerons que les transistors NPN.

  3. En particulier “effet d’antenne” lorsqu’on approche la main d’un circuit dont une des entrées est restée “en l’air”

  4. les circuits combinatoires (sans boucles) et séquentiels (avec boucles) seront étudiés dans les chapitres suivants

  5. L’oeuvre la plus célèbre de George Boole (1815-1864) est intitulée Une investigation dans les lois de la pensée, sur lesquelles sont fondées les théories mathématiques de la logique et des probabilités (1854), plus connue sous le titre abrégé Les lois de la pensée

  6. Les travaux d’Augustus de Morgan (1806-1871) influencèrent fortement George Boole, et ses vives recommandations permirent à ce dernier, bien qu’autodidacte, d’obtenir la Chaire de Mathématiques du Queen’s College de Cork.

  7. Ce produit peut être infini, mais c’est une autre histoire

  8. Nous ne montrerons ici que la méthode pour 3 et 4 variables, le passage à 5 ou 6 variables nécessite une bonne vision dans l’espace