Codage et Compression

Pr Amina SERIR

Master 1 ST
Introduction au module
◼ Transmission numérique
On s’intéresse à la compression à la fois pour le
stockage sur des supports de mémoire et pour
la transmission. Certes les capacités des
disques durs de nos ordinateurs et le débit des
réseaux ne cessent d’augmenter. Cependant,
notre utilisation de l’image et du son
également.
◼ De nombreux autres appareils numériques

ont vu le jour : téléphone portable, le GPS,

appareil photo numérique,…..
L’utilisation de données sous leurs formes numériques
ne serait pas possible aujourd’hui sans la compression
préalable de celles-ci. Et ceci pour plusieurs raisons:
- Les capacités de stockage des utilisateurs, même si
elles ne cessent d’augmenter, ne sont pas infinies.
- La durée de transmission de ces données numériques
est conditionnée par le débit du réseau qui est utilisé et
qui est parfois relativement faible.
La compression des données numériques permet donc
de diminuer la taille de stockage et de rendre possible
leurs transports sur des réseaux de communication
(internet, GSM, câble, TV, satellite).
 Sommaire
1. Notions fondamentales de codage source
et codage canal (1 semaine)
2. Codages entropiques (2 semaines)
3. Codage du canal (3 semaines)
4. Méthodes de compression avec pertes (2
semaines)
5. Techniques de compression d’images
(Cas du JPEG) (4 semaines)
Chapitre 1:
Notions fondamentales de codage
source et codage canal

Pr Amina SERIR

Master 1 ST
Chapitre 1: Notions fondamentales
de codage source et codage canal

I.1 Définition, différence et Intérêt du

codage canal et du codage source
I.2 Sources et codage source
I.3 Canal et codage Canal
I.4 Notions sur le codage conjoint
I.5 Notions de probabilité (rappel)
I.1 Définition, différence et Intérêt
du codage canal et du codage source
◼ La théorie des communications s’intéresse
aux moyens de transmettre une information
depuis la source jusqu’à un utilisateur à
travers un canal.
I.1 Définition, différence et Intérêt
du codage canal et du codage source
◼ La nature de la source peut être très variée.
Il peut s’agir par exemple d’une voix, d’un
signal électromagnétique ou d’une séquence
de symboles binaires.
Exemples de signaux paroles
Exemples d’images
Exemples de signaux
Electrocardiogramme
Electro-Encéphalogramme
EEG
Exemple de trace sismique
I.1 Définition, différence et Intérêt
du codage canal et du codage source
Le canal peut être une ligne téléphonique, une
liaison radio, un support magnétique ou
optique.
I.1 Définition, différence et Intérêt
du codage canal et du codage source
◼ Le codeur représente l’ensemble des
opérations effectuées sur la sortie de la
source avant la transmission. Ces opérations
peuvent être par exemple :
- la modulation,
- la compression,

- le brouillage,

- l’ajout de redondance pour combattre les

effets du bruit, ou encore l’adaptation à des

contraintes de spectre.
I.1 Définition, différence et Intérêt
du codage canal et du codage source
Elles ont pour but de rendre la sortie de la
source compatible avec le canal.
Enfin le décodeur doit être capable, à partir de
la sortie du canal, de restituer de façon
acceptable l’information fournie par la source.
I.1 Définition, différence et Intérêt
du codage canal et du codage source
◼ La théorie de l’information a été créée par Claude
Elwood Shannon dans les années 40. Il s’agit d’une
théorie mathématique qui décrit les aspects les plus
fondamentaux des systèmes de communication. Elle
consiste en l’élaboration et l’étude de modèles pour
la source et le canal qui utilisent différents outils
comme les probabilités et les automates finis.
◼ Dans ce cours, nous étudierons certains de ces
modèles qui, bien que considérablement plus simples
que les sources et les canaux physiques, permettent
de donner une bonne approximation de leur
comportement.
 I.1 Définition, différence et Intérêt
du codage canal et du codage source

◼ Pour simplifier, on étudiera séparément les

modèles de sources et les modèles de canaux
ainsi que leurs codages respectifs.
- Le but du codeur de source est de représenter
la sortie de la source en une séquence binaire, et
cela de façon la plus économique possible, c’est
de la compression des données (éliminer les
redondances inutiles).
 I.1 Définition, différence et Intérêt
du codage canal et du codage source

- Le but du codeur de canal et de son décodeur

