Geeraerts"> Représentation des données de base - Portail des formations NSI
Skip to content

Représentation des données : type et valeur de base

Représentation binaire de l’information

Avant de pouvoir étudier la manière dont l’ordinateur traite l’information, nous devons fixer la manière dont cette information est représentée. L’objet de ces leçons est d’étudier la représentation binaire, qui est aujourd’hui1 la représentation universellement utilisée en informatique pour toutes les informations que les ordinateurs manipulent.

Définition :

La représentation binaire signifie que toute l’information sera représentée à l’aide de deux symboles uniquement. Ces deux symboles sont en général les chiffres \(0\) et \(1\), mais on peut également considérer que ce sont les valeurs logiques faux et vrai.

\(\square\)

Dans ce chapitre, nous développerons des techniques permettant de représenter tout type d’information (nombres, texte, images,…) à l’aide d’un représentation binaire, et de manipuler cette représentation. Nous verrons également comment concevoir des techniques de détection et de correction d’erreur sur cette représentation. Mais avant d’aborder cette matière, il est important de bien comprendre la différence entre une information, et sa représentation. L’exemple suivant illustre cette différence.

Exemple :

Considérons la quantité 17, nous pouvons en trouver plusieurs représentations:

  • la représentation usuelle, dite en base \(10\): 17,

  • en base \(2\): 10001 (nous aborderons les les notions de base et de changement de base en détail dans la suite),

  • en chiffres romains: XVII,

\(\blacksquare\)

On voit donc qu’une même information, qu’un même concept admet plusieurs représentations. Le choix de la représentation binaire comme représentation universelle en informatique s’explique par le fait qu’on peut aisément représenter deux valeurs différentes à l’aide d’états différents de composants électriques comme les transistors. Ces même transistors, assemblés en portes logiques, permettent également de manipuler l’information binaire.

Unités de quantité d’information

Commençons par fixer des unités permettant de mesurer la quantité d’information. Nous utiliserons la taille de la représentation binaire de l’information comme mesure:

Définition :

Chaque chiffre (0 ou 1) d’une représentation binaire est appelé bit (contraction de l’anglais binary digit, ou chiffre binaire). Une séquence de 8 bits est appelée un octet (ou byte en anglais).

\(\square\)

Les symboles associés à ces unités sont les suivants (SCC14.3 - Unit Symbols Subcommittee 2004):

Unité Symbole
bit b
octet o
byte B

Nous mesurerons donc l’information en terme de bits ou d’octets (bytes). Naturellement, les quantités d’information manipulées usuellement s’expriment en milliers, millions,… d’octets, il faut donc fixer des noms pour ces unités. Les préfixes officiellement reconnus par l’industrie (“Quantities and Units – Part 13: Information Science and Technology” 2008) sont similaires aux kilo-, méga-,… du système SI. Ces préfixes ne se réfèrent pas à des puissances de 10 comme dans le système SI mais à des puissances de 2:

Nom Abréviation Quantité
kibioctet kio \(2^{10}=1024\approx 10^3\)
mébioctet Mio \(2^{20}=1\ 048\ 576\approx 10^6\)
gibioctet Gio \(2^{30}=1\ 073\ 741\ 824\approx 10^9\)
tebioctet Tio \(2^{40}=1 099\ 511\ 627\ 776\approx 10^{12}\)

La définition de ces préfixes est relativement récente (elle date du début des années 2000). En pratique, on est souvent confronté à al’utilisation des préfixes traditionnels kilo-, méga-, tera-, etc du système SI, qui sont, pour rappel:

Nom Abréviation Quantité
kilooctet ko \(10^3\) octets
mégaoctet Mo \(10^6\) octets
gigaoctet Go \(10^9\) octets
teraoctet To \(10^{12}\) octets

On voit donc qu’un mégaoctet est un petit peu plus petit qu’un mébioctet…Force est de reconnaître qu’une certaine confusion règne ! Cette confusion a d’ailleurs donné lieu à des procès retentissants, notamment aux États-Unis, où des consommateurs ont entamé une class action contre plusieurs fabricants de disques durs et mémoires, les accusant de tromperie sur la capacité de stockage des produits2.

Écriture des nombres dans différentes bases

Nous allons maintenant rappeler les techniques permettant de représenter des nombres dans différentes bases, car ces techniques serviront à expliquer les différents encodages binaires des nombres entiers et rationnels.

La représentation usuelle des nombres est une représentation décimale et positionnelle. Cela signifie:

  1. que les nombres sont représentés par une séquence de chiffres de \(0\) à \(9\) inclus. Il y a bien dix chiffres différents utilisés, d’où le terme décimal; et

  2. que la position de chaque chiffre dans la séquence permet d’associer ce chiffre à une puissance de 10.

Dans cette représentation usuelle, 10 est appelé la base. On parle aussi de représentation en base 10.

Exemple :

Par exemple, la représentation:

\[1234,56\]

signifie que le nombre est composé de:

  • \(4\) unités, ou \(4\times 10^0\);

  • \(3\) dizaines, ou \(3\times 10^1\);

  • \(2\) centaines, ou \(2\times 10^2\);

  • \(1\) millier, ou \(1\times 10^3\);

  • \(5\) dixièmes, ou \(5\times 10^{-1}\); et

  • \(6\) centièmes, ou \(6\times 10^{-2}\).

On voit donc que les puissances de \(10\) associées aux différentes positions (aux différents chiffres) vont décroissantes quand on lit le nombre de gauche à droite, et que la puissance \(10^0\) correspond au chiffre qui se trouve juste à gauche de la virgule.

\(\blacksquare\)

On note également que la base donne le nombre de chiffres que l’on peut utiliser pour représenter les nombres. En base 10, on peut utiliser 10 chiffres différents, à savoir les chiffres de \(0\) à \(9\) inclus.

Ces concepts se généralisent dans n’importe quelle base. Fixons à partir de maintenant une base \(b\geq 2\). Dans cette base, le nombre:

\[d_n\cdots d_0\ ,\ d_{-1}\cdots d_{-k}\]

représente la valeur:

\[\begin{aligned} N& =&d_n\times b^n + d_{n-1}\times b^{n-1}+\cdots+d_0\times b^0+d_{-1}\times b^{-1}+\cdots d_{-k}\times b^{-k}\\ &=&\sum_{i=-k}^{n}d_i\times b^i &\; \;\;\;[1]\end{aligned}\]

où tous les \(d_i\) sont des chiffres dans \(\{0,\ldots b-1\}\).

Exemple :

Si on fixe \(b=2\), le nombre \(1001,{}101\) représente:

\[\begin{aligned} &&1\times 2^3 + 0\times 2^2 + 0\times 2^1+ 1\times 2^0 + 1\times 2^{-1}+0\times 2^{-2}+1\times 2^{-3}\\ &=&8 + 0 + 0 + 1 + \frac{1}{2} + 0 + \frac{1}{8}\\ &=&9,625. \end{aligned}\]

La dernière valeur est bien entendu donnée en base \(10\).

Symétriquement, la valeur \(-4,5\) (en base \(10\)) est représentée par:

\[-100,1\]

en base \(2\). Notons au passage que cette dernière représentation n’est pas stricto sensu une représentation binaire, étant donné que les symboles \(,\) (virgule) et \(-\) (moins unaire) sont utilisés, en plus du \(0\) et du \(1\). Nous verrons plus tard comment une telle valeur peut être représentée en utilisant des \(0\) et des \(1\) uniquement.

\(\blacksquare\)

Afin d’éviter toute confusion dans la suite, nous noterons, quand c’est nécessaire, la base en indice des nombres. Par exemple, \(101_2\) signifie que le nombre \(101\) doit être interprété comme étant en base \(2\) (c’est-à-dire \(5_{10}\)). Notons que dans certains langages de programmation, comme le C (Banahan, Brady, and Mark Doran 1991), on utilise d’autres conventions pour expliciter certaines bases: les nombres en base \(16\) son préfixés par 0x, et les nombres en base \(2\) par 0b. Enfin, notons qu’en base \(2\), nous grouperons souvent les bits par paquets de \(4\), en introduisant un petit espace, et ce, uniquement dans un souci de lisibilité. Nous écrivons ainsi \(1011\ 1001\) au lieu de \(10111001\).

En informatique, les bases usuelles sont la base \(2\), la base \(8\) (on parle d’octal) et la base \(16\) (on parle d’hexadécimal). Pour la base \(16\), on est confronté au problème suivant: les chiffres utilisés devraient être \(0\), \(1\),…\(10\), \(11\), \(12\), \(13\), \(14\) et \(15\). Mais les “chiffres” de \(10\) à \(15\) demandent deux symboles pour être représentés, ce qui risque de porter à confusion. Par exemple, doit-on interpréter \(10_{16}\) comme le chiffre \(10\) (et alors \(10_{16}=10_{10}\)) ou comme les chiffres \(1\) et \(0\) (et donc \(10_{16}=1\times 16+0\times 1=16_{10}\)) ? Pour éviter ce problème, on remplace les “chiffres” de \(10\) à \(15\) par les lettres de a à f, selon la correspondance suivante:

Lettre: a b c d e f
Valeur: 10 11 12 13 14 15

Exemple :

En base 16:

\[\begin{aligned} \mathtt{a}5\mathtt{f},\mathtt{b} &=&10\times 16^2 + 5\times 16^1 + 15\times 16^0 + 11\times 16^{-1}\\ &=&2655,6875_{10}. \end{aligned}\]

\(\blacksquare\)

Sur base de ces définitions, nous pouvons déjà faire quelques remarques utiles.

Chiffres de poids fort, de poids faible

Dans la représentation positionnelle usuelle, le chiffre le plus à gauche est associé à une puissance plus élevée de la base. On parle donc de chiffre de “poids fort”; le chiffre étant associé à la puissance la plus faible est appel chiffre de “poids faible”. En particulier, en binaire, on parle de bit de poids fort et bit de poids faible.

