Présentation du cours

1h cours (7 semaines) + 3h TD (6 semaines)

Contenu :

Encodages et représentations
Représentations des nombres
- Écriture positionnelle en base quelconque
- Représentation des nombres relatifs
- Nombres à virgule flottante (IEEE 754)
Logique booléenne et circuits
- Opérateurs
- Circuits
- Additionneurs, UAL, etc.
Peut-être un peu d'assembleur si assez de temps...

Représentation de valeurs

Définition

Un bit (binary digit) est une unité d'information qui représente un état logique pouvant prendre deux valeurs (souvent notées \(0\) et \(1\)).

Proposition

Avec \(n\) bits, on peut représenter \(2^n\) valeurs différentes

1 bit : \(0\), \(1\)
2 bits : \(00\), \(01\), \(10\), \(11\)
3 bits : \(000\), \(001\), \(010\), \(011\), \(100\), \(101\), \(110\), \(111\)

Proposition

Pour représenter \(k\) valeurs distinctes, il faut utiliser au moins \(\lceil \log_2(k)\rceil\) bits

6 valeurs : \(log_2(6) \simeq 2,59\) → 3 bits
8 valeurs : \(log_2(8) = 3\) → 3 bits
9 valeurs : \(log_2(9) \simeq 3,17\) → 4 bits

Octet

En pratique on considère les bits par groupes de 8 :

1 octet = 8 bits = 256 valeurs
La mémoire des ordinateurs est adressée par octets (chaque octet a un numéro qui est son adresse)
Les octets peuvent être interprétés comme une valeur entre 0 et 255

Pour les grandes valeurs, on utilise des unités multiples de l'octet

Historiquement :

1 kilooctet (ko) = 1024 o
1 mégaoctet (Mo) = 1024 ko
1 gigaoctet (Go) = 1024 Mo
...

Depuis 1998 :

1 kilooctet (ko) = 1000 o
1 mégaoctet (Mo) = 1000 ko
1 gigaoctet (Go) = 1000 Mo
...

1 kibioctet (kio) = 1024 o
1 mébioctet (Mio) = 1024 kio
1 gibioctet (Gio) = 1024 Mio
...

Texte

Si l'alphabet est simple, on peut utiliser un format ASCII (p.ex. ISO-latin-9 pour le français)

1 octet par caractère

Si on veut utiliser un alphabet plus large, on peut utiliser l'Unicode

159 801 caractères (dernière mise à jour en sept. 2025)
163 systèmes d'écriture (modernes et historiques)
symboles divers (emoji, musique, etc.)

Il existe plusieurs encodages Unicode :

UTF-8
- 1 à 4 octets par caractère
- 0xxxxxxx
- 110xxxxx 10xxxxxx
- 1110xxxx 10xxxxxx 10xxxxxx
- 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
- Compatible ASCII
- Environ 97% des pages web actuelles

UTF-16
- 2 ou 4 octets par caractère
- Non compatible ASCII
- Utilisé en interne par Windows et Java

UTF-32
- Taille fixe de 4 octets par caractère

Attention ! L'encodage doit être connu pour éviter les problèmes

Images

Pour représenter une image, on peut décrire chacun de ses pixels

Pour une image en couleurs de \(n \times m\) pixels :

\(n \times m\) pixels
3 composantes par pixel (RGB)
1 octet pour chaque composante (0 à 255)

→ \(3\times n\times m\) octets pour représenter l'image

(3 Mo pour une image 1000x1000)

Audio

Source : Digital Audio Basics: Audio Sample Rate and Bit Depth

Pour représenter une fonction continue (p.ex. piste audio)

Un ou plusieurs canaux indépendants (mono: 1 canal, stereo: 2 canaux)
Mesures régulières au cours du temps (échantillons) → taux d'échantillonage en Hertz
Taille fixée pour les échantillons (bit depth) → nombre fini de valeurs possibles

Taille d'un fichier audio (en octets) :

taille d'un échantillon (en octets)
taux d'échantillonage (en Hz)
durée (en secondes)
nombre de canaux

Environ 10Mo par minute pour un fichier wave en stereo, 44.1 kHz, 16 bits par échantillon.

Audio

Source : Digital Audio Basics: Audio Sample Rate and Bit Depth

Un signal audio peut être décomposé en une superposition de signaux sinusoïdaux

Pour reconstruire une sinusoide : au moins 2 mesures par période
Pour enregistrer une fréquence de \(f\) Hz : au moins \(2f\) Hz d'échantillonage

On considère que l'oreille humaine perçoit les fréquences jusqu'à 20 kHz

→ Un échantillonage de 44.1 kHz permet d'enregistrer les fréquences audibles

Compression

Nombre d'images RGB de \(n\times m\) pixels : \(\left(256^3\right)^{n\times m}\)
Nombre de bits nécessaires : \(log_2\left((256^3)^{n\times m}\right) = 8\times 3\times n\times m\)

→ Il faut au moins \(3\times n\times m\) octets

Idée 1

Les images qui nous intéressent sont très différentes des images "aléatoires" (beaucoup de régularités)

Idée 2

Si on représente une image différente mais proche de l'image de départ, ça ne fait presque aucune différence

Compression de Huffman

\(\operatorname{a\ b\ a\ c\ b\ f\ a\ a\ d\ a\ e}\)

↓

\(0.100.0.101.100.1111.0.0.110.0.1110\)

↓

\(0100010110011110011001110\)

Si toutes les valeurs n'ont pas la même fréquence on peut représenter les plus fréquentes sur moins de bits

construction d'un arbre par le bas en regroupant les symboles les moins fréquents
on obtient un "code préfixe" de taille variable

→ Longueur moyenne d'un message est plus petite qu'avec un code de taille fixe

Compression

Sans pertes (lossless)

permet de retrouver les données exactes d'entrées
exploite des régularités attendues dans les données
ex: PNG (images), GIF (images, limité à 256 couleurs), FLAC (audio), ZIP (générique)

Avec pertes (lossy)

encode des données proches des données d'entrée
ex: JPG (images), MP3 (audio), H.264 (vidéo)

Cours n°1 :Représentations

Présentation du cours

Représentation de valeurs

ASCII

ASCII

Octet

Texte

Images

Audio

Audio

Compression

Compression de Huffman

Compression

Sans pertes (lossless)

Avec pertes (lossy)

Cours n°1 :
Représentations