Code Gray

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ération binaire. Ceux ci ne peuvent prendre que deux valeurs, notées par convention 0 et 1.

C'est un concept essentiel de l'informatique. En effet, les processeurs des ordinateurs sont composés de millions de transistors (imprimés sur un circuit électronique) qui chacun ne gère que des bits 0 (« le courant ne passe pas ») et 1 (« le courant passe »).

Un calcul informatique n'est donc qu'une suite d'opérations sur des paquets de 0 et de 1, appelés octets lorsqu'ils sont regroupés par 8.

Sommaire 1 Conversions 1.1 Énumération des premiers nombres 1.2 Expression d'un nombre 1.2.1 Représentation des entiers positifs 1.2.2 Représentation des entiers négatifs 1.2.2.1 Complément à un 1.2.2.2 Complément à deux 1.3 Du système décimal vers le système binaire 1.4 Entre les bases 2, 8 et 16 1.4.1 Du binaire vers octal ou hexadécimal 1.4.2 Vers le binaire 1.4.3 Par position dans une chaîne de caratères 1.5 Table des valeurs des groupements de chiffres binaires 2 La soustraction 3 Code de Gray ou binaire réfléchi 4 Décimal codé binaire (« binary coded decimal », ou BCD) 5 Applications 5.1 Théorie de l'information 5.2 Logique 5.3 Informatique 6 Histoire 7 Voir aussi 8 Liens externes

Conversions

Le codage le plus courant est l'équivalent en base deux de la numération de position que nous utilisons quotidiennement en base 10.

Énumération des premiers nombres

Les premiers nombres s'écrivent :

décimal  binaire
   0       0000
   1       0001
   2       0010
   3       0011
   4       0100
   5       0101

(Sachant que les colonnes binaires correspondent respectivement à 8,4,2 et 1)

On passe d'un nombre binaire au suivant en ajoutant 1, comme en décimal, sans oublier les retenues et en utilisant les tables d'additions suivantes:

 0+0=0    0+1=1    1+0=1   1+1=10

ainsi:

   11
+   1
 ====
  100

Détail :

1 + 1 = 10           => on pose 0, et retient 1
1 + 1(retenue) = 10  => on pose 0, et retient 1
0 + 1(retenue) = 1   =>         1

---

L'arithmétique binaire (plus simplement le calcul binaire) est utilisé par les systèmes électroniques les plus courants (calculatrices, ordinateurs, etc.) car le niveau de tension peut servir à représenter les deux chiffres 0 et 1 ; 0 représentant l'état bas et 1 l'état haut.

Tout nombre peut s'écrire en binaire, c'est-à-dire qu'il se décompose en somme de puissances de 2 (1, 2, 4, 8, 16, 32, 64, etc.), par exemple 35 se décompose en :

(1 * 2⁵) + (0 * 2⁴) + (0 * 2³) + (0 * 2²) + (1 * 2¹) + (1 * 2⁰) = 32 + 2 + 1 = 35

donc le nombre décimal 35 se note 100011 en binaire.

Expression d'un nombre

Un nombre décimal à plusieurs chiffres tel que 123 s'exprime ainsi :

1 * 100 + 2 * 10 + 3 * 1 = 1 * 10² + 2 * 10¹ + 3 * 10⁰

Sa représentation en binaire est 1111011 et s'exprime de la même façon :

1 * 64 + 1 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 1 * 2 + 1 * 1 = 1 * 2⁶ + 1 * 2⁵ + 1 * 2⁴ + 1 * 2³ + 0 * 2² + 1 * 2¹ + 1 * 2⁰

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×2³ + 0×2² + 1×21 + 1×20
  59 = 111011 en binaire

Avec N bits, ce système permet de représenter les nombres entre 0 et 2^N-1. Il est donc possible de compter sur ses dix doigts jusqu'à 1023 (2¹⁰-1) en binaire. Il suffit d'affecter à chaque doigt une valeur binaire (pouvant être représenté par un doigt plié).

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)

Ceci 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é à 1 est 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 à complémenter 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é.

Complément à deux

Afin de pallier 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 a 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 -2^n-1 et 2^n-1-1.

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. À dire vrai, pour proposer une méthode plus simple à comprendre, il faut trouver la puissance de 2 la plus grande possible inférieure ou égale au nombre de départ. On soustrait au nombre d'origine (RO) cette puissance, en notant un 1, puis l'on cherche à nouveau un multiple (RM) pour le reste (Rr).

• 1. RO = RM1+Rr1
• 2. Rr1 = RM2+Rr2
• 3. Rr2 = RM3+Rr3

...

 32 768  1 fois  32 768  on fait 2 multiplié 14 fois par lui-même soit 215