Comme nous l’avons dit, le bit de poids fort est, par convention à gauche dans la représentation (positionnelle) usuelle. Mais quand on s’intéresse à des valeurs qui ne sont plus écrites sur papier, mais bien stockées ou manipulées par des circuits électroniques (où les notions de “gauche” et “droite” n’ont pas forcément de sens), il est parfois utile de préciser explicitement quel est le bit de poids fort ou le bit de poids faible.

Ajouts de zéros

Dans toutes les bases, et à condition d’utiliser la représentation positionnelle usuelle (avec le chiffre de poids fort à gauche), on peut toujours ajouter des \(0\) à gauche de la partie entière ou à droite de la partie décimale, sans modifier la valeur du nombre représentée. Par exemple, \(13,5_{10}=0013,5000_{10}\). Par contre, on ne peut pas ajouter de zéros à d’autres endroits sans modifier la valeur du nombre. Par exemple, \(101_2\neq 101000_2\) (voir aussi la remarque suivante).

Multiplier ou diviser par la base

Dans toutes les bases, on peut aisément multiplier ou diviser par la base en déplaçant la position de la virgule:

Note :

Dans toute base \(b\), déplacer la virgule de \(k\) position vers la droite ( ou ajouter \(k\) zéros à droite dans le cas d’un nombre entier) revient à multiplier par \(b^k\). Déplacer la virgule de \(k\) positions vers la gauche revient à diviser par \(b^k\). Si on souhaite faire une division entière par \(b^k\), le reste est constitué des \(k\) chiffres de poids faible, et on obtient le quotient en retranchant ces \(k\) chiffres de poids faible.

\(\square\)

Nous utiliserons les opérateurs \(\div\) et \(\bmod\) pour noter respectivement la division entière et le reste de la division. Voici quatre exemples qui illustrent ces remarques:

Exemple :

\[\begin{aligned} 101,111_2\times 4_{10} &=& 101,111_2\times 2^2\\ &=&10111,1_2\\ 101,111_2 / 2_{10} &=& 10,1111_2\\ 1011\ 1011_2 \div 100_2 &=& 1011\ 1011_2\div 2^2\\ &=&10\ 1110\\ 1011\ 1011_2 \bmod 100_2 &=& 11_2. \end{aligned}\]

\(\blacksquare\)

Combien de nombres représentables sur \(n\) chiffres ?

Enfin, l’observation suivante aura toute son importance dans la suite. Fixons une base \(b\) et considérons des nombres entiers positifs sur \(n\) chiffres. Nous avons \(b\) choix pour chacun de ces \(n\) chiffres, soit un total de \(b^n\) nombres différents que l’on peut représenter sur \(n\) chiffres. Ces nombres sont tous les nombres de:

\[\underbrace{0\cdots 0}_{n\text{ chiffres}}\]

à:

\[\underbrace{(b-1)\cdots (b-1)}_{n\text{ chiffres}} = b^n-1.\]

Note :

En base \(b\), il y a \(b^n\) nombres (entiers positifs) représentables sur \(n\) chiffres: les nombres de \(0\) à \(b^n-1\).

\(\square\)

Notons que quand nous souhaiterons représenter des nombres négatifs de manière purement binaire (donc, sans utiliser le symbole -), nous aurons besoin d’utiliser certaines de ces représentations pour “encoder” des nombres négatifs.

Exemple :

Il y a donc \(2^n\) nombres binaires sur \(n\) bits. Par exemple, il y a \(2^{32}=4\ 294\ 967\ 296_{10}\) (soit à peu près \(4\) milliards de) nombres binaires différents sur \(32\) bits.

\(\blacksquare\)

Changements de base

Comment peut-on, étant donné un nombre \(N\) donné dans une certaine base, trouver sa représentation dans une autre base \(b\) ? Répondre à cette question revient à calculer les valeurs \(d_i\) de l’équation \([1]\) dans la base \(b\).

Cas des nombres entiers

Nous allons commencer par supposer que \(N\) est un nombre entier positif. Observons d’abord que si \(N<b\), on exprime le nombre à l’aide du chiffre correspondant dans la nouvelle base3. Autrement, divisons \(N\) par \(b\) (il s’agit de la division entière), ce qui nous donne un quotient \(q_0=N\div b\) et un reste \(r_0=N\mod b\). La relation existant entre ces valeurs est:

\[\begin{aligned} N&= q_0\times b +r_0.&[2]\end{aligned}\]

Comme nous avons supposé que \(N\geq b\), nous savons que \(q_0\neq0\). Recommençons l’opération en divisant \(q_0\) par \(b\); nous obtenons à nouveau un quotient que nous appelons \(q_1\) et un reste que nous appelons \(r_1\). Nous avons donc la relation:

\[\begin{aligned} q_0&= q_1\times b+r_1,\end{aligned}\]

En combinant cette équation avec \([2]\), nous obtenons:

\[\begin{aligned} N&= (q_1\times b+r_1)\times b+r_0\\ &= q_1\times b^2+r_1\times b+r_0. \end{aligned}\]

Si \(q_1>0\), on recommence en divisant \(q_1\) par \(b\), pour obtenir un nouveau quotient \(q_2\) et un nouveau reste \(r_2\) tels que:

\[\begin{aligned} N&= (q_2\times b+r_2)\times b^2+r_1\times b+r_0\\ &= (q_2\times b^3)+r_2\times b^2+r_1\times b+r_0.\end{aligned}\]

Si nous continuons ce développement en réalisant \(k+1\) divisions, nous obtenons une suite de restes \(r_0\), \(r_1\),…\(r_k\) tels que:

\[\begin{aligned} N &= (q_k\times b^{k+1})+r_k\times b^k+\cdots+r_2\times b^2+r_1\times b+r_0.\\\end{aligned}\]

Supposons que nous avons continué ce développement jusqu’à ce que \(q_k=0\) (ce qui finira toujours par arriver étant donné qu’on est parti d’un \(N\) fixé). On a alors:

\[\begin{aligned} N &=(q_k\times b^{k+1})+r_k\times b^k+\cdots+r_2\times b^2+r_1\times b+r_0\\ &=(q_k\times b^{k+1})+r_k\times b^k+\cdots+r_2\times b^2+r_1\times b^1+r_0\times b^0\\ &=(q_k\times b^{k+1})+\sum_{i=0}^{k}r_i\times b^i \\ &=(0\times b^{k+1})+\sum_{i=0}^{k}r_i\times b^i \\ &=\sum_{i=0}^{k}r_i\times b^i.&[3]\end{aligned}\]

On peut maintenant comparer cette dernière équation \([3]\) à l’équation \([1]\), et constater que les restes \(r_i\) que nous avons calculés en effectuant des divisions successives par \(b\) correspondent aux \(d_i\) que nous cherchons pour représenter le nombre \(N\) en base \(b\). Attention tout de même que le premier reste calculé (\(r_0\)) est le chiffre de poids faible ! Pour résumer:

Note :

Pour exprimer un nombre \(N\) en base \(b\), on divise \(N\) par \(b\) de manière répétée. La séquence des restes calculés donne la représentation de \(N\) en base \(b\) du chiffre de poids faible au chiffre de poids fort (autrement dit: “à l’envers”).

\(\square\)

Nombres réels

Nous pouvons maintenant généraliser ce principe aux nombres réels4. Commençons par observer qu’un nombre rationnel qui possède une expression finie dans une base ne possède pas forcément une expression finie dans toutes les bases. Prenons par exemple le nombre \(\frac{1}{3}\). Nous savons qu’il n’est possible de l’exprimer de manière finie en base \(10\), mais bien de manière infinie périodique:

\[\frac{1}{3}=0,3333_{10}\ldots\]

Nous notons cette représentation infinie périodique en soulignant la partie qui se répète infiniment souvent:

\[\frac{1}{3}=0,\underline{3}.\]

Par contre, comme \(\frac{1}{3}=3^{-1}\), on peut exprimer \(\frac{1}{3}\) de manière finie en base \(3\):

\[\frac{1}{3}=0,1_{3}.\]

Voyons maintenant comment représenter un nombre \(N<1\) dans une base \(b\) arbitraire. Notons que nous supposons que \(N<1\) car on peut traiter séparément la partie entière et la partie fractionnelle d’un nombre. Pour exprimer \(N\) en base \(b\), nous allons procéder par multiplication successive par \(b\). Supposons que \(N\) est de la forme:

\[\begin{aligned} N &= 0,\alpha_0\end{aligned}\]

\(\alpha_0\) représente la séquence de chiffres de la partie fractionnaire du nombre. En multipliant \(N\) par \(b\) on obtient un nouveau nombre de la forme:

\[\begin{aligned} N\times b &= \beta_1,\alpha_1\end{aligned}\]

\(\beta_1\) est la partie entière, et \(\alpha_1\) la partie décimale. Comme nous avons supposé que \(N<1\), nous savons que \(0\leq \beta_1 \leq b-1\). Considérons le nouveau nombre \(0,\alpha_1\), et appelons-le \(N_1\). Nous avons donc :

\[\begin{aligned} N_1 &= 0,\alpha_1\\ N &= \frac{\beta_1}{b} + \frac{N_1}{b}.& [4]\end{aligned}\]

Multiplions maintenant \(N_1\) par \(b\), nous obtenons un nombre de la forme:

\[\begin{aligned} N_1\times b &= \beta_2,\alpha_2 \end{aligned}\]

avec \(0\leq \beta_2 \leq b-1\). Nous pouvons à nouveau poser \(N_2\) et obtenir:

\[\begin{aligned} N_2 &= 0,\alpha_2\\ N_1 &= \frac{\beta_2}{b} + \frac{N_2}{b}.& [5]\end{aligned}\]

En combinant \([5]\) et \([4]\), nous obtenons:

\[\begin{aligned} N &= \frac{\beta_1}{b} + \frac{\frac{\beta_2}{b} + \frac{N_2}{b}}{b}\\ &= \frac{\beta_1}{b} +\frac{\beta_2}{b^2} + \frac{N_2}{b^2}\\ &= \beta_1\times b^{-1} + \beta_2\times b^{-2} + N_2\times b^{-2}.\end{aligned}\]

