Représentation des données : types et valeurs de base

Types et valeurs de base

Binaire & différentes bases

Encodage de l'information

Objectifs :
  • Codage des nombres entiers relatifs

Comment coder les nombres négatifs

Nombre négatif, méthode naïve

Pour représenter les entiers relatifs en notation binaire, on doit étendre la représenta- tion aux nombres négatifs. Une solution est de réserver un bit pour le signe de l’entier à représenter et d’utiliser les autres pour représenter sa valeur absolue.

Méthode naïve, exemple

Avec des mots de 8 bits, en utilisant 1 bit pour le signe et 7 bits pour la valeur absolue, on pourrait représenter les entiers relatifs
_ _ _ _ _ _ _ _

Par exemple :
1 0000011 => -3 0 0000011 => 3

Les problèmes de la méthodes naives

1) Tout d'abord il y a 2 zéros (un positif & un négatif):
  • 0 0000000 = +0
  • 1 0000000 = -0

Certaines addition deviennent fausse :
\underbrace{00000011}_{3} + \underbrace{10000100}_{-4} \underbrace{=}_{\neq} \underbrace{10000111}_{-7}

Opposé d'un nombre

L’opposé d’un nombre a est le nombre b tel que a + b = 0 .

L'opposé de 5

  • Déterminer l’écriture binaire du nombre 5 sur 4 bits.
  • Cherchez le nombre binaire qui additionné à 5 sera égal à 0 (les dépassements sont ignorés).
  • Quel est le codage binaire de (-5) ?

Codage de -7



Quel est le codage binaire de (-7) sur 4 bits ?

Les nombres relatifs en complement à 2 sur 4bits

En complément à 2 sur 4 bits on code :
  • 16 nombres (2^4)
  • Ces nombres sont compris entre -8 (-2^3) et 7 (2^3-1)

Nombre signé & complément à deux

On utilise la notation en complément à deux. Les nombres positifs sont représentés normalement,
en revanche les nombres négatifs sont obtenus de la manière suivante :
  • On inverse les bits de l'écriture binaire de sa valeur absolue (opération binaire NON), on fait ce qu'on appelle le complément à 1;
  • On ajoute 1 au résultat (les dépassements sont ignorés).

Exemple

Pour coder le nombre -4 sur 8 bits :

  • Le nombre 4 : 00000100_{\overline{2}}
  • On inverse les bits : 11111011_{\overline{2}}
  • On ajoute 1 : 11111100_{\overline{2}}

Exercice 5

Exercice 6

Nombre signé & complément à deux sur n bits

Avec la notation en complément à deux sur des mots de n bits, on écrit les entiers relatifs compris entre -2^{n-1} et 2^{n-1} - 1 :
  • un entier relatif x positif ou nul compris entre 0 et 2^{n-1} - 1 est représenté par l’entier naturel x compris entre 0 et 2^{n-1} - 1 ;
  • un entier relatif x strictement négatif compris entre -2^{n-1} et -1 est représenté par l’entier naturel x + 2^n compris entre 2^{n-1} et 2n - 1.

Exemple sur 16 bits

Avec des mots de 16 bits, on écrit les entiers relatifs compris entre :
-2^{15} = -32 768 et 2^{15} - 1 = 32 767.

Exercice 7

Overflow

Overflow

Overflow

Tout tenait à une seule petite variable : celle allouée à l'accélération horizontale. En effet, l'accélération horizontale maximum d'Ariane 4 donnait une valeur décimale d'environ 64. Cette valeur étant traitée dans un registre mémoire à 8 bits, cela donne en base binaire 2^8 = 256 valeurs disponibles, un nombre suffisant pour 64.
Mais Ariane 5 était bien plus puissante et brutale : son accélération pouvait atteindre la valeur 300, qui donne 100101100_{\overline{2}} et nécessite un registre à 9 bits. Ainsi, la variable codée sur 8 bits a connu un dépassement de capacité, puisque son emplacement mémoire n'était pas assez grand pour accepter une valeur aussi importante. Il aurait fallu la coder sur un bit de plus, donc 9 bits, ce qui aurait permis de stocker une valeur limite de 2^9-1 = 511, alors suffisante pour coder la valeur 300.
De ce dépassement de capacité a résulté une valeur absurde dans la variable, ne correspondant pas à la réalité.
Par effet domino, le logiciel décida de l'autodestruction de la fusée à partir de cette donnée erronée.

