Composition opérations

Identification

Infoforall

3 - Composition de portes logiques


Nous avons vu comment réaliser des portes logiques avec des transistors.

On peut notamment faire des NON (NOT) et des NON-ET (NAND) avec des transistors.

Nous avons vu les opérations basiques ET (AND), OU (OR), NON-OU (NOR).

Voyons maintenant les XOR !

Les XOr : le bleu, le rouge et le gris

Evaluation ✎ :

Documents de cours : open document ou pdf

1 - NOT AND NAND OR NOR

a b s a s ET & OU ≥1 & ≥1 =1 1 5V True 0V False 0V False 5V True Vcc = 5V 0V

Commençons par un rappel : les 5 fonctions de base.

NON NOT

Il s'agit de la fonction inversion.

Voici la table de vérité du NON :

a NOT a
0 1
1 0
AND NAND

Le AND vaut dire : Toutes les entrées d'un coup.

On se souviendra qu'en tant que fonction logique le NAND est juste une inversion de AND.

a NAND b = NOT (a AND b)

a NAND b = a.b

a b a AND b
0 0 0
0 1 0
1 0 0
1 1 1
a b a NAND b
0 0 1
0 1 1
1 0 1
1 1 0
OR NOR

La fonction OR veut dire : Au moins l'une des entrées.

On se souviendra qu'en tant que fonction logique le NOR est juste une inversion de OR.

a NOR b = NOT (a OR b)

a NOR b = a+b

a b a OR b
0 0 0
0 1 1
1 0 1
1 1 1
a b a NOR b
0 0 1
0 1 1
1 0 1
1 1 0
Symboles européens / américains ANSI
NOT Schéma du NON ANSI : un TRIANGLE avec un point au bout
AND Schéma du AND ANSI : un AND
NAND Schéma du NAND ANSI : un AND avec un point au bout
OR Schéma du OR ANSI : un OR
NOR Schéma du NOR ANSI : un OR avec un point en sortie

2 - XOR et XNOR

Il nous reste à voir un cas : le cas où on veut bien une entrée à 1 seulement. Pas 2, pas 3, pas 0. Une sortie uniquement.

C'est ça le XOR.

Son nom en français : le OU EXCLUSIF. On comprend mieux l'histoire du X du coup !

01° Compléter la table de vérité du XOR en utilisant simplement la définition précédente.

Valeur de a Valeur de b a XOR b
0 0 ?
0 1 ?
1 0 ?
1 1 ?

...CORRECTION...

Valeur de a Valeur de b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

02° Compléter la table de vérité du XOR à 3 entrées en utilisant simplement la définition précédente.

Valeur de a Valeur de b Valeur de c XOR
0 0 0 ?
0 0 1 ?
0 1 0 ?
0 1 1 ?
1 0 0 ?
1 0 1 ?
1 1 0 ?
1 1 1 ?

...CORRECTION...

Valeur de a Valeur de b Valeur de c XOR
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

Que fait cette fonction XOR si nous n'avons que deux booléens a et b ?

Valeur de a Valeur de b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

Le XOR permet de vérifier que les deux valeurs sont différentes !

En gros, a XOR b revient à écrire en Python a != b.

03° Tester le code a != b dans le cas particulier des variables a et b ne pouvant valoir que 0 ou 1. Conclusion.

Valeur de a Valeur de b a != b
0 0 ?
0 1 ?
1 0 ?
1 1 ?

...CORRECTION...

Valeur de a Valeur de b a != b
0 0 0
0 1 1
1 0 1
1 1 0

Et si voulons au contraire vérifier une EGALITE ?

Comme la différence est le complément de l'égalité, il suffit de complémenter le XOR.

On écrira que NOT(a XOR b) = a XNOR b.

Valeur de a Valeur de b a XNOR b
0 0 1
0 1 0
1 0 0
1 1 1

Comme vous pouvez le voir, nous obtenons bien 1 lorsque les deux entrées sont identiques (11 ou 00).

Pour information : Symbole dans un schéma logique

On symbolise le XOR comme un carré enplaçant = 1 pour indiquer que seul l'un des deux peut être VRAI.