Nous pouvons continuer ce développement, en multipliant successivement tous les \(N_i=0,\alpha_i\) par \(b\), pour obtenir un suite aussi longue que souhaitée de \(\beta_i\) tels que:

\[\begin{aligned} N &= \beta_1\times b^{-1} + \beta_2\times b^{-2} +\cdots \beta_k\times b^{-k} + N_k\times b^{-k}\\ &=\sum_{i=1}^{k} \beta_i b^{-i}+ N_k\times b^{-k}& [6].\end{aligned}\]

En comparant \([6]\) et \([1]\), on voit que la séquence des \(\beta_i\) ainsi calculée correspond à la séquence des \(d_{-i}\) nécessaires pour exprimer \(N\) en base \(b\). Ce développement sera arrêté soit lorsque \(N_i=0\), soit dès qu’on détecte deux valeurs \(N_j\), \(N_i\) (\(i\neq j\)) telles que \(N_j=N_i\), ce qui signifie que l’expression de \(N\) en base \(b\) est infinie périodique.

Exemple :

Considérons \(N=-24,42_{10}\) à exprimer en base \(2\). Nous allons commencer par exprimer \(24\) en base \(2\), en divisant successivement \(24\) par \(2\). On commence par \(24/2=12\) avec un reste de \(0\). Autrement dit \(q_0=12\) et \(r_0=0\). On poursuit en divisant \(q_0\) par \(2\), etc:

\(i\) \(q_i\) \(r_i\)
0 12 0
1 6 0
2 3 0
3 1 1
4 0 1

On lit maintenant la séquence des restes de haut en bas, en on obtient: \(24_{10} = 11000_2\).

Pour la partie fractionnaire, on procède par multiplication successive par \(2\). On commence par \(0,42\times 2=0,84\). Autrement dit, \(\beta_1=0\) et \(N_1=0,84\). On multiplie à nouveau \(N_1\) par \(2\), soit \(2\times 0,84= 1,68\). On obtient donc:

\(i\) \(\beta_i\) \(N_i\)
1 0 0,84
2 1 0,68
3 1 0,36
4 0 0,72
5 1 0,44
6 0 0,88
7 1 0,76
8 1 0,52
9 1 0,04
10 0 0,08
11 0 0,16
12 0 0,32
13 0 0,64
14 1 0,28
15 0 0,56
16 1 0,12
17 0 0,24
18 0 0,48
19 0 0,96
20 1 0,92
21 1 0,84

On voit donc que \(N_{21}=N_1\), la suite du développement se poursuivra donc ad infinitum de manière cyclique. Donc:

\[0,42_{10}=0,0\underline{110\ 1011\ 1000\ 0101\ 0011}_2\]

et finalement:

\[-24,42_{10} = - 1\ 1000, 0\underline{110\ 1011\ 1000\ 0101\ 0011}_2.\]

\(\blacksquare\)

Opérations en base 2

Comme la base \(2\) est celle qui nous sera la plus utile dans la suite, nous allons maintenant nous intéresser aux différentes opérations que nous pouvons appliquer aux nombres dans cette base.

Opérations arithmétiques

On peut utiliser l’addition, la soustraction, la multiplication et la division euclidienne sur les nombres dans n’importe quelle base, en particulier la base \(2\). Pour l’addition, on procède en base \(2\) comme en base \(10\), en faisant d’abord la somme des unités, puis des chiffres correspondant au poids \(2^1\) (au lieu de \(10^1\) en base \(10\)), \(2^2\), etc…Il faut simplement être attentif au fait qu’un report a lieu dès que la somme dépasse \(2_{10}=10_2\). Par exemple: \(1+0\) donne une somme de \(1\), et un report de \(0\). Par contre, \(1+1=10_2\) donne une somme de \(0\) et un report de \(1\). De même, \(1+1+1=11_2\) donne une somme de \(1\) et un report de \(1\). Par exemple:

Exemple :

\[\begin{array}{cccccc} &{}^1&{}^1&{}^1&{}^1\\ & &1&0&1&1\\ +& &1&1&0&1\\ \hline &1&1&0&0&0 \end{array}\]

\(\blacksquare\)

Opérations logiques

En base 2, on peut utiliser une série d’opérations qui n’ont pas d’équivalent naturel dans les autres bases. Ce sont les opérations logiques, que l’on peut appliquer en considérant que le 0 représente la valeur logique faux, et que le 1 représente la valeur logique vrai.

On définit les opérateurs binaires5 et\(\;\) (noté \(\wedge\)), ou\(\;\) (noté \(\vee\)), et ou exclusif\(\;\) (noté \(\,\mathit{XOR}\,\)); ainsi que l’opérateur unaire non\(\;\) (noté \(\neg\)). Pour définir leur effet sur deux nombres binaires, on commence par les définir sur deux bits (ou un bit dans le cas du \(\neg\)). Pour ce faire, on utilise une table de vérité, qui donne, pour chaque valeur possible des opérandes (de l’opérande), la valeur renvoyée par l’opérateur. Voici les tables de vérité de ces opérateurs:

Définition :

\(x\) \(y\) \(x\wedge y\)
0 0 0
0 1 0
1 0 0
1 1 1
\(x\) \(y\) \(x\vee y\)
0 0 0
0 1 1
1 0 1
1 1 1
\(x\) \(y\) \(x \,\mathit{XOR}\, y\)
0 0 0
0 1 1
1 0 1
1 1 0
\(x\) \(\neg x\)
0 1
1 0

\(\square\)

On remarquera que ces opérateurs expriment l’idée intuitive qu’on peut s’en faire à la lecture de leur nom. L’opération \(x\land y\) vaut \(1\) si et seulement \(x\) et \(y\) sont vraies (soit \(x=1\) et \(y=1\)). L’opération \(x\lor y\) vaut \(1\) si et seulement si \(x\) ou \(y\) est vraie. L’opération \(x \,\mathit{XOR}\, y\) vaut \(1\) si et seulement si soit \(x\) est vraie soit \(y\) est vraie mais pas les deux en même temps (si \(x\) est vraie, cela exclut donc le fait que \(y\) soit vraie et vice-versa). Finalement, \(\neg x\) remplace la valeur de vérité de \(x\) par son opposé (vrai par faux et faux par vrai).

On peut maintenant généraliser ces opérations à n’importe quel nombre binaire, en appliquant les opérations bit à bit: étant donné deux nombres sur \(n\) bits \(A=a_{n-1}a_{n-2}\cdots a_0\) et \(B=b_{n-1}b_{n-2}\cdots b_0\), on applique l’opération sur chaque paire de bits \(a_i\), \(b_i\) pour obtenir le bit \(c_i\) du résultat. Par exemple, \(A\wedge B\) est le nombre \(C=c_{n-1}c_{n-2}\cdots c_0\), où \(c_{n-1}=a_{n-1}\wedge b_{n-1}\), \(c_{n-2}=a_{n-2}\wedge b_{n-2}\),…et \(c_0=a_0\wedge b_0\). Et ainsi de suite pour les autres opérations.

Masques

Ces opérations logiques permettent de réaliser certaines manipulations des valeurs binaires, appelées masques ou masquages. On observe que \(x\wedge 0=0\) et \(x\wedge 1=x\), quelque soit la valeur de \(x\) (sur un bit). De ce fait, le \(\wedge\) peut être utilisé pour masquer certains bit d’un nombre, c’est-à-dire remplacer ces bits par des 0 tout en conservant les autres. Il suffit de prendre la conjonction de ce nombre avec une valeur binaire comprenant des \(0\) à toutes les positions qu’on veut masquer, et des \(1\) partout ailleurs.

Exemple :

Supposons qu’on souhaite masquer les 4 bits de poids fort d’un nombre \(N\) de 8 bits. On peut faire: \(N\wedge 0000\ 1111\). Si \(N=1010\ 1010\), on a bien \(N \wedge 0000\ 1111=0000\ 1010\).

\(\blacksquare\)

Les masques peuvent être très utiles. On peut déjà observer que les masques permettent de calculer le reste d’une division entière par une puissance de \(2\). En effet, nous avons déjà vu plus haut que le reste de la division entière de \(N\) par \(2^k\) est le nombre composé des \(k\) bits de poids faible de \(N\). On peut donc masquer les autres bits pour ne retenir que ces \(k\) bits.

Exemple :

Par exemple:

\[\begin{aligned} 1010\ 0101_2 \bmod 8_{10} &= &1010\ 0101_2 \bmod 2^3\\ &= &1010\ 0101_2 \wedge 0000\ 0\underbrace{111}_3\\ &= &0000\ 0101_2\\ &= &101_2. \end{aligned}\]

\(\blacksquare\)

Décalages, division et multiplications

Une autre opération utile (mais qui n’est pas réservée aux nombres binaires) est l’opération de décalage de \(n\) positions (où \(n\) est un naturel). Il y a deux types de décalage:

  • le décalage vers la gauche de \(n\) positions, d’un nombre \(b\) est noté \(b<<n\), et consiste à ajouter \(n\) zéros à la droite (chiffres de poids faible) du nombre (quitte à supprimer les \(n\) chiffres de poids forts pour garder le même nombre de bits). Les chiffres constituant le nombre initial sont donc bien décalés vers la gauche.

  • le décalage vers la droite de \(n\) positions, d’un nombre \(b\) est noté \(b>>n\), et consiste à supprimer les \(n\) chiffres de poids faibles du nombre \(n\) (quitte à ajouter des \(0\) à gauche pour garder le même nombre de bits)

Exemple :

Par exemple, en binaire: \(0010\ 1101 >> 3 = 0000\ 0101\). De même \(0010\ 1101 << 2 = 1011\ 0100\).

\(\blacksquare\)

Comme nous l’avons déjà vu plus haut, ces opérations permettent d’effectuer des multiplications (décalage vers la gauche de \(k\) positions) et des divisions (décalage vers la droite de \(k\) positions) par \(2^k\) (ou, de manière générale, par \(b^k\) dans n’importe quelle base \(b\)).

Exemple :

Par exemple:

  • \(45_{10}\times 10_{10}= 45_{10} \times 10_{10}^1 = 45_{10} << 1 = 450_{10}\)

  • \(531_{10}\div 10_{10}= 531 >> 1 = 53_{10}\)

  • \(100010_2\div 4_{10}= 100010 \div 2^2 = 100010 >> 2 = 1000_2\)