Les nombres flottants

Le missile Patriot : erreur 404, scud introuvable, 28 morts


Nous sommes le 25 février 1991 sur le champ de bataille de la guerre du Golfe.

Un Scud iraquien frappe la caserne de Dhahran, en Arabie saoudite, et tue 28 soldats du 14ème détachement de quartier-maître de l’armée américaine.
L’attaque aurait dû être interceptée par le système radar des missiles Patriot en service. Mais un bug logiciel dans la gestion des horodatages par le système s’est mêlée à la partie.

Comprendre ce qui c'est passé.

Le temps était compté par l'horloge interne du système en 1/10 de seconde.
Quelle est la représentation de \dfrac{1}{10} = 0,1_{10} en binaire ?

Comment représenter 5,1875 en binaire ?

  • D’un côté la partie entière 5
  • De l’autre la partie décimale 0,1875


On commence par la partie entière.
Représenter 5 en base 2, pas de problème :)
5_{\overline{10}} = 101_{\overline{2}}

Comment représenter 5,1875 en binaire ?

Et maintenant la partie décimal, comment représenter le ”,1875” ?
Méthode des puissance négative de 2
0, 187510 = 0, 125 + 0, 0625
0, 187510 = {\color{red}0} \times 0,5 +{\color{red}0} \times 0,25 + {\color{red}1} \times 0, 125 + {\color{red}1} \times 0, 0625
0, 187510 = 0, {\color{red}0011}

Comment représenter 5,1875 en binaire ?


Méthode des multiplications succéssives
  • 0, 1875 \times 2 = 0, 375 \Rightarrow 0, 375.
  • 0, 375 \times 2 = 0, 75. \Rightarrow 0 , 75
  • 0, 75 \times 2 = 1, 5. \Rightarrow 1, 5
  • 0, 5 \times 2 = 1, 0. \Rightarrow 1, 0
    On trouve 0, le procéssus s'arrete.

On a donc : 0, 1875_{\overline{10}} = 0, 0011 _{\overline{2}}

Comment représenter 5,1875 en binaire ?

5, 1875 _{\overline{10}} = 101, 0011 _{\overline{2}}

Déterminer les représentations binaires des nombres suivants

  • 11,75_{\overline{10}}
  • 6,375_{\overline{10}}
  • 5655,5625_{\overline{10}}
  • 0,1_{\overline{10}}
\dfrac{1}{10} = 0,1_{10} = 0,0001100110011001100110011..._{2}.
0,1 n'as pas d'écriture binaire finie. L'ordinateur de bord arrondissait 1/10 à 24 chiffres (codage sur 24 bits), d'où une petite erreur dans le décompte du temps pour chaque \dfrac{1}{10} de seconde.
Conséquence :
Au moment de l'attaque, la batterie de missile Patriot était allumée depuis environ 100 heures, ce qui avait entraîné une accumulation des erreurs d'arrondi de 0,34 s.
Pendant ce temps, un missile Scud parcourt environ 500 m, ce qui explique que le Patriot soit passé à côté de sa cible.
Conséquence : le système a scruté dans la mauvaise partie du ciel et n’a trouvé aucune cible. En l’absence de cible, la détection initiale était supposée être une piste parasite et le missile avait été retiré du système.
En cause, la batterie de missiles Patriot qui était en service depuis 100 heures, au bout desquelles l’horloge interne du système avait dérivé d’un tiers de seconde. En raison de la vitesse du missile, cela équivalait à une distance manquante de 600 mètres.
Ironie du sort, deux semaines auparavant, le 11 février 1991, les Israéliens avaient identifié le problème et avaient informé l’armée américaine et le bureau du projet Patriot, le fabricant de logiciels. Comme solution provisoire, les Israéliens avaient recommandé de redémarrer régulièrement les ordinateurs du système. Le fabricant a fourni un logiciel mis à jour à l’armée le 26 février.

Et python dans tous ça ?

Titre du popup

Message du popup !