On trouve également le symbole suivant qui correspond à la norme ANSI américaine :

Schéma du XOR
XOR ANSI, image dans le domaine public, réalisée par jjbeard, récupérée sur Wikipedia

Pour information : Symbole dans un schéma logique

On symbolise le XNOR comme un XOR complémenté.

On trouve également le symbole suivant qui correspond à la norme ANSI américaine :

Schéma du XOR
XOR ANSI, image dans le domaine public, réalisée par jjbeard, récupérée sur Wikipedia

3 - Technologie NAND

Je vous avais signalé que la porte NAND était complète : on peut réaliser toutes les autres fonctions avec un système qui ne contient que des portes NAND.

Nous allons montré ici que ça fonctionne bien.

Du point de vue du programme, cela va vous permettre de complèter des tables de vérité.

Trouver rapidement la réponse d'un NAND, inverse du AND
a b a NAND b
0 0 1
0 1 1
1 0 1
1 1 0

Le AND n'est VRAI que lorsque toutes les entrées sont à VRAI.

Le NAND n'est FAUX que lorsque toutes les entrées sont à VRAI. Le plus rapidement est donc de trouver rapidement ce cas unique (1-1), de placer 0 en sortie. Et de mettre 1 dans les autres cas.

NOT avec des NAND

Exemple avec le NOT qu'on peut construire ainsi : on relie les deux entrées d'une NAND

a a a s

On a donc bien une réponse qui vaut NON a.

04° Compléter la table de vérité suivante. Obtient-on bien la réponse d'un NON ?

a a AND a a NAND b
0 ? ?
1 ? ?

...CORRECTION...

a a AND a a NAND b
0 0 1
1 1 0

La réponse finale correspond bien à un NOT.

Créer un AND avec un NAND

Comment faire un AND avec des NAND ?

Il suffit de prendre une NAND et de complémenter (inverser) le résultat.

a AND b = NOT (a NAND b)

Le premier NAND permet de réaliser une fonction NAND.

Le second NAND permet de réaliser une fonction NOT.

Avec des explications sur les shémas :

a b a NAND b a NAND b NOT(a NAND b)

La sortie est NOT(a NAND b) = a AND b

05° Compléter la table de vérité suivante. Obtient-on bien la réponse d'un AND ?

Valeur de a Valeur de b a NAND b NOT(a NAND b)
0 0 ??
0 1 ??
1 0 ??
1 1 ??

...CORRECTION...

Valeur de a Valeur de b a NAND b NOT(a NAND b)
0 0 10
0 1 10
1 0 10
1 1 01

La réponse de la sortie finale correspond bien à celle d'un AND.

Créer un OR avec un NAND

Comment faire un OR avec des NAND ?

Il faut :

  • Inverser l'entrée a
  • Inverser l'entrée b
  • Appliquer NAND sur ces deux réponses

Les deux NAND de gauche permettent de réaliser une fonction NOT.

Le NAND de droite permette juste de réaliser une fonction NAND.

Avec quelques explications :

a b NOT a NOT b NOT a NAND NOT b

La sortie est donc NOT a NAND NOT b = a OR b

06° Compléter la table de vérité suivante. Obtient-on bien la réponse d'un OU ?

a b NOT a NOT b NOT a NAND NOT b
0 0 ? ? ?
0 1 ? ? ?
1 0 ? ? ?
1 1 ? ? ?

...CORRECTION...

a b NOT a NOT b NOT a NAND NOT b
0 0 1 1 0
0 1 1 0 1
1 0 0 1 1
1 1 0 0 1

La réponse de la sortie finale correspond bien à celle d'un OR.

Règles de propriété

Vous savez que l'exposant est prioritaire sur le reste.

Vous savez que la multiplication est prioritaire sur l'addition.

Et le NOT AND et OR alors ?

Et bien, c'est pareil :

La fonction prioritaire est le NOT.

Le AND est prioritaire sur le OR.

Pourquoi ?

On peut écrire a AND b de cette façon a . b

On peut écrire a OR b de cette façon a + b

07° Un élève écrit ceci en python : not a or not b and c.