\(\blacksquare\)

Représentation des entiers non-signés

Si nous devons manipuler des nombres entiers non-négatifs6 uniquement, on peut se contenter d’exprimer ce nombre en base \(2\). Cette représentation n’utilisera que les symboles \(0\) et \(1\) et constitue donc bien une représentation binaire. Ces nombres sont souvent appelés les nombres “non signés” en informatique, car il n’est pas nécessaire d’utiliser de symbole pour représenter leur signe. Dans les langages comme C ou C++, par exemple, on trouve le type unsigned int (Banahan, Brady, and Mark Doran 1991; Stroustrup 2018).

Si on considère une représentation sur un nombre \(n\) fixé de bits, cette technique permet de représenter tous les nombres de \(0\) (représenté par \(\underbrace{0\cdots 0}_n\)) à \(2^{n}-1\) (représenté par \(\underbrace{1\cdots 1}_n\)).

Représentation des nombres entiers signés

Voyons maintenant comment nous pouvons incorporer les nombres négatifs dans notre représentation. On ne peut pas se contenter de convertir les nombres vers la base \(2\), car le signe \(-\) qui est utilisé pour signaler qu’un nombre est négatif n’est pas directement manipulable par un ordinateur qui manipule des valeurs en binaire. Il faut donc trouver une technique pour représenter ce signe à l’aide de \(0\) et de \(1\) uniquement. Nous allons étudier quatre techniques différentes. Nous présenterons ces techniques en supposant que l’on considère une représentation sur \(n\) bits (par exemple, \(n=8\)).

Bit de signe

La première technique est la plus simple. Elle n’a que peu d’intérêt pratique, mais nous l’étudions quand même car elle sans doute la première idée à laquelle on pourrait songer, et qu’il est dès lors utile de la comparer à celles qui sont utilisées en pratique. Elle consiste à réserver le bit de poids fort pour représenter le signe du nombre (\(1\) signifiant que le nombre est négatif), qui sera représenté en valeur absolue sur les \(n-1\) bits de poids faible.

Exemple :

Avec le bit de signe sur \(n=8\) bits, le nombre \(5\) est représenté par: \(0000\ 0101\). Le nombre \(-5\) est représenté par \(1000\ 0101\).

\(\blacksquare\)

Cette technique présente plusieurs inconvénients:

  • la valeur \(0\) possède deux représentations: \(0\cdots 0\) et \(10\cdots 0\) (qui représente \(-0\));

  • il est difficile d’effectuer des opérations sur cette représentation. En particulier, effectuer la somme (selon la procédure usuelle) d’un nombre positif et d’un nombre négatif ne donne pas le résultat attendu…

Les valeurs représentables à l’aide du bit de signe, et sur \(n\) bits vont de \(-2^{n-1}+1\) (représentée par \(1\cdots 1\)) à \(2^{n-1}-1\) (représentée par \(01\cdots 1\)). Cela fait au total \(2^n-1\) valeurs différentes, alors qu’il existe \(2^n\) représentations. La différence provient du fait que le zéro a deux représentations distinctes.

Complément à 1

Le complément à \(1\) d’un nombre binaire \(N\) est le nombre \(\overline{N}\) qu’on obtient en inversant tous les bits de \(N\). On peut utiliser le complément à \(1\) pour signaler qu’un nombre est négatif. Plus précisément, si on a une représentation sur \(n\) bits, on représente tous les nombres entiers non-négatifs par leur représentation binaire habituelle, et tous les nombres non-positifs par le complément à \(1\) de leur valeur absolue. Afin de pouvoir distinguer les nombres positifs des nombres négatifs, on limite les valeurs qu’on peut représenter: si on a une représentation sur \(n\) bits, on se limite aux nombres qui, en valeur absolue, tiennent sur \(n-1\) bits. Ainsi, le bit de poids fort sera toujours égal à \(0\) pour les nombres positifs, et à \(1\) pour les nombres négatifs.

Exemple :

Le nombre \(5\) est représenté par \(0000\ 0101\). La représentation de \(-5\) est obtenue en inversant tous les bits de la représentation de \(5\), soit \(1111\ 1010\). Sur \(8\) bits, la valeur \(128\), par exemple, n’est pas représentable, elle s’exprime en binaire par un nombre de \(8\) bits au moins: \(1000\ 0000\), et cette représentation s’interprète, en complément à \(1\), comme \(-0111\ 1111_2=-127\).

\(\blacksquare\)

L’avantage du complément à \(1\) sur le bit de signe est qu’il permet de faire des additions de manière relativement naturelle: on peut faire la somme usuelle de deux nombres (positifs ou négatifs) en complément à \(1\) et obtenir la réponse correcte, à condition d’ajouter le dernier report au résultat.

Exemple :

Nous donnons deux exemples sur \(4\) bits.

Considérons \(3-2 = 3+(-2)\). En binaire, avec le complément à \(1\), on obtient \(0011 + 1101\). En faisant la somme euclidienne, on obtient \(1\ 0000\), soit, sur \(4\) bits, \(0000\) avec un dernier report de \(1\). On ajoute ce report aux \(4\) bits de poids faible, et on obtient: \(0001\).

Considérons \(2-4 = 2+(-4)\). En binaire, avec le complément à \(1\), on obtient \(0010 + 1011\). En faisant la somme euclidienne, on obtient \(1101\) (le dernier report est égal à \(0\)), ce qui est bien la représentation, en complément à \(1\), de \(-2\).

\(\blacksquare\)

Malheureusement, comme avec le bit de signe, \(0\) possède toujours deux représentations en complément à \(1\): \(0\cdots 0\) et \(1\cdots 1\). De ce fait, on ne peut, sur \(n\) bits, représenter que les nombres de \(-2^{n-1}+1\) à \(2^{n-1}-1\), soit à nouveau \(2^n-1\) valeurs différentes.

Complément à 2

Cette représentation est celle qui est utilisée en pratique pour les nombres entiers sur les processeurs modernes.

Le complément à \(2\) d’un nombre \(N\) est le nombre \(\overline{N}^2=2^n-N\) (où \(n\) est toujours le nombre de bits de la représentation). La représentation des nombres en complément à \(2\) suit le même principe que le complément à \(1\): les nombres non-négatifs sont représentés par leur encodage binaire usuel; et les nombres négatifs sont représentés par le complément à \(2\) de leur valeur absolue.

Exemple :

Voici 3 exemples sur \(n=8\) bits:

  • \(1\) est représenté par \(00000001\);

  • \(-1\) est représenté par la représentation de \(2^8-1\), soit \(11111111\);

  • \(-5\) est représenté par la représentation de \(2^8-5\), soit \(11111011\).

\(\blacksquare\)

La technique du complément à \(2\) possède de nombreux avantages. Tout d’abord, \(0\) ne possède plus qu’une seule représentation, à savoir \(0\cdots 0\). Ensuite, on peut faire usage de l’addition usuelle sur tous les nombres positifs ou négatifs en complément à deux (il n’est pas nécessaire d’utiliser le report circulaire comme dans le cas du complément à \(1\), celui-ci peut être oublié).

Exemple :

Voici un exemple d’addition sur \(4\) bits. Considérons la somme \(7-5=7+(-5)\). En binaire et avec le complément à \(2\), \(-5\) est représenté par la représentation “classique” de \(2^4-5=16-5=11_{10}\), soit \(1011_2\). On a donc: \(0111_2 + 1011_2= 1\ 0010_2\), que l’on tronque sur \(4\) bits (on oublie systématiquement le dernier report) pour obtenir \(0010_2\), soit \(2_{10}\).

\(\blacksquare\)

Par ailleurs, comme zéro n’a plus qu’une seule représentation, on peut maintenant représenter \(2^n\) valeurs différentes sur \(n\) bits. La plus petite valeur représentable est maintenant \(-2^{n-1}\) (représentée par \(10\cdots 0\)), et la plus grande est \(2^{n-1}-1\) (représentée par \(01\cdots 1\)). On a donc gagné une valeur dans les négatifs par rapport au complément à \(1\).

Enfin, remarquons que \(\overline{N}^2\) peut être calculé plus facilement grâce à \(\overline{N}\), le complément à \(1\). En effet:

Théorème 1.1. Pour tout \(N\): \(\overline{N}^2=\overline{N}+1\).

Preuve

Nous considérons une représentation des nombres sur \(n\) bits. Nous savons que la somme d’un nombre avec son complément à \(1\) donne:

\[\begin{aligned} N + \overline{N} &= 1\cdots 1 \\ &= 2^n-1. \end{aligned}\]

Donc, en ajoutant \(1\) de part et d’autre de cette équation, nous avons:

\[\begin{aligned} N + \overline{N} + 1 &= 2^n-1 +1 \\ &= 2^n. \end{aligned}\]

En retranchant \(N\) de deux côtés, nous avons:

\[\begin{aligned} 2^n -N &= N + \overline{N} + 1 -N\\ &= \overline{N} + 1. \end{aligned}\]

Or, \(2^n-N=\overline{N}^2\), par définition. La dernière équation prouve donc que \(\overline{N}^2 = \overline{N}+1\). \(\Box\)

Excès à \(K\)

La technique de l’excès à \(K\) est à nouveau une idée simple: elle consiste à fixer une valeur \(K\) (appelée biais) suffisamment grande, et à représenter tous les nombres \(N\) (positifs ou négatifs) par la représentation binaire de \(N+K\) (nécessairement positif). De ce fait, sur \(n\) bits, toutes les valeurs entre \(-K\) (représentée par \(0\cdots 0\)) et \(2^n-1-K\) (représentée par \(1\cdots 1\)) sont représentables. On choisit souvent \(K\) égal à \(2^{n-1}\) de manière à répartir les valeurs positives et négatives représentables de manière équitable, mais ce n’est pas obligatoire (par exemple, dans la norme IEEE754 que nous verrons plus tard, ce n’est pas le cas).

Exemple :