+     0  0 fois  16 384  on fait 2 multiplié 13 fois par lui-même soit 214
+ 8 192  1 fois   8 192         idem         12      idem              213
+ 4 096  1 fois   4 096         idem         11      idem              212
+     0  0 fois   2 048         idem         10      idem              211
+     0  0 fois   1 024         idem          9      idem              210
+   512  1 fois     512         idem          8      idem              29
+   256  1 fois     256         idem          7      idem              28
+     0  0 fois     128         idem          6      idem              27
+     0  0 fois      64         idem          5      idem              26
+     0  0 fois      32         idem          4      idem              25
+    16  1 fois      16         idem          3      idem              24
+     8  1 fois       8         idem          2      idem              23
+     4  1 fois       4         idem          1      idem              22
+     0  0 fois       2         idem          0      idem              21 = 2
+     1  1 fois       1                                                 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 pour aérer la lecture).

Ce nombre nécessite 16 bits pour son écriture (il est compris entre 2¹⁵ et 2¹⁶). L'autre méthode pour convertir un nombre décimal en base 2 est d'utiliser des successions de divisions par le nombre 2. Ainsi, on a:

45853 / 2 = 22926 reste 1
22926 / 2 = 11463 reste 0
11463 / 2 =  5731 reste 1
 5731 / 2 =  2865 reste 1
 2865 / 2 =  1432 reste 1
 1432 / 2 =   716 reste 0
  716 / 2 =   358 reste 0
  358 / 2 =   179 reste 0
  179 / 2 =    89 reste 1
   89 / 2 =    44 reste 1
   44 / 2 =    22 reste 0
   22 / 2 =    11 reste 0
   11 / 2 =     5 reste 1
    5 / 2 =     2 reste 1
    2 / 2 =     1 reste 0
    1 / 2 =     0 reste 1

Soit (en lisant les restes obtenus en sens inverse): 1011001100011101

Entre les bases 2, 8 et 16

Du binaire vers octal ou hexadécimal