A quoi correspond en réalité cette opération ?

  • A : (not a) or (not (b and c))
  • B : not (a or not (b and c))
  • C : not (a or not b) and c
  • D : (not a) or ((not b) and c)

...CORRECTION...

not a or not b and c

On commence par mettre des parenthèses autour des not, qui sont prioritaires.

(not a) or (not b) and c

Ensuite, on sait que le AND est prioritaire sur le OR.

(not a) or (not b) and c

La réponse de la sortie finale correspond bien à celle d'un OR.

(not a) or ((not b) and c)

C'est donc la réponse D.

Voici quelques exemples de réponses :

>>> a = True >>> b = False >>> c = False >>> not a or not b and c False # C'est la réponse attendue >>> (not a) or (not (b and c)) True # Réponse A : non valide >>> not (a or not (b and c)) False # Réponse B : peut-être valide >>> not (a or not b) and c False # Réponse C : peut-être valide >>> (not a) or ((not b) and c) False # Réponse D : peut-être valide # On change de configuration >>> a = False >>> not a or not b and c True # C'est la réponse attendue >>> (not a) or (not (b and c)) True # mais A est non valide >>> not (a or not (b and c)) False # Réponse B : non valide >>> not (a or not b) and c False # Réponse C : non valide >>> (not a) or ((not b) and c) True # Réponse D : peut-être valide

Voilà, on vient de voir qu'on peut noter cette expression de deux façons :

  • not a or not b and c
  • (not a) or ((not b) and c)

Les parenthèses ne sont pas obligatoires, mais permettent à quelqu'un qui ne fait pas attention de ne pas se tromper.

Comme avec  5 + 2 * 5  qui est équivalent à  5 + (2 * 5) .

Créer un NOR avec des NAND

C'est facile : on prend le OU précédent est on le complémente !

La sortie est donc NOT( a OR b) = a NOR b

Créer un XOR avec des NAND

C'est plus complexe cette fois : il faut 4 NAND !

Avec quelques explications :

a b a b a NAND b a NAND b a NAND (a NAND b) (a NAND b) NAND b

La sortie de la dernière NAND est donc (a NAND (a NAND b)) NAND ((a NAND b) NAND b) = a XOR b

08° Remplir les différentes tables de vérité ci-dessous permettant de vérifier la combinaison précédente.

On commence par le a NAND b :

(a NAND (a NAND b)) NAND ((a NAND b) NAND b) = a XOR b

Ensuite, on calcule les termes de chaque côté du NAND central :

