Section 2.5
Le système binaire
Dans cette section, nous allons découvrir comment représenter les nombres naturels (0, 1, 2, 3, etc.) à l'aide uniquement des symboles 0 et 1, en utilisant un système de notation qu'on appelle le système binaire. Ce système de notation nous sera utile pour représenter les nombres dans un circuit. C'est sur ce système que se base la représentation des nombres dans un ordinateur.
Le système décimal
Avant de plonger dans le système binaire, il est important de comprendre comment les nombres sont représentés dans notre système de numération (d'écriture des nombres) usuel, le système décimal.
Dans le système décimal, on utilise dix symboles différents pour représenter les nombres. Ces symboles sont les chiffres de 0 à 9. Pour représenter un nombre, on utilise une notation positionnelle : On écrit le nombre en utilisant une suite de symboles, chaque symbole représentant une valeur différente qui dépend de la position du symbole dans le nombre. Pour obtenir le nombre représenté par une suite de symboles, on additionne les valeurs de chaque symbole.
Dans un nombre représenté en décimal, le chiffre situé tout à droite représente les unités. Ce chiffre a un poids de un. Le chiffre situé à sa gauche représente les dizaines et a un poids de dix. Viennent ensuite les centaines, les milliers, etc.
Le poids de chaque chiffre dépend de sa position. On peut calculer le poids d'un chiffre en utilisant la formule 10n, où n est la position du chiffre depuis la droite, en commençant à compter à partir de 0. La position d'un chiffre correspond au nombre de chiffres à sa droite.
♣︎ Exemple
Prenons un exemple de nombre représenté en décimal, par exemple le nombre 2638.
Le nombre 2638 est composé de quatre chiffres : 2, 6, 3 et 8.
Le chiffre le plus à droite, de poids le plus faible, est le chiffre 8. Ici, le chiffre 8 a un poids de 100 = 1. Ce chiffre contribue donc de 8 × 1 = 8 à la valeur du nombre.
Le deuxième chiffre depuis la droite est le chiffre 3. À cette position, le poids est de 101 = 10. En effet, il y a 1 chiffre à sa droite. Ce chiffre contribue donc de 3 × 10 = 30 à la valeur du nombre.
Après vient le chiffre 6, en position 2 (car il y a 2 chiffres à sa droite). À cette position, le poids est donc de 102 = 100. Le chiffre contribue de 6 × 100 = 600 à la valeur du nombre.
Enfin, le chiffre 2, en position 3, a un poids de 103 = 1000. Il contribue donc de 2 × 1000 = 2000 à la valeur du nombre.
En additionnant les valeurs de chaque chiffre, on obtient la valeur totale du nombre : 8 + 30 + 600 + 2000 = 2638.
Le système décimal, qui utilise 10 symboles différents, est aussi appelé la numération en base 10, ou tout simplement base 10. On dit que la base du système décimal est 10. Les puissances de la base donnent le poids des différentes positions.
Décomposition canonique
On appelle la décomposition canonique d'un nombre la représentation de ce nombre sous forme de somme de puissances de la base, soit dix en décimal.
♣︎ Exemple
La décomposition canonique de 2638 en base 10 est :
2 × 103 + 6 × 102 + 3 × 101 + 8 × 100
On peut aussi écrire cette décomposition de la manière suivante :
2 × 1000 + 6 × 100 + 3 × 10 + 8 × 1
Notez que par convention d'écriture les multiplications s'effectuent avant les additions. On peut donc se passer de parenthèses dans l'écriture de la décomposition canonique d'un nombre.
✎ Auto-évaluation
Le système décimal est un système de numération qui utilise symboles différents qu'on appelle des .
Le système décimal est un système de numération : Chaque chiffre a un qui dépend de sa position dans la représentation du nombre.
✎ Auto-évaluation
La décomposition canonique de 843 en base 10 est : × 100 + × 10 + × 1.
Le système binaire
Tout comme le système décimal, le système binaire utilise une notation positionnelle. À la différence du système décimal, le système binaire utilise deux symboles différents pour représenter les nombres, et non dix. Le système binaire est donc appelé la numération en base 2, ou tout simplement base 2.
Les deux symboles utilisés dans le système binaire sont le 0 et le 1. On appelle un tel symbole un chiffre binaire, ou bit (abréviation de binary digit, en anglais littéralement chiffre binaire).
Dans cette section, nous allons apprendre à lire des nombres écrits en binaire, compter en binaire, ainsi que d'écrire des nombres arbitraires en binaire. Enfin, nous allons découvrir comment additionner des nombres écrits en binaire. Toutes ces opérations nous permettront de comprendre comment fonctionne le système binaire et ainsi de pouvoir faire usage de cette façon de représenter les nombres lors de la conception de circuits logiques ainsi que de programmes plus tard dans le cours.
Lire en binaire
En notation binaire, les nombres sont représentés sous forme de séquences de bits (de 0 et de 1). Comme en base 10, chaque symbole a un poids qui lui est propre et qui dépend de la position du symbole. Cependant, contrairement à la base 10, les poids sont basés sur les puissances de deux, non de dix.
! Remarque
Les puissances de deux sont les nombres de la forme 2n, pour n un nombre naturel (0, 1, 2, etc.). La première puissance de deux, 20, vaut 1. Chaque puissance de deux suivante est simplement le double de la précédente.
Les dix premières puissances de 2 sont donc 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.
Comme dit à l'instant, chaque bit a un poids qui est une puissance de deux qui dépend de la position du bit. Le bit le plus à droite a un poids de 1, puis le bit à sa gauche a un poids de 2, le suivant de 4, puis 8 et ainsi de suite, en doublant à chaque étape.
Pour calculer la valeur d'un nombre écrit en binaire, il suffit d'additionner les valeurs de chaque bit. La valeur d'un bit est égale au poids du bit multiplié par 0 ou par 1, selon que le bit est égal à 0 ou 1.
Cette addition correspond à la décomposition canonique en base 2 du nombre.
♣︎ Exemple
Prenons par exemple la séquence de bits 1101. Ce séquence de bits correspond à un nombre écrit en binaire, que nous allons calculer.
La décomposition canonique de 1101 en base 2 est :
1 × 23 + 1 × 22 + 0 × 21 + 1 × 20
Ou encore :
1 × 8 + 1 × 4 + 0 × 2 + 1 × 1
En effectuant, le calcul (8 + 4 + 0 + 1), on obtient la valeur du nombre: 13, ici exprimé en notation décimale.
★ À essayer
Entrez un nombre écrit en binaire ci-dessous et appuyez sur le bouton pour calculer sa valeur en décimal.
! Remarque
Tout comme en base 10, il est possible de rajouter des zéros à gauche d'un nombre écrit en binaire. Cela n'a aucune influence sur la valeur du nombre, en effet la valeur d'un bit à 0 est toujours de 0, et ce peu importe la position du bit.
Par exemple, les séquences de bits 1101 et 01101 représentent le même nombre.
En vérité, c'est comme il y avait un nombre infini de zéros à gauche du nombre 1101, et que l'on avait décidé de ne pas les écrire. Il n'est pas faux d'en écrire un certain nombre, ce sera même parfois demandé comme on le verra plus tard dans le cours. À noter que, comme il y en a une infinité, il est impossible de tous les écrire.
Décomposer à l'aide d'un tableau
Lorsque l'on cherche à savoir la valeur d'un nombre écrit en binaire, il est parfois plus simple de s'aider d'un tableau doté de trois lignes. Sur la ligne du milieu, on note les bits du nombre. Ensuite, on note le poids de chaque bit en dessus de celui-ci. En dessous de chaque bit, on écrit la valeur du bit, qui corresponds à la multiplication du poids du bit par le bit lui-même (soit 0, soit 1).
♣︎ Exemple
Prenons par exemple la séquence de bits 10110101. Ce séquence de bits correspond à un nombre écrit en binaire, que nous allons calculer à l'aide du tableau ci-dessous.
| Poids | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| Bit | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| Valeur | 128 | 0 | 32 | 16 | 0 | 4 | 0 | 1 |
La première ligne du tableau représente le poids de chaque bit. Le poids d'un bit est 2 à la puissance de la position du bit, le bit le plus à droite étant à la position 0. La deuxième ligne contient les bits eux-mêmes. Finalement, la troisième ligne contient la valeur de chaque bit, qui est le produit du poids du bit par le bit lui-même.
Si l'on prend la somme de toutes les valeurs des bits, on obtient la valeur du nombre. Dans notre exemple, la valeur du nombre est donc de 128 + 32 + 16 + 4 + 1 = 181.
! Remarque
En binaire, il est très simple de savoir si un nombre est pair ou impair. Pour cela, il suffit de regarder le bit le plus à droite, le bit de poids 1. Si ce bit est à 1, alors le nombre est impair, sinon il est forcément pair.
De plus, en binaire, il est très simple de multiplier un nombre par 2. Il suffit pour cela de décaler tous les bits du nombre d'une position vers la gauche, ce qui revient simplement à ajouter un 0 tout à droite.
✎ Auto-évaluation
En binaire, la séquence de bits 11001 représente le nombre (exprimé ici en système décimal).
✎ Auto-évaluation
En binaire, la séquence de bits 110010010010001 correspond à un nombre .
Compter en binaire
Maintenant que nous comprenons mieux les principes de base de la notation binaire des nombres, ainsi que comment lire des nombres exprimés en binaire, la deuxième opération que nous allons aborder est celle de compter en binaire.
Comme dans le système décimal, on commence à compter à partir de zéro. Dans ce cas, comme dans le système décimal, nous disposons directement d'un symbole pour représenter le zéro, il s'agit du bit 0.
0
Après le zéro, vient le un, qui est lui aussi représenté par un unique symbole, le bit 1 :
1
Après cela, les choses se compliquent un peu. En effet, il n'y a pas de symbole pour représenter le nombre deux. Pour cela, nous allons devoir utiliser plus d'un symbole. Pour écrire le nombre deux en binaire, on écrit :
10
En effet, si l'on décompose la séquence de bits, on obtient bien : 1 × 21 + 0 × 20 = 2.
! Remarque
Attention, il est tentant de prononcer le nombre binaire 10 comme « dix ». Il est important de faire la distinction entre la notation et le nombre qui est représenté. Lorsqu'on dit « dix », on parle du nombre dix (qui est représenté par la suite de chiffres 10 en décimal). En binaire la notation 10 a un autre sens : elle représente le nombre deux. Pour ce fait, on préférera dire « un, zéro » pour se référer à la notation ou simplement « deux » pour se référer au nombre.
Vient ensuite le nombre trois. Pour écrire le nombre trois en binaire, on écrit :
11
En effet, on a bien : 1 × 21 + 1 × 20 = 3. Vient ensuite le nombre quatre, qui est représenté par :
100
On peut continuer ainsi indéfiniment, par un processus que nous allons discuter sous peu. Voici les 16 premiers nombres écrits en décimal et en binaire :
Vous pouvez vérifier par vous-même que si vous tentez de lire les nombres en binaire (à droite), vous obtenez bien les nombres exprimés en décimal (à gauche).
Étant donné la représentation d'un nombre en binaire, comment obtenir la représentation binaire du nombre suivant ? C'est ce que nous allons voir à présent en abordant la notion d'incrémentation.
Incrémenter
On appelle incrémenter un nombre le fait d'ajouter 1 à ce nombre. Nous allons à présent voir comment s'y prendre pour incrémenter un nombre en binaire.
Pour incrémenter un nombre représenté en base 2, on commence par se placer sur le bit le plus à droite. Si ce bit est un 0, on le remplace simplement par un 1 et on recopie le reste des bits.
Si le bit est un 1, on le remplace par un 0 et on recommence la même procédure au bit suivant, une position plus à gauche.
Si on vient à dépasser le bit le plus à gauche, et ce sans avoir pu remplacer un 0 par un 1, on considère qu'il y a un bit à 0 sur la gauche, que l'on peut donc remplacer par un 1.
La procédure d'incrémentation peut être représentée par le schéma suivant :
! Remarque
Comme nous allons le voir dans la suite du cours, nous appelons ce genre de procédure un algorithme. Un algorithme est une suite finie d'instructions non-ambigües qui permet de résoudre un problème. Le problème en question ici est celui de déterminer la représentation binaire du successeur d'un nombre donné en binaire.
L'algorithme ci-dessus n'est pas le seul et unique algorithme possible pour incrémenter un nombre binaire. Ci-dessous est présenté un autre algorithme. Certains préfèrerons l'un, d'autres l'autre.
Algorithme alternatif
Pour incrémenter un nombre binaire, on peut aussi commencer par chercher le 0 le plus à droite dans le nombre. On remplace le 0 à cette position par un 1. Tout ce qui est à droite de cette position est remplacé par des 0, et tout ce qui est à gauche est recopié tel quel.
Comme pour l'algorithme précédent, si le nombre ne contient que des 1, on considère qu'il contient un 0 tout à gauche.
Comprendre l'algorithme
Pour comprendre l'algorithme d'incrémentation, il est important de réaliser que la valeur d'un bit dépend de sa position.
Pour incrémenter un nombre, on souhaite ajouter 1 à ce nombre. Il faudrait donc mettre un 1 à la position la plus à droite (celle de poids 1). Si cette position est inoccupée (contient un 0), on met un 1 et le tour et joué. En effet, mettre un 1 à cette position correspond à ajouter 1 au nombre.
Cependant, si cette position est déjà occupée (contient un 1), on doit trouver une autre position pour notre 1. Cependant, c'est là la seul position de poids 1 disponible. Pour sortir de cette impasse, on enlève ce bit à 1 de cette position et on ajoute sa valeur à la valeur que l'on souhaite ajouter au nombre.
Ainsi, à la place d'ajouter 1 au nombre, on cherche maintenant à ajouter 2. On regarde donc la position de poids 2. Si elle est inoccupée, on y met simplement un 1. Sinon, on enlève le bit à 1 de cette position et on ajoute 2 à la valeur que l'on souhaite ajouter au nombre, ce qui nous amène ensuite à chercher une position de poids 4. On continue ainsi jusqu'à ce que l'on ait trouvé une position qui soit inoccupée.
✎ Auto-évaluation
Lorsque l'on compte en binaire, après 0, 1 viennent , , puis .
✎ Auto-évaluation
En binaire, lorsque l'on incrémente 10110, on obtient . Si l'on incrémente encore ce nombre, on obtient .
Écrire en binaire
Maintenant que nous avons vu comment incrémenter un nombre binaire, nous allons voir comment écrire un nombre en binaire. Nous pourrions imaginer que pour trouver la représentation binaire d'un nombre il fasse commencer avec 0 et continuellement incrémenter jusqu'à tomber sur le nombre en question. Cependant, il existe une méthode plus efficace que cette méthode naïve.
Pour écrire un nombre en binaire, on commence par chercher la décomposition du nombre en somme de puissances de 2. Une fois cette décomposition trouvée, il suffit de mettre un 1 à chaque position de poids correspondant à une puissance de 2 de la somme, et un 0 aux autres positions.
Comment trouver cette décomposition ? Pour cela, on peut utiliser l'algorithme représenté dans le schéma suivant :
L'idée de l'algorithme est très simple : tant que le nombre n'est pas zéro, on cherche la plus grande puissance de 2 inférieure ou égale au nombre, on la note, et on la soustrait au nombre. À la fin de l'exécution de l'algorithme, tous les nombres notés sont les puissances de 2 qui composent le nombre initial.
! Remarque
Cet algorithme est un exemple de ce qu'on appelle un algorithme glouton. On dit de cet algorithme qu'il est glouton car il prend toujours la décision qui le rapproche le plus de son but à chaque étape. Ici, l'algorithme enlève toujours la plus grande puissance de 2 possible à chaque étape.
Une fois la décomposition du nombre obtenue, il suffit d'inscrire un 1 à chaque position dont le poids a été noté. Le reste des positions sont remplies par des 0. Bien entendu, on inscrit généralement pas les 0 inutiles à gauche.
♣︎ Exemple
Prenons l'exemple du nombre 138. En suivant l'algorithme, on commence par chercher la plus grande puissance de 2 inférieure ou égale à 138. On trouve 128, on la note, et on la soustrait au nombre. On obtient 138 - 128 = 10. On recommence, et on trouve 8. On note cette puissance et on la soustrait au nombre. On obtient 10 - 8 = 2. On recommence, et on trouve 2, que l'on note et soustrait. Finalement, on obtient 0, et on arrête.
On a donc que 138 = 128 + 8 + 2. Pour obtenir la représentation binaire de 138, on inscrit un 1 à chaque position dont le poids a été noté. On obtient donc 10001010. En effet, on met un 1 aux positions de poids 128, 8 et 2.
Notation
Lorsque l'on suit l'algorithme décrit ci-dessus, on peut noter les différentes soustractions effectuées en colonne, comme ci-dessous.
De cette façon, on peut facilement voir les différentes soustractions effectuées et les puissances de 2 qui ont été notées.
★ À essayer
Entrez un nombre écrit en décimal ci-dessous et appuyez sur le bouton pour afficher sa décomposition en puissances de 2 et sa représentation binaire.
✎ Auto-évaluation
La représentation binaire de 42 est , et la représentation binaire de 79 est .
Additionner en binaire
La dernière opération que nous allons voir dans cette (longue) section est l'addition de deux nombres écrits en binaire.
Pour procéder à l'addition de deux nombres représentés en base 2, il suffit de procéder par une addition en colonnes, comme pour l'addition en base 10.
Pour cela, on commence par aligner les deux nombres à additionner, de tel sorte que les bits de même poids soient alignés. En pratique, cela signifie que les deux nombres doivent être alignés à droite. Au dessus des deux nombres, on laisse de la place pour une éventuelle retenue, et en dessous on laisse de la place pour le résultat.
♣︎ Exemple
Prenons par exemple les nombres 101110 et 1011, ici exprimés en base 2. Les deux nombres sont alignés à droite, et on laisse de la place pour une retenue et pour le résultat.
De plus, on tire un trait sous le nombre du bas, en dessus du résultat. Un signe plus (+) est placé à gauche du nombre du bas pour signifier que l'on effectue une addition.
On procède ensuite à l'addition colonne par colonne. En commençant par la colonne tout à droite, on additionne les bits qui se situent dans la colonne. Au maximum, à cause de la retenue, on peut obtenir 1 + 1 + 1 = 3.
On exprime ensuite le résultat de l'addition en binaire. Pour rappel, voici comment on représente les nombres entre 0 et 3 en binaire :
Le bit de poids 1 de la somme est placé comme résultat en bas de la colonne, alors que le bit de poids 2 est placé en retenue pour la colonne sur la gauche. Pour rappel, on considére que si un bit est absent, alors il est considéré comme égal à 0. Ainsi, pour une somme de 0 ou de 1, on place un 0 en retenue.
On continue ainsi jusqu'à ce que l'on ait traité toutes les colonnes. Attention à ne pas oublier de traiter la retenue de la dernière colonne, et ce même si les deux nombres à additionner n'ont pas de bit inscrit dans la colonne.
♣︎ Exemple
Continuons avec l'exemple précédent. Après l'addition des deux nombres, on obtient le résultat suivant :
En dessous de la barre se trouvent les bits du résultat de l'addition. Dans ce cas, on peut voir que l'addition de 101110 et 1011 donne 111001. La ligne du dessus contient les éventuelles retenues. Pour signifier un 0 en retenue, on laisse la case vide ou on y inscrit un 0.
On peut s'assurer que le résultat est correct en convertissant les deux nombres en base 10 puis en effectuant l'addition. Le premier nombre est 46 et le second est 11. Leur somme est donc de 57. En binaire, 57 est représenté par 111001. On peut donc vérifier que le résultat est correct.
★ À essayer
Entrez deux nombres binaires ci-dessous pour calculer leur somme.
✎ Auto-évaluation
Complétez l'addition binaire suivante :
! À maîtriser
Avant de poursuivre, assurez-vous de pouvoir :
- Expliquer ce qu'est le système décimal.
- Expliquer ce qu'est le système binaire.
- Expliquer ce qu'est un bit et lister les deux différents bits.
- Lire un nombre exprimé en système binaire.
- Écrire un nombre en système binaire.
- Incrémenter un nombre exprimé en sytème binaire.
- Additionner deux nombres exprimés en système binaire en utilisant une addition en colonnes.