Codage de l'information

In [ ]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib

Information binaire

Une machine informatique, lit, transforme et transmet de l'information. La plus petite quantité d'information qui peut être transmise ou stockée est une information binaire (oui/non, pile/face, gagné/perdu, mort/vivant, vrai/faux). Cette information binaire est appelée bit (contraction de binary unit). Par exemple, l'application d'une tension de +/- 5V sur un fil électrique permet de transmettre une information binaire. Les deux états binaires sont conventionnellement désignés par les symboles 0 et 1. La correspondance entre un symbole binaire et sa signification, par exemple pile ou face, est arbitraire. Cette correspondance est appelée codage.

Plus généralement, toute information est transmise et stockée sous la forme d'une suite de symboles binaires 0 ou 1. Cette information n'a une signification que s'il existe une règle de codage qui explique comment interpréter cette suite de symboles.

Octet

Un groupe de 4 bits est appelé un quartet. Il y a $2^4=16$ quartets distincts. Les informaticiens ont pris l'habitude d'associer à chaque quartet un chiffre ou une lettre :

quartet symbole
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 A
1011 B
1100 C
1101 D
1110 E
1111 F

Cette correspondance n'a rien de fortuite. Les colonnes de gauche et de droite peuvent s'interpréter comme étant les écritures en base deux, respectivement en base seize, des entiers 0 à 15.

Un octet est un groupe de 8 bits, autrement dit formé de deux quartets. Il y a $2^8=256$ octets différents. Chaque octet peut être représenté par ses deux chiffres en base seize.

L'octet 11001001 s'écrit C9 en base seize.

En pratique on manipule de grandes quantités d'information et on utilise souvent les unités ci-dessous :

  • 1 Kio = $2^{10}$ octets = $1024$ octets
  • 1 Mio = $2^{20}$ octets = $1\,048\,576$ octets
  • 1 Gio = $2^{30}$ octets = $1\,073\,741\,824$ octets

Codage des entiers non signés

En informatique l'expression entiers non signés désigne les entiers positifs. Un entier non signé est représenté par par son écriture en base deux. Sur $n$ bits on peut représenter les entiers de 0 à $2^n-1$.

Codage des entiers signés

Il s'agit ici des entiers relatifs.

Sur $n$ bits, la plage des entiers représentables va de $-2^{n-1}$ à $2^{n-1}-1$ :

  • Un entier positif est représenté par son écriture en base deux.
  • Un entier négatif $p$ est représenté par l'écriture en base deux de l'entier positif $p+2^n$.

Codage des flottants

Sur $n$ bits il n'est possible de représenter que $2^n$ nombres réels distincts. Le principe utilisé est de séparer les $n$ bits en trois parties :

  • 1 bit de signe
  • $e$ bits d'exposant qui représentent un entier relatif $p$
  • $m$ bits de mantisse qui représentent un entier naturel $a$

Le nombre représenté par les $n$ bits est le réel $\pm a\times 2^p$.

Sur les ordinateurs équipés d'un processeur 64 bits une valeur de type float est codé sur 64 bits. Le nombre de réels représentables par un float est donc majoré par $2^{64}$.

La norme IEEE 754 spécifie les règles de codage. Le mot de 64 bits est divisé en trois parties :

  • bits 0-51 : La mantisse qui code les chiffres significatifs.
  • bits 52-62 : L'exposant qui code l'ordre de grandeur.
  • bit 63 : Le signe du flottant.

Codage IEEE 754

Les nombres réels représentables sous cette forme sont appelés les nombres flottants. Les flottants ne sont pas répartis de façon homogène sur la droite réelle. La densité est de plus en plus forte lorsqu'on se rapproche de 0.

On peut remarquer que le nombre $\frac{1}{10}$ n'est pas un nombre flottant. Ainsi, après l'affectation x = 0.1, la variable x ne contient pas le flottant 0.1 car ce flottant n'existe pas. La variable x contient le flottant le plus proche de $\frac{1}{10}$.