Voici trois exemples sur 8 bits avec \(K=2^{n-1}=2^7=128_{10}\):

  • \(1\) est représenté par la représentation binaire de \(1+2^7=129\), soit \(1000\ 0001\);

  • \(-1\) est représenté par la représentation de \(2^7-1\), soit \(0111\ 1111\);

  • \(-5\) est représenté par la représentation de \(2^7-5\), soit \(0111\ 1011\).

\(\blacksquare\)

Comparaison des différentes représentation

Afin de bien comprendre comment les différentes techniques de représentation fonctionnent, il peut être utile de les comparer. C’est l’objet de la Table suivante : elle montre comment une même représentation binaire sur \(n\) bits (colonne de gauche) représente des valeurs différentes en fonction de la convention utilisée (voir aussi, à ce sujet, la discussion à la fin du présent chapitre).

Valeur représentée
Représentation Non signé Bit Signe Cpl. 1 Cpl. 2 Excès \(K\)
\(00\cdots 00\) \(0\) \(0\) \(0\) \(0\) \(-K\)
\(00\cdots 01\) \(1\) \(1\) \(1\) \(1\) \(-K+1\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(01\cdots 11\) \(2^{n-1}-1\) \(2^{n-1}-1\) \(\;\;\;2^{n-1}-1\;\;\;\) \(2^{n-1}-1\) \(\;\;\;2^{n-1}-1 - K\)
\(10\cdots 00\) \(2^{n-1}\) \(0\) \(-2^{n-1}+1\;\;\;\) \(-2^{n-1}\) \(2^{n-1}-K\)
\(10\cdots 01\) \(2^{n-1}+1\) \(-1\) \(-2^{n-1}+2\;\;\;\) \(\;\;\;-2^{n-1}+1\;\;\;\) \(\;\;\;2^{n-1}+1 - K\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(11\cdots 11\) \(2^n-1\) \(-2^{n-1}+1\) \(0\) \(-1\) \(2^n-1-K\)

Comparaison des différentes représentations (sur \(n\) bits).

Représentation des nombres “réels”

Nous allons maintenant étudier des techniques permettant de représenter des nombres qui ne sont pas entiers. Comme nous l’avons déjà observé, il est impossible, en toute généralité, de représenter tous les nombres réels à l’aide d’un ordinateur. En effet, les nombres irrationnels7, comme le nombre \(\pi\), ont une partie décimale infinie non-périodique8. Or tout ordinateur ne dispose jamais que d’une quantité finie de mémoire, et, la représentation explicite d’un nombre réel irrationnel (dans n’importe quelle base naturelle) demanderait donc une mémoire infinie.

Les nombres que nous allons être en mesure de représenter sont tous des nombres rationnels, c’est-à-dire des nombres que nous exprimerons (dans une base fixée) sous la forme \(\alpha,\beta\): à l’aide d’une partie entière \(\alpha\) et d’une partie fractionnaire \(0,\beta\), toutes les deux finies. Par exemple, pour le nombre \(42,625\), nous avons \(\alpha=42\) et \(\beta=625\).

Une première technique: la virgule fixe

Comme nous l’avons déjà remarqué, si nous pouvons exprimer séparément \(\alpha\) et \(0,\beta\) en binaire, nous ne pouvons pas exprimer explicitement la virgule, et nous devons donc trouver une manière de contourner ce problème. Une première technique, qui est simple mais qui a ses limites, consiste à fixer arbitrairement la position de la virgule au sein d’une représentation de taille fixée. Par exemple, si on considère des représentations sur \(n=32\) bits, on pourrait décider que les \(16\) bits de poids fort représentent la partie entière \(\alpha\), et que les \(16\) bits de poids faible représentent la partie fractionnaire de \(0,\beta\).

Exemple :

Avec la convention ci-dessus, le nombre \(42,625\) est représenté par:

\[\begin{array}{|c|c|} \hline 0000\ 0000\ 0010\ 1010 & 1010\ 0000\ 0000\ 0000\\ \hline \end{array}\]

En effet, \(42,625_{10}=10\ 1010,101_2\). On remarque que des zéros on été ajoutés pour compléter les \(32\) bits: à gauche de la partie entière et à droite de la partie décimale.

\(\blacksquare\)

Le problème de cette technique est qu’elle limite de manière excessive les nombres qu’on peut représenter, comme le montre l’exemple suivant:

Exemple :

En suivant la convention donnée ci-dessus, le nombre \(2^{-17}\) ne peut pas être représenté. En effet:

\[2^{-17} = 0,0000\ 0000\ 0000\ 0000\ 1_2\ ,\]

et donc, la partie \(\beta\) n’est pas représentable sur les \(16\) bits alloués dans notre représentation. On a affaire à un nombre trop petit, on parle d’underflow.

De même, le nombre \(2^{16}\) ne peut pas être représenté car:

\[2^{16} = 1\ 0000\ 0000\ 0000\ 0000_2 .\]

On a ici affaire à un overflow.

\(\blacksquare\)

Ces deux exemples sont un peu frustrants. On a en effet une représentation sur \(32\) bits, qui permettrait aisément de représenter tant \(2^{-17}\) que \(2^{16}\), si on avait l’opportunité de déplacer la virgule. En effet, tant la partie entière de \(2^{-17}\) que la partie décimale de \(2^{16}\) se réduisent à un seul \(0\), et ne nécessitent donc certainement pas \(16\) bits.

La virgule flottante: IEEE754

Pour remédier à ce problème, on peut utiliser une technique dite de virgule flottante, où la position de la virgule n’est pas spécifiée a priori, mais où la représentation binaire du nombre (tant sa partie entière que sa partie décimale) s’accompagne d’une information qui indique où positionner la virgule. Une telle technique s’inspire de la notation scientifique des nombres, qui consiste à exprimer tous les nombres (en base 10) sous la forme: \(\(0,f\times 10^x.\)\)

Exemple :

Voici trois nombres et leur représentations “scientifiques” respectives:

\[\begin{aligned} 42,625 &=& 0,42625\times 10^2\\ 0,00034 &=& 0,34 \times 10^{-3}\\ 25 &=& 0,25\times 10^2. \end{aligned}\]

\(\blacksquare\)

On voit bien sur ces exemples que l’exposant \(x\) indique la position de la virgule, où, pour être plus précis, le nombre de décalages (vers la droite pour un exposant positif, vers la gauche pour un exposant négatif) de la virgule qu’il faut affecter au nombre \(0,\ldots\) pour retrouver le nombre d’origine.

Ce principe se retrouve dans le standard industriel IEEE754-20089, dont nous allons maintenant étudier une partie, à titre exemplatif (“IEEE Standard for Floating-Point Arithmetic” 2008). Nous allons nous concentrer sur la représentation des nombres sur \(32\) bits. Dans cette norme10, les \(32\) bits sont répartis entre:

  • un bit de signe \(s\), le bit de poids fort;

  • suivi de \(8\) bits représentant un exposant \(e\), exprimé en excès à 127;

  • suivis de \(23\) bits de signifiant \(f\).

Une telle représentation est l’encodage du nombre suivant:

\[(-1)^s \times 1,f\times 2^e\ .\]

On voit donc que le bit \(s\) se comporte bien comme un bit de signe (le nombre représenté est négatif si et seulement si \(s=1\)). On suppose qu’on a préalablement exprimé le nombre sous la forme \(1,f\), et seuls les bits de \(f\) sont effectivement stockés dans la représentation, ce qui permet d’économiser un bit. Enfin, l’exposant \(e\) est une puissance de \(2\) et non pas de \(10\) comme dans la représentation scientifique, ce qui est logique étant donné que nous utilisons une représentation binaire. L’exposant indique donc bien un décalage à affecter à la virgule.

Exemple :

Considérons à nouveau le nombre \(42,625_{10}\). Pour trouver sa représentation IEEE754, nous commençons par l’exprime en binaire:

\[42,625_{10} =10\ 1010,101_2\ .\]

Nous normalisons ensuite cette représentation en déplaçant la virgule de \(5\) positions vers la gauche pour obtenir un nombre de la forme \(1,f\times 2^e\):

\[42,625_{10} =1,0101\ 0101 \times 2^{5}.\]

À noter que l’exposant est positif pour maintenir l’égalité. Nous pouvons maintenant trouver aisément les différents composants de la représentation:

  • le signe \(s=0\), car le nombre est positif;

  • l’exposant \(e=5\), que nous devons représenter en excès à \(127\) sur \(8\) bits. Cela revient à représenter \(5+127=132\) en binaire, soit \(1000\ 0100\);

  • enfin, le signifiant est la partie après la virgule: \(f=01010101\).

Nous avons donc la représentation:

\[\begin{array}{|c|c|c|} \hline 0 & 1000\ 0100 & 0101\ 0101\ 0\cdots 0\\ \hline \end{array}\]

Remarquons que les \(0\) ont été ajoutés dans les bits de poids faible du signifiant, afin de ne pas changer sa valeur (ajouter des zéros dans les bits de poids forts reviendrait à insérer des zéros juste à droite de la virgule). ../.

Comme ces nombres sont relativement longs à écrire, il est souvent pratique d’utiliser une représentation en hexadécimal pour la totalité de l’encodage binaire:

\(0100\) \(0010\) \(0010\) \(1010\) \(1000\) \(0000\) \(0000\) \(0000\)
=
\(4\) \(2\) \(2\) \(\mathtt{a}\) \(8\) \(0\) \(0\) \(0\)

soit: \(422\mathtt{a}8000\).

\(\blacksquare\)

Un problème que nous devons encore résoudre est la représentation de \(0\). En effet, \(0\) ne peut pas s’exprimer sous la forme \(1,f\), il faut donc fixer une représentation spéciale. La norme IEEE754 en retient deux: \(10\cdots 0\), soit \(00\cdots 0\).

Notons enfin que la norme admet également des valeurs spéciales, comme \(\infty\) et Not a Number (ou NaN). Ces valeurs sont utilisées pour certains résultats des opérations arithmétiques. Par exemple pour une division par \(0\), comme on peut le voir dans le tableau suivant:

\(x/y\) \(y\neq 0,\infty,\textbf{NaN}\) \(y=\infty\) \(y=0\) \(y=\textbf{NaN}\)
\(x\neq 0,\infty,\textbf{NaN}\;\;\;\) valeur la plus proche de \(x/y\) 0 \(\infty\) NaN
\(x=\infty\) \(\infty\) NaN \(\infty\) NaN
\(x=0\) \(0\) \(0\) NaN NaN
 \(x=\textbf{NaN}\) NaN NaN NaN NaN

En pratique, la manipulation de cette représentation demande des circuits spéciaux, que l’on trouve sur la plupart des processeurs modernes.

Exemple :

Sur le processeur Intel 486 (I486 Microprocessor Programmer’s Reference Manual 1990), il est possible de manipuler des données en virgule flottante selon la norme IEEE754 (originelle), sur 32, 64 ou même 80 bits. Ces données doivent être chargées dans des registres spéciaux de 80 bits appelés st0,…st7. Des instructions dédiées comme fadd, fsub, fdiv, etc implémentent les opérations arithmétiques sur ces registres. Ces opérations ne sont pas réalisées par l’ALU, mais par un circuit dédié du processeur: le FPU (floating point unit), qui était un circuit séparé sur les processeurs Intel précédent le 486 (par exemple, pour le 386, il fallait acheter séparément un co-processeur appelé 387 pour disposer d’un FPU).

\(\blacksquare\)

Représentation des caractères

Maintenant que nous avons étudié des techniques pour représenter et manipuler des nombres en binaire, intéressons-nous à d’autres types d’informations. Nous commencerons par le texte, c’est-à-dire des séquences de caractères. L’idée générale de la représentation (en binaire) des caractères consiste à faire correspondre à chaque caractère un et un seul nombre naturel, et à représenter le caractère par la représentation binaire de ce naturel. Comme il n’existe pas de manière universelle et naturelle d’associer un nombre à chaque caractère, il faut fixer une table, qui fait correspondre chaque caractère à un nombre.

Émile Baudot
Codes historiques: Émile Baudot et les téléscripteurs

Le besoin de représenter et transmettre de l’information de manière mécanique est une préoccupation qui a reçu une première réponse lors de l’introduction du télégraphe, où le fameux code Morse était utilisé pour représenter les lettres par une série de traits et de points. Au dix-neuvième siècle, un français, Jean-Maurice Émile Baudot11 invente le premier code pratique permettant de représenter tout l’alphabet latin (ainsi que des symboles de ponctuation usuels) sur \(5\) bits. Ce code est présenté à la figure ci-dessous.

La machine de Baudot comprenait un clavier de \(5\) touches, avec lequel on entrait les caractères à transmettre, selon le code que nous avons présenté. Le récepteur disposait d’une machine imprimant automatiquement les caractères transmis sur un ruban de papier. La cadence à laquelle les caractères pouvaient être transmis (par exemple, \(10\) caractères par minute) était mesurée en bauds, une unité que l’on connait encore aujourd’hui, bien qu’elle soit tombée en désuétude. Le système de Baudot sera plus tard amélioré pour utiliser du ruban perforé pour stocker les informations à transmettre. Cela donnera lieu aux téléscripteurs (ou teletypes en anglais, abbrévié TTY), sortes de machines à écrire qui ont la capacité d’envoyer et de recevoir du texte en utilisant le code de Baudot, sur des lignes téléphoniques. Ces systèmes ont été largement utilisés pour la transmission d’information, notamment par la presse, jusque dans les années 1980.

Le code Baudot, un système historique de représentation binaire des caractères (on peut associer le + à 1 et le - à 0), breveté en 1882 en France. On voit ici un extrait du brevet américain (1888).
Le code ASCII

L’évolution la plus marquante des développements historiques que nous venons de présenter est le code ASCII (American Standard Code for Information Interchange, présenté en 1967), qui est encore en usage aujourd’hui. Il comprend \(128\) caractères encodés sur \(7\) bits, et est présenté à la figure suivante.

Le code ASCII. Chaque caractère est représenté par une valeur hexadécimale sur 2 chiffres: le chiffre de poids fort est donné par la ligne, le chiffre de poids faible par la colonne.

Exemple :

Avec le code ASCII la chaîne de caractères MOOC NSI est représentée par (en hexadécimal):

4D 4F 4F 43 20 4E 53 49,

ou, en binaire, par:

\(100\ 1101\ \ 100\ 1111\ \ 100\ 1111\ \ 100\ 0011\ \ 010\ 0000\ \ 100\ 1110\ \ 101\ 0011\ \ 100\ 1001\)

\(\blacksquare\)

Ce code, bien adapté à la langue anglaise, ne permet pas de représenter les caractères accentués. C’est pourquoi plusieurs extensions ont vu le jour, sur \(8\) bits, où les 128 caractères supplémentaires permettaient d’encoder les caractères propres à une langue choisie. Par exemple sur l’IBM PC, ces extensions étaient appelées code pages. En voici deux exemples:

  • le code page 437: le jeu de caractère ASCII standard auxquels on a ajouté les caractères accentués latin;

  • le code page 737: le code ASCII standard plus les caractères grecs, voir figure suivante.

L’utilisation de ces code pages supposait que l’utilisateur connaissaient le code qui avait été utilisé pour représenter le texte source, et qu’il disposait des moyens logiciels et matériels pour afficher les caractères correspondants. En pratique, cela se révélait souvent fastidieux, et donnait lieu à des surprises si on se trompait de code page

Le Code Page 737: une extension du code ASCII pour obtenir les caractères grecs. (“Code Page 737 — Wikipedia, the Free Encyclopedia” n.d.)
Unicode

Plus récemment, le projet Unicode12 a vu le jour, et s’est donné pour objectif de créer une norme reprenant la plupart des systèmes d’écriture utilisés dans le monde, et de leur attribuer un encodage. La version en cours d’Unicode est la version 11 et elle comprend \(137\ 439\) caractères. La norme Unicode associe plusieurs encodages à chaque caractère. L’encodage le plus courant est appelé UTF-8: il s’agit d’un encodage à longueur variable car chaque caractère est encodé sur 1, 2, 3 ou 4 octets. Tous les caractères encodés sur 1 octet sont compatibles avec le standard ASCII. Les encodages sur 2, 3 et 4 octets sont utilisés pour représenter d’autres caractères, aussi exotiques soient-ils… Par exemple, la figure suivante présente l’encodage Unicode de l’alphabet Tagbanwa, en usage aux Philippines (“Tagbanwa (Unicode Block) — Wikipedia, the Free Encyclopedia” n.d.; “Tagbanwa” 1991).

La norme Unicode est devenue aujourd’hui bien adoptée, notamment par les sites et navigateurs web.

Extrait du standard Unicode, alphabet Tagbanwa (“Tagbanwa (Unicode Block) — Wikipedia, the Free Encyclopedia” n.d.).

Représentation d’images

Il existe de nombreux formats permettant de stocker et manipuler des images, les plus utilisés étant sans doute le JPEG13 (“Information Technology – Digital Compression and Coding of Continuous-Tone Still Images: Requirements and Guidelines” 1994), le PNG14 (“Information Technology – Computer Graphics and Image Processing – Portable Network Graphics (PNG): Functional Specification” 2004) ou le TIFF15 (on pourrait encore citer des formats historiques comme le GIF ou le BMP…) Ces formats sont utilisés par les sites webs, par les appareils photos numériques, etc. Tous ces formats représentent des images de type bitmap16, et suivent le même principe de base. Une image y est vue comme une matrice de points, appelés pixels (contraction de l’anglais picture elements), qui sont indivisibles, et monochromatiques. Ce sont les éléments de base constitutifs d’une image. La couleur de chaque pixel peut (comme on l’a fait pour les caractères) alors être représentée par un naturel selon un encodage fixé a priori. Par exemple, sur \(8\) bits on pourra avoir une palette de 256 couleurs, ou 256 niveaux de gris… On peut alors représenter l’image comme la suite des encodages binaires de chacun des pixels, la matrice étant lue ligne par ligne (par exemple). Un fichier contenant une image contiendra en général d’autres informations utiles (commes les dimensions de l’image).

Les formats d’images utilisés en pratique comme JPEG ne se contentent pas de stocker la suite des pixels de l’image, mais appliquent aussi des techniques de compression pour réduire l’espace nécessaire pour stocker cette information (“Information Technology – Digital Compression and Coding of Continuous-Tone Still Images: Requirements and Guidelines” 1994). Notons enfin qu’une vidéo n’est jamais qu’une séquence d’image fixes. Les concepts développés ici s’appliquent donc aux différents formats (MPEG, AVI, etc) utilisés pour encoder des images en mouvement.

Détection et correction d’erreurs

Lorsque les informations sont stockées ou transmises, il arrive parfois que des erreurs soient introduites (par exemple, sur un réseau non-fiable). Il est alors utile de développer des techniques de représentation de l’information qui permettent au récepteur de détecter la présence d’erreurs éventuelles (auquel cas, il peut demander une re-transmission), voire de les corriger par lui-même. Nous allons maintenant étudier deux de ces techniques. Elles sont toutes les deux basées sur le même principe: introduire de la redondance dans l’information transmise, de manière à pouvoir détecter un nombre restreint d’erreurs, voire reconstituer l’information d’origine.

Bit de parité

Cette technique est sans doute la première à avoir été mise en œuvre. Elle consiste à ajouter, à toute information transmise, un bit (appelé bit de parité) qui indique si le nombre de bits à \(1\) dans l’information à représenter est impair (bit de parité à \(1\)) ou pair (bit de parité à \(0\)). Ainsi, si un seul bit est modifié, la parité change nécessairement, et cette erreur peut être détectée (mais pas corrigée car on n’a pas de moyen d’identifier le bit qui a été modifié).

Plus précisément, étant donnée une information binaire

\[b_{n-1}\cdots b_0,\]

on lui associé le bit de parité (ou bit de contrôle) \(b_c\) calculé de la manière suivante:

\[b_c=b_{n-1} \,\mathit{XOR}\, b_{n-2}\cdots \,\mathit{XOR}\, b_0.\]

On peut vérifier que \(b_c=1\) si et seulement si le nombre de bits à \(1\) parmi \(b_{n-1}\),…, \(b_0\) est impair.

Exemple :

Fixons \(n=7\). Si l’information considérée est \(011\ 1111\) (ce qui correspond par exemple au caractère ASCII ?, (voir la figure donnant la table ascii), on a le bit de contrôle \(b_c=0\). On obtient alors l’octet \(0011\ 1111\), en supposant que le bit de contrôle est le bit de poids fort.

Supposons maintenant que la donnée soit modifiée en \(0011\ \mathbf{0}111\) (le bit \(b_3\) a été inversé), suite à une erreur. On peut calculer la parité de l’information reçue \(0 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 0 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1=1\), et constater que ce n’est pas le bit de contrôle reçu. On a donc détecté une erreur. Si, par exemple, l’information a été transmise sur un réseau, on peut demander une retransmission.

Supposons maintenant qu’une erreur ait lieu sur le bit de parité: la valeur \(\mathbf{1}011\ 1111\) est reçue. À nouveau, une erreur est détectée, même si l’information à proprement parler est correcte.

Supposons maintenant que deux erreurs ont lieu: \(0011\ \mathbf{00}11\). On voit que le bit de contrôle calculé est \(0\), ces deux erreurs ne seront donc pas détectées.

\(\blacksquare\)

On peut facilement se convaincre que la technique du bit de parité permet de détecter un nombre impair d’erreurs, mais ne permet d’en corriger aucune car rien ne permet d’identifier le bit qui a été altéré.

Code de Hamming

Le code de Hamming est en fait une famille de codes dont la version de base (appelée Hamming\((7,4)\) et que nous allons étudier ici) a été introduite dans les années 1950 (Hamming 1950) par Richard Hamming17, pour détecter et corriger des erreurs qui avaient lieu lors de la lecture de cartes et de rubans perforés.

Ce système est plus puissant que le bit de parité: il permet de corriger les erreurs de transmission, à condition que celles-ci affectent au maximum 1 bit. Naturellement, pour arriver à ce résultat, il faudra utiliser plus d’un bit de contrôle.

Pour expliquer le code de Hamming, nous allons changer quelque peu nos conventions et numéroter les bits à partir de \(1\). Nous allons considérer, pour l’exemple, des représentations (information et bits de contrôle) sur \(7\) bits, mais ces principes se généralisent aisément. Sur ces \(7\) bits, tous les bits dont le numéro est une puissance de \(2\) (donc, les bits \(1\), \(2\) et \(4\)) sont des bits de contrôle (\(C_i\)), les \(4\) bits restants sont des bits de données (\(D_i\)):

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7\\ \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline \end{array}\]

Chacun des bits de contrôle sera en fait un bit de parité, mais ne portera pas sur tous les bits de données (sans quoi il serait inutile d’avoir plusieurs bits de contrôle qui auraient tous la même valeur). Au contraire, nous allons associer les bits de contrôle à des bits de données bien choisis, de manière à pouvoir reconstituer le numéro du bit erroné en cas d’erreur. Nous effectuons cette association de la manière suivante

Note :

Dans le code de Hamming, le bit de contrôle \(C_i\) est un bit de parité pour tous les bits de données \(S_j\), tels que le bit de poids \(i\) est à 1 dans l’expression binaire de \(j\).

\(\square\)

Quand un bit \(C_i\) est un bit de parité pour un bit de donnée \(D_j\), nous dirons que “\(C_i\) vérifie \(D_j\)”.

Élucidons cette définition dans le cas où \(n=7\). Les représentations binaires de numéros des bits de donnée sont les suivants \(011=3_{10}\), \(101=5_{10}\), \(110=6_{10}\) et \(111=7_{10}\). Donc, le bit de donnée \(3\) est vérifié par les bits de contrôle \(2\) et \(1\) (car en effet \(1+2=3\)); le bit de donnée \(5\) est vérifié par \(4\) et \(1\) (\(4+1=5\)); le bit de donnée \(6\) est vérifié par \(4\) et \(2\) (\(4+2=6\)); et le bit de donnée \(7\) est vérifié par \(4\), \(2\) et \(1\) (\(4+2+1=7\)). On peut donc observer les deux propriétés suivantes, qui découlent de la définition des bits de contrôle et qui seront cruciales dans la suite pour corriger erreurs:

  1. quand on fait la somme des numéros des bits de contrôle qui vérifient un bit de donnée \(D_j\), on retrouve cette valeur \(j\); et

  2. chaque bit de donnée est vérifié par au moins \(2\) bits de contrôle. Cela provient du fait que les numéros de bits de données ne sont pas des puissances de \(2\), leur représentation en binaire comprend donc au moins deux bits à \(1\).

On peut ré-exprimer la relation entre les bits de contrôle et les bits de données de la façon suivante, ce qui nous permet de calculer directement les bits de contrôle:

  • le bit de contrôle \(C_1\) vérifie les bits de données \(D_3\), \(D_5\) et \(D_7\);

  • le bit de contrôle \(C_2\) vérifie les bits \(D_3\), \(D_6\) et \(D_7\); et

  • le bit de contrôle \(C_4\) vérifie les bits \(D_5\), \(D_6\) et \(D_7\).

Par exemple le bit de contrôle \(C_2\) est un bit de parité pour \(D_3\), \(D_6\) et \(D_7\), donc

\[C_2=D_3 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7.\]

Mettons ces idées en pratique sur un exemple:

Exemple :

Supposons que nous ayons la donnée \(1011\):

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline &&1&&0&1&1\\ \hline \end{array}\]

En appliquant le développement ci-dessus, nous obtenons:

\[\begin{array}{rclllll} C_1 &= &D_3 \,\mathit{XOR}\, D_5 \,\mathit{XOR}\, D_7 &= &1 \,\mathit{XOR}\, 0 \,\mathit{XOR}\, 1 &= &0;\\ C_2 &= &D_3 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7 &= &1 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1 &= &1;\\ C_4 &= &D_5 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7 &= &0 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1 &= &0. \end{array}\]

La représentation de la donnée accompagnée de son code de Hamming est donc:

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline 0&1&1&0&0&1&1\\ \hline \end{array}\]

