Représentation des données

Représentation des entiers relatifs

Rappel. Il est possible de représenter les entiers naturels (les nombres $n \in \mathbb{N}$) à l'aide de leur écriture en base deux.

Par exemple, $\overline{10110100}^2$ représente le nombre : $\dotfill$

Avec cette représentation, le bit le plus à gauche est appelé le bit de poids fort, le bit le plus à droite est appelé le bit de poids faible.

Soit $N$ un entier naturel. On appelle capacité le nombre de nombres binaires qu'il est possible de représenter sur $N$ bits.

Avec $N = 8$ bits il est possible de coder $256$ valeurs (par exemple les entiers positifs de $0$ à $255$). Avec $N = 16$ bits il est possibles de coder $65 536$ valeurs.

Soit $N$ un entier naturel.

Soient $n_1\in \mathbb{N}$ et $n_2 \in \mathbb{N}$ deux entiers pouvant s'écrire sur $N$ bits. On ajoute bit à bit les deux nombres en reportant les retenues éventuelles. Si l'addition du bit de poids fort génère une retenue, on dit qu'il y a dépassement de capacité.

On additionne $n_1 = 42$ et $n_2 = 14$ écrits sur $8$ bits.

On additionne $n_1 = 5$ et $n_2 = 6$ écrits sur 8 bits.

Pour soustraire deux nombres, on utilise la même méthode, car pour tout entiers $a$ et $b$ on a : $a - b = a + (-b)$.

Il faut donc trouver une manière de représenter $-b$, à savoir les entiers relatifs.

Soit $n \in \mathbb{Z}$. On note $\overline{b_N \ldots b_1 b_0}$ l'écriture en base 2 de $|n|$ écrit sur $N$ bits.

Le complément à 2 $\overline{c_N \ldots c_1 c_{0}}$ de $n$ est défini de la manière suivante :

Si $n$ est positif, $n = |n|$ : dans ce cas il s'agit de l'écriture en base deux usuelle de $n$.

On a alors : $ \overline{c_N \ldots c_1 c_{0}} = \overline{b_N \ldots b_1 b_0} $ et le bit de poids fort est toujours 0.
Si $n$ est négatif, $n = -|n|$ :
- on inverse les bits de l'écriture binaire de $n$ ;
- on ajoute 1 au résultat (les dépassements de capacité sont ignorés).
Dans ce cas on a alors : $\overline{c_N \ldots c_1 c_{0}} = \overline{ \texttt{\textasciitilde} b_N \ldots \texttt{\textasciitilde} b_1 \texttt{\textasciitilde} b_0} + 1 $, où $\texttt{\textasciitilde}0 = 1$ et $\texttt{\textasciitilde}1 = 0$ et le bit de poids fort est toujours 1.

On représente $n = -5$ écrit sur $N = 8$ bits à l'aide du complément à 2.

On représente $n = -4$ écrit sur $N = 4$ bits à l'aide du complément à 2.

Soit $N$ un entier naturel.

La représentation binaire en complément à 2 sur $N$ bits permet de représenter les $2^{N}$ entiers $n \in [-2^{N - 1} ; 2^{N - 1} - 1]$.

Sur $N = 3$ bits, on peut représenter tous les entiers entre $-2^{-2} = -4$ et $2^{2} - 1 = 3$.

Représentation en complément à 2	`000`	`001`	`010`	`011`	`100`	`101`	`110`	`111`
Entier $n$ en base 10	$0$	$1$	$2$	$3$	$-4$	$-3$	$-2$	$-1$

Soit $n = \overline{b_N \ldots b_1 b_0}$ un entier positif écrit sur $N$ bits, et $-n = \overline{c_N \ldots c_1 c_0}$ son complément à 2. Alors en ajoutant bit à bit et en ignorant les dépassements de capacité on a toujours : $$n + (-n) = \underbrace{\overline{0 \ldots 0}}_{N \text{ fois }} $$

Effectuer le calcul $42 - 14$ à l'aide de la méthode du complément à 2 en écrivant les entiers sur $N = 8$ bits.

Effectuer le calcul $-4 - 3$ à l'aide de la méthode du complément à 2 en écrivant les entiers sur $N = 3$ bits.

Comment corriger ce problème ?

Représentation des nombres réels

