Le
systeme binaire
(du latin
bin?r?us
, ≪ double ≫) est le
systeme de numeration
utilisant la
base
2
. On nomme couramment
bit
(de l'
anglais
binary digit
, soit ≪ chiffre binaire ≫) les
chiffres
de la numeration binaire positionnelle. Un bit peut prendre deux valeurs, notees par convention
0
et
1
.
Le systeme binaire est utile pour representer le fonctionnement de l'
electronique numerique
utilisee dans les
ordinateurs
. Il est donc utilise par les
langages de programmation de bas niveau
.
Le systeme binaire le plus courant est la
base deux
mathematique
, permettant de representer des
nombres
a l'aide de la
numeration de position
avec seulement deux chiffres : le 0 et le 1.
Dans ce type de codage, chaque nombre est represente de facon unique par une suite ordonnee de
chiffres
. Et chaque position
m
represente une
puissance
(
m
? 1) de la
base
. Si l'on se limite dans un premier temps aux
nombres entiers
positifs, en
base dix
ces puissances sont : un (1), dix (represente par 10), cent (dix fois dix, represente par 100), mille (dix fois cent, represente par 1000), dix mille, etc. En base deux, ces puissances sont : un (1), deux (represente lui aussi par 10), quatre (deux fois deux, represente par 100), huit (deux fois quatre, represente par 1000), seize (deux fois huit, represente par 10000), etc.
On voit que la signification des representations 10, 100, 1000, etc. depend de la base utilisee : 10 est toujours egal a la base, c'est-a-dire
dix
en base dix, mais
deux
en base deux.
En base dix, on utilise dix chiffres, de zero a neuf ; en base
n
, on utilise
n
chiffres, de zero a
n
? 1 ; donc en base deux on utilise les deux chiffres ≪ 0 ≫ et ≪ 1 ≫.
Un nombre qui s'exprime en base
B
par les quatre chiffres 1101 s'analyse :
, qui donne :
1101 en base
B
= 10 :
|
|
|
|
|
|
1101 en base
B
= 8 :
|
|
|
|
|
|
1101 en base
B
= 2 :
|
|
|
|
|
|
Les premiers nombres, et chiffres de la base de numeration 10, s'ecrivent :
decimal
|
binaire
|
commentaire
|
0
|
0
|
zero
|
1
|
1
|
un = base puissance zero (valable pour toutes les bases, donc deux et dix)
|
2
|
10
|
deux = deux puissance un (un zero derriere le 1)
|
3
|
11
|
4
|
100
|
quatre = deux puissance deux (deux zeros derriere le 1)
|
5
|
101
|
6
|
110
|
7
|
111
|
8
|
1000
|
huit = deux puissance trois (trois zeros derriere le 1)
|
9
|
1001
|
On donne a chaque bit une
puissance de deux
, comme cette suite 1, 2, 4, 8, 16, 32, 64. Pour obtenir le nombre 7, on additionne les trois premiers bits ; pour obtenir 6, on additionne seulement le bit de poids 4 et le bit de poids 2.
La mise en forme de cet article est a ameliorer
(
).
La mise en forme du texte ne suit pas les recommandations de Wikipedia : il faut le ≪
wikifier
≫.
Les techniques des quatre operations de base (
addition
,
soustraction
,
multiplication
et
division
) restent
exactement les memes
qu'en notation decimale ; elles sont juste simplifiees de facon drastique parce qu'il n'y a que les deux chiffres 0 et 1. Pour la multiplication par exemple, quelle que soit la base, la multiplication par 10 (c’est-a-dire par la base elle-meme)
[
1
]
se fait en ajoutant un zero a droite.
Seules changent d'une part la forme de la suite de chiffres qui exprime le resultat (elle ne compte que des zeros et un), d'autre part la signification de cette suite (10 signifie ≪ deux ≫ et non ≪ dix ≫, 100 signifie ≪ quatre ≫ et non ≪ cent ≫, etc.).
On passe d'un nombre binaire au suivant en ajoutant 1, comme en decimal, sans oublier les retenues et en utilisant la table ordinaire (mais reduite a sa plus simple expression) :
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0 avec 1 retenue
0 - 0 = 0 0 - 1 = 1 avec 1 retenue 1 - 0 = 1 1 - 1 = 0
On constate que l'addition de deux bits A et B donne A XOR B avec une retenue valant A ET B.
Ainsi :
11
+ 1
____
100
Detail :
1 + 1 = 10 => on pose 0 et on retient 1
1 + 1(retenue) = 10 => on pose 0 et on retient 1
0 + 1(retenue) = 1 => on pose 1 devant 00
Multiplier par deux se fait en decalant chaque chiffre d'un cran a gauche et en inserant un zero a la fin.
Par exemple, deux fois onze :
1011 onze
//// decalage et insertion de 0
10110 vingt-deux
La division entiere par deux se fait en decalant chaque chiffre d'un cran a droite, le chiffre de droite etant le reste supprime.
Par exemple onze divise par deux :
1011 onze
\\\ decalage et suppression du chiffre a droite
101 cinq reste un
L'arithmetique binaire (plus simplement le calcul binaire) est utilisee par les systemes electroniques les plus courants (calculatrices, ordinateurs, etc.) car les deux chiffres 0 et 1 s'y traduisent par la tension ou le passage d'un courant. Par exemple, le 0 peut etre represente par l'etat bas (tension ou courant nul) et 1 par l'etat haut
[ref. necessaire]
(tension qui existe, courant qui passe).
Pour completer la representation des entiers, il faut pouvoir ecrire des entiers
negatifs
.
Deux representations existent, le complement a un et le
complement a deux
.
Avant de coder avec tout complement, il est necessaire de verifier le bon nombre de bits est utilises pour encoder le nombre en tant que nombre binaire signe.
Le nombre de bits est suffisant si et seulement s'il verifie l'equation ou n correspond au nombre de bits et N au nombre a encoder.
correspond au nombre de caracteres possibles (1 est soustrait a 2n puisque l'on compte a partir de 0) tout en reservant un bit pour le signe.
Ce codage consiste a inverser la valeur de chaque bit.
Par exemple pour obtenir ?7 :
0111 sept
1000 moins sept
Un defaut de ce systeme est que zero a deux representations : 0000 et 1111 (≪ +0 ≫ et ≪ ?0 ≫). Il n'est pas utilise par les ordinateurs courants, mais l'etait par des ordinateurs anciens comme le
Control Data 6600
. Les deux representations du zero compliquent les circuits de test.
Le complement a deux consiste a realiser un complement a un, puis d'ajouter 1.
Par exemple pour obtenir ?7 :
0111 sept
1000 complement a un
1001 complement a deux en ajoutant 1
Ce codage a l'avantage de ne pas necessiter de differenciation speciale des nombres positifs et negatifs, et evite en particulier le probleme de double representation du zero.
Voici une addition de ?7 et +9 realisee en complement a deux sur 4 bits :
-7 1001
+9 1001
__ ____
2 (1) 0010 (on ≪ ignore ≫ la retenue)
Avec
n
bits, ce systeme permet de representer les nombres entre ?2
n
?1
et 2
n
?1
? 1.
Les bases 8 (octale) et 16 (hexadecimale) sont des bases puissances de la base 2. Ces deux bases sont couramment employees en informatique pour des raisons pratiques : les nombres ecrits dans ces bases sont humainement plus ≪ manipulables ≫ car d'ecriture plus courte et celle-ci est facilement obtenue par regroupement de chiffres de l'ecriture du nombre en base 2.
- Octal : base 8 = 2
3
. Il suffit de parcourir le nombre binaire de la droite vers la gauche en regroupant les chiffres binaires 3 par 3 : chaque paquet de 3 (le dernier devant etre parfois complete par des 0 a gauche) est l'ecriture binaire d'un chiffre en base 8 (0
8
= 000, 1
8
= 001, 2
8
= 010, 3
8
= 011, 4
8
= 100, 5
8
= 101, 6
8
= 110, 7
8
= 111).
- 10101101110
2
va s'ecrire 10 101 101 110 et en convertissant la valeur de chacun des blocs en un chiffre octal, on obtient le nombre octal 2556
8
.
- Hexadecimal : base 16 = 2
4
. Il suffit de parcourir le nombre binaire de la droite vers la gauche en regroupant les chiffres binaires 4 par 4 : chaque paquet de 4 bits est la representation binaire d'un chiffre en base 16. En base 16, il faut 16 symboles et conventionnellement, on utilise les 10 chiffres decimaux suivis des 6 premiers caracteres de l'alphabet selon la regle suivante: A
16
= 10
10
= 1010
2
, B
16
= 11
10
= 1011
2
, C
16
= 12
10
= 1100
2
, D
16
= 13
10
= 1101
2
, E
16
= 14
10
= 1110
2
et F
16
= 15
10
= 1111
2
.
- 10101101110
2
va s'ecrire 101 0110 1110 et en convertissant la valeur de chacun des blocs en decimal on obtient : 5, 6, 14 c'est-a-dire 56E
16
.
On pourrait facilement etendre ce principe a toutes les bases qui sont puissances de 2.
Il suffit de convertir la valeur de chacun des chiffres sous leur forme binaire en utilisant un nombre de chiffres correspondant a la puissance de la base : 16 = 2
4
, 8 = 2
3
, donc 4 chiffres pour l'hexadecimal et 3 pour l'octal :
- 1A2F
16
va s'ecrire 1 ⇒ 0001, A ⇒ 1010, 2 ⇒ 0010, F ⇒ 1111, soit 0001 1010 0010 1111
2
.
- 156
8
va s'ecrire 1 ⇒ 001, 5 ⇒ 101, 6 ⇒ 110, soit 001 101 110
2
.
Table des valeurs des groupements de chiffres binaires
[
modifier
|
modifier le code
]
Binaire
|
Decimal
|
Octal
|
Hexadecimal
|
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
|
Decimal
|
Octal
|
Hexadecimal
|
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
|
|
Le code de Gray, egalement appele binaire reflechi, permet de ne faire changer qu'un seul bit a la fois quand un nombre est incremente ou decremente d'une unite. Le nom du code vient de l'ingenieur americain
Frank Gray
, qui deposa un brevet sur ce code en 1947
[
2
]
.
Pour calculer directement le code de Gray d'un entier a partir de celui de son predecesseur on peut proceder ainsi :
- lorsqu'il y a un nombre pair de 1 on inverse le dernier bit ;
- lorsqu'il y a un nombre impair de 1 on inverse le bit directement a gauche du 1 le plus a droite.
Decimal code binaire (DCB, ou BCD pour
binary coded decimal
)
[
modifier
|
modifier le code
]
Afin de concilier la logique binaire de l'ordinateur avec la logique humaine, on peut convertir en binaire, plutot que les nombres eux-memes, chacun des chiffres qui les composent en notation decimale positionnelle. Chacun de ces chiffres est alors code sur 4 bits :
1994 = 0001 1001 1001 0100
1×1000 + 9×100 + 9×10 + 4×1
Avec n bits (n multiple de 4), il est possible de representer les nombres entre 0 et 10
n/4
-1. Soit approximativement entre 0 et 1.778
n
-1. Le DCB est un code redondant, en effet certaines combinaisons ne sont pas utilisees (comme 1111 par exemple).
Cette representation evite par construction tous les problemes genants de cumul d'arrondi qui interviendraient lors de la manipulation de grands nombres depassant la taille des circuits en arithmetique entiere et obligent a recourir au flottant. Il est cependant possible de manipuler des
nombres a precision arbitraire
en utilisant un codage plus efficace que le DCB.
Il existe des variantes du codage DCB :
- le code Aiken ou 0, 1, 2, 3, 4 sont codes comme en DCB et 5, 6, 7, 8, 9 sont codes de 1011 a 1111 ; ce code permet d'obtenir le complement a 9 en permutant les 1 et les 0 ;
- le codage binaire excedant 3, qui consiste a representer le chiffre a coder + 3.
En
theorie de l'information
, l'
entropie
d'une source d'information est exprimee en
bits
. La theorie elle-meme est indifferente a la representation des grandeurs qu'elle utilise.
La
logique classique
est une logique bivalente : une proposition est soit vraie, soit fausse. Il est donc possible de representer la verite d'une
proposition
par un chiffre binaire.
On peut par exemple modeliser les operations de l'arithmetique binaire a l'aide de l'
algebre de Boole
.
L'algebre de Boole represente un cas tres particulier d'usage des
probabilites
ne faisant intervenir que les seules valeurs de verite 0 et 1. Voir
Theoreme de Cox-Jaynes
.
Le binaire est utilise en informatique car il permet de modeliser le fonctionnement des composants de
commutation
comme le
TTL
ou le
CMOS
. La presence d'un seuil de tension aux bornes des transistors, en negligeant la valeur exacte de cette tension, representera 0 ou 1. Par exemple le chiffre 0 sera utilise pour signifier une absence de tension a 0,5
V
pres, et le chiffre 1 pour signifier sa presence a plus de 0,5
V
. Cette
marge de tolerance
permet de pousser les cadences des microprocesseurs a des valeurs atteignant plusieurs
gigahertz
.
En
informatique
, la representation binaire permet de clairement manipuler des
bits
: chaque chiffre binaire correspond a un bit. Cependant, la representation binaire necessitant l'usage de beaucoup de chiffres (meme pour des nombres assez petits), elle entraine d'importants problemes de
lisibilite
et donc de
risques d'erreur
de transcription pour les programmeurs. On prefere donc d'autres
representations
: la notation hexadecimale, qui permet de manipuler l'information par paquets de 4 bits, est adaptee a la quasi-totalite des
microprocesseurs
actuels travaillant avec des mots de 8, 16, 32 ou 64 bits ; plus rare, la notation
octale
, populaire du temps des premiers
mini-ordinateurs
DEC
a 12 ou 36 bits, qui permet de representer l'information par paquets de 3 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)
- Les hexagrammes chinois, plus tard reconnus comme la premiere expression d'une numeration binaire, apparaissent dans le
Yi Jing
vers 750 av J.C. (
periode des Zhou de l'Ouest
[
3
]
) mais leur signification mathematique, si elle a ete connue, fut oubliee ensuite
[
4
]
.
- Le mathematicien
indien
Pingala
est credite d'une table representant 0 a 7 en numeration binaire, dans son
Chanda?-??stra
datant peut-etre du troisieme ou deuxieme siecle av J.C.
[
5
]
,
[
6
]
.
- Vers 1600 le mathematicien anglais
Thomas Harriot
effectue des operations en numeration binaire, ainsi qu'en temoigne ses manuscrits publies recemment seulement
[
7
]
.
- A la meme epoque
Francis Bacon
utilise un code secret bilitere (a deux lettres) pour proteger 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 E → 5 → 00101 → codee AABAB
[
8
]
.
- John Napier
, mathematicien ecossais inventeur des logarithmes, dans son traite
Rhabdologie
publie en 1617, decrit trois systemes pour faciliter les calculs, dont un, dit
checkerboard
, est binaire
[
9
]
.
- L'espagnol
Caramuel
dans son
Mathesis biceps vetus et nova
publie en 1670, parait le premier a avoir donne une etude des numerations non decimales, dont binaire, succinctement
[
10
]
.
- A
Leibniz
revient d'avoir etudie le systeme binaire pour lui-meme, montre comment s'y pratiquent les quatre operations (≪ si aisees qu’on n’a jamais besoin de rien essayer ni deviner, comme il faut faire dans la division ordinaire
[
11
]
≫), note que ce calcul ≪ est le plus fondamental pour la science, et donne de nouvelles decouvertes
[
11
]
≫, et meme envisage que ≪ ce type de calcul pourrait egalement etre realise avec une machine (sans roues), de la maniere suivante certainement tres facilement et sans effort. Avec une boite munie de trous, qui peuvent etre ouverts et fermes
[
12
]
. ≫
En outre, ayant communique ≪ au R. P.
Bouvet
, Jesuite Francais celebre, qui demeure a Pekin, (sa) maniere de compter par 0 et 1, il n’en fallut pas davantage pour lui faire reconnaitre que c’est la clef des figures de Fohy ≫, en 1701
[
11
]
. Ainsi fut dechiffree l’enigme des
hexagrammes
attribues a
Fuxi
, et Leibniz fait ensuite publier son expose du systeme binaire par l'
Academie des sciences de Paris
en 1703
[
11
]
.
- En 1847
George Boole
publie les premiers travaux de son
algebre binaire, dite booleenne
, n'acceptant que deux valeurs numeriques : 0 et 1.
- 1872 : publication d'une application du systeme binaire pour la resolution du probleme du baguenodier (
Luc-Agathon-Louis
Gros
,
Theorie du baguenodier par un clerc de notaire lyonnais
, Lyon,
Aime Vingtrinier
,
(
lire en ligne
)
)
- 1876 : L.-V. Mimault depose le brevet 3011 concernant :
- les systemes telegraphiques multiples, imprimeurs et ecrivants bases sur des combinaisons mecaniques ou graphiques provenant de ≪ (
X
+ 1) puissance
m
≫ ;
- les systemes telegraphiques multiples, imprimeurs et ecrivants bases sur des combinaisons de la progression 1 : 2 : 4 : 8 : 16
[
13
]
.
- ↑
Attention : 10 et non
dix
; en base deux, 10 vaut
deux
.
- ↑
(en)
Frank Gray pour
Bell Labs
,
Brevet U.S. 2,632,058 :
Pulse code communication
, depose le 13 novembre 1947, publie le 17 mars 1953, sur
Google Patents
.
- ↑
(en)
E. L. Shaugnessy, ≪ I Ching (Chou I) ≫, dans M. Loewe (dir.),
Early Chinese Texts: A Bibliographical Guide
, Berkeley, 1993, p. 216-228.
- ↑
Temoignage du pere
Bouvet
rapporte par Leibniz (
sur Wikisource
).
- ↑
(en)
Kim Plofker
,
Mathematics in India
, Princeton (N.J.),
Princeton University Press
,
, 357
p.
(
ISBN
978-0-691-12067-6
,
lire en ligne
)
,
chap.
3
(≪ Mathematical Traces in the Early Classical Period ≫)
,
p.
55-57
.
- ↑
(en)
B.
Van Nooten
, ≪
Binary numbers in Indian antiquity
≫,
Journal of Indian Philosophy
,
vol.
21,
n
o
1,
,
p.
31?50
(
ISSN
0022-1791
,
DOI
10.1007/BF01092744
)
.
- ↑
L’edition electronique des manuscrits de Thomas Harriot (1560-1621)
;
fac-simile en ligne
.
- ↑
(en)
Bacon's cipher
.
- ↑
(en)
John Napier,
Rabdologiæ
, traduit du latin par William Frank Richardson, 'ntroduction par Robin E. Rider, 1990, MIT Press
(
ISBN
0-262-14046-2
)
.
- ↑
Robert Ineichen,
Leibniz, Caramuel, Harriot und das Dualsystem
, Mitteilungen der deutschen Mathematiker-Vereinigung, vol. 16, 2008, issue 1, p. 14.
- ↑
a
b
c
et
d
Leibniz,
Explication de l'arithmetique binaire, qui se sert des seuls caracteres 0 et 1, avec des remarques sur son utilite, et sur ce qu'elle donne le sens des anciennes figures chinoises de Fohy
(
lire sur Wikisource
et sur
Memoires de l'Academie des sciences
de Paris, 1703,
p.
85-89
).
- ↑
De progressione dyadica
, manuscrit date de 1679, traduction de Yves Serra, p. 5 (
lire en ligne
) ; voir aussi Yves Serra,
Le manuscrit ≪ De Progressione Dyadica ≫ de Leibniz
(
lire en ligne
sur
Bibnum
).
- ↑
Description des notes
contenues dans le brevet sous plis.
Sur les autres projets Wikimedia :
Sur les autres projets Wikimedia :
Sur les autres projets Wikimedia :
|
1 a 9
|
unaire (1)
,
binaire (2)
,
ternaire (3)
,
quaternaire (4)
,
quinaire (5)
,
senaire (6)
,
septenaire (7)
,
octal (8)
,
nonaire (9)
|
|
10 a 60
|
decimal (10)
,
undecimal (11)
,
duodecimal (12)
,
tridecimal (13)
,
quindecimal (15)
,
hexadecimal (16)
,
octodecimal (18)
,
vicesimal (20)
,
base 36
,
sexagesimal (60)
|
Autre base
|
base d'or (φ)
,
mixte
,
negabinaire (?2)
,
negaternaire (-3)
,
bases complexes
(en)
:
quater-imaginaire (2
i
)
|
Notions
|
|