est de reproduire le plus fidèlement possible cette
séquence binaire malgré le passage à travers le
canal bruité: Accroitre la sécurité de la
transmission en présence du bruit (ajouter de la
redondance pour détecter, voire corriger les
principales erreurs).
I.1 Définition, différence et Intérêt
du codage canal et du codage source

◼ Cette séparation entre codage de source et codage

de canal n’implique en pratique aucune limitation sur
les performances du système complet.
I.1 Définition, différence et Intérêt
du codage canal et du codage source

◼ L’optimisation d’une chaine de transmission peut se

faire en optimisant séparément les codeurs source et
canal.
◼ Objectif de la recherche et innovation: Optimiser
conjointement le codeur de source et de canal.
I.2 Sources et Codage source
◼ Sources d’information:
◼ Définition: systèmes capables de sélectionner et une
séquence de signes (ou message) appartenant à un
ensemble (ou alphabet) donné.
◼ Ex. de signes : lettres, chiffres, échantillons.
◼ Ex. de sources : système à 2 niveaux logiques, texte

Deux sortes de sources d’information: Discrète et

Continue.
I.2 Sources et Codage source
◼ Sources d’information discrètes:
◼ Caractéristique : alphabet utilisé fini

◼ Exemples : Sources d’information

alphanumériques, de symboles binaires,

d’information numérique(e.g.
signaux quantifiés en amplitude, en fréquence
ou en phase)
I.2 Sources et Codage source
Sources d’information discrètes:
Classification :
◼ Sources sans mémoire : signes générés

indépendamment les uns des autres =>

modèle de Bernoulli
Sources avec mémoire : prise en compte de la
dépendance entre un signe émis et les signes
précédents
=> modèle de Markov
I.2 Sources et Codage source
Sources d’information discrètes:
Classification des sources de Markov :
◼ Source du 1 er ordre = la mémoire se limite

au dernier signe émis

– Ex : modélisation du processus de réalisation
d’un phonème
◼ Source d’ordre m = la mémoire tient compte
des m signes émis
– Ex : description statistique des langues écrites
usuelles
I.2 Sources et Codage source
Sources d’information continues:
◼ Caractéristique : nombre théorique de

signes croît à l’infini

◼ Remarque : Limite pratique fixée par la

précision limitée des observations

◼ Exemples : Sources de signaux analogiques :

Parole,Musique, Images, Mesures.

I.2 Sources et Codage source
Modélisation des sources d’information:
◼ Mécanisme statistique d’émission des signes

◼ Source discrète : une loi de probabilité

donnée associée à une variable aléatoire

discrète.
◼ Source continue : une loi de densité de
probabilité associée à une variable aléatoire
continue
I.2 Sources et Codage source
Modélisation des sources d’information:
◼ Exemples :

◼ TEXTE = succession des réalisations de la

variable aléatoire : "caractère sortant du

clavier » .
◼ IMAGE_NB = succession de "niveaux de gris"

mesurés sur une image.

I.2 Sources et Codage source
Principe du codage source:
◼ Signal = Information + Redondance

◼ Objectif : Coder seulement l’information et

éliminer la redondance.
◼ Besoin d’évaluation objective de la quantité

d’information propre (théorie de l’information).

 I.3 Canal et Codage Canal
Contexte:

Systèmes de télécommunications
Exemples : WiFi, TNT, Bluetooth, 3G, …
Causes de l’altération : mauvaises conditions de reception.
Résultat : les données reçues sont différentes des données émises.
Stockage de données sur support physique
Stockage : écriture sur support physique (CD, disque dur).
Causes de l’alteration : CD rayé, …
Résultat : les données lues sont différentes des données écrites.
 I.3 Canal et Codage Canal
Conséquences:

L’équipement qui va utiliser les données (téléphone mobile, lecteur DVD) ne

sait pas que le flux de données comporte des erreurs.

L’impact de l’utilisation de données altérées dépend de l’application et du

type d’altération.
Fort impact : un bit faux dans le codage d’un numéro de carte bleue .
Faible impact : plusieurs paquets manquants dans le codage d’une
conversation téléphonique.
I.3 Canal et Codage Canal
Enjeu:
◼ Comment savoir si un flux de données comporte des