a b a NAND b a
NAND
(a NAND b
(a NAND b)
NAND
b
(a NAND (a NAND b))
NAND
((a NAND b) NAND b)
0 0 ? ? ? ?
0 1 ? ? ? ?
1 0 ? ? ? ?
1 1 ? ? ? ?

...CORRECTION...

Premier Test : le NAND initial

a b a NAND b a
NAND
(a NAND b
(a NAND b)
NAND
b
(a NAND (a NAND b))
NAND
((a NAND b) NAND b)
0 0 1 ? ? ?
0 1 1 ? ? ?
1 0 1 ? ? ?
1 1 0 ? ? ?

Deuxième Test : le NAND plus complexe avec a

a b a NAND b a
NAND
(a NAND b
(a NAND b)
NAND
b
(a NAND (a NAND b))
NAND
((a NAND b) NAND b)
0 0 1 1 ? ?
0 1 1 1 ? ?
1 0 1 0 ? ?
1 1 0 1 ? ?

3e Test : le NAND plus complexe avec b

a b a NAND b a
NAND
(a NAND b
(a NAND b)
NAND
b
(a NAND (a NAND b))
NAND
((a NAND b) NAND b)
0 0 1 1 1 ?
0 1 1 1 0 ?
1 0 1 0 1 ?
1 1 0 1 1 ?

Dernier test : on cherche le 1 1 dans les deux NAND complexes :

a b a NAND b a
NAND
(a NAND b
(a NAND b)
NAND
b
(a NAND (a NAND b))
NAND
((a NAND b) NAND b)
0 0 1 1 1 0
0 1 1 1 0 1
1 0 1 0 1 1
1 1 0 1 1 0

C'est bien un XOR : on a VRAI que si l'UNE des entrées a b est VRAI.

Créer un XNOR avec des NAND

On prend le XOR précédent et on complémente.

5 NAND pour faire une seule fonction ? Peut-on faire mieux ?

Vous vous doutez bien qu'il y a derrière un ensemble de théories mathématiques permettant d'éviter de remplir ces tables et de simplement démontrer que tout ceci est vrai.

Cette théorie est hors-programme en NSI mais vous pouvez aller voir les fichies qui en traitent sur ce site (ou un autre).

On notera également qu'on peut faire la même chose avec le NOR : c'est une fonction logique complète : on peut créer toutes les autres fonctions logiques en utilisant des combinaisons de NOR.

4 - Application pratique : égalité

Comment faire un ordinateur 8 bits pour comparer 8 bits ? Il utilise un XNOR sur chacun des bits. Si la valeur de sortie est 1111 1111, c'est que les deux octets sont identiques, bit à bit.

On peut utiliser 8 XNOR en même temps.

Les XNOR comparent alors les bits de même poids et renvoie pour chaque couple 1 si c'est 00 ou 11 qui est reçu. Et voilà.

0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0

La sortie n'étant pas 1111 1111, on pourra dire que les deux entrées sont différentes.

L'ensemble des 8 conducteurs rouges consistuent ce qu'on nomme un BUS. On voit ici qu'on peut envoyer et traiter 8 bits d'un seul coup.

On dit qu'on peut traiter 8 bits en parallèle. Cette opération constitue donc UNE opération.

Si on veut faire de même avec des données de 16 bits, il faudra au moins DEUX opérations mémoires : on compare d'abord les 8 premiers bits, on stocke en mémoire et on ramène les 8 bits suivants.

09° Un processeur 16 bits (bus, mémoire, UAL, tout fonctionne avec 16 bits d'un coup) est-il meilleur qu'un processeur 8 bit pour traiter des données de 8 bits maximum ?

...CORRECTION...

Et bien non : dans les deux cas, chaque opération correspondra à une opération basique de l'UAL.

10° Un processeur 16 bits (bus, mémoire, UAL, tout fonctionne avec 16 bits d'un coup) est-il meilleur qu'un processeur 8 bit pour traiter des données de 16 bits maximum ?

...CORRECTION...

Cette fois, c'est oui car le processeur 16 bits utilisera toujours une seule opération sur chaque calcul. Le processeur 8 bits devra lui décomposer les opérations en plusieurs sous-opérations lorsqu'il devra traiter des données de plus de 8 bits. Il va donc être plus lent.

On retiendra donc qu'un ordinateur 128 bits est plus rapide qu'un ordinateur 64 bits si on le fait travailler sur des données de plus de 64 bits.

11° Vous ne travaillez qu'avec des données de 64 bits maximum. On vous propose un ordinateur double-coeur (2 processeurs) de 64 bits ou un ordinateur de 128 bits. Que choisir ? On considère que les deux ordinateur ont la même fréquence de traitement.

...CORRECTION...

Cette fois, ça va dépendre du programme : est-il capable d'utiliser le double-coeur ou pas ?

Si le programme gère la capacités double-coeur, autant prendre le 64 bits.

Sinon, ça ne changera pas grande chose. Les 128 bits consommera peut-être un peu plus d'énergie.

12° Vous ne travaillez qu'avec des données de 64 bits maximum. On vous propose un ordinateur de 64 bits 3 Ghz ou un ordinateur de 128 bits 2 GHz. Que choisir ?

...CORRECTION...

Comme les données sont sur 64 bits, la différence n'est pas sur le nombre de bits traitables en parallèle.

Pour contre, l'ordinateur 64 bits traite 3 milliards d'opérations par seconde. Il est plus rapide que le 128 bits qui n'en traite que 2 milliards.

13° Vous ne travaillez qu'avec des données de 128 bits au maximum. On vous propose un ordinateur de 64 bits 3 Ghz ou un ordinateur de 128 bits 2 GHz. Que choisir ?

...CORRECTION...

Cette fois, ça va dépendre du nombre de données réelleemnt supérieures à 128 bits. Si elles sont nombreuses, autant partir sur l'ordinateur 128 bits, moins rapide mais n'effectuant qu'une opération sur les données de 128 bits.

L'ordinateur de 64 bits est plus rapide (3 GHz) mais devra faire plusieurs sous-opérations pour les données de plus de 64 bits.

5 - Addition

Regardons maintenant comment un ordinateur parvient à faire des additions alors qu'il ne sait gérer que les 0, les 1 et les fonctions logiques ET, OU, NAND ...

Commençons par regarder ce que donne la somme de a + b, a et b étant des nombres binaires.

a b a + b
0 0 0
0 1 1
1 0 1
1 1 10

Séparons le résultat final sur deux colonnes : une pour la retenue éventuelle et une pour l'unité.

a b Retenue de a + b Unité de a + b
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

14° Quelle fonction logique correspond à la colonne de la retenue ? Quelle fonction logique correspond à la colonne de l'unité ?

...CORRECTION...

a b a AND b a XOR b
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

Et voilà : pour réaliser une addition, il suffit d'un ET et d'un OU EXCLUSIF.

L'addition est donc bien une opération basique réalisable par l'UAL.

Bien entendu, si on travaille sur plusieurs bits, l'addition sera une opération basique uniquement si le processeur travaille avec le bon nombre de bits.

Pour un processeur 8 bits, additionner des nombres supérieurs à 255 nécessitent plus d'opérations puisqu'il doit décomposer cela en plusierus sous-opérations.

Demi-additionneur

C'est le nom donné au circuit qui additionne deux bits sans savoir gérer une éventuelle retenue déjà en mémoire.

b a S (somme) R (retenue)

Si on veut pouvoir faire l'addition de a et b et d'une retenue d'entrée re précédente éventuelle, il faut un disposif plus complexe qu'on nomme alors un additionneur.

On commencera alors par additionner la retenue au résultat précédent (mais on ne gère pas correctement pour l'instant la retenue finale).

b a re S1 S R1 R2

Nous voilà bien embêtés avec une somme mais deux retenues !

Pour finaliser, nous allons utiliser un simple OU sur les deux retenues.

b a re S1 S R1 R2 R

15° Compléter le table de vérité suivant qui reprend l'exemple de l'addition.

re a b S1=
a XOR b
S=
S1 XOR re
R1=
a AND b
R2=
S1 AND re
R=
R1 OR R2
0 0 0 ? ? ? ? ?
0 0 1 ? ? ? ? ?
0 1 0 ? ? ? ? ?
0 1 1 ? ? ? ? ?
1 0 0 ? ? ? ? ?
1 0 1 ? ? ? ? ?
1 1 0 ? ? ? ? ?
1 1 1 ? ? ? ? ?

...CORRECTION...

re a b S1=
a XOR b
R1=
a AND b
R2=
S1 AND re
R=
R1 OR R2
S=
S1 XOR re
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1
0 1 0 1 0 0 0 1
0 1 1 0 1 0 1 0
1 0 0 0 0 0 0 1
1 0 1 1 0 1 1 0
1 1 0 1 0 1 1 0
1 1 1 0 1 0 1 1

Comme dans le cas précédent de la comparaison, un processeur de 128 bits peut faire en une opération une addition de deux données de 128 bits.

Sur une machine 64 bits, il faudra décomposer les choses en deux opérations et stocker les résultats intermédiaires.

6 - Complément Python

Dans un langage de programmation, les variables contiennent habituellement autre chose que 0 ou 1. La plupart des variables ne sont pas des variables booléennes. Alors, comment ça fonctionne ?

Voici les opérateurs classiques qui nous avons déjà rencontré :

Python JS
NON - NOT not a !a
ET - AND a and b a && b
NON-ET - NAND not(a and b) !(a && b)
OU - OR a or b a || b
NON-OU - NOR not(a or b) !(a || b)
OU EXCLUSIF - XOR (a and not(b)) or (b and not(a))
ou juste
a != b
(a && !b) or (b && !a)
ou juste
a != b

Sachez qu'il existe des opérateurs permettant de réaliser directement des opérations sur les bits. On parle d'opérateur logique bit à bit. Pourquoi ? Car ils réalisent ce que nous avons montré plus haut sur l'égalité par exemple.

En quoi consiste les opérateurs logiques bit à bit ? On applique la fonction sur les bits de la même colonne :

16° Voici un court programme qui affiche le résultat d'un ET / AND logique appliqué bit à bit sur deux entrées. Utiliser le programme pour visualiser les contenus de a, b et c. Les bits de c doivent valoir 1 si les bits respectifs de a et b à cet endroit sont de 1 également.

Remarquez bien que a and b donne simplement True : a est différent de 0 et b aussi. Ici, on travaille bit à bit. Expliquer pourquoi il n'y a qu'un seul bit à 1 dans c.

1 2 3 4 5 6 7 8 9
a = 45 b = 240 c = a & b # ET bit à bit bits = 16 print(f"a : {a:0{bits}b}") print(f"b : {b:0{bits}b}") print(f"a & b : {c:0{bits}b}")

...CORRECTION...

a : 0000000000101101 b : 0000000011110000 a & b : 0000000000100000

17° Voici un court programme qui affiche le résultat d'un OU / OR logique appliqué bit à bit sur deux entrées. Sans utiliser le programme tenter de voir ce que va s'afficher pour c. Utiliser le programme pour vérifier.

Remarquez bien que a or b donne simplement True : a et b sont différents de 0 et b aussi.

a : 0000000000101101 b : 0000000011110000 a | b : ----------------
1 2 3 4 5 6 7 8 9
a = 45 b = 240 c = a | b # OU bit à bit bits = 16 print(f"a : {a:0{bits}b}") print(f"b : {b:0{bits}b}") print(f"a | b : {c:0{bits}b}")

...CORRECTION...

a : 0000000000101101 b : 0000000011110000 a | b : 0000000011111101
On peut afficher | en utilisant la combinaison ALT-Gr + 6.

Nous verrons en terminale qu'on peut très facilemnet faire de la cryptographie avec un OU EXCLUSIF.

On prend une valeur a, par exemple un octet, compris entre 0 et 255.

On lui applique une clé b de 8 bits par exemple : une clé dont la valeur est dans [0;28-1]

Comment ? Simplement en calculant bit à bit a XOR b. En Python, c'est a ^ b.

18° Utiliser le programme suivant sur votre octet. Noter la valeur finale de l'octet.

1 2 3 4 5 6 7 8 9 10
a = 45 # octet à codé b = 240 # clé c = a ^ b # XOR bit à bit bits = 8 print(f"a : {a:0{bits}b}") print(f"b : {b:0{bits}b}") print(f"a ^ b : {c:0{bits}b}") print(f"L'octet contient maintenant {c}")

...CORRECTION...

a : 00101101 b : 11110000 a ^ b : 11011101 L'octet contient maintenant 221

On voit donc qu'un octet initialement à 45 est transformé en 221.

19° Utiliser le programme sur 221 avec la même clé. Quel est le résultat ?

...CORRECTION...

a : 11011101 b : 11110000 a ^ b : 00101101 L'octet contient maintenant 45

Et voilà, il s'agit du principe d'un cryptage par clé symétrique : on utilise la même clé pour encoder le message et décoder le message. Bien entendu, avec un clé de 8 bits, notre cryptage n'est pas très performant !

En Terminale, nous verrons comment crypter l'intégralité d'un texte (et plus globalement n'importe quel contenu : une photo, un film...

Voici pour cette introduction en deux temps. On retiendra donc qu'on peut expliquer les opérations de l'UAL par l'utilisation de circuits électroniques réagissant comme des fonctions logiques spécifiques : NOT, AND, NAND, OR, NOR, XOR, XNOR.

Ces fonctions peuvent être réalisées en combinant un ensemble de porte NOR ou NAND.

De quoi sont composées fondamentalement les portes NAND et NOR : de deux transistors.

Activité publiée le 07 03 2020
Dernière modification : 07 03 2020
Auteur : ows. h.