\(\blacksquare\)

Cette technique de codage permet non seulement de détecter une erreur mais également de la corriger. Nous pouvons aisément nous convaincre du fait qu’on peut détecter une erreur (c’est-à-dire le fait qu’un seul bit soit inversé), en constatant que chaque bit de donnée est vérifié par au moins un bit de parité parmi \(C_1\), \(C_2\), \(C_3\). Or, nous savons déjà que la technique du bit de parité permet de détecter tout changement d’un seul bit.

En ce qui concerne la correction de l’erreur, supposons que celle-ci est unique. Nous avons alors deux cas à considérer:

  • soit cette erreur a lieu sur un bit de donnée, \(D_j\). Dans ce cas, tous les bits de contrôle qui vérifient \(D_j\) auront une valeur qui ne correspond pas à la donnée vérifiée. Il suffit dès lors de faire la somme des numéros de ces bits de vérification pour retrouver la valeur \(j\) (cfr. la première des deux propriétés énoncés ci-dessus).;

  • soit cette erreur a lieu sur un bit de contrôle \(C_i\). Dans ce cas, ce bit sera le seul a poser problème, et nous saurons donc qu’il n’y a pas d’erreur dans les données (sans quoi il y aurait au moins deux bits de contrôle problématiques, selon la seconde propriété énoncée ci-dessus).

