Le but de ce cours est de présenter les pré-requis à l'étude des unités fonctionnelles d'une machine. Ces pré-requis sont principalement la numération binaire et la logique booléenne. De manière plus précise, ce cours étudie :
Soit I un ensemble d'informations. Soit un ensemble fini de symboles appelé alphabet. Les ai sont appelés caractères de A. Un ensemble ordonné de caractères est appelé mot. La base du codage est le cardinal de l'ensemble A.
Coder I consiste à faire correspondre à chaque éléments de I un mot de A. Un codage est redondant si un élément est associé à plusieurs codes.
Un codage peut être à longueur fixe :
ou à longueur variable
? Pour un codage de longueur fixe n, si b est la base du codage, montrer que l'on peut représenter bn éléments, et que l'on a alors bn! codages possibles.
! Ne pas confondre un nombre et sa représentation !
La représentation d'un nombre est un codage. La représentation d'un nombre dans une base b donnée:
Alphabet de 2 caractères : 0 et 1 (caractères binaires appelés bits)
Correspondance basée sur la représentation des nombres en base 2.
0 | → | 000 |
1 | → | 001 |
2 | → | 010 |
3 | → | 011 |
4 | → | 100 |
5 | → | 101 |
6 | → | 110 |
7 | → | 111 |
? Pourquoi ce tableau ne contient pas le code de 8 ?
Généralement, les bits les plus à gauche sont appelés poids forts.
! Le codage binaire naturel n'est qu'un codage particulier.
Décimal Codé Binaire : chaque chiffre d'un nombre est codé sur 4 bits
0 | → | 0000 |
1 | → | 0001 |
2 | → | 0011 |
... | ... | |
10 | → | 0001 0000 |
11 | → | 0001 0001 |
Ce code simplifie la conversion décimal binaire.
Distance de 1 entre deux mots de code consécutif
0 | → | 000 |
1 | → | 001 |
2 | → | 011 |
3 | → | 010 |
4 | → | 110 |
5 | → | 111 |
6 | → | 101 |
7 | → | 100 |
Ce code évite le changement simultané de 2 bits, et donc les états transitoires indésirables.
La transformation d'un 0 en 1 ou d'un 1 en 0 est une erreur fréquente en informatique (problème de transmission, défaillance d'un circuit, etc...)
Un code redondant peut être utilisé pour détecter des erreurs.
Exemple : ajout d'un bit (dit bit de parité). Le bit supplémentaire maintient la parité de l'information :
Il existe d'autres codes correcteur d'erreurs, où l'augmentation de la redondance permet de détecter et corriger une erreur. Dans le code de Hamming, 3 bits sont ajoutés à quatre bits de données pour contrôler la parité de trois groupes de trois bits de données différents.
? Comment un tel codage permet t'il la détection d'une erreur ?
Face aux multiple possibilités de codage, des organismes de normalisation ont vu le jour (le plus célèbre étant l'ISO).
Code ASCII = code employé pour les caractères alphanumériques (a,b,1,?, ,,,). Code sur 7 bits (+ 1 bit de parité).
Unicode = code récent sur 16 bits contenant pratiquement tous les alphabets existants (employé dans java).
L'homme a 10 doigt. Le système de numération humain est le système décimal. L'ordinateur a 2 état significatifs (impulsion électriques). Le système de numération qu'il emploie est donc le système binaire.
! L'homme compte sur ses doigts, l'ordinateur compte sur ses bits.
exprimé en base b(noté ) vers une représentation en base 10 :
Cas de la partie fractionnaire :
a0 est le reste de la division entière du nombre par la base b. Des divisions entières successives par la base donnent donc tous les ai.
Cas de la partie fractionnaire : sur un principe similaire, des multiplications successives par la base donnent tous les ai.
? Quelles sont les représentations de 100 dans toutes les bases inférieures à 10 ?
? Conversion avec une base puissance de la base de départ, par exemple octale (8 = 23) ou hexadécimale (16 = 24) et binaire.
Sur n bits : signe = bit de poids fort (0 : positif, 1 : négatif), n-1 bits = valeur absolue.
Intervalle de valeurs représentés pour n bits : [-2n-1 + 1, 2n-1 - 1]
? Quelles sont les 2 représentations possibles pour zéro ?
Complément à 1: inversion de chaque bit de la valeur absolue du nombre à représenter.
-1 | → | 110 |
-2 | → | 101 |
-3 | → | 100 |
Intervalle de valeurs représentés pour n bits : [-2n-1 + 1, 2n-1 - 1]
? Quelles sont les 2 représentations possibles pour zéro ?
Complément à 2 = complément à 1 + 1
-1 | → | 111 |
-2 | → | 110 |
-3 | → | 101 |
Intervalle de valeurs représentés pour n bits : [-2n-1, 2n-1 - 1]
? Combien de représentation possible pour zéro ?
Ajout au nombre de la valeur d'un excès (souvent translation de 2n-1, ainsi le bit de poids fort fait office de bit de signe).
Intervalle de valeurs représentés pour n bits avec un excès de 2n-1 : [-2n-1, 2n-1 - 1]
Intérêt : simplifie toutes les opérations ou les comparaisons (qui se font uniquement sur des nombres positifs).
Plusieurs représentations possibles :
Un nombre réel est représenté par un signe, une mantisse m, un exposant e, et une base b.
! La représentation en virgule flottante est la représentation des réels la plus utilisée.
Il existe une infinité de représentation du même nombre. Représentation normalisée : pour une base b, la mantisse est prise dans l'intervalle [1,b[ (zéro admet une représentation particulière).
La précision et l'intervalle de valeurs représentées dépendent du nombre de bits utilisés pour coder la mantisee et l'exposant.
Sur 32 bits :
S | exposant E | mantisse M |
---|---|---|
1 bits | 8 bits | 23 bits |
Exemple : -5 est codé par 1100 0000 1010 0000 0000 0000 0000 0000
? Vérifier que ce codage est le bon !
! La norme IEEE 754 est la norme la plus utilisée pour représenter les réels.
La représentation des nombre réels sur une machine se base sur un nombre fini de valeurs. C'est donc une représentation approchée.
Précision de la représentation = différence entre les mantisses de deux nombres réels consécutifs.
! La précision ne dépend que de la mantisse.
IEEE 754, simple précision (32 bits) : la précision est de 2-23.
Les valeurs particulières représentés avec IEEE 754 :
E | M | Valeur représentée |
---|---|---|
max | 0 | |
max | NaN | |
0 | 0 | 0 |
0 | 0 | nombres dénormalisés |
La valeur (propageable) NaN signifie Not A Number. Elle est pratique pour représenter le résultat de certains calcul (e.g., ).