Les bases 8 (octale) et 16 (hexadécimale) sont des bases multiples de la base 2. Ces deux bases ont été couramment employées en informatique et pour des raisons pratiques; ces bases étant fortement liées à la base 2 et les nombres écrits dans ces bases étant plus "manipulables" (car d'écriture plus courte) par l'intellect humain. L'écriture de nombres dans ces bases est facilement obtenue par regroupement de chiffres de l'écriture du nombre en base 2.

• Octal : base 8 : 8 = 2³, il suffit de regrouper à partir de la droite et par paquets de 3 les chiffres binaires (voir bāguà). Chaque paquet de 3 (le dernier devant être parfois complété par des 0 à gauche), étant l'écriture binaire d'un chiffre en base 8 (0₈=000, 1₈=001, 2₈=010, 3₈=011, 4₈=100, 5₈=101, 6₈=110, 7₈=111).

• 10101101110₂ va s'écrire 10 101 101 110 et en convertissant la valeur de chacun des blocs en un chiffre octal, on obtient le nombre octal 2556₈.

• Hexadécimal : base 16 : 16 = 2⁴, donc on regroupe à partir de la droite et par paquets de 4 les chiffres binaires. Chaque paquet de 4 bits étant la représentation binaire d'un chiffre en base 16. Il faut donc 16 chiffres, il a été décidé d'utiliser les 10 chiffres décimaux plus les 6 premiers caractères de l'alphabet avec la convention suivante: A₁₆=10₁₀=1010₂, B₁₆=11₁₀=1011₂, C₁₆=12₁₀=1100₂, D₁₆=13₁₀=1101₂, E₁₆=14₁₀=1110₂ et F₁₆=15₁₀=1111₂.

• 10101101110₂ va s'écrire 101 0110 1110 et en convertissant la valeur de chacun des blocs en décimal on obtient : 5, 6, 14 c'est-à-dire 56E₁₆.

On pourrait facilement étendre ce principe à toutes les bases qui sont puissances de 2.

Vers le binaire

Il suffit de convertir la valeur de chacun des chiffres sous leur forme binaire.

• 1A2F₁₆ va s'écrire 1, 10=8+2, 2, 15=8+4+2+1 soit 1 1010 0010 1111₂
• 156₈ va s'écrire 1, 5=4+1, 6=4+2 soit 1 101 110₂

Par position dans une chaîne de caratères

Une astuce, par exemple pour écrire un programme d'émulation d'instructions assembleur 16 bits, programme qui tournera sur une machine avec un processeur 8 bits. Elle permet d'éviter le calcul et ne s'appuie que sur la position d'une sous-chaîne (ou d'un caractère) dans une chaîne de référence, pour trouver la position du caractère (ou d'une sous-chaîne) correspondant dans la chaîne de référence qui est associée. Aussi, des fois que, les voici :

• entre binaire et hexadécimal

Pour convertir du binaire (4 bits) en hexadécimal, ou réciproquement, sans avoir à calculer, c'est possible avec les chaînes suivantes :

binhexa "0000111100101101000" et hexabin "0137FEC92586DA48"

En effet, la position (unique) d'une chaîne constituée de 4 bits dans la chaîne "binhexa" donne la position du caractère hexadécimal correspondant dans la chaîne associée "hexabin". Et réciproquement, la position (unique) d'un caractère hexadécimal dans la chaîne "hexabin", donne la position du début de la sous-chaîne de 4 "bits" correspondante dans la chaîne associée "binhexa".

Exemple :

• b"1110" est en 6^e position dans la chaîne binhexa, "0000111100101101000", ce qui correspond dans la chaîne hexabin "0137FEC92586DA48" au caractère h"E" ;
• h"4" est en 15^e position dans la chaîne hexabin, "0137FEC92586DA48", ce qui correspond dans la chaîne binhexa "0000111100101101000" à la position du premier caractère de la chaîne de 4 bits "0100".

• entre binaire et octal

Idem avec les chaînes de caractères associées suivantes :

binoct "0001110100" et octbin "01376524"

Table des valeurs des groupements de chiffres binaires

Binaire Décimal Octal Hexadécimal 0000 0 0 0 0001 1 1 1 0010 2 2 2 0011 3 3 3 0100 4 4 4 0101 5 5 5 0110 6 6 6 0111 7 7 7

Binaire Décimal Octal Hexadécimal 1000 8 10 8 1001 9 11 9 1010 10 12 A 1011 11 13 B 1100 12 14 C 1101 13 15 D 1110 14 16 E 1111 15 17 F

La soustraction

La soustraction en binaire se déroule de la même manière qu’en décimal.

Principe de base :

0 − 0 = 0

0 − 1 = 1 (avec retenue)

1 − 0 = 1

1 − 1 = 0

Exemple de soustraction :

    *   * * *   (les colonnes avec * contiennent des retenues)
  1 1 0 1 1 1 0
−     1 0 1 1 1
----------------
= 1 0 1 0 1 1 1

Code de 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é.

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 10^n/4-1. Soit approximativement entre 0 et 1.778ⁿ-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 efficace 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édant 3 qui consiste à représenter le chiffre à coder + 3.

Applications

Théorie de l'information

En théorie de l'information, l'entropie d'une source d'information est exprimée en bits. 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 ₍₁₀₎ = 111111 ₍₂₎ = 77 ₍₈₎ = 3F ₍₁₆₎
• 64 ₍₁₀₎ = 1000000 ₍₂₎ = 100 ₍₈₎ = 40 ₍₁₆₎
• 255 ₍₁₀₎ = 11111111 ₍₂₎ = 377 ₍₈₎ = FF ₍₁₆₎
• 256 ₍₁₀₎ = 100000000 ₍₂₎ = 400 ₍₈₎ = 100 ₍₁₆₎

Histoire

• 1650 av J.C. - Multiplication égyptienne
• 1600 - Table de Thomas Harriot(1560-1621), première expression du binaire connue en France
• 1605 - Francis Bacon utilise un code secret bilitaire (à deux lettres) pour protéger ses messages (il remplace les lettres du message par leur position en binaire, puis les 0 et les 1 par des A et des B. Exemple : lettre F → 5 → 00101 → codée AABAB
• 1617 - Neper, dans son traité 'Rhabdologie', montre comment effectuer simplement les opérations sur des nombres binaires.
• 1670 - Juan Caramuel y Lobkowitz fait la première étude raisonnée sur les numérations non décimales.
• 1677 - Leibniz étudie le binaire comme mode de calcul des fractions décimales, De progresso dyadica est publié en 1679.
• 1688 - La Chine s'empare des idées de Leibniz et redécouvre des travaux chinois datant de trois mille ans avant J.C.
• 1703 - Leibniz publie son exposé sur le système binaire devant l'Académie des sciences de Paris dans les Mémoires
• 1847 - George Boole publie les premiers travaux de son Algèbre de Boole
• Dans les années 1930 - nombreux théoriciens : R. Valtat (F), Louis Couffignal (F), E.W. Phillips (UK), Alan Turing (UK), Claude Shannon (USA).

Voir aussi

• Format des données
• Préfixe binaire
• Virgule flottante
• Système bibi-binaire de Boby Lapointe
• Algèbre de Boole
• Nombre négatif
• Complément à 1
• Complément à 2
• Auguste De Morgan
• Entier en précision multiple

Liens externes

• Le traitement numérique
• Mise en œuvre de la numération
• Traducteur,Texte-Binaire-Hexadécimal-Décimal-Base64, etc...
• Convertisseur binaire - hexadecimal - décimal

Base de numération positionnelle
1 à 9	unaire (1), binaire (2), trinaire (3), quaternaire (4), quinaire (5), sénaire (6), septénaire (7), octal (8), nonaire (9)
10 à 60	décimal (10), duodécimal (12), hexadécimal (16), vicésimal (20), sexagésimal (60),
Autre base	base d'or (φ),
Notions	base • chiffre • nombre • notation positionnelle • numération

• Portail de la logique
• Portail de l’informatique
• Portail des mathématiques