Voir la source de ISN Représentation binaire

==La représention binaire==
{{ISN:men
|savoirs=Un ordinateur est une machine qui manipule des valeurs numériques représentées sous forme binaire.
|capacites='''Manipuler''' à l'aide d'opérations élémentaires les trois unités de base : bit, octet, mot.
|observation=On met en évidence, sous forme de questionnement, la présence du numérique dans la vie personnelle et professionnelle, au travers d'exemples.}}
=== Systèmes de numération ===
Quand des sociétés humaines ont commencé à compter, des systèmes de numération ont été mis au point, pour permettre de communiquer des nombres avec moins de mots.

{{Latex:Label|sceau-cylindre}}
{{WikimediaCommons:Image
|local=Cylinder_seal_cowshed_Louvre_Klq17.jpg
|commons=Cylinder_seal_cowshed_Louvre_Klq17.jpg
|thumb=thumb
|latexwidth=8cm
|caption=Sceau-cylindre en jaspe et son impression : troupeau à l'étable, Mésopotamie, période d'Uruk (4100--3000 av. J.-C.).
}}
La numération la plus évidente à inventer consiste à montrer des collections de symboles. Des comptables de Mésopotamie ont utilisé des cylindres pour imprimer sur de l'argile des données commerciales. Les « imprimés » étaient complétés par des marques faites à l'aide d'un stylo en roseau, le ''calame''.

'''Exercice'''
* Pourquoi cette méthode a-t-elle été remplacée par d'autres plus tard ?
* Retrouvez l'origine du mot calcul en Mésopotamie : qu'appelait-on les ''calculi'' ?

Les comptages simples, tels que des encoches sur un morceau de bois ou d'os, les collections de ''calculi'' dans une bourse en terre, deviennent plus pratiques quand on regroupe les unités par paquets. En Mésopotamie, la méthode utilisée consistait à faire des paquets de 60 : ça a mené à l'invention d'un système numérique à base 60.

Autres civilisations, autre mœurs, autres bases de numération, voici quelques exemples :

{|border="1" latex="|p{0.25\\textwidth}|p{0.25\\textwidth}|p{0.5\\textwidth}|"
! Époque
! Civilisation
! base de numération
|----
| Depuis -3000
| Civilisation Sumérienne, puis Mésopotamienne, Chine, Inde
| [http://fr.wikipedia.org/wiki/Syst%C3%A8me_sexag%C3%A9simal Base sexagésimale ('''60''')] : on peut utiliser les pouces et les phalanges pour compter jusqu'à 60 avec les mains
|----
| Encore valide en 2013
| Tous pays
| Base sexagésimale ('''60''') : une heure compte 60 minutes, elles-même subdivisées en 60 secondes.
|----
| Jusqu'au XVIème siècle
| Civilisations aztèque, civilisation Maya
| [http://fr.wikipedia.org/wiki/Syst%C3%A8me_vic%C3%A9simal Base vicésimale ('''20''')] : les calculs étaient faits dans cette base jusqu'à l'invasion espagnole
|----
| Moyen-Âge
| Pays européens
| Base vicésimale ('''20''') : cette base était souvent utilisée en concurrence avec la base décimale. Il en reste de nombreux vestiges : le nombre « quatre vingt » toujours utilisé, le sou, égal à un vingtième de franc.
|----
| -200
| Empire romain
| [http://fr.wikipedia.org/wiki/Duod%C3%A9cimal Base duodécimale ('''12''')]. Le comptage par douze est souvent utilisé, et a laissé de nombreuses traces dans notre vocabulaire. Quelles sont les traces que vous connaissez ? Cherchez les sens du mot « grosse ».
|----
| Jusqu'à 1971
| Empire brittanique
| Base duodécimale ('''12'''). La pièce de 1 shilling valait 12 pence (pluriel de penny)
|----
| Encore valide en 2013
| États-Unis
| Base duodécimale ('''12'''). Un pied (mesure de longueur) se divise en 12 pouces
|}


==== Questions sur les bases de numération ====
[[Image:Compa.jpg|thumb|Plusieurs façons d'écrire des chiffres de base 10.]]La base décimale que nous utilisons aujourd'hui vient de nos chiffres « arabes », qui ont été inventés en Inde.

* Pourquoi la base 10 est-elle utilisée très largement partout ?
* Est-ce la base la mieux appropriée dans tous les cas ?
* Est-il facile de construire une machine à calculer qui fonctionne avec la base 10 ?

=== Exemple en base 5 ===
Comme la majorité d'entre nous a cinq doigts aux membres, l'utilisation d'une base 5 paraît judicieuse. 

Cette base est souvent utilisée, par exemple pour compter des points dans une rencontre sportive, ou pour compter des voix dans un bureau de vote.

====Exercice résolu====
Comment pourrions-nous noter le nombre de jours d'une année non bissextile, en base 5 ? Les symboles utilisés pour les chiffres seront 0, 1, 2, 3 et 4.

'''Solution'''
Les calculs seront menés en base 10, qui nous est plus familière.

On divise 365 par 5 : <math>365 \div 5 = 73</math>, reste <math>0</math>.

On divise 73 par 5 : <math>73 \div 5 = 14</math>, reste <math>3</math>.

On divise 14 par 5 : <math>14 \div 5 = 2</math>, reste <math>4</math>.

On divise 2 par 5 : <math>2 \div 5 = 0</math>, reste <math>2</math>.

On s'arrête là, et on écrit la suite des restes à l'envers : <math>2430</math>. C'est la représentation en base 5 du nombre de jours d'une année non bissextile.

On peut vérifier que :
<math>\begin{array}{rcl}2 \times 5^3 + 4 \times 5^2 + 3 \times 5^1 + 0 \times 5^0 &=&\\ 2 \times 125 + 4 \times 25 + 3 \times 5 + 0 \times 1& =&\\250 + 100 + 15 &=& 365\end{array}</math>

====Convention de notation====
On utilise souvent les premiers symboles de la suite 0123456789ABCDEF... (autant qu'il en faut, pas plus); comme symboles numériques pour une base donnée. Par exemple, pour la base 12, les symboles sont 0123456789AB.

Chaque fois qu'une ambiguïté est possible, on place un symbole de la base en indice du nombre écrit. Par exemple, le résultat de l'exercice résolu peut s'écrire <math>365_{10}=2430_5</math>, ou encore <math>365_{dec} = 2430_{quin}</math>, ce qui signifie que 365 en base 10 (décimale) vaut 2430 en base 5 ([http://fr.wikipedia.org/wiki/Syst%C3%A8me_quinaire quinaire]).

=== La base 2 pour les ordinateurs ===


La base 5, ou base quinaire, semble adaptée pour les humains, à cause de leurs cinq doigts. Il existe des méthode de comptage avec les mains pour les bases 10, 12, 20 et 60.

Cependant les ordinateurs sont faits d'automatismes électroniques, où il est plus facile de distinguer deux états seulement : arrêt/marche, ou éteint/allumé, qu'on représente aussi souvent comme faux/vrai, ou 0/1.

[[Image:TTL-7400.jpg|thumb|Un composant de la famille 7400 TTL.]]'''Exemple''' : les composants électroniques de la famille TTL (''transistor-transistor logic'') obéissent à la norme suivante :
* les tensions utilisées sont toujours entre 0 et 5 V ;
* les tensions entre 0 et 2 V correspondent à la valeur binaire <math>0_{bin}</math> ;
* les tensions entre 3 et 5 V correspondent à la valeur binaire <math>1_{bin}</math> ;
* les tensions ne restent presque jamais entre 2 et 3 V, et on s'arrange pour ne faire des calculs qu'en dehors des moments où existent des risques (''aléas'') d'avoir des tensions entre 2 et 3 volt.

==== Exercice résolu ====
Trouver la représentation en binaire de 365 en décimal.

'''Solution'''

On effectue la suite d'opérations suivantes :

<math>\begin{array}{rcl}
365 \div 2 = 184 &{reste}& 1\\
184 \div 2 = 92&{reste}&0\\
92\div 2 = 46&{reste}&0\\
46\div 2 = 23&{reste}&0\\
23\div 2 = 11&{reste}&1\\
11\div 2 = 5&{reste}&1\\
5\div 2 = 2&{reste}&1\\
2\div 2 = 1&{reste}&0\\
1\div 2 = 0&{reste}&1\\
\end{array}</math>

Donc la solution est : <math>365_{dec}=101110001_{bin}</math>

'''Vérifiez que'''... <math>
\begin{array}{lcl}
1 \times 2^8 +&&\\
0 \times 2^7 +&&\\
1 \times 2^6 +&&\\
1 \times 2^5 +&&\\
1 \times 2^4 +&&\\
0 \times 2^3 +&&\\
0 \times 2^2 +&&\\
0 \times 2^1 +&&\\
1 \times 2^0 &= &365
\end{array}
</math>

Dans l'exemple précédent, on voit que pour représenter <math>365_{dec}</math> en binaire, 9 chiffres sont nécessaires. On peut retenir que pour un même nombre, l'écriture binaire est toujours environ trois fois plus longue que l'écriture décimale. Ce désavantage, pour les ordinateurs, est largement compensé par la grande simplicité des opérations que permet le système binaire.

==== La simplicité des opérations en binaire ====

Comparez les tables de multiplications en systèmes décimal et binaire !

Combien vous a-t-il fallu de temps pour mémoriser les tables de multiplication au cours de votre scolarité ? Les connaissez-vous bien ?

La table de multiplication en binaire est beaucoup plus simple ! (On a retiré la multiplication par zéro des tables de l'illustration, et on a un peu triché en supprimant les lignes et colonnes de 10 dans le cas de la table en base deux).

'''Exercices''' 
* Retrouvez les tables de multiplication complètes en système binaire. On doit tenir compte du chiffre zéro. Il faut la table de multiplication et la table d'addition. Ne pas oublier de signaler quand il y a une retenue.
* Multipliez <math>101110001_{bin}</math> par <math>11_{bin}</math>, vérifiez que le résultat est le même que pour la multiplication de 365 par 3.

=== Conversions d'un nombre d'une base à l'autre ===
En vous inspirant des exercices ci-dessus, on peut décrire en toute généralité ''l'algorithme'' qui permet de convertir un nombre
écrit en base X vers sa représentation en base Y. Il faut pour cela :
# passer de la suite des symboles représentant le nombre en base X au nombre entier représenté, 
# puis de ce nombre vers la suite de symboles le représentant en base Y.

==== Algorithme pour passer de la représentation d'un nombre en base X à sa valeur ====

<pre>
debut
 chaineConstante symboles := "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 chaine nombreEnBaseX
 caractere c
 entier val := 0
 entier i
 entier X
 lire (nombreEnBaseX)
 lire (X)
 tantQue longueur(nombreEnBaseX) > 0 :
    val := X * val
    c := premierCaractereDe (nombreEnBaseX)
    nombreEnBaseX = sousChaine(nombreEnBaseX, debut=1)
    i := position (C, symboles)
    val := val + i
 fin tantQue
 resultat := val
fin
</pre>

'''Exemple de fonctionnement'''

On lance le programme, et on répond "101" puis "2". 

À ce stade, ('''ligne 10''')
* symboles vaut "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", 
* val vaut 0, 
* nombreEnBaseX vaut "101", 
* X vaut 2. 
* Les valeurs de c et i sont indéterminées.

'''Au premier passage''' dans la boucle tantQue, 
* la longueur de nombreEnBaseX vaut 3, dont on entre dans la boucle. 
* val prend la valeur 2 * 0, il reste nul. 
* puis c prend la valeur "1" et 
* nombreEnBaseX est raccourci à gauche pour devenir "01". 
* i prend la valeur 1 (position de "1" dans la chaîne "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"), 
* puis val prend la valeur 0+1 = 1.

'''Au deuxième passage''' dans la boucle tantQue, 
* la longueur de nombreEnBaseX vaut 2, dont on entre dans la boucle. 
* val prend la valeur 2 * 1 = 2. 
* puis c prend la valeur "0" et 
* nombreEnBaseX est raccourci à gauche pour devenir "1". 
* i prend la valeur 0 (position de "0" dans la chaîne "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"), 
* puis val prend la valeur 2+0 = 2.

'''Au troisième passage''' dans la boucle tantQue, 
* la longueur de nombreEnBaseX vaut 1, dont on entre dans la boucle. 
* val prend la valeur 2 * 2 = 4. 
* puis c prend la valeur "1" et 
* nombreEnBaseX est raccourci à gauche pour devenir "". 
* i prend la valeur 1 (position de "1" dans la chaîne "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"), 
* puis val prend la valeur 4+1 = 5.

'''Il n'y a pas de quatrième passage''' dans la boucle tantQue, puisque la longueur de nombreEnBaseX vaut 0. On passe donc à la suite, ce qui établit le résultat à 5.

'''Exercice'''

* Vérifiez que si on lance l'algorithme et qu'on répond "75" puis "8", le résultat vaut 61 (en base décimale).
* Vérifiez que si on lance l'algorithme et qu'on répond "AA" puis "16", le résultat vaut 176 (en base décimale).

==== Algorithme pour passer d'une valeur entière à sa représentation base Y ====
<pre>
debut
    chaineConstante symboles := "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    entier val
    entier Y
    chaine repr := ""
    caractere c
    entier quotient
    entier reste
    lire (val)
    lire (Y)
    tantQue val > 0 :
       quotient := val div Y
       reste    := val mod Y
       val := quotient
       c := niemeCaractere (reste, symboles)
       repr := concatener (c, repr)
    fin tantQue
    resultat := repr
fin
</pre>

'''Exemple de fonctionnement'''

On lance l'algorithme et on répond "5" et "2". À ce moment-là ('''à la ligne 11'''), 
* symboles vaut "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", 
* val vaut 5, Y vaut 2 et 
* repr vaut "" (chaîne vide). 
* Les valeurs de c, quotient, reste sont indéterminées.

'''Au premier passage''' dans la boucle, 
* val vaut 5, donc on y entre. 
* quotient prend la valeur 2 et 
* reste prend la valeur 1 ; 
* val prend la valeur 2 ; 
* c devient "1" puisque c'est le caractère numéro 1 de "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ; 
* repr devient "1" attaché à "", donc "1".

'''Au deuxième passage''' dans la boucle, 
* val vaut 2, donc on y entre. 
* quotient prend la valeur 1 et 
* reste prend la valeur 0 ; 
* val prend la valeur 1 ; 
* c devient "0" puisque c'est le caractère numéro 0 de "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ; 
* repr devient "0" attaché à "1", donc "01".

'''Au troisième passage''' dans la boucle, 
* val vaut 1, donc on y entre. 
* quotient prend la valeur 0 et 
* reste prend la valeur 1 ; 
* val prend la valeur 0 ; 
* c devient "1" puisque c'est le caractère numéro 1 de "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ; 
* repr devient "1" attaché à "01", donc "101".

'''Il n'y a pas de quatrième passage''' dansla boucle, puisque val vaut 0. On passe donc à la suite et le résultat vaut "101".

'''Exercice'''
* Vérifiez que si on lance l'algorithme et qu'on répond "61" puis "8", le résultat vaut 75 (en base octale).
* Vérifiez que si on lance l'algorithme et qu'on répond "176" puis "16", le résultat vaut AA (en base hexadécimale).

=== D'autres bases pour les octets ===
La valeur <math>176_{dec}</math> est égale à <math>10101010_{bin}</math>.

Il est assez facile de repérer une faute de frappe quand on écrit '''176''', quand on se relit. Cependant, une faut de frappe telle que 10101110 au lieu de 10101010 peut passer plus facilement inaperçue. Et le risque augmente avec la longueur des nombres.

Remarquons que <math>10101010_{bin} = 176_{dec}</math>, cependant que <math>10101110_{bin} = 180_{dec}</math>. L'erreur est plus évidente à repérer en codage décimal.

==== Base hexadécimale (16) ====
On utilise très souvent la base hexadécimale pour représenter les octets, c'est à dire les nombres binaires à 8 chiffres, de 00000000 à 11111111. En effet, seize est égal à deux puissance quatre : autrement dit, chaque chiffre hexadécimal correspond directement à quatre chiffre binaires, sans erreur possible.

<math>10101010_{bin} = AA_{hex}</math>, cependant que <math>10101110_{bin} = AE_{hex}</math>. L'erreur est plus évidente à repérer en codage hexadécimal, et en plus, elle montre tout de suite que l'erreur se situe dans les quatre chiffre binaires de poids faible (à droite du nombre).

'''N.B.''' : en base hexadécimale, les chiffres sont 0123456789ABCDEF.

==== base octale (8) ====
De même que la base hexadécimale est très pratique pour exprimer des nombres binaires de quatre ou huit chiffres, la base octale va bien pour exprimer des nombres binaires de 3, 6, 9 ou 12 chiffres : en effet, huit est égal à deux à la puissance 3.

'''N.B.''' : en base octale, les chiffres sont 01234567.