Circuits logiques
Rappel d'ouverture (5 minutes, cours fermé)
- Donnez la table de vérité du OU EXCLUSIF.
- Quelle est la seule ligne où le OU et le OU EXCLUSIF donnent des résultats différents ?
- \(a\) vaut 1 et \(b\) vaut 0. Que valent \(a.b\), \(a+b\) et \(\bar{a}\) ?
Corrigé
- \(0 \oplus 0 = 0\), \(0 \oplus 1 = 1\), \(1 \oplus 0 = 1\), \(1 \oplus 1 = 0\).
- Celle où les deux entrées valent 1 : le OU vaut 1, le OU EXCLUSIF vaut 0. Retenez cette ligne, c'est elle qui fera toute la différence dans le circuit que vous allez construire.
- \(a.b = 0\) (le ET exige les deux), \(a+b = 1\) (le OU se contente d'un seul), \(\bar{a} = 0\).
Un peu d'électronique
Le transistor
Le fonctionnement d'un ordinateur réside presque essentiellement sur un composant inventé en 1947 et qui ne cesse de se perfectionner et de se miniaturiser encore aujourd'hui: le transistor.
Il existe des transistors de diverses technologies. Ici je vous présente le PNP.
C'est un composant électronique doté de 3 pattes:
- (C) Le collecteur
- (B) La base
- L'émetteur
Voici son symbole électrique et ce à quoi ça ressemble:
L'objet n'est pas ici d'être expert en transistors mais de saisir un de ses usages fondamentaux: L'interrupteur commandé.
Si la tension à la base n'est pas suffisamment forte, le courant entre le collecteur et l'émetteur est coupé.
Une opération logique avec des transistors : ET
La LED ne s'allumera que si la tension est suffisante à la base de Q1 et de Q2. Si l'une ou l'autre des bases n'est pas alimentée, le courant est coupé et la LED s'éteint.
Portes et Circuits logiques
On peut résumer ces circuits électroniques dans des composants qu'on appelle des portes logiques. Chaque porte logique réalise une opération booléenne élémentaire.
Le circuit électronique précédent se résume entièrement à la porte logique ET. Voici les représentations des différentes portes logiques :
Exemple de circuit logique
Un circuit logique est un assemblage de portes logiques connectées entre elles. Les entrées du circuit sont les variables booléennes, et la sortie est le résultat de l'expression booléenne correspondante.
Par exemple, le circuit suivant réalise l'expression \(\overline{a.b}\) (c'est une porte NAND) :
- On connecte \(a\) et \(b\) à une porte ET.
- On connecte la sortie de la porte ET à une porte NON.
- La sortie finale est \(\overline{a.b}\).
Exercices
Prédire avant de brancher
Ces exercices se font dans un éditeur de circuits, et l'éditeur répond instantanément. C'est un piège : on peut brancher au hasard jusqu'à ce que la lampe s'allume, et repartir sans avoir rien compris.
La règle est donc la même que pour le compteur du chapitre précédent : avant de relier quoi que ce soit, écrivez la table de vérité que vous voulez obtenir, puis construisez le circuit, puis vérifiez qu'il produit bien cette table, ligne par ligne. Si le circuit fonctionne mais que vous ne savez pas dire pourquoi, l'exercice n'est pas fait.
Interrupteurs et lampe
On donne le circuit logique suivant avec les interrupteurs a (en haut) et b (en bas). L'interrupteur est à 1 s'il est fermé.
On note la lampe S. La lampe est à 1 si elle est allumée.
- Exprimez S en fonction de a et de b.
- Etudiez la table de vérité de S
- Proposez une simplification drastique de ce circuit.
Correction — Interrupteurs et lampe
L'expression booléenne du circuit est :
Table de vérité :
| \(a\) | \(b\) | \(\bar{a}\) | \(\bar{b}\) | \(\bar{a}.b\) | \(a.\bar{b}\) | \(S\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
Simplification : On reconnaît exactement la table de vérité du OU EXCLUSIF. Le circuit entier se simplifie en une seule porte :
Porte NAND
La porte NAND réalise l'opération NON(A ET B), i.e. \(\overline{a.b}\)
- Dressez la table de vérité de la porte NAND
Voici son comment elle est représentée sur un circuit:
Sachant que $\bar{\bar{x}} = x $, à l'aide de la loi de Morgan, exprimez \(a+b\) unqiuement grâces aux opérations ET et NON.
Correction — Porte NAND
Table de vérité :
| \(a\) | \(b\) | \(a.b\) | \(\overline{a.b}\) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Expression de \(a+b\) avec ET et NON uniquement :
On applique la double négation puis la loi de De Morgan :
Soit : \(a + b = \text{NON}\bigl(\text{NON}(a)\ \text{ET}\ \text{NON}(b)\bigr)\)
Turing Complete
Ces exercices sont les premiers niveaux d'un jeu nommé "turing complete". Ce jeu, partant de la simple porte NAND, vous emmène jsuqu'à construire un ordinateur entier.
Au début des exercices, seule la porte NAND est utilisable. A chaque fois que vous arrivez à créer une nouvelle porte, elle devient utilisable.
Réalisez chacun de ces exercices les uns sous les autres dans l'interface suivante et sauvegardez votre travail avec le bouton "télécharger le circuit".
- Créer une porte NOT. Seule porte autorisée: NAND
- Créer une porte AND (on utilisera les lois de de Morgan pour exprimer AND à partir de NAND et NOT)
- Créer une porte OR (on utilisera aussi les lois de de Morgan)
- Créer une porte NOR
- Créer une porte XOR
Pourquoi appelle-t-on une porte NAND une porte universelle?
Sauvegardez votre circuit, et réalisez le même exercice, cette fois en partant de la porte NOR. Il faudra peut-être réaliser les portes dans un ordre différent.
Correction — Turing Complete
Télécharger la correction (turing.json)
Pourquoi NAND est-elle une porte universelle ?
En partant uniquement de NAND, on peut reconstruire toutes les portes :
- NOT : \(\overline{a.a} = \bar{a}\) → NAND(a, a)
- AND : NOT(NAND(a, b))
- OR : NAND(\(\bar{a}\), \(\bar{b}\)) = \(\overline{\bar{a}.\bar{b}} = a + b\) (De Morgan)
- NOR : NOT(OR(a, b))
- XOR : construit à partir des portes précédentes
Toute expression booléenne pouvant s'écrire avec NOT, AND, OR, la porte NAND suffit à tout réaliser : c'est une porte universelle. La porte NOR l'est également.
Circuit demi-additionneur
Ce circuit prend 2 bits en entrée et les additionne, comme s'il s'agissait d'entiers binaires dont on pose l'addition.
Le circuit prend en entrée deux bits \(a\) et \(b\). Il renvoie la somme \(S\), ainsi que la retenue \(C_{out}\)
Ainsi, on peut directement construire la table de vérité du circuit résultant:
| \(a\) | \(b\) | \(S\) | \(C_{out}\) | Commentaire |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0+0=0 et je retiens 0 |
| 0 | 1 | 1 | 0 | 0+1=1 et je retiens 0 |
| 1 | 0 | 1 | 0 | 1+0=1 et je retiens 0 |
| 1 | 1 | 0 | 1 | 1+1=0 et je retiens 1 |
- En observant la colonne \(s\), on reconnaît la table de vérité de la porte XOR.
- En observant la colonne \(C_{out}\), on reconnaît la table de vérité de la porte AND.
Réalisation du demi-additionneur
Réalisez le circuit demi-additionneur dans l'interface et téléchargez le résultat.
Indice léger
Vous cherchez deux sorties à partir des mêmes deux entrées, donc deux circuits séparés qui partagent leurs entrées. Traitez-les l'un après l'autre, et commencez par celui dont la table de vérité vous paraît la plus familière.
Indice précis
Comparez la colonne de la retenue avec la table du ET : elles sont identiques. Comparez ensuite la colonne de la somme avec celle du OU, puis avec celle du OU EXCLUSIF : une seule des deux convient, et c'est la ligne où \(a\) et \(b\) valent tous les deux 1 qui tranche.
Correction — Demi-additionneur
Circuit additionneur complet (Full Adder)
Le circuite additionneur prend en entrée deux bits \(a\) et \(b\) ainsi qu'une retenue \(C_{in}\).
Il émet 2 informations en sortie, la somme obtenue \(S\), ainsi que la retenue \(C_{out}\)
Full-Adder
- Complétez la table de vérité suivante pour l'additionneur complet.
| \(a\) | \(b\) | \(C_{in}\) | \(S\) | \(C_{out}\) | Commentaire |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0+0+0=0 et je retiens 0 |
| 0 | 0 | 1 | |||
| 0 | 1 | 0 | |||
| 0 | 1 | 1 | |||
| 1 | 0 | 0 | |||
| 1 | 0 | 1 | |||
| 1 | 1 | 0 | |||
| 1 | 1 | 1 |
- Montrer que \(S = a \oplus b \oplus C_{in}\)
- Montrer que \(C_{out} = (a \oplus b) . C_{in} + a . b\)
- Réalisez alors le circuit de l'additionneur complet et sauvegardez-le.
Indice léger
Un additionneur complet additionne trois bits : \(a\), \(b\) et la retenue entrante. Or vous savez déjà en additionner deux. Comment obtenir la somme de trois nombres quand on ne dispose que d'un outil qui en additionne deux ?
Indice précis
Additionnez d'abord \(a\) et \(b\) avec un demi-additionneur : vous obtenez une somme partielle et une retenue. Additionnez ensuite cette somme partielle avec \(C_{in}\), avec un second demi-additionneur : vous obtenez la somme finale et une seconde retenue.
Reste à décider la retenue sortante. Regardez votre table : elle vaut 1 dès que l'une des deux retenues intermédiaires vaut 1. Il ne peut jamais y en avoir deux à la fois, vérifiez-le sur les huit lignes.
Correction — Full-Adder
Table de vérité complète :
| \(a\) | \(b\) | \(C_{in}\) | \(S\) | \(C_{out}\) | Commentaire |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0+0+0=0 et je retiens 0 |
| 0 | 0 | 1 | 1 | 0 | 0+0+1=1 et je retiens 0 |
| 0 | 1 | 0 | 1 | 0 | 0+1+0=1 et je retiens 0 |
| 0 | 1 | 1 | 0 | 1 | 0+1+1=2 et je retiens 1 |
| 1 | 0 | 0 | 1 | 0 | 1+0+0=1 et je retiens 0 |
| 1 | 0 | 1 | 0 | 1 | 1+0+1=2 et je retiens 1 |
| 1 | 1 | 0 | 0 | 1 | 1+1+0=2 et je retiens 1 |
| 1 | 1 | 1 | 1 | 1 | 1+1+1=3 et je retiens 1 |
Preuve que \(S = a \oplus b \oplus C_{in}\) :
| \(a\) | \(b\) | \(C_{in}\) | \(a \oplus b\) | \(a \oplus b \oplus C_{in}\) | \(S\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 |
Les colonnes \(a \oplus b \oplus C_{in}\) et \(S\) sont identiques. ✓
Preuve que \(C_{out} = (a \oplus b).C_{in} + a.b\) :
| \(a\) | \(b\) | \(C_{in}\) | \(a \oplus b\) | \((a \oplus b).C_{in}\) | \(a.b\) | \((a \oplus b).C_{in} + a.b\) | \(C_{out}\) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
Les deux dernières colonnes sont identiques. ✓
Additionneur 4 bits
Un additionneur 4 bits est composé d'un Half-Adder et de 3 Full-Adders en chaîne. Le but est d'additionner le nombre formé par les bits de la première colonne avec le nombre formé par les bits de la deuxième colonne.
Les composants d'affichage en bas vous permettent de visualiser sous forme décimale chaque nombre, et il y en a aussi un pour le résultat.
Réalisez ce circuit et sauvegardez-le
??? tip "Indice léger"
N'essayez pas de concevoir un circuit qui additionne quatre bits d'un coup. Vous avez déjà l'outil qui traite **une colonne** ; il vous en faut simplement plusieurs, et il faut décider ce que l'on branche entre eux.
??? tip "Indice précis"
Posez l'addition à la main sur deux nombres de 4 bits, et regardez ce qui circule d'une colonne à la suivante : **la retenue**, toujours de droite à gauche. Chaînez donc quatre additionneurs complets, la sortie $C_{out}$ de l'un devenant le $C_{in}$ du suivant.
Deux questions restent, et elles se répondent en regardant votre addition posée : que branche-t-on sur le $C_{in}$ du tout premier ? Et que faire du $C_{out}$ du dernier ?