In [ ]:
0.1 + 0.1 + 0.1
Out[ ]:
0.30000000000000004

Un point essentiel à garder à l'esprit est que les calculs effectués sur des types float sont fondamentalement des calculs approchés et non pas exacts. Tester l'égalité entre deux flottants n'est généralement pas pertinent. Il convient plutôt de tester un encadrement.

Codage d'une image noir et blanc

Pour pouvoir être manipulées par une machine informatique les données continues doivent au préalable être discrétisées. Une image en noir et blanc est ainsi représentée par une matrice constituée d'un nombre fini de pixels. De plus, l'intensité lumineuse de chaque pixel est elle-même discrétisée en un nombre fini de valeurs. L'usage est de représenter cette intensité par un entier non signé codé sur un octet. L'échelle comprend donc 256 valeurs allant de 0 (pixel noir) jusqu'à 255 (pixel blanc).

Codage d'une image couleur

N'importe quelle couleur peut être produite en superposant des sources de lumières rouge, verte et bleue dans des proportions adéquates. La couleur d'un pixel peut donc être représentée par trois nombres compris entre 0 et 255 donnant respectivement les quantités de chacune des couleurs primaires rouge, verte et bleue. C'est le principe du codage RGB.

Codage des caractères

Les caractères utilisés dans les diverses langues humaines ont été répertoriés par la norme Unicode. Chacun de ces caractères est identifié par un nombre appelé son point de code.

La fonction python ord retourne le point de code d'un caractère donné :

In [ ]:
ord('é')
Out[ ]:
233

La fonction python chr retourne le caractère correspondant à un point de code donné :

In [ ]:
chr(233)
Out[ ]:
'é'

Pour transmettre ou stocker un caractère, comme toute autre information il faut disposer d'une règle de codage. La norme utf-8 spécifie des règles de codage pour les caractères Unicode.

In [ ]:
'é'.encode()
Out[ ]:
b'\xc3\xa9'

La lettre b au début indique que la valeur retournée par python n'est pas de type str (chaîne de caractères), mais une suite d'octets.

La fonction encode, appliquée à une chaîne de caractères, retourne la suite d'octets qui représente cette chaîne selon le codage utf-8.

Le caractère 'é' est codé en utf-8 par les deux octets C3 A9, c'est-à-dire par la suite de bits : 1100 0011 1010 1001.

Exercices

Question 1

La résolution d'une image vidéo HD 720p est de 1280 pixels sur 720 pixels.

(a) Quel est l'espace mémoire nécessaire pour stocker une image vidéo HD 720p ?

(b) Les images sont transmises sur le cable HDMI à la cadence de 25 images par seconde. Quelle est le débit en bits/s ?

Question 2

On souhaite transmettre des messages en utilisant uniquement les 26 lettres de l'alphabet ainsi qu'un espace pour séparer les mots.

(a) Proposer un codage pour les messages.

(b) En utilisant votre codage, combien d'octets sont nécessaires pour transmettre le message NANCY A LE TORTICOLIS ?

Pilotage à distance d'un robot

On considère la pièce rectangulaire ci-dessous :

scene

Les unités sont exprimées en mètres. Les rectangles noirs représentent des obstacles.

Un robot, situé dans cette pièce, peut s'orienter selon les directions cardinales (N/S/W/E) et avancer d'un nombre entier de mètres. Ce robot est relié par liaison radio à un ordinateur qui doit pouvoir le piloter. La réalisation des programmes côté ordinateur et côté robot nécessite de spécifier précisément la nature de l'information échangée et le codage précis de cette information.

Un mouvement est une orientation dans une direction cardinale suivi d'un déplacement en ligne droite d'un nombre entier de mètres. Un ordre est un message envoyé par l'ordinateur vers le robot et comportant une succession de mouvements.

Question 3

Spécifier une règle de codage pour transmettre un ordre.

Question 4

On suppose que le robot se trouve à la position $(0, 0)$, orienté vers l'Est. Proposer une séquence d'octets qui permet de déplacer le robot jusqu'à la position $(11, 14)$ ?