Portes logiques et circuits combinatoires¶
Les circuits d’un ordinateur manipulent uniquement des 0 ou des 1 représentés en interne par des tensions hautes ou basses. Les premiers ordinateurs construits dans la période 1945-1950 sont basés sur une technologie de tube à vide ou tube électrique. En 1947, aux laboratoires Bell, Shockley, Bardeen et Brattain inventent le transistor au germanium un petit composant électronique qui se comporte comme un interrupteur. Les transistors, plus petits et dissipant moins de chaleur, vont supplanter les tubes électriques : en 1954 le germanium est remplacé par le silicium, en 1955 apparaissent les premiers ordinateurs entièrement transistorisés, en 1960 le transistor à effet de champ permet l’intégration de dizaines composants dans un centimètre carré. Les transistors sont ensuite directement gravés dans une plaque de silicium constituant un cicrcuit intégré.
Bien que les technologies aient évoluées, de l'ENIAC (premier ordinateur entièrement électronique) aux ordinateurs actuels, les principes fondamentaux utilisés sont les mêmes.
Les microprocesseurs permettent d'implémenter des portes logiques.
Portes logiques¶
En logique classique le 0 représente la valeur Faux et le 1 la valeur Vrai.
Définitions
Un transistor possède trois broches : la grille, la sortie (ou drain) et la source soumis à des états de tension haute ou basse qu’on peut assimiler aux valeurs binaires 1 et 0 d’un bit.
Exemple :
| Tension | Valeur du bit |
|---|---|
| < 2,1 V | 0 |
| > 4 V | 1 |
Une fonction logique prend un ou plusieurs bits en entrée et renvoie un ou plusieurs bits en sortie. Une porte logique est un circuit électronique représentant une fonction logique.
Une table logique représente les sorties produites par une fonction logique pour toutes les entrées possibles.
La porte NON¶
Supposons que l'on souhaite implémenter sous forme de circuit éléctronique la fonction logique NON qui prend en entrée la valeur 1 ou 0 et qui renvoie la valeur inverse.
Alors un seul transistor sera suffisant. Ce transistor prendra en entrée :
- Soit une tension haute et fournira en sortie une sortie basse.
- Soit une tension basse et fournira en sortie une sortie haute.
Exercice
Compléter sa table de vérité
| A | \(\neg\)A |
|---|---|
| 0 | |
| 1 |
| A | \(\neg\)A |
|---|---|
| 0 | 1 |
| 1 | 0 |
On peut représenter cette porte logique sans se soucier des transistors utilisés physiquement.
Il existe deux conventions de représentation symbolique des portes logiques, une européenne et une américaine.
La porte ET (AND)¶
Pour la porte ET on utilise deux transistors en série.
Exercice
Compléter sa table de vérité
| A | B | A \(\wedge\) B |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
| A | B | A \(\wedge\) B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
La porte OU (OR)¶
Pour la porte OU on utilise deux transistors en parallèle.
Exercice
Compléter sa table de vérité
| A | B | A \(\vee\) B |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
| A | B | A \(\vee\) B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
La porte NAND (NON ET)¶
Exercice
Compléter sa table de vérité
| A | B | \(\neg\) (A \(\wedge\) B) |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
| A | B | \(\neg\) (A \(\wedge\) B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
La porte NOR (NON OU)¶
Exercice
Compléter sa table de vérité
| A | B | \(\neg\) (A \(\vee\) B) |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
| A | B | \(\neg\) (A \(\vee\) B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
La porte XOR (OU exclusif)¶
Pour le OU exclusif une seule des entrées doit être vraie (pas les deux).
Exercice
Compléter sa table de vérité
| A | B | A \(\oplus\) B |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
| A | B | A \(\oplus\) B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Circuits logiques combinatoires¶
Pour construire des fonctions logiques plus complexes nous allons assembler plusieurs portes logiques élémentaires
Demi Additionneur (half adder)¶
Le demi-additionneur est un circuit combinatoire qui permet de réaliser la somme arithmétique de deux entiers valant 0 ou 1. En sortie, on obtient le bit S de l'unité de la somme et le bit C de la retenue (carry en anglais).
Exercice
- Nommer les deux portes logiques du demi-additionneur ci-dessus.
- Construire la table de vérité du demi additionneur.
| A | B | S (bit somme) | C (bit retenue) |
|---|---|---|---|
| 0 | 0 | ||
| 0 | 1 | ||
| 1 | 0 | ||
| 1 | 1 |
- La porte XOR et la porte AND.
| A | B | S (bit somme) | C (bit retenue) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Additionneur (full adder)¶
En combinant deux portes "OU exclusif", deux portes "ET" et une porte "OU", on obtient un additionneur.
Comme son nom l'indique, l'additionneur permet d'additionner 2 bits (A et B) en tenant compte de la retenue entrante ("Cin" "carry in" en anglais). En sortie on obtient le bit de l'unité du résultat de l'addition (S) et la retenue sortante ("Cout").
Exercice
- Construire la table de vérité de l'additionneur.
| A | B | Cin | S (bit somme) | Cout (bit retenue) |
|---|---|---|---|---|
| 0 | 0 | 0 | ||
| 0 | 0 | 1 | ||
| 0 | 1 | 0 | ||
| 0 | 1 | 1 | ||
| 1 | 0 | 0 | ||
| 1 | 0 | 1 | ||
| 1 | 1 | 0 | ||
| 1 | 1 | 1 |
| A | B | Cin | S (bit somme) | Cout (bit retenue) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
En combinant plusieurs circuits "additionneur", on obtient des additionneurs capables d'additionner des nombres codés sur plusieurs bits.
Algèbre booléenne¶
Nous venons d'utiliser l'algèbre de Boole, du nom du mathématicien britannique George Boole (1815 - 1864).
Propriétés de l'algèbre booléenne¶
Propriétés de l'algèbre booléenne
Ces propriétés sont utiles notamment pour simplifier certaines expressions booléennes.
- opérateur involutif : \(\neg(\neg x) = x\)
- élément neutre : \(1 \wedge x = x\) ou \(0 \vee x = x\)
- élément absorbant : \(0 \wedge x = 0\) ou \(1 \vee x = 1\)
- idempotence : \(x \wedge x = x\) ou \(x \vee x = x\)
- complément : \(x \wedge (\neg x) = 0\) ou \(x \vee (\neg x) = 1\)
- commutativité : \(x \wedge y = y \wedge x\) ou \(x \vee y = y \vee x\)
- associativité : \(x \wedge ( y \wedge z) = (x \wedge y) \wedge z\) ou \(x \vee ( y \vee z) = (x \vee y) \vee z\)
- distributivité : \(x \wedge ( y \vee z) = (x \wedge y) \vee (x \wedge z)\) ou \(x \vee ( y \wedge z) = (x \vee y) \wedge (x \vee z)\)
- loi de Morgan : \(\neg(x \wedge y) = \neg x \vee \neg y\) ou \(\neg(x \vee y) = \neg x \wedge \neg y\)
Vous noterez que certaines de ces propriétées rappellent celles de l'addition et de la multiplication sur \(\mathbb{Z}\). Si vous voulez en savoir plus, vous pouvez par exemple regarder cette vidéo :
Structures algébriques (anneaux en particulier)
Par ailleurs, ces règles sont définies d’une manière particulière, si on définit une règle pour un des deux opérateurs, on peut obtenir la règle pour l’autre opérateur en interchangeant 1 avec 0 et \(\wedge\) avec \(\vee\). Ce constat qui n'a l'air de rien est très important en algèbre, si un jour vous entendez parler de dualité alors j'espère que vous aurez un petit moment de nostalgie en pensant à ce cours.