Circuits combinatoires
Remarque prof
TODO Ce cours doit être améliorer. En particulier, il faut ajouter des exemples Python pour chaque opérateur.
Prérequis
Il est conseillé pour s'attaquer à ce chapitre d'avoir déjà vu la programmation jusqu'au chapitre Architecture avec des fonctions.
Erreurs de rendu
Il peut y avoir des erreurs de rendu dans le cours, sur les formules mathématiques qui comportent des barres horizontales supérieures.
Transistor, portes logiques
Les calculs dans nos ordinateurs sont réalisés à l'aide de transistors. Ce sont des composants électroniques un peu particuliers, qui on deux entrées, la grille et la source et une sortie, le drain.
Le principe est que le courant appliqué à la grille contrôle le passage d'un courant de la source vers le drain. Autrement dit un transistor est un interrupteur contrôlé éléctriquement, sans aucune pièces mécaniques.
On peut donc combiner des transistors pour former des portes logiques combinatoires qui implantent des operateurs booléens, comme le ET (and en Python). Dans ce cas, la présence ou l'absence de courant dans une entrée ou une sortie de la porte représente les valeurs \(1\) (\(vrai\)) et \(0\)(\(faux\)) des booléens.
Combiner des portes logiques ensembles permet de créer des circuits combinatoires, qui implantent des fonction booléennes. Une fonction booléenne est simplement une fonction au sens mathématique, mais qui travaille uniquement sur des booléens, c'est à dire qui associe à des valeurs d'entrées booléennes une ou plusieurs valeurs de sortie booléennes. Elles sont très similaires aux expressions booléennes que nous avons vu en programmation Python, et utilisent les mêmes opérateurs non, et et ou.
Un booléen, qui a deux valeurs possibles, peut représenter un bit d'un nombre binaire, et donc les circuits combinatoires permettent d'implanter des opérations, comme l'addition, sur des données binaires.
C'est que nous allons explorer dans ce chapitre.
Remarque
Même si ce chapitre n'est pas directement lié à la programmation, certaines notions que nous allons aborder peuvent vous aider à mieux formuler les conditions dans les structures de contrôle.
Logisim
Nous allons utiliser un logiciel de simulation libre, Logicim. L'interface se présente comme suit :
- Le menu circuits logiques contient la liste des portes et autres composants que nous pouvons simuler dans Logicim. Nous utiliserons uniquement ceux de Gates (portes), le Pin de la famille Wiring (câblage), et la LED de la famille Input/Output (entrées/sorties).
- Les propriétés composants ne nous seront que peu utiles.
- Le mode intéraction (icone de petite main) permet d'interragir avec les composants, en particulier les Pins, en cliquant dessus pour changer leur valeur.
- Le mode édition (icone pointeur) nous permet d'éditer le circuit, en cliquant sur les composants dans le menu circuit logiques, et en cliquant ensuite dans l'espace de création pour les placer.
- Une fois des composants placés, on peut créer des fils pour connecter leurs entrées et sorties en cliquant sur une entrée, une sortie ou un fil et en tirant (maintenir le clic) le fil jusqu'à une autre sortie, entrée ou fil.
Vous allez créer votre premier circuit, qui sera très simple. Simplement un Pin, connecté à une LED.
Passez en mode interaction et cliquez sur le pin pour changer sa valeur, qui va passer à \(0\), puis à \(1\).
Quand la LED reçoit \(1\) sur son entrée, elle s'allume :
Vous remarquez que le pin a trois états : \(\times\), \(0\) et \(1\). Ce n'est pas forcément très pratique, parce que l'état \(\times\) ne représente rien dans notre cas. Vous pouvez changer ça en cliquant sur le pin, puis en changeant sa propriété Three-state? à No.
Remarque
il y a plusieurs standards pour les représentations des portes logiques. Un exprime l'opérateur d'une porte par sa forme, l'autre utilise des portes carrées ou rectangulaires et écrit l'opérateur au milieu.
J'utiliserai la représentation avec les formes parce que je la trouve plus visuelle, mais vous pouvez utiliser celle que vous voulez. Vous pouvez changer de représentation en allant dans Window > Preferences > International puis en sélectionnant Shaped ou Rectangular dans la liste Gate Shape.
Portes des opérateurs basiques
On va créer des portes basiques pour s'entraîner un peu. On introduira par la même occasion leur notations mathématiques, et un tableau qui récapitule la valeur de sortie de la porte en fonction de son entrée, la table de vérité.
Remarque
Il y a souvent plusieurs symboles possibles pour un même opérateur, ne n'en présenterai qu'un seul pour chaque opérateur.
Porte NOT (NON)
Symbole :
Notation mathématique \(\overline{a}\), se lit non a ou a barre.
Table de vérité :
| \(a\) | \(\bar{a}\) |
|---|---|
| \(0\) | \(1\) |
| \(1\) | \(0\) |
Activité
Créez le circuit suivant, et vérifiez que le NOT est bien conforme à sa table de vérité en comparant ses entrées et ses sorties.
Porte AND (ET)
Symbole :
Remarque
Par défaut, la porte a plus de deux entrées. Ce n'est pas un problème, les entrées non connectées sont ignorées. Toutefois, vous pouvez changer le nombre d'entrées dans les propriétés du composant Number Of Inputs.
Notation mathématique \(a \cdot b\), se lit a et b.
Exercice : table de vérité du AND
A l'aide du circuit suivant, dressez la table de vérité de l'opérateur AND.
Testez toutes les combinaisons possibles d'entrées, il y en a 4 !
| \(a\) | \(b\) | \(a \cdot b\) |
|---|---|---|
| \(0\) | \(0\) | ? |
| \(0\) | \(1\) | ? |
| \(1\) | \(0\) | ? |
| \(1\) | \(1\) | ? |
| \(a\) | \(b\) | \(a \cdot b\) |
|---|---|---|
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(0\) |
| \(1\) | \(1\) | \(1\) |
Porte OR (OU)
Symbole :
Notation mathématique \(a + b\), se lit a ou b.
Exercice : table de vérité du OR
A l'aide du circuit suivant, dressez la table de vérité de l'opérateur OR.
Testez toutes les combinaisons possibles d'entrées, il y en a 4 !
| \(a\) | \(b\) | \(a + b\) |
|---|---|---|
| \(0\) | \(0\) | ? |
| \(0\) | \(1\) | ? |
| \(1\) | \(0\) | ? |
| \(1\) | \(1\) | ? |
| \(a\) | \(b\) | \(a + b\) |
|---|---|---|
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(1\) |
Un peu de mathématiques
Les opérateurs booléens ont des règles de priorités, comme les opérateurs pour les nombres décimaux. On peut si besoin mettre des parenthèses. A noter que le not agit comme des parenthèses, et donc est prioritaire sur \(+\) et \(\cdot\) :
Le et est distributif pour le ou :
Le et et le ou sont tous deux associatifs :
Le et et le ou sont tous deux commutatifs :
On peut voir le et comme l'équivalent de la multiplication, et le ou comme l'équivalent de l'addition.
Portes NAND, NOR et XOR
Certaine opérations booléennes sont omniprésentes dans l'électronique et l'informatique, si bien qu'elles ont leur propre portes logiques !
Porte NAND (NON ET)
Le NAND est le non d'un et : \(\overline{a \cdot b}\)
Symbole :
Notation mathématique \(a \uparrow b\), se lit a non et b, ou a nand b.
Exercice : table de vérité du NAND
Dressez la table de vérité de l'opérateur NAND.
Utilisez le circuit suivant :
Alternativement, vous pouvez réfléchir à l'aide de la table de vérité du ET.
On pouvait procéder soit en testant le circuit, soit en prenant le NON de la table de vérité de \(a \cdot b\)
| \(a\) | \(b\) | \(a \cdot b\) | \(a \uparrow b\) |
|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(0\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(1\) | \(0\) |
Porte NOR
Le NOR est le non d'un ou : \(\overline{a + b}\)
Symbole :
Notation mathématique \(a \downarrow b\), se lit a non ou b ou a nor b.
Exercice : table de vérité de NOR
Dressez la table de vérité de l'opérateur NOR.
Utilisez le circuit suivant :
Alternativement, vous pouvez réfléchir à l'aide de la table de vérité du OU.
On pouvait procéder soit en testant le circuit, soit en prenant le NON de la table de vérité de \(a + b\)
| \(a\) | \(b\) | \(a + b\) | \(a \downarrow b\) |
|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(1\) | \(0\) |
| \(1\) | \(1\) | \(1\) | \(0\) |
Porte XOR
Le XOR est le et d'un ou et d'un non et : \((a + b) \cdot \overline{a \cdot b}\)
Symbole :
Notation mathématique \(a \oplus b\), se lit a ou exclusif b ou a xor b.
Exercice : table de vérité du XOR
Dressez la table de vérité de l'opérateur XOR.
Utilisez le circuit suivant :
| \(a\) | \(b\) | \(a \oplus b\) |
|---|---|---|
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(0\) |
La sortie du XOR vaut \(1\) quand ses entrées sont différentes.
Théorème de De Morgan
Le théorème de De Morgan donne une relation entre le AND et le OR, utilisant le NOT :
Une des conséquences de ce théorème est qu'on peut simuler n'importe quel circuit combinatoire avec uniquement des portes NAND (ou uniquement des NOR), on dit que l'opérateur NAND est universel. Pour montrer celà, on va exprimer les trois opérateurs de base AND, OR et NOT avec uniquement l'opérateur NAND.
Les exercices sont proposés sous forme de manipulation de formule et sous forme de manipulation de circuit. Choisissez celle que vous préférez à chaque fois.
NOT avec NAND
Exercice : NOT avec NAND
Version circuit
En utilisant uniquement des NAND (et le pin et la led), créez un circuit qui a la même table de vérité que le circuit suivant :
Version formelle
Trouvez une expression équivalente à \(\overline{a}\) et ne comportant que des \(\uparrow\).
Version circuit
L'idée est de créer un circuit qui prends un booléen en entrée, et produit un booléen de la valeur inverse en sortie, en utilisant uniquement des NAND.
Remarque : on peut diriger le même booléen dans les deux entrées d'une porte.
Version formelle
Regardez l'aide de la version circuit, peut-être qu'elle vous inspirera. Aussi, il n'est pas trop tard pour changer de version !
Version circuit
Version formelle
AND avec NAND
Exercice : AND avec NAND
Version circuit
En utilisant uniquement des NAND (et les pins et la led), créez un circuit qui a la même table de vérité que le circuit suivant :
Version formelle
Trouvez une expression équivalente à \(a \cdot b\) et ne comportant que des \(\uparrow\).
Utilisez la transformation du NOT en NAND que nous avons fait juste avant. Remarque : \(\overline{\overline{a}} = a\) (non non a vaut a)
Version circuit
On remplace le AND par un NAND, et on inverse sa sortie avec un NAND utilisé comme un NOT.
Version formelle
OR avec NAND
Exercice : OR avec NAND
Version circuit
En utilisant uniquement des NAND (et les pins et la led), créez un circuit qui a la même table de vérité que le circuit suivant :
Version formelle
Trouvez une expression équivalente à \(a + b\) et ne comportant que des \(\uparrow\).
Utilisez la transformation du NOT en NAND que nous avons fait juste avant.
\(a + b = \overline{\overline{a + b}} = \overline{\overline{a} \cdot \overline{b}}\)
Version circuit
On remplace le OR par un NAND, et on inverse ses entrées sortie avec des NAND utilisés comme des NOT.
Version formelle
En électronique, pouvoir exprimer toutes les expressions booléennes avec uniquement des portes NAND présente deux avantages :
- Les portes NAND sont très peu chères à produire
- Devoir produire une seule et même porte quand un composant electronique en comporte plusieurs milliards, c'est beaucoup d'économies d'échelle, et celà simplifie les procédés de fabrication.
Additionneur binaire
On va réaliser un petit additionneur d'entiers binaire, un circuit qui réalise l'addition de deux entiers codés sur \(n\) bits.
L'addition binaire fonctionne sur le même principe que l'addition décimale.
Pour une additionner deux nombres décimaux, on additionne leurs chiffres deux à deux en partant du rang le plus bas, et si la somme des deux chiffres dépasse \(10_{10}\), on ne garde que le premier chiffre, et on propage le second sous forme d'une retenue à additionner au rang suivant.
Ainsi, pour faire \(79 + 63\), on a les étapes suivantes :
- \(9 + 3 = 12\). Notre résultat rang \(0\) est donc \(2\) et on retiens \(1\) .
- \(7 + 6 = 13\), auquel on ajoute la retenue, \(13 + 1 = 14\). Notre résultat rang \(1\) est donc \(4\) et on retient \(1\).
- \(0 + 0 = 0\), auquel on ajoute la retenue, \(0 + 1 = 1\), Notre résultat rang \(2\) est \(1\) et n'a pas de retenue.
- \(79 + 63 = 142\)
C'est le même principe pour une addition avec des nombres en base 2 !
Additionnez \(11_{2}\) et \(10_{2}\) avec une addition en base 2.
\(11_{2} + 10_{2}\)
- \(1_{2} + 0_{2} = 1_{2}\), notre résultat rang \(0\) est \(1_{2}\).
- \(1_{2} + 1_{2} = 10_{2}\), notre résultat rang \(1\) est \(0_{2}\) et on retiens $\(1_{2}\).
- \(0_{2} + 0_{2} = 0_{2}\), auquel on ajoute la retenue : \(0_{2} + 1_{2} = 1\), notre résultat rang \(2\) est \(1_{2}\).
- \(11_{2} + 10_{2} = 101_{2}\)
Jusqu'à maintenant, on a utilisé des LED pour afficher l'état de nos sorties, mais pour des additions on préfèrera des \(1\) et des \(0\). On utilisera donc des pins de sortie à la place.
Addition de deux entiers sur 1 bit
Commençons par créer un additionneur sur 1 bit. On notera \(a\) et \(b\) les deux bits en entrée, \(s\) la somme et \(r\) la retenue. On a la table de vérité suivante :
| \(a\) | \(b\) | \(s\) | \(r\) |
|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(1\) | \(0\) |
| \(1\) | \(1\) | \(0\) | \(1\) |
A quelles opérations booléennes correspondent \(s\) et \(r\) ?
Comparez les colonnes à celles des tables de vérité des opérateurs.
\(s\) corresponds à un XOR, et \(r\) a un AND.
Implantez le circuit qui calcule r et s sur deux pins de sortie à partir de a et b sur deux pins d'entrée.
Vous n'avez besoin que de deux portes logiques !
Vous pouvez relier un même pin d'entrée à plusieurs portes.
Vous pouvez télécharger ce circuit en cliquant sur ce lien
Ce circuit ne tient pas compte d'une éventuelle retenue précédente, donc il n'est valide que pour additionner le rang 0. C'est ce que l'on appelle un demi additionneur, et on notera l'opération qu'il fait :
On va réaliser un circuit qui prends en entrée une retenue \(p\) en plus de \(a\) et \(b\), pour que notre circuit puisse être appliqué à n'importe quel rang dans une addition binaire.
Le principe est qu'on va utiliser un premier demi additionneur pour effectuer l'addition de \(a\) et \(b\) :
puis un second demi additionneur pour additionner le résultat \(s_{1}\) avec la retenue en entrée \(e\) :
Finalement, on combine les retenues des demi-additionneurs \(r_{1}\) et \(r_{2}\) dans \(r\) en utilisant un OR.
Vous pouvez télécharger ce circuit en cliquant sur ce lien :
En dressant les tables de vérités de toutes ces opérations, on remarque que \(r_{1}\) et \(r_{2}\) ne sont jamais à \(1\) en même temps, ce qui justifie de les combiner dans \(r\) par un OR.
| \(a\) | \(b\) | \(s_{1}\) | \(r_{1}\) |
|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(1\) | \(0\) |
| \(1\) | \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(0\) | \(1\) |
| \(s_{1}\) | \(e\) | \(s\) | \(r_{2}\) |
|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(1\) | \(0\) |
| \(1\) | \(1\) | \(0\) | \(1\) |
| \(1\) | \(0\) | \(1\) | \(0\) |
| \(1\) | \(1\) | \(0\) | \(1\) |
| \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) |
| \(r_{1}\) | \(r_{2}\) | \(r\) |
|---|---|---|
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) |
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
Remarquez la disposition des portes logiques, des entrées et des sorties :
- Les deux bits des nombres à additionner \(a\) et \(b\) sont en haut, le bit de résultat \(s\) est en bas.
- La retenue du rang précédent en entrée \(e\) est à droite, la retenue générée à ce rang \(r\) est à gauche.
On peut abstraire notre additionneur 1 bit comme le bloc suivant :
Si on veut faire un additionneur 2 bits, il nous suffit alors de placer côte à côte deux additionneurs 1 bit, et des les connecter par leur retenue.
Celà donne le circuit suivant. Vous pouvez le télécharger en cliquant sur ce lien :
On peut continuer encore et encore pour créer des additionneurs à \(n\) bits.
Remarque
Les additionneurs présents dans les ordinateurs modernes sont un peu plus complexes que ça pour des raisons de performances, mais le principe reste le même.
Dépassement d'entiers
Utilisez l'additionneur à 2 bits de la section précédente. En lisant uniquement le résultat sur les bits \(s_{0}\) et \(s_{1}\), calculez :
Codez les deux entiers sur les pins d'entrée. Lisez le résultat sur les pins de sortie.
On choisit \(a = 01_{2}\) et \(b=10_{2}\)
Celà nous donne l'état suivant pour le circuit :
Le résultat est donc \(11_{2}\)
Même exercice avec
Remarquez-vous quelque chose ?
Le résultat ne se lit que sur les bits \(s_{0}\) et \(s_{1}\) !
On choisit \(a = 11_{2}\) et \(b=10_{2}\)
Celà nous donne l'état suivant pour le circuit :
Le résultat est donc \(01_{2}\)
Le résultat est tronqué, il devrait être \(101_{2}\), et la retenue la plus à gauche est activée.
Voyons celà plus en détail.
Exercice : dépassements d'entiers
Quelle est la valeur (décimale) maximale que l'on peut représenter en base 2 sur 2 bits ?
C'est la valeur de \(11_{2}\), c'est à dire \(3_{10}\).
Quelle est la valeur (décimale) maximale de l'addition de deux nombres en base 2 sur 2 bits ?
C'est la valeur de \(11_{2} + 11_{2}\), c'est à dire \(3_{10} + 3_{10} = 6_{10}\)
Combien de bit faut-il au minimum pour coder \(6_{10}\) en base 2 ?
Convertissez \(6_{10}\) en base 2 avec un des algorithmes vus précédemment en cours.
La représentation de \(6_{10}\) en base 2 est \(110_{2}\), il faut donc 3 bits.
En fait, le résultat de l'addition de deux entiers codés en base 2 sur \(n\) bits nécessite au maximum \(n + 1\) bits pour être représentée.
Pour des raisons de performances, on manipule dans la plupart des langages de programmations des entiers qui sont codés sur un nombre de bits fixes. En général, les tailles disponibles sont 8, 16, 32 et 64 bits.
Ce qui veut dire que quand on additionne deux nombres, le résultat peut parfois ne pas tenir sur le nombre de bit prévu, et être tronqué, c'est ce que l'on appelle un dépassement d'entier.
C'est aussi vrai pour la multiplication : le résultat de la multiplication de deux entiers sur \(n\) bits nécessite au maximum \(2n\) bits pour être représenté !
Les erreurs dues à des dépassements sont plutôt rares, mais très vicieuses, parce que le programme ne plante pas directement, mais est "pollué" par des valeurs erronnées. Il faut donc avoir conscience de ces limitations.
Python a choisi de sacrifier les performances pour plus de robustesse, et permet de manipuler des entiers de taille complètement arbitraire. Un dépassement d'entier est donc impossible en Python, mais les implémentations de Python les plus performantes sont beaucoup moins rapides que les implémentations les plus performantes d'autres langages, comme le C ou le Rust.
Exploration
Activité (exploration, difficile)
Dans le jeu Minecraft, la redstone permet de créer des circuits combinatoires, et bien plus.
Logiciel non libre
Minecraft n'est pas un logiciel libre, et son utilisation est payante. Il existe toutefois des alternatives libres qui supportent la redstone, comme Mineclone 2, un mod du jeu Minetest,
Des instructions pour implanter des portes logiques à l'aide de la redstone se trouvent sur le wiki de Minecraft
Essayez de faire un petit additionneur binaire à l'aide de redstone : utilisez des leviers pour coder les entrées (levier baissé 0, levié monté 1), et utilisez des pistons ou des lampes à redstone pour coder la sortie.
Commencez par un additionneur simple, à un ou deux bits, puis si vous y arrivez, essayez de passer sur un additionneur à plus de bits, comme par exemple 4.
Les circuits de redstone réalisant des opérations complexes sont difficiles à réaliser, parce qu'ils prennent souvent beaucoup de place et qu'il faut gérer les croisements de fils de redstone. C'est en réalité un défi relativement proche du design de composants électroniques, où la place et les matériaux sont en quantité limités.
L'essentiel
Au Programme
Les booléens sont des nombres qui ne peuvent avoir que deux valeurs possible, \(vrai\) et \(faux\), souvent notés \(1\) et \(0\).
Ils correspondent au type bool en Python.
Les expressions booléennes sont des expressions qui combinent des valeurs booléennes à l'aide d'opérateurs :
- Le
ET, qui est l'opérateuranden Python. - Le
OU, qui est l'opérateuroren Python. - Le
NON, qui est l'opérateurnoten Python.
La table de vérité d'une expression booléenne est un tableau qui sur chaque ligne associe les valeurs possibles de chaque variable dans l'expressions avec la valeur de l'expression. Voici une table de vérité qui récapitule les trois opérateurs précédents.
a |
b |
not a |
a and b |
a or b |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
Ces opérations booléennes sont la base de nos ordinateurs, qui les implantent sous forme de portes logiques.
Comme les nombres sont représentés en général sur un nombre finis de bits dans un ordinateur, et donc le résultat de certaines opérations, comme par exemple l'addition, peuvent conduire à des dépassements du nombre de bits disponible.