« Algèbre de Boole/Utiliser le système binaire » : différence entre les versions
imported>Emirix m Révocation des modifications de 193.252.106.18 (retour à la précédente version de Emirix) |
|||
| Ligne 79 : | Ligne 79 : | ||
2^10-1=1 024-1 |
2^10-1=1 024-1 |
||
=1 023 |
=1 023 |
||
On remarque qu'avec 10 doigts |
On remarque qu'avec 10 doigts on peut prendre en compte les 10 premières puissances de 2 s'échelonnant de 2^0 à 2^9 c'est-à-dire la somme des 10 premières puissances de 2]. |
||
====Représentation des entiers négatifs==== |
====Représentation des entiers négatifs==== |
||
| Ligne 94 : | Ligne 94 : | ||
1010 complément à un |
1010 complément à un |
||
Le souci avec un tel système est qu'il y a toujours deux représentations de la valeur 0 pour un nombre de bit donné. |
|||
''voir article détaillé : [[complément à un]]'' |
''voir article détaillé : [[complément à un]]'' |
||
| Ligne 100 : | Ligne 100 : | ||
=====Complément à deux===== |
=====Complément à deux===== |
||
Afin de palier ce défaut, on a introduit |
Afin de palier ce défaut, on a introduit la représentation par complément à deux. Celle-ci consiste à réaliser un complément à un de la valeur, puis d'ajouter 1 au résultat. |
||
Par exemple pour obtenir -5: |
Par exemple pour obtenir -5: |
||
| Ligne 113 : | Ligne 113 : | ||
+7 0111 |
+7 0111 |
||
__ ____ |
__ ____ |
||
2 (1) |
2 (1) 0010 (on 'ignore' la retenue) |
||
Avec n bits, ce système permet de représenter les nombres entre -2<sup>n-1</sup> et 2<sup>n-1</sup>-1. |
Avec n bits, ce système permet de représenter les nombres entre -2<sup>n-1</sup> et 2<sup>n-1</sup>-1. |
||
Version du 18 janvier 2006 à 17:36
Cet article est consacré au système de numération binaire. En astrophysique, un système binaire est également un système constitué de deux astres tournant l'un autour de l'autre (voir étoile binaire).
Le système binaire est un système de numération utilisant la base 2. On nomme couramment bit (de l'anglais binary digit, soit « chiffre binaire ») les chiffres de la numérotation binaire. Ceux ci ne peuvent prendre que deux valeurs, notées par convention 0 et 1.
Usage
Le système binaire est utilisé pour représenter un ensemble de deux valeurs antinomiques, comme vrai/faux, blanc/noir, marche/arrêt (on et off en anglais) tel le système des booléens. Il convient notamment pour représenter le fonctionnement de l'électronique numérique utilisée dans les ordinateurs, d'où son usage en informatique. S'il se montre peu intuitif pour l'usage humain (plus habitué à compter avec ses doigts, donc en base décimale), il permet d'utiliser en électronique des circuits de commutation, dont le coût unitaire est si faible (quelques picoeuros) que la charge des traductions depuis et vers le système décimal ne constitue plus un problème.
Exemple de conversion du système décimal vers le système binaire
Pour développer l'exemple ci-dessus, le nombre 45 853 écrit en base décimale provient de la somme de nombres ci-après écrits en base décimale.
32 768 1 fois 32 768 en fait 2 multiplié 15 fois par lui même soit 215 + 0 0 fois 16 384 en fait 2 multiplié 14 fois par lui même soit 214 + 8 192 1 fois 8 192 idem 13 idem 213 + 4 096 1 fois 4 096 idem 12 idem 212 + 0 0 fois 2 048 idem 11 idem 211 + 0 0 fois 1 024 idem 10 idem 210 + 512 1 fois 512 idem 9 idem 29 + 256 1 fois 256 idem 8 idem 28 + 0 0 fois 128 idem 7 idem 27 + 0 0 fois 64 idem 6 idem 26 + 0 0 fois 32 idem 5 idem 25 + 16 1 fois 16 idem 4 idem 24 + 8 1 fois 8 idem 3 idem 23 + 4 1 fois 4 idem 2 idem 22 + 0 0 fois 2 idem 1 idem 21 = 2 + 1 1 fois 1 idem 0 idem 20 = 1 =45 853
Soit écrit en système positionnel et en numération décimale (en écrivant les puissances de 2) :
45 853 = 1×215 + 0×214 + 1×213 + 1×212 + 0×211 + 0×210 + 1×29 + 1×28 +
0×27 + 0×26 + 0×25 + 1×24 + 1×23 + 1×22 + 0×21 + 1×20
Soit en système positionnel et en numération binaire puisque l'on ne reporte pas les puissances de 2
45 853 décimal s'écrit 1011 0011 0001 1101 binaire (séparés par groupes de 4 bits)
On voit qu'il y a 16 bits.
Codage binaire
Il existe différents systèmes numériques basés sur la représentation binaire.
Numération de position
Le codage le plus courant est l'équivalent en base deux de la numération de position que nous utilisons quotidiennement en base 10.
Représentation des entiers positifs
Pour trouver la représentation binaire d'un nombre, on le décompose en somme de puissances de 2. Par exemple avec le nombre dont la représentation décimale est 59 :
59 = 1×32 + 1×16 + 1×8 + 0×4 + 1×2 + 1×1 59 = 1×25 + 1×24 + 1×23 + 0×22 + 1×21 + 1×20 59 = 111011 en binaire
Avec n bits, ce système permet de représenter les nombres entre 0 et 2n-1. Il est donc possible de compter sur ses dix doigts jusqu'à 1023 (210-1) en binaire. Il suffit d'affecter à chaque doigt une valeur binaire (pouvant être représenté par un doigt plié).
[Pour Robertv, avec 10 doigts on peut compter jusqu'à 1023. En effet si chaque doigt représente une puissance de 2 avec la convention doigt levé, alors la puissance de 2 est retenue (1 en binaire); doigt replié, alors la puissance de 2 n'est pas retenue (0 en binaire).
Doigt Main Puis. Valeur en
de 2 numération
décimale
Auriculaire de la main droite levé 2^0 1
Annulaire = 2^1 + 2
Majeur = 2^2 + 4
Index = 2^3 + 8
Pouce = 2^4 + 16
Pouce de la main gauche levé 2^5 + 32
Index = 2^6 + 64
Majeur = 2^7 + 128
Annulaire = 2^8 + 256
Auriculaire = 2^9 + 512
-------
Somme =1 023
(Pour mémoire 2^10 =1 024)
Ce qui confirme la formule
2^10-1=1 024-1
=1 023
On remarque qu'avec 10 doigts on peut prendre en compte les 10 premières puissances de 2 s'échelonnant de 2^0 à 2^9 c'est-à-dire la somme des 10 premières puissances de 2].
Représentation des entiers négatifs
Pour compléter la représentation des entiers, il faut pouvoir écrire des entiers négatifs. On ajoute pour cela à la représentation un bit de signe, placé en tête. Un bit de signe nul indique une valeur positive, un bit de signe positionné à un une valeur négative. Cette règle permet de rester cohérent avec le système de représentation des entiers positifs : il suffit d'ajouter un 0 en tête de chaque valeur.
Complément à un
Ce codage, fort simple, consiste à inverser la valeur de chaque bit composant une valeur binaire.
Par exemple, pour obtenir -5 :
0101 valeur décimale 5 1010 complément à un
Le souci avec un tel système est qu'il y a toujours deux représentations de la valeur 0 pour un nombre de bit donné.
voir article détaillé : complément à un
Complément à deux
Afin de palier ce défaut, on a introduit la représentation par complément à deux. Celle-ci consiste à réaliser un complément à un de la valeur, puis d'ajouter 1 au résultat.
Par exemple pour obtenir -5:
0101 codage de 5 en binaire 1010 complément à un 1011 on ajoute 1 : représentation de -5 en complément à deux
Ce codage à l'avantage de ne pas nécessiter de différenciation spéciale des nombres positifs et négatifs, et évite en particulier le problème d'ordinateurs anciens (Control Data 6600) qui avaient un « +0 » et un « -0 » dont il fallait faire comprendre aux circuits de tests que c'était le même nombre ! Voici une addition de -5 et +7 réalisée en complément à deux sur 4 bits :
-5 1011 +7 0111 __ ____ 2 (1) 0010 (on 'ignore' la retenue)
Avec n bits, ce système permet de représenter les nombres entre -2n-1 et 2n-1-1.
voir article détaillé : Complément à deux
Code Gray ou binaire réfléchi
Ce codage permet de ne faire changer qu'un seul bit à la fois quand un nombre est augmenté d'une unité.
0 0000 1 0001 2 0011 3 0010 4 0110 5 0111 6 0101 7 0100
Pour passer d'une ligne à la suivante, on inverse le bit le plus à droite possible conduisant à un nombre nouveau.
Le nom de code binaire réfléchi vient d'une méthode de construction plus pratique pour choisir quel bit inverser quand on passe d'un nombre au suivant:
- On choisit un code de départ: zéro est codé 0 et un est codé 1.
- Puis, à chaque fois qu'on a besoin d'un bit supplémentaire, on symétrise les nombres déjà obtenus (comme une réflexion dans un miroir) et on rajoute un 1 au début des nouveaux nombres:
0 0 0 .0 0 00 0 .00 0 000
1 1 1 .1 1 01 1 .01 1 001
miroir->------ 2 .11 2 011
2 .1 2 11 3 .10 3 010
3 .0 3 10 -------
4 .10 4 110
5 .11 5 111
6 .01 6 101
7 .00 7 100
Ce code est surtout utilisé pour des capteurs de positions, par exemple sur des règles optiques. En effet, si on utilise le code binaire standard, lors du passage de la position un (01) à deux (10) -- permutation simultanée de 2 bits -- il y a risque de passage transitoire par trois (11) ou zéro (00), ce qu'évite le code Gray.
On remarquera que le passage du maximum (sept sur 3 bits) à zéro se fait également en ne modifiant qu'un seul bit. Ceci permet par exemple d'encoder un angle, comme la direction d'une girouette: 0=Nord, 1=Nord-Est, 2=Est, ... 7=Nord-Ouest. Le passage de Nord-Ouest à Nord se fait également sans problème en ne changeant qu'un seul bit. Voir Roue de codage.
Le code Gray sert également dans les tables de Karnaugh utilisées lors de la conception de circuits logiques.
Décimal codé binaire (« binary coded decimal », ou BCD)
Ce codage consiste à représenter chacun des chiffres de la numérotation décimale sur 4 bits:
1994 = 0001 1001 1001 0100
1×1000 + 9×100 + 9×10 + 4×1
Il présente l'avantage de simplifier la conversion avec la notation décimale.
Avec n bits (n multiple de 4), il est possible de représenter les nombres entre 0 et 10n/4-1. Soit approximativement entre 0 et 1.778n-1. Le BCD est un code redondant, en effet certaines combinaisons ne sont pas utilisées (comme 1111 par exemple).
Cette représentation évite par construction tous les problèmes gênants de cumul d'arrondi qui interviendraient lors de la manipulation de grands nombres dépassant la taille des circuits en arithmétique entière et obligent à recourir au flottant. Il est cependant possible de manipuler des nombres à précision arbitraire en utilisant un codage plus efficient que le BCD.
Il existe des variantes du codage BCD:
- code Aiken où 0, 1, 2, 3, 4 sont codés comme en BCD et 5, 6, 7, 8, 9 sont codés de 1011 à 1111. Il permet d'obtenir le complément à 9 en permutant les 1 et les 0.
- codage binaire excédent 3 qui consiste à représenter le chiffre à coder + 3.
Applications
Théorie de l'information
En théorie de l'information, on peut utiliser le bit comme unité de mesure de l'information. La théorie elle-même est indifférente à la représentation des grandeurs qu'elle utilise.
Logique
La logique classique est une logique bivalente: une proposition est soit vraie, soit fausse. Il est donc possible de représenter la vérité d'une proposition par un chiffre binaire. On peut par exemple modéliser les opérations de l'arithmétique binaire à l'aide de l'algèbre de Boole.
L'algèbre de Boole représente un cas très particulier d'usage des probabilités ne faisant intervenir que les seules valeurs de vérité 0 et 1. Voir Théorème de Cox-Jaynes.
Informatique
Le binaire est utilisé en informatique car il permet de modéliser le fonctionnement des composants de commutation comme le TTL ou le CMOS. La présence d'un seuil de tension au bornes des transistors, en négligeant la valeur exacte de cette tension, représentera 0 ou 1. Par exemple le chiffre 0 sera utilisé pour signifier une absence de tension à 0,5V près, et le chiffre 1 pour signifier sa présence à plus de 0,5V. cette marge de tolérance permet de pousser les cadences des microprocesseurs à des valeurs atteignant sans problème (hormis d'échauffement) plusieurs gigahertz. Ne sachant pas techniquement réaliser des composants électroniques à plus de deux états stables (0 ou plus de 0,5V), on n'utilise que la logique (bivalente) et donc le système binaire.
En informatique, la représentation binaire permet de clairement manipuler des bits : chaque chiffre binaire correspond à un bit. La représentation binaire nécessitant l'usage de beaucoup de chiffres (même pour des nombres assez petits), ce qui entraînerait d'importants problèmes de lisibilité et donc de risques d'erreur de transcription pour les programmeurs on lui préfère pour eux une représentation parfois octale ou plus fréquemment hexadécimale. La quasi totalité des microprocesseurs actuels travaillant avec des mots de 8, 16, 32 ou 64 bits, la notation hexadécimale permet de manipuler l'information par paquets de 4 bits (contre 3 pour la notation octale plus populaire du temps des premiers mini-ordinateurs DEC à 12 ou 36 bits).
- 63 (10) = 111111 (2) = 77 (8) = 3F (16)
- 64 (10) = 1000000 (2) = 100 (8) = 40 (16)
- 255 (10) = 11111111 (2) = 377 (8) = FF (16)
- 256 (10) = 100000000 (2) = 400 (8) = 100 (16)