Exemple :

Continuons l’exemple ci-dessus et imaginons qu’il y ait une erreur sur le bit \(D_3\), soit:

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline 0&1&\mathbf{0}&0&0&1&1\\ \hline \end{array}\]

Re-faisons le calcul de chacun des bits de contrôle:

Bit \(C_1\) : le calcul de \(D_3 \,\mathit{XOR}\, D_5 \,\mathit{XOR}\, D_7\) donne \(1\), au lieu de \(0\);

Bit \(C_2\) : le calcul de \(D_3 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7\) donne \(0\) au lieu de \(1\); et enfin

Bit \(C_4\) : le calcul de \(D_5 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7\) donne \(0\), ce qui est bien la bonne valeur.

Il y a donc des problèmes avec les bits de contrôle \(C_1\) et \(C_2\). On en déduit que le bit erroné est le bit \(D_j\) avec \(j=1+2=3\). On peut donc re-constituer la donnée d’origine en inversant le bit \(D_3\).

Continuons toujours le même exemple et supposons qu’il y ait une erreur sur le bit de contrôle \(C_2\), soit:

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline 0&\mathbf{0}&1&0&0&1&1\\ \hline \end{array}\]

Re-faisons le calcul de chacun des bits de contrôle:

Bit \(C_1\) : le calcul de \(D_3 \,\mathit{XOR}\, D_5 \,\mathit{XOR}\, D_7\) donne \(0\), ce qui est bien la bonne valeur;

Bit \(C_2\) : le calcul de \(D_3 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7\) donne \(0\) au lieu de \(1\); et enfin

Bit \(C_4\) : le calcul de \(D_5 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7\) donne \(0\), ce qui est bien la bonne valeur.

Il y a donc un problème sur le bit \(C_2\) uniquement, c’est donc lui qui est erroné et la donnée est donc transmise correctement.

\(\blacksquare\)

Applications des codes correcteurs d’erreur

Comme nous l’avons déjà évoqué, le bit de parité est une technique qui a largement été utilisée pour détecter des erreurs lors de la transmission de données en ASCII sur des lignes téléphonique ou des réseaux informatiques. Le code de Hamming a initialement été développé pour détecter et corriger des erreurs lors de la lecture de cartes perforées.