On appelle partie fractionnaire de $x\in \mathbb{R}$ le nombre $f\in [0 ; 1[$ tel que $x - f \in \mathbb{Z}$. On appelle partie entière de $x$ le nombre $x - f$.

On représente les nombres $f \in [0 ; 1[$ en binaire en les décomposant en somme de puissances inverses de 2. Le bit immédiatement après la virgule correspond à $2^{-1}$, puis $2^{-2}$ etc.

Pour convertir une partie fractionnaire écrite en base 10 en base 2 :

On multiplie la partie fractionnaire par 2.
Extraire la partie entière du résultat : c'est le bit suivant dans la représentation en base 2.
Continuer jusqu'à ce que la partie fractionnaire soit nulle.

Convertir $\overline{0,011}^2$ en base 10.

Convertir $\overline{0,8125}^{10}$ en base 2.

Convertir $\dfrac{1}{3}$ en base 2.

Convertir $0,1$ en base 2.

Pour représenter les nombres réels (à approximation près), on utilise un système similaire à la notation scientifique. Par exemple, le nombre d'Avogadro est $6,0221 \times 10^{23}$ et la masse du proton est $9,1094 \times 10^{-31}$. Dans les deux cas, on a utilisé 5 chiffres significatifs et deux chiffres pour l'exposant (en plus du signe).

On utilise en binaire la décomposition suivante :

$$ x = \text{ signe } \times (1 + \text{ mantisse } ) \times 2^{ \text{ exposant } } \qquad \text{ avec } 0 \leq \text{ mantisse } < 1 $$

Les nombres flottants (précision simple, norme IEE 754) stockés sur 32 bits vérifient :

1 bit pour le signe ;
8 bits pour l’exposant ;
23 bits pour la mantisse représentée en base 2.

$$ \underbrace{ \underbrace{\fbox{\hspace{1.5pt} \text{ Signe } \hspace{0.5pt}}}{1 \text{ bit}} \hspace{1pt} \underbrace{\fbox{\hspace{17.5pt} \text{ Exposant } \hspace{17.5pt}}} \hspace{1pt} \underbrace{\fbox{\hspace{88pt} \text{ Mantisse } \hspace{78pt}}}}{23\text{ bits}}% } $$}

L'exposant est un entier compris entre $-126$ et $127$, mais les valeurs correspondant à $-127$ et $128$ sont réservés respectivement pour coder d'une façon particulière les nombres très proches de $0$, $+\infty$, $-\infty$ et $NaN$. (Not a Number, le résultat de $+\infty - \infty$ par exemple.)

La constante d'Avogadro $6,0221 \times 10^{23}$ s'encode ainsi en :

01100110111111110000101110111101

Source. https://www.h-schmidt.net/FloatConverter/IEEE754.html

Ceci explique :

🐍 Code Python
print(0.1 + 0.2)

⚙️ Résultat

0.30000000000000004

Pour comparer des nombres flottants, on n'utilise jamais l'opérateur ==. On utilise plutôt une marge d'erreur. Par exemple à $10^{-3}$ près :

🐍 Code Python
print(abs(0.1 + 0.2 - 0.3) <= 10**(-3))    

⚙️ Résultat

True

Représentation des caractères

L’American Standard Code for Information Interchange (Code américain normalisé pour l’échange d’information : ASCII) est une norme informatique d'encodage de caractères. Elle contient 128 points de code et permet d’encoder les chiffres arabes de 0 à 9, les 26 lettres de l’alphabet latin en minuscules et en capitales, des symboles mathématiques et de ponctuation, ainsi que des caractères spéciaux.

Dans ce code, seules 128 valeurs sont utilisés (impossible d'encoder la lettre "ç" par exemple !). Le bit de poids fort d'un octet représentant un caractère est donc toujours 0.

Quel texte représente les trois octets suivants : 01001110 01010011 01001001 ?

La norme Unicode attribue un identifiant numérique, appelé point de code, différent à chacun des milliers de caractères nécessaires à la transcription des différentes langues mondiales, existantes ou non, on retrouve par exemple le klingon et l’elfique et différents éléments tels que les émoticônes.

Cette norme ne précise pas sous quelle forme cet identifiant doit être encodé par le système informatique. Il existe donc plusieurs normes d’encodages différentes en fonction des besoins, mais chacune a en commun d’associer à chaque caractère le même identifiant numérique.

L'encodage UTF-8 (Unicode Transformation Format) est un code à taille variable destiné à représenter les codes Unicode. Le fonctionnement est le suivant :

Si le bit de poids fort est à 0, le point de code est codé sur un octet, et correspond à un caractère ASCII.
Si le bit de poids fort est à 1, le nombre de 1 consécutifs indique le nombre d’octet utilisé pour coder le point de code. Les deux bits de poids forts des octets suivants sont fixés à 10 pour indiquer qu'ils continuent la séquence.

Nombre d'octets	Premier code	Dernier code	Octet 1	Octet 2	Octet 3	Octet 4
1	0000	007F	0xxxxxxx
2	0080	07FF	110xxxxx	10xxxxxx
3	0800	FFFF	1110xxxx	10xxxxxx	10xxxxxx	10xxxxxx
4	10000	10FFFF	11110xxx	10xxxxxx	10xxxxxx	10xxxxxx

Le message suivante est codé en UTF-8, combien de caractères sont-ils représentés ? Combien d’entre eux correspondent à un caractère ASCII ?

0110001 0110101 11100010 10000010 10101100

On peut obtenir en Python le code d’un caractère à partir de la fonction ord, et inversement on peut obtenir un caractère à partir de son code à l’aide de la fonction chr.

Par exemple :

🐍 Code Python
print(ord("a")) 
print(ord("A")) 
print(ord("€")) 
print(chr(200)) 
print(chr(240))

⚙️ Résultat

Circuits combinatoires

Un circuit combinatoire est un circuit électronique muni de $n$ entrées et de $m$ sorties au format binaire (0/1). Sa spécification se fait à base de fonctions booléennes ou de tables de vérité.

Les portes logiques sont des circuits combinatoires élémentaires, qu'il est possible de réaliser éléctroniquement à l'aide de transistors.

Si $C$ est un circuit combinatoire quelconque, alors il est possible de le construire uniquement à l'aide des portes AND et NOT.

A	B	S
0	0	0
0	1	0
1	0	0
1	1	1

A	S
1	0
0	1