Codage

Principe de codage
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 :
· numéro de téléphone d'un particulier
· numéro de sécurité sociale
· code postal
ou à longueur variable
· alphabet morse
· ADN

Quelques codes

! Ne pas confondre un nombre et sa représentation !

Notation positionelle
La représentation d'un nombre est un codage. La représentation d'un nombre dans une base b donnée:

Code binaire naturel
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.

Code BCD/DCB
Décimal Codé Binaire : chaque chiffre d'un nombre est sur codé 4 bits

0	0000
1	0001
2	0011
10	0001 0000
11	0001 0001

Ce code simplifie conversion décimal binaire.

Code de Gray
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.
Détection d'erreurs
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 :
· 0110 devient 01100,
· 1011 devient 10111
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.

Codage des données alphanumériques
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é).

· A est codé par 1000001,
· e est codé par 1100101,
· 7 est codé par 0110111,
· ! est codé par 0100001,
· etc...
Unicode = code récent sur 16 bits contenant pratiquement tous les alphabets existants (employé dans java).

Système de numération
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.
Conversions binaire-décimale
Base b vers base 10
exprimé en base b(noté ) vers une représentation en base 10 :

Cas de la partie fractionnaire :

Base 10 vers base b

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.

Représentation des nombres négatifs

Signe et valeur absolue
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]

Notations complémentés
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]

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]

Notation excédentaire
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).
Représentation des nombres réels
Plusieurs représentations possibles :
· virgule fixe : revient à manipuler des entiers (caisses enregistreuses)
· couple (numérateur,dénominateur) : représentation juste uniquement pour les nombres rationnels
· virgule flottante
Virgule flottante
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.
Norme IEEE754
· nombres codés sur 32 bits (simple précision), ou 64 bits (double précision)
· la mantisse appartient à l'intervalle [1,0, 10,0[ (en binaire)
· le seul chiffre à gauche de la virgule étant toujours 1, n'est pas représenté
· l'exposant est codé avec un excès de 127 (simple précision) ou 1023 (double précision)
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

! La norme IEEE 754 est la norme la plus utilisée pour représenter les réels.

Précision
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 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., ).