erreurs ?
- 1ere étape : détecter les erreurs.
◼ Que faire lorsque le flux de données a traiter est erroné ?
- Corriger les erreurs (protocoles de la couche 1 et lecture de
données sur support CD).
- Solliciter l’émission de nouvelles données (protocoles a
partir de la couche 2).
- Interpoler entre les données précédentes et les données
suivantes (applications).
- On effectue le codage de l’information à transmettre.
I.3 Canal et Codage Canal
Les méthodes de codage canal:
◼ Codes en blocs linéaires
1. Matrice génératrice et matrice de contrôle de parité
2. Codes cycliques
3. Décodage optimal soft-decision
4. Décodage hard-decision
◼ Codes convolutifs
◼ Combinaisons de codes
I.4 Notions du codage conjoint
◼ Le problème du codage source canal conjoint
est alors beaucoup plus difficile à résoudre.
◼ De nombreux chercheurs avaient déjà
remarqué que se préoccuper de l’impact des
erreurs de transmission sur la distorsion
totale améliorait l’efficacité globale du
système. Ces préoccupations sont apparues
de manière sensiblement différentes suivant
que leurs auteurs étaient de culture « codage
source » ou « codage canal ».
I.4 Notions du codage conjoint
◼ Les différentes approches:
- Protection des codes source: le premier
réflexe a été de régler les codeurs source de
telle manière que des erreurs éventuelles de
transmission aient un impact moins néfaste au
décodage. On vise alors à rendre les codeurs
source plus robustes, sans forcément prendre
en compte les techniques de codage canal.
I.4 Notions du codage conjoint
Cette stratégie peut être améliorée dans un
contexte hiérarchique, où différents éléments
transmis n’ont pas la même « importance »
pour restituer la source.
I.4 Notions du codage conjoint
◼ Equilibrage des rendements: le codage conjoint a
également des conséquences importantes au niveau
système. En effet, il a été observé que la stratégie
traditionnelle, consistant à comprimer au maximum la
source pour un niveau de distorsion donné,
n’améliore pas toujours les performances du système
global. Ceci parce qu’elle rend plus sensible le train
binaire aux erreurs de transmission : une erreur peut
avoir des conséquences catastrophiques sur la
compréhension du signal après décompression.
I.4 Notions du codage conjoint
◼ Pour compenser cet effet, il faudrait alors
mieux protéger le train binaire issu du codeur
source contre les erreurs de transmission.
Dans la théorie de Shannon, ça ne pose
aucun problème. En pratique, il existe
toujours des contraintes de complexité
matérielle et de délai qui limitent l’utilisation
de codeurs canal très sophistiqués, de sorte
que le bilan global, pour cette stratégie, n’est
pas toujours intéressant.
I.4 Notions du codage conjoint
◼ Une meilleure stratégie consisterait à
obtenir cet équilibrage entre codeur source et
canal par une véritable conception conjointe.
 I.5 Notions de probabilité (rappels)
◼

 S = s1 , s2 ,... sK  K
P( S = si ) = pi p
i =1
i =1

S = si
P( S = si ) = pi = P( Ai )
I.5 Notions de probabilité (rappels)
0  P( Ai )  1
P( Ai ) = 1 quand Ai est certain
P( Ai ) = 0 quand Ai est impossible
I.5 Notions de probabilité (rappels)
I.5 Notions de probabilité (rappels)
I.5 Notions de probabilité (rappels)
I.6 Quantité d’information propre
I.7 Entropie d’une source discrète
On considère que l’apparition d’un événement peu probable
apporte beaucoup d’information tandis que l’occurrence d’un
événement certain ne fournit au contraire aucune information.
Si un symbole (lettre ou valeur) a a une probabilité p(a) d’être
tirée, son information propre est définie par:
I (a) = − log 2 ( p(a))

En particulier I(a) vaut zéro si p(a) = 1. Le choix de la

fonction log et de sa base seront expliqués plus loin.

47
I.7 Entropie d’une source discrète
La valeur moyenne de l’information propre calculée sur
l’ensemble de l’alphabet revêt une grande importance. Il s’agit
donc de l’espérance de la variable aléatoire I. Elle est
appelée entropie de la source et est notée H(A) :

H ( A) = − p (a ) log 2 ( p (a ))
a A
Si une source émet n lettres équiprobables (ou encore avec
une loi de probabilité uniforme), son entropie est donc log 2 (n)
Si n = 2 r, son entropie est alors r. Or pour représenter 2 r
lettres distinctes en binaires, r cases sont nécessaires.
 I.5 Entropie d’une source discrète

L’entropie d’une source est quelquefois donnée en

bits/seconde. Si l’entropie d’une source discrète est H et si les
lettres sont émises toutes les  s secondes, son entropie en
bits/s est H /  s .