On pourrait croire que les progrès technologiques ont diminué voire supprimé la nécessité des codes correcteurs d’erreur. Il n’en est rien: nous sommes encore aujourd’hui confrontés à une série d’applications où la transmission d’information fait l’objet d’erreurs. Prenons deux exemples:

  1. La lecture d’un CD ou d’un DVD est un processus délicat, car le rayon LASER qui doit lire la surface du disque est très fin, et que le disque lui-même est souvent couvert de poussières, de griffes, voire de traces de doigts… De nombreuses erreurs de lecture ont donc lieu en permanence…

  2. Avec l’âge des smartphones, une nouvelle famille de code barres, appelés codes matriciels, ont fait leur apparition. Les plus célèbres sont les codes QR (la figure suivante donne un exemple) qui ont été inventés dans les années 1990 au Japon pour simplifier la logistique de pièces automobiles, et ont depuis été standardisés (“Information Technology – Automatic Identification and Data Capture Techniques – QR Code Bar Code Symbology Specification” 2015). À nouveau, les conditions de lecture de ces codes ne sont pas toujours idéales, et de nombreuses erreurs de lecture ont lieu (c’était d’ailleurs déjà le cas avec les code à barre “classiques” unidimensionnels que l’on retrouve aujourd’hui sur tous les emballages de produits manufacturés).

Ces deux exemples ont en commun la technique utilisée pour détecter et corriger les erreurs, à savoir les codes de Reed18 et Salomon19, introduits en 1960 par ces deux auteurs (Reed and Solomon 1960). Nous n’allons pas expliquer ici comment ils fonctionnent, cela nous emmènerait trop loin… mais ces deux exemples montrent que les codes détecteurs et correcteurs d’erreur restent importants. Ils font d’ailleurs encore l’objet d’une recherche active.

image image

Conclusion: sémantique d’une représentation binaire

Cette section nous a convaincu que tous les types d’information manipulés par l’ordinateur peuvent être représentés uniquement à l’aide de \(0\) et de \(1\). Il est maintenant naturel de se poser la question inverse, à savoir: “quel est le sens à associer à une représentation binaire donnée ?”

Exemple :

La représentation binaire \(1000\ 0001\) s’interprète comme \(129_{10}\) si on considère des nombres non-signés; comme \(-1_{10}\) si on considère le bit de signe; comme \(-127_{10}\) si on considère le complément à deux; comme le caractère “ü” si on considère qu’on a affaire à un caractère ASCII étendu…

\(\blacksquare\)

La réponse à cette question est que rien ne permet, a priori de décider quelle interprétation donner à une séquence binaire particulière. C’est le contexte, et en particulier le programme qui est exécuté sur ces données, qui leur donne un sens. Nous le prouvons à l’aide du programme C++ de la figure suivante. Il consiste à placer la même représentation binaire (sur 32 bits) dans trois variables x, y et z différentes, qui ont des types différents. Cela signifie que les instructions machines qui seront in fine exécutées pour afficher ces variables (instructions std::cout << à la fin du programme) seront différentes. Dans le cas la variable x, la représentation binaire sera interprétée comme un entier signé en complément à deux; dans le cas de la variable y, la représentation binaire sera interprétée comme un entier non-signé; et dans le cas de la variable z, la représentation binaire sera interprétée comme un caractère (les 24 bits de poids fort seront donc ignorés).

#include <iostream>

int main() {
    int x ; // x est un entier signe (complement a  deux)
    unsigned int y ; // y est un entier non negatif
    char z ; // z est un caractere

    // Toutes ces variables tiennent sur 32 bits

    // On place la meme valeur de 32 bits dans les 3 variables
    // avec le bit de poids fort valant  1
    // 1000 0000  0000 0000  0000 0000  0010 1111

    x = 0b10000000000000000000000000101111 ;
    y = 0b10000000000000000000000000101111 ;
    z = 0b10000000000000000000000000101111 ;

    // L'affichage des trois valeurs est different
    // L'affichage tient compte du type: ce sont les
    // instructions qui donnent leur semantique aux
    // valeurs representees en binaire.

    std::cout << x << std::endl ;

    std::cout << y << std::endl ;

    std::cout << z << std::endl ;

}

La sortie du programme confirme cela:

-2147483601
 2147483695
 /

Banahan, Mike, Declan Brady, and Mark Doran. 1991. The c Book. Addison Wesley. .

“Code Page 737 — Wikipedia, the Free Encyclopedia.” n.d. Accessed September 1, 2017. https://en.wikipedia.org/w/index.php?title=Code_page_737&oldid=782268129.

Hamming, Richard W. 1950. “Error Detecting and Error Correcting Codes.” Bell System Technical Journal 29 (2): 147—160.

I486 Microprocessor Programmer’s Reference Manual. 1990. Intel Corporation. http://bitsavers.trailing-edge.com/components/intel/80486/i486_Processor_Programmers_Reference_Manual_1990.pdf.

“IEEE Standard for Floating-Point Arithmetic.” 2008. IEEE. https://doi.org/10.1109/IEEESTD.2008.4610935.

“Information Technology – Automatic Identification and Data Capture Techniques – QR Code Bar Code Symbology Specification.” 2015. International Organization for Standardization. https://www.iso.org/standard/62021.html.

“Information Technology – Computer Graphics and Image Processing – Portable Network Graphics (PNG): Functional Specification.” 2004. International Organization for Standardization. https://www.iso.org/standard/29581.html.

“Information Technology – Digital Compression and Coding of Continuous-Tone Still Images: Requirements and Guidelines.” 1994. International Organization for Standardization. https://www.iso.org/standard/18902.html.

P., Brousentsov N., Maslov S. P., Ramil Alvarez J., and Zhogolev E. A. n.d. “Development of Ternary Computers at Moscow State University.” Accessed August 8, 2018. http://www.computer-museum.ru/english/setun.htm.

“Quantities and Units – Part 13: Information Science and Technology.” 2008. International Organization for Standardization. https://www.iso.org/standard/31898.html.

Reed, Irving S., and Gustave Solomon. 1960. “Polynomial Codes over Certain Finite Fields.” Journal of the Society for Industrial and Applied Mathematics 8 (2): 300–304.

SCC14.3 - Unit Symbols Subcommittee. 2004. “IEEE Standard Letter Symbols for Units of Measurement (SI Customary Inch-Pound Units, and Certain Other Units).” 260.1-2004. IEEE. https://standards.ieee.org/standard/260_1-2004.html.

Stroustrup, Bjarne. 2018. A Tour of c++. Addison-Wesley.

“Tagbanwa.” 1991. The Unicode Consortium. http://www.unicode.org/charts/PDF/U1760.pdf.

“Tagbanwa (Unicode Block) — Wikipedia, the Free Encyclopedia.” n.d. Accessed September 1, 2017. https://en.wikipedia.org/w/index.php?title=Tagbanwa_(Unicode_block)&oldid=775143371.


  1. Il y a eu quelques expériences utilisant des représentations ternaires. On peut citer les ordinateurs soviétiques Setun (1959–1965) (P. et al. n.d.). 

  2. Voir par exemple: https://en.wikipedia.org/wiki/Binary_prefix#Inconsistent_use_of_units

  3. Par exemple, \(10_{10}\) est exprimé par \(\mathtt{a}\) en base \(16\)

  4. En pratique, sur un ordinateur, nous ne pourrons représenter et manipuler de manière précise que les nombres qui possèdent une représentation finie en base \(2\), ce qui exclut d’office tous les nombres irrationnels, comme \(\pi\) ou \(\sqrt{2}\), par exemple. Mais cela n’empêche que même les nombres irrationnels possèdent aussi une représentation (infinie non-périodique) dans d’autres bases que la base \(10\)

  5. Attention ! Ici, binaire signifie que l’opérateur porte sur deux opérandes, comme l’addition par exemple. Au contraire, un opérateur unaire porte sur une seule opérande (comme le moins dans \(-5\) par exemple). 

  6. On se souviendra qu’un nombre positif est un nombre \(>0\) et qu’un nombre négatif est un nombre \(<0\). Les nombres \(\geq 0\) sont donc les nombres “non-négatifs”. 

  7. Il s’agit des nombres réels qui ne sont pas rationnels. 

  8. C’est-à-dire qu’elle ne peut pas être exprimée sous la forme d’un préfixe fini suivi d’une répétition infinie d’une séquence finie, car il est connu que tout nombre qui peut être exprimé de cette manière est rationnel. 

  9. L’IEEE est l’Institute of Electrical and Electronics Engineers, une association à but non-lucratif américaine regroupant des centaines de milliers de professionnels de l’électronique et de l’informatique. Elle conçoit et publie des normes qui peuvent ensuite être adoptées et mises en pratique par l’industrie. La norme IEEE754-2008 est la révision en 2008 de la norme 754 qui définit une représentation en virgule flottante adaptée aux ordinateurs. Le groupe de travail qui conçoit et publie cette norme possède une page web qu’on peut consulter pour plus d’information: https://standards.ieee.org/develop/wg/754.html

  10. Le site web http://babbage.cs.qc.cuny.edu/IEEE-754/ implémente un convertisseur automatique qu’on peut utiliser pour se familiariser avec cette norme. 

  11. Ingénieur français, né le 11 septembre 1845, mort le 28 mars 1903. 

  12. Le consortium qui conçoit et publie Unicode possède un site web https://unicode.org/

  13. Voir https://jpeg.org/ 

  14. Voir: http://www.libpng.org/pub/png/ 

  15. Voir: https://www.loc.gov/preservation/digital/formats/fdd/fdd000022.shtml 

  16. Notons qu’il existe d’autres formats, comme le SVG, qui représentent les images sous formes de points connectés par des lignes ou des courbes décrites de manière mathématique. Ces formats ont l’avantage de permettre des agrandissements sans perte de qualité. 

  17. Né le 11 février 1915 et mort le 7 janvier 1998 , Richard Hamming est un mathématicien américain, récipiendaire du prix Turing en 1968, qui a travaillé entre autres pour le projet Manhattan et aux laboratoires des Bell Labs. 

  18. Irving Reed, né le 12 novembre 1923, et mort le 11 septembre 2012, est un mathématicien et ingénieur américain, qui a enseigné à l’University of Southern California, É-U d’Amérique. 

  19. Gustave Solomon, né le 27 octobre 1930 et mort le 31 janvier 1996 est un mathématicien et ingénieur américain, qui a travaillé pour la Hughes Aircraft Company