info:gene:repdonnees [WEBGE Wikis]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
[[info:accueilinfo|{{ :iconemaison.jpg?nolink&25|Sommaire "Bases d'algorithmique et de programmation"}}]]  

===== Représentation des données en machine =====
[Mise à jour le 19/8/2024]


**Sources**
  * Numérique et sciences informatiques 1<sup>er</sup> - ellipses

**Ressources**
  * Complément à 2 (<html><a href="https://fr.wikipedia.org/wiki/Compl%C3%A9ment_%C3%A0_deux" target="_blank">Wikipédia</a></html>)
  * Editeur hexadécimal en ligne : <html><a href="https://hexed.it/" target="_blank">HexEdit</a></html>

\\


==== 1. Introduction ====
Les données et les programmes stockés dans la mémoire des machines numériques sont représentés à l'aide de deux chiffres : **0** et **1**.

<callout type="primary" icon="true">**0** et **1** sont appelés chiffres binaires (//Binary Digits//) ou **bits**.</callout>

Ces chiffres binaires sont regroupés en paquets de **8 bits** (//**octets**// ou //**bytes**//) puis couramment organisés en **mots** de 2, 4 ou 8 octets. Une machine dite 32 bits manipule des mots de 4 octets lorsqu'elle effectue des opérations. Ce regroupement de bits est à la base de la représentation des entiers, des réels et des caractères.

<callout type="primary" icon="true">Il est nécessaire d'utiliser des codes (**encoder**) pour représenter des **entiers**, des **décimaux** et des **caractères**. </callout>

\\


==== 2. Encodage des entiers naturels ====
=== 2.1 Écriture en base 2 ===

Une séquence de chiffres binaires peut s'interpréter comme un nombre écrit en base 2. Dans cette base, les chiffres **0** et **1** d'une séquence sont associés à un **__poids__ 2<sup>i</sup>** qui dépend de la position i des chiffres dans la séquence.

<callout type="primary" icon="true">Une séquence de **n bits** b<sub>i</sub>, //b<sub>n-1</sub>,b<sub>n-2</sub>,...,b<sub>1</sub>,b<sub>0</sub>// correspond au nombre décimal N tel que : \\ $$N_{10} = b_{n-1}2^{n-1}+b_{n-2}2^{n-2}+ ... +b_12^1+b_02^0 = \displaystyle\sum_{i=0}^{i=n-1}b_i2^i$$ 
</callout>

<callout icon="fa fa-hand-stop-o" color="red" title="ATTENTION">Cet encodage permet de représenter des entiers dans l'intervalle [**0**,**2<sup>n</sup> - 1**]</callout>

//Exemples//  \\
- Un octet (n = 8) permet de coder tous les nombres entre 0 et 255 \\
- 10011011<sub>2</sub> = 1*2<sup>7</sup> + 0*2<sup>6</sup> + 0*2<sup>5</sup> + 1*2<sup>4</sup> + 1*2<sup>3</sup> + 0*2<sup>2</sup> + 1*2<sup>1</sup> + 1*2<sup>0</sup> = 128 + 16 + 8 + 2 + 1 = 155<sub>10</sub>

\\

=== 2.2 Écriture en base 16 ===
La base 16 ou hexadécimale est souvent utilisée pour simplifier l'écriture des nombres binaires.

<callout type="primary" icon="true">On passe d'un nombre en base 16 à un nombre en base 2 en regroupant les chiffres binaires par 4.</callout>

// Exemple//
1001 1110 0111 0101<sub>2</sub> = 9E75<sub>16</sub>

\\

=== 2.3 Boutisme ===
**Sources** 
  * Boutisme sur <html><a href="https://fr.wikipedia.org/wiki/Boutisme" target="_blank">Wikipédia</a></html>

{{ :info:gene:280px-big-endian-fr.svg.png?nolink&180|}}
La représentation en machine des entiers naturels sur des mots de 2, 4 ou 8 octets se heurte au problème de l'ordre dans lequel ces octets sont organisés en mémoire. Ce problème est appelé le **boutisme** (ou endianness).

  * **Big endian**
<callout type="primary" icon="true">Le gros boutisme consiste à placer l'**octet de poids fort** en premier, c'est-à-dire à l'adresse mémoire la plus petite.</callout>

{{ :info:gene:280px-little-endian-fr.svg.png?nolink&180|}}
  * **Little endian**
<callout type="primary" icon="true">Le petit boutisme consiste à placer l'**octet de poids faible** en premier. C'est-à-dire à l'adresse mémoire la plus petite.</callout>

<callout type="warning" icon="true">Bien que le boutisme soit géré au niveau du système d'exploitation, il peut être nécessaire d'en tenir compte lorsqu'on accède aux **octets en mémoire** ou lors d'**échanges sur un réseau**.</callout>

{{ :python:python.png?nolink&50|}}

\\

=== 2.4 Bases 2,10 et 16 en Python ===
Voir [[python:bases:variables|Variables, types numériques et entrées / sorties dans la console]]

\\

==== 3. Encodage des entiers relatifs (complément à 2) ====
{{ :info:gene:maxresdefault.jpg?nolink&350|}}

**Ressource**
  * La notation en complément à 2 sur <html><a href="https://fr.wikipedia.org/wiki/Compl%C3%A9ment_%C3%A0_deux" target="_blank">Wikipédia</a></html> et <html><a href="https://slideplayer.fr/slide/1146566/" target="_blank">SlidePlayer</a></html>

//Le code complément à 2 permet d'effectuer simplement des **opérations arithmétiques** sur les entiers relatifs codés en binaire. Il opère toujours sur des nombres binaires ayant le **même nombre de bits** (par commodité, celui-ci est généralement un multiple de 4).// <html><a href="" target="_blank">Wikipédia </a></html>

<callout icon="fa fa-hand-stop-o" color="red" title="ATTENTION">Le code complément à 2 permet de représenter des entiers dans l'intervalle [**-2<sup>n-1</sup>**,**2<sup>n-1</sup> - 1**]. Le bit de **poids fort** (bit le plus à gauche) ou **MSB** (Most Significant Bit)  donne le **signe** du nombre représenté (**0 => positif** ou **1 => négatif**). </callout>

//Exemple// \\
- Un octet (n = 8) permet de coder en complément à 2 tous les nombres entre -128 et 127. \\
- Le nombre 01110001<sub>2</sub> est positif et égal à 89<sub>10</sub> \\
- Le nombre 11111111<sub>2</sub> est négatif et égal à -1<sub>10</sub> 

**Obtention d'un nombre binaire en complément à 2**

<callout type="warning" icon="true">Avant de convertir un nombre décimal en binaire complément à 2, il faut s'assurer de représenter ce nombre avec suffisamment de bits. **-2<sup>n-1</sup>≤-N** avec N>0. </callout>

//Exemple// : nombre de bits nécessaires pour coder **-125000<sub>10</sub>** \\
-2<sup>n-1</sup> ≤ -125000 \\
⇒ 2<sup>n-1</sup> > 125000 \\
⇒ log<sub>10</sub>(2<sup>n-1)</sup> > log<sub>10</sub>(125000) or log<sub>10</sub>(a<sup>b</sup>) = b*log<sub>10</sub>(a) \\
⇒ n-1 > log<sub>10</sub>(125000)/log<sub>10</sub>(2) \\
⇒ n > (log<sub>10</sub>(125000)/log<sub>10</sub>(2)) + 1
⇒ n > 17,93 ⇒ **n=18**

//Vérification// : pour n = 18, N<sub>10</sub> ∈ [-2<sup>17</sup>, 2<sup>17</sup>-1] soit **-131072 ≤ N<sub>10</sub> ≤ 131071**


<callout type="primary" icon="true">**Méthode**
  * Les nombres positifs sont représentés de manière usuelle.
  * Les **nombres négatifs** sont obtenus en calculant l'opposé du nombre positif par deux opérations successives:
    * On **inverse les bits de l'écriture binaire** (opération binaire NON), on fait ce qu'on appelle le complément à un ;
    * On **ajoute 1** au résultat (**les dépassements sont ignorés**). \\ Cette opération correspond au calcul de **2<sup>n</sup> − |x|**, où n est la longueur de la représentation et |x| la valeur absolue du nombre à coder. \\ Ainsi, −1 s'écrit comme 256−1 = 255 = 11111111<sub>2</sub>, pour les nombres sur 8 bits. Ceci est à l'origine du nom de cette opération : « complément à 2 puissance n », quasi-systématiquement tronqué en « complément à 2 ».

La même opération effectuée sur un nombre négatif donne le nombre positif de départ: **2<sup>n</sup> − (2<sup>n</sup> − x) = x**.
</callout>

\\


==== 4. Représentation approximative des nombres réels ====

=== 4.1 Nombres décimaux ===
L'encodage des nombres //**flottants**// est inspiré de l'écriture scientifique des nombres décimaux qui se compose d'un **signe** (+ ou -), d'un nombre décimal //m// appelé //**mantisse**//, compris dans l'intervalle **[1, 10[** et d'un entier relatif //n// appelé exposant. L'écriture scientifique d'un nombre décimal est de la forme <html><strong>&#177;</strong></html>**//m// x 10<sup>//n//</sup>**.

<callout type="primary" icon="true">On remarquera que **le nombre 0 ne peut pas être représenté par cette écriture**.</callout>

=== 4.2 Norme IEEE 754 ===
**Ressource**
  * IEEE 754 <html><a href="https://fr.wikipedia.org/wiki/IEEE_754" target="_blank">Wikipédia</a></html>

**Présentation**

La représentation des nombres //flottants// et les opérations arithmétiques sur ces nombres a été définit par la norme IEEE 754. C'est la norme couramment utilisée dans les ordinateurs. Selon la précision souhaitée, la norme définit un format sur **32 bits** (**simple précision**) et un autre sur **64 bits** (**double précision**). 

<callout type="primary" icon="true">Un nombre flottant a la forme suivante : **(-1)<sup>s</sup>//m// x 2<sup>(e-d)</sup>**. \\ **s** : signe (0 => positif, 1 => négatif)\\ **m** : mantisse comprise dans l'intervalle [1,2[ \\ **e** : exposant, décalé (**biaisé**) d'une valeur **d** qui dépend du format choisi (32 ou 64bits)</callout>

__Remarques__
  * La **mantisse** est comprise dans l'intervalle [1,2[ donc //m// est toujours de la forme 1,xxxx. Aussi pour gagner 1 bit, **on ne stocke que les chiffres après la virgule**, qu'on appelle la //**fraction**//.
  * L'**exposant** peut être positif ou négatif. Cependant, la représentation habituelle des nombres signés (**complément à 2**) **n'est pas utilisée** car, elle rendrait la comparaison entre les nombres flottants un peu plus difficile. Pour régler ce problème, l'exposant est « **biaisé** », afin de le **stocker sous forme d'un nombre non signé**.

** Format simple précision (32 bits)**

Un nombre flottant simple précision est stocké dans un mot de 32 bits : **1 bit de signe**, **8 bits pour l'exposant** et **23 bits pour la mantisse**.

Pour le format **32 bits**, l'**exposant décalé (e-d)** est un entier sur **8bits** qui représente les nombres entre 0 et 255. **d=127**, on représente ainsi des exposants signés dans l'intervalle [-126, 127] car, 0 et 255 représentent des nombres particuliers (voir tableau des valeurs spéciales).

----

//Exemple//

Conversion en décimal de **N<sub>2</sub> = 1 10001100 1010110110000000000000**
  * signe = -1<sup>1</sup> = **-1** 
  * exposant = (2<sup>7</sup> + 2<sup>3</sup> + 2<sup>2</sup>) - 127 = (128 + 4 + 2) - 127 = **7**
  * mantisse = 1 + 2<sup>-1</sup> + 2<sup>-3</sup> + 2<sup>-5</sup> + 2<sup>-6</sup> + 2<sup></sup> + 2<sup>-8</sup> + 2<sup>-9</sup> = **1,677734375** 

 donc **N<sub>10</sub>** = - 1,677734375 * 2<sup>7</sup> = **-214,75**

----

** Tableau récapitulatif simple précision, double précision**

|                   ^  exposant (e)     ^ fraction (f)  ^    valeur                                       ^
|  **32 //bits//**  |  8 //bits//       |  32 //bits//  ^  (-1)<sup>s</sup> x 1,f x 2<sup>(e-127)</sup>)   ^
|  **64 //bits//**  |  11 //bits//      |  52 //bits//  ^  (-1)<sup>s</sup> x 1,f x 2<sup>(e-1023)</sup>)  ^

**s** : signe (0 => positif, 1 => négatif) \\
**//f//** : fraction de la mantisse m \\
**e** : exposant

<callout type="primary" icon="true">En **simple précision (32 bits)**, les nombres flottants positifs peuvent représenter les nombres décimaux compris dans l'intervalle **[10<sup>-38</sup>,0<sup>38</sup>]**, **[10<sup>-308</sup>,0<sup>308</sup>] en double précision (64 bits)**.</callout>

**Valeurs spéciales**

Le format des nombres flottant ne permettant pas de représenter le nombre 0, la norme IEE 754 utilise les valeurs de l'exposant 0 et 255 pour remédier à ce problème et représenter d'autres valeurs spéciales.

^  Signe  ^  Exposant  ^  Fraction                ^  Valeur spéciale         ^
|  0      |  0         |  0                       |  +0                      |
|  1      |  0         |  0                       |  -0                      |
|  0      |  255       |  0                       |  +<html>&#8734; </html>  |
|  1      |  255       |  0                       |  -<html>&#8734; </html>  |
|  0      |  255       |  <html>&#x2260;</html>0  |   NaN                    |

**NaN** : Not a Number permet de représenter des résultats d'opérations invalides (0/0 etc.)

** Nombres dénormalisés**

Dans la représentation précédente (**normalisée**), le plus petit nombre est 2<sup>-126</sup> soit environ 10<sup>-38</sup>. Il n'y a **pas de nombre représentable** dans l'intervalle [0, 2<sup>-126</sup>[. 

<callout type="primary" icon="true">La norme **IEEE 754** permet d'encoder des nombres de la forme **(-1)<sup>s</sup> x 0,f x 2<sup>-126</sup>**. Sans les **nombres dénormalisés**, les deux tests x - y = 0 et x = y ne seraient pas systématiquement équivalent.</callout>

**Arrondis**

<callout type="warning" icon="true">La représentation des nombres décimaux par des flottants est une représentation **approximative**. La norme IEEE 754 définit quatre modes d'arrondi pour choisir le meilleur flottant.</callout>

  * //Au plus près//(par défaut) : le flottant le plus proche de la valeur exacte;
  * //Vers zéro// : le flottant le plus proche de 0;
  * //Vers plus l'infini// : le plus petit flottant supérieur ou égal à la valeur exacte;
  * //Vers moins l'infini// : le plus grand flottant inférieur ou égal à la valeur exacte;

//Exemple// Le nombre flottant le plus proche de **N<sub>10</sub> = 1,6** est **N<sub>2</sub> = 0 01111111 10011001100110011001101**

N<sub>10</sub> = 1 + (2<sup>-1</sup> + 2<sup>-4</sup> + 2<sup>-5</sup> + 2<sup>-8</sup> + 2<sup>-9</sup> + 2<sup>-12</sup> + 2<sup>-13</sup> + 2<sup>-16</sup> + 2<sup>-17</sup> + 2<sup>-20</sup> + 2<sup>-21</sup> + 2<sup>-23</sup>) x + 2<sup>127-127</sup> = 1,60000002384185791015625

\\

{{ :python:python.png?nolink&50|}}
=== 4.3 Les flottants en Python ===
Voir [[python:bases:variables|Variables, types numériques et entrées / sorties dans la console]]

\\

==== 5. Représentation des caractères ====
<callout type="primary" icon="true">La représentation des caractères dans les ordinateurs permet de **stocker et échanger** des textes. Associer un numéro unique à un caractère s'appelle l'**encodage**</callout>

{{ :info:gene:ascii.png?nolink&110|}}
=== 5.1 Codage ASCII ===
Dans les années 60, les ordinateurs utilisent des mots de 8 octets. Le code <html><a href="https://fr.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange" target="_blank">ASCII</a></html> (**A**merican **S**tandard **C**ode for **I**nformation **I**nterchange) normalise la représentation des caractères. Dans ce code, le bit de poids fort **b<sub>7</sub> est toujours à 0**. Entre **00<sub>16</sub>** et **20<sub>16</sub>** les caractères sont dit spéciaux (espace, tabulation, fin de ligne, etc). 
{{ :reseaux:generalites:ascii.png?nolink&600 |}}


Un texte codé en ASCII est simplement une suite d'octets correspondant à la séquence de caractères.
<code>
 C  e  c  i     e  s  t     u  n     t  e  x  t  e  !
43 65 63 69 20 65 73 74 20 75 6e 20 74 65 78 74 65 21
</code>

Le code ASCII est encore utilisé aujourd'hui. Cependant, il a l'inconvénient de ne pas représenter les caractères accentués. Il est également limité à l'alphabet latin.

<callout type="primary" icon="true">De nombreux autres encodages ont été proposés et utilisés pour résoudre ces problèmes. Le code qui a fini par s'imposer au niveau international est le code **UTF-8** (**U**nicode **T**ransformation **F**ormat).</callout>

=== 5.2 ISO 8859 ===
  * **Ressource** : <html><a href="https://fr.wikipedia.org/wiki/ISO/CEI_8859-1" target="_blank">ISO-8859-1</a></html> sur Wikipédia

A compléter

<callout type="primary" icon="true">Bien que les pages ISO-8859-n permettent l'encodage d'un très grand nombre de caractères, elles **ne conviennent pas** quand on souhaite écrire un texte avec un **mélange de caractères** dans différentes pages.</callout>


{{ :info:gene:unicode.jpg?nolink&70|}}
=== 5.3 Codage Unicode ===
La norme <html><a href="https://fr.wikipedia.org/wiki/Unicode" target="_blank">Unicode</a></html>, développée par un consortium du même nom, définit un jeu de caractères qui vise à inclure le plus grand nombre possible de systèmes d'écriture. Il contient à l'heure actuelle (2021) 143000 caractères couvrant 150 systèmes d'écriture ainsi que les emojis.

<callout type="tip" icon="true">Chaque caractère a un code unique, appelé "//code point//" ou **point de code** et noté **U+XXXX** où chaque X est un caractère hexadécimal. En pratique  la séquence de X est au minimum de 4 caractères.</callout>

Cette norme définit plusieurs techniques d'encodage pour représenter les points de code de manière plus ou moins économique selon la technique choisie. Ces encodages, appelés //formats de transformation universelle// ou //**U**niversal **T**ransformation **F**ormat// (**UTF**) en anglais, portent les noms **UTF-n**, où //n// indique le nombre minimal de //bits// pour représenter un point de code. \\ \\ 

{{ :info:gene:utf8.png?nolink&100|}}
== 5.3.1 UTF-8 ==
<callout type="primary" icon="true"><html><a href="https://fr.wikipedia.org/wiki/UTF-8" target="_blank">UTF-8</a></html> (**U**niversal **T**ransformation **F**ormat) est un **code à taille variable** destiné à représenter les caractères Unicode avec au minimum **8 bits**. C'est le format le plus utilisé sous Linux, dans les protocoles réseaux et les sites Web.</callout>

Les caractères sont représentés sur **1,2,3 ou 4 octets**. UTF-8 est **compatible** avec le code **ASCII** : les codes UTF-8 d'un octet avec le bit de poids fort à zéro sont les caractères du code ASCII (ainsi les programmes qui fonctionnaient sur des textes encodés en ASCII devraient continuer à fonctionner si ces mêmes textes sont encodés en UTF-8. \\ 
Les caractères codés sur plus d'un octet ont tous le bit de poids fort à 1, de telle sorte qu'ils sont en général ignorés par les logiciels qui ne connaissent que le code ASCII.
^  Nb Octets  ^  Premier "code point"  ^  Dernier "code point"  ^  Octet 1  ^  Octet 2  ^  Octet 3  ^  Octet 4  ^
|  1          | U+0000                 | U+007F                 | 0xxxxxxx  |           |           |           |
|  2          | U+0080                 | U+07FF                 | 110xxxxx  | 10xxxxxx  |           |           |
|  3          | U+0800                 | U+FFFF                 | 1110xxxx  | 10xxxxxx  | 10xxxxxx  |           |
|  4          | U+10000                | U+10FFFF               | 11110xxx  | 10xxxxxx  | 10xxxxxx  | 10xxxxxx  |

__Principe de l'encodage__ 
  * Si le bit de poids fort d'un octet est à 0, alors il s'agit d'un caractère ASCII codé sur les 7 bits restants.
  * Sinon, les premiers bits de poids fort de l'octet indiquent le nombre d'octets utilisés pour encoder le caractère à l'aide d'une séquence de bits à 1 et se termine par un bit à 0.\\ Exemple : 110xxxxx signifie que le caractère est codé sur 2 octets.
  * Dans le cas d'un encodage sur k octets, les k-1 octets qui suivent l'octet de poids fort doivent tous être de la forme 10xxxxxx.
//Exemples//
^  Pt de code  ^ point de code binaire     ^  UTF-8 (binaire/hexa)                    ^
|  U+004B      | 01001011           | 01001011 (4b)                             |
|  U+00C5      | 11000101           | 11000011 (C3) 10000101 (85)               |
|  U+0A9C      | 00001010 10011100  | 11100000 (E0) 10101010 (AA) 10011100 (9C) |   \\  \\

== 5.3.2 UTF16 ==
Voir <html><a href="https://fr.wikipedia.org/wiki/Unicode" target="_blank">Unicode</a></html> sur Wikipédia. \\ \\

== 5.3.3 UTF-32 ==
Voir <html><a href="https://fr.wikipedia.org/wiki/Unicode" target="_blank">Unicode</a></html> sur Wikipédia. \\ \\

== 5.3.4 UNICODE et Python ==
{{ :python:python.png?nolink&50|}}

<callout type="primary" icon="true">Les chaînes de caractères en Python sont des séquences de caractères au format **UTF-8**. Ces caractères peuvent être saisi directement avec leur point de code à l'aide d'une séquence d'échapement '\u' suivie du point de code en hexadécimal.</callout>

//Exemple//
<code python *.py>
a = '\u0042'
print(a) # Affichage du caractère A
</code>

A compléter

\\

{{ :python:python.png?nolink&50|}}
=== 5.4 Les chaînes de caractères en Python ===
Voir [[python:bases:chaines|Les séquences : chaînes de caractères]]

\\


==== 6. Pour aller plus loin ====
**Real Python** - <html><a href="https://realpython.com/python-encodings-guide/" target="_blank">Unicode & Character Encodings in Python: A Painless Guide</a></html>

----
==== Résumé ====

  * Les **nombres entiers** sont représentés en **binaire** (base 2) dans un ordinateur. La notation **hexadécimale** (base 16) simplifie l'écriture des nombres binaires. Il existe deux représentations des nombres stockés sur plusieurs octets, **le petit et le gros boutisme**, qui se différencient selon l'ordre des octets en mémoire. Le codage des nombres relatifs utilise la technique du **complément à deux** pour faciliter les opérations arithmétiques.

  * Les **nombres flottants** sont une représentation **approximative** des nombres réels dans un ordinateur. La norme internationale IEEE 754  définit un encodage en simple (32 bits) ou double précision (64 bits) ainsi que des règles d'**arrondi**. Les opérations arithmétiques sur les nombres flottants n'ont pas toujours les mêmes propriétés que ces mêmes opérations sur les réels. 

  * Les caractères sont représentés par des entiers et des tables de correspondances sont établies par des normes (ASCII, Unicode). La norme ASCII définit un jeu restreint de 127 caractères. Le format Unicode est conçu pour représenter les caractères de toutes les langues. Il existe plusieurs formats d'encodage Unicode (UTF-8, UTF-16, UTF-32) qui se distinguent par le nombre d'octets minimum pour représenter les points de code.