1

Samson LASAULCELaboratoire des Signaux et Systèmes, Gif/Yvette

Compression et Transmission des Signaux

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 2

De Shannon à Mac Donalds

Monsieur X1951 –

Mac Donalds1955 –

Claude Elwood Shannon1916 – 2001

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 3

Où sommes-nous sur la carte des STIC?

Technologies de l’Information

Sciences de l’Information

Théorie del’Information

Informatique …Théorie deShannon

Théorie de l’InformationQuantique

Théorie del’Estimation

…

Codages pratiques(normes)

Composants …Théorèmes de codage …

Interaction?

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 4

Une classification des signaux

La dimension tempsSignaux à temps continu (TC)Signaux à temps discret (TD)

La dimension amplitudeSignaux continusSignaux discrets

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 5

Théorème d’échantillonnageThéorème 1 [Shannon – Nyquist – Küpfmüller]

Hyp: signaux à support spectral fini, continus ou discrets.

Concl: signaux à temps continus↔ signaux à temps discrets, pourvu que

Dém: [Shannon1949], “Communication in the presence of noise”.

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 6

A propos des théorèmes de codage

Ce qu’offre un théorème de codagePartie atteignabilité (démonstration souvent constructive): existence d’un bon code,

idées et concepts de codagePartie réciproque: performances ultimes du système de compression/transmission

DémonstrationQuasi-totalité des théorèmes pour les signaux à temps discretPlus difficile pour les signaux discretsSi le cas discret est disponible, on peut généralement en déduire le cas continu

(au moins gaussien)Constante de temps!

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 7

Compressionsans Pertes

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 8

Deux types de compression

Signaux discrets Signaux continus (ex: gaussiens)

∃ toujours des pertes

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 9

Débit critique?

Entropie d’une variable aléatoire discrète et scalaire

Remarque: approche de l’ingénieur (sémantique, affectif, …).

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 10

DéfinitionsSource et taux de codage (source)

Message binairede longueur

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 11

Théorème CS sans pertes (CSSP) Théorème 2 [Shannon1948 – Cover1991]

Hyp: source discrète X d’alphabet et sans mémoire, soit ε>0.Concl: (i) il existe un code sans préfixe dont le taux de codage est aussi proche du

taux critique (l’entropie) que l’on veut:

(ii) tout code dont le taux de codage excède le taux critique ne peut avoirune erreur de reconstruction évanescente

Dém: [Shannon1948], “A mathematical theory of communications”, [Cover1991], “Elements of information theory”. Idée fondamentale: séquences typiques.

LGN → x souvent typique

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 12

Grandes lignes de la démonstrationDémonstration de l’atteignabilité

Idée 1: n grandIdée 2: séquence très probable → mot court

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 13

CSSP: à la recherche du Graal (1)

Codage de Huffman [Huffman1952]Normes: fax, JPEG, HDTV, MP3, …Idée du codage (cas scalaire)Propriétés

Code sans préfixeLe taux de codage converge vers l’entropie

FIN DE LA QUETE???Inconvénients

Il faut connaître la distribution de la sourceCas des sources binairesComplexité exponentielle en n

Remarque: Idées 1 et 2 exploitées

hyperbolique

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 14

CSSP: à la recherche du Graal (2)

Codage arithmétique [Rissanen1979]Normes: JPEG, H263, …Idée du codage (cas scalaire)

Représenter une séquence par un réelAssocier à ce réel un intervalle de [0,1] dont la longueur est proportionnelle à la

probabilité de la séquenceFaire une partition de [0,1] à partir de la distribution de la source

CaractéristiquesLe taux de codage converge vers l’entropie

Adaptatif (peut apprendre en ligne la distribution de la source et accommoder une source variable) . Codage incrémental. Facile à prendre en compte la mémoire de la source.

En pratique, meilleures performances que le codage de HuffmanSource binaire: OK, particulièrement simple à faire

Inconvénients:ComplexitéBrevets

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 15

CSSP: à la recherche du Graal (3)

Plus généralement: autres codages universels [LZ77, LZ78, LZW]Normes: les fameux .zipBut: pouvoir être utilisé pour toutes les sources

Représenter une séquence par un réelAssocier à ce réel un intervalle de [0,1] dont la longueur est proportionnelle à la

probabilité de la séquenceFaire une partition de [0,1] à partir de la distribution de la source

PrincipeMettre des séparateurs dans les chaînes de donnéesRemplacer une chaîne par un pointeur

PropriétéLe taux de codage converge vers l’entropieDictionnaire adaptatif

InconvénientsIgnore d’éventuels a priori sur la sourceOptimum pour une classe de machine à états (ex: stationnaire et ergodique)

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 16

Transmission des

Signaux

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 17

Rappel du contexte (avant 1948)Codage à répétition

Probabilité d’erreur

Rendement informatif

Codage de HammingRendement informatif:Probabilité d’erreur: ne tend pas vers 0 car elle est déterminée par la distribution

des distances de Hamming entre mots, dominée par la distance minimale. Ordmin = 3 donc le décodeur ne peut pas corriger plus d’une erreur par mot.

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 18

DéfinitionsCanal et taux de codage [Shannon1948]

sans mémoiresans retour d’info

BLER

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 19

Information mutuelleDéfinition (variables discrètes et scalaires)

Lien avec l’entropie

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 20

Théorème du codage canalThéorème 3 [Shannon1948 – Cover1991]

Hyp: canal discret sans mémoire et sans retour d’information. On définit

Concl: (i) il existe un code de taux de codage R < C dont la probabilité d’erreurest évanescente;

(ii) le taux de codage de tout code dont la probabilité d’erreur estévanescente vérifie nécessairement R ≤ C.

Dém: [Shannon1949], “Communication in the presence of noise”, [Cover1991], “Elements of information theory”. Atteignabilité par typicité conjointe, réciproque par Fano.

Idée 1: mettre de la redondanceIdée 2: mots longsIdée 3: codage aléatoire (iid et dico variable, la structure importe peu!).

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 21

Retrouvons la capacité du CBS (1/2)Canal binaire symétrique

Observation sur le codage à répétition (cas du rendement 1/3)

000001010100

000 111011101110111

Contenu de la boulede centre 000 et de rayon 1.

Contenu de la boulede centre 111 et de rayon 1.

NB: pas d’intersection entre les boules

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 22

Retrouvons la capacité du CBS (2/2)Empilement de sphères

Visualisation

Volume d’une boule dans {0,1}n

Approximation du terme dominant pour n grand

Rayon d’une boule de bruit

Nombre maximal de message distincts (M)

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 23

Capacité de canal pour des modèlestrès usités

Canal binaire symétrique (CBS)

Canal à effacement binaire (CEB)

Canal gaussien (BBAG)

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 24

Turbo-codage et turbo-décodage [Berrou93]Principaux ingrédients* Mots de code longs* Echange d’information souple au décodeur* Complexité maîtrisée (2 codeurs simples aulieu d’un compliqué).

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 25

Performances des turbo-codes BER

∼ SNR

HypothèsesModulation BPSKRendement du codeur: ½Limite de Shannon à 0 dBCanal gaussien

0.7 dB

Un concept générateurd’idées

Turbo-estimationTurbo-détectionTurbo-égalisation“Réveil” des LDPC

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 26

Codes de contrôle de parité à faible densité – LDPC

InventeursGallager 1962Redécouverts par MacKay 1995

Turbo vs LDPC?Out of scopeVoir par exemple: http://www.josephboutros.org/ldpc_vs_turbo/

IngrédientsMots longsImmitent le codage aléatoireInformation souple

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 27

Compressionavec Pertes

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 28

Théorèmes de CS avec pertesThéorème pour les sources discrètes [Shannon1959]

Hyp: soit X une source discrète i.i.d et sa représentation approchéeConcl: la fonction taux distorsion est donnée par

Théorème pour les sources gaussiennes [Shannon1959]Hyp: et

Concl:

1959 – 1974 ThéorieModèle sourceCritère (plus arbitraire)

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 29

Étude (hyper-compressée!)du cas JPEG

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 30

Principales étapesEtapes

Transformée DCT sur des blocsQuantificationCodage RLECodage entropique

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 31

Zoom sur un bloc

Pb: sensibilité aux erreurs → théorème de séparation!

« Vide »

Théorie taux distorsion:quantification scalaire vs vectorielle0,255 bit/symbole – 1,53 dB

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 32

Meilleure amie et pire ennemie

Uniformité spatiale Uniformité fréquentielle

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 33

Ouverture (fermeture) 1/2

Capacité pour d’autres modèles de canaux point à pointCanaux variables dans le temps (sélectivité temporelle) Canaux sélectifs en fréquenceCanaux à entrées et sorties vectoriellesConnaissance imparfaite du canal au récepteur et/ou l’émetteur

Codage de source – canal conjointCompression robuste aux erreurs de transmissionAnalogique vs numériqueMulti-terminal

Autres problèmesCapacité zéro-erreur [Shannon1956]

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 34

Ouverture (fermeture) 2/2Canaux multi-terminaux: problèmes ouverts!

Canal de diffusion [Cover1972]Canal à relais [Cover1979]Canal à interférenceUne théorie de l’information pour les réseaux unifiéeSécurité de l’information [Shannon1949]: une nouvelle forme de cryptographie

Evolution des approchesApproche classique: lien entre l’énergie et l’informationNouvelle approches: limite ultime de la quantité d’information par élément de

volume de matière?Théorie de l’information quantique

Journées X – ENS – UPS; ENS Paris; 14 mai 2008 35

Quelquesréférencespassionnantes

Articles et livresArticles de C. ShannonT. Cover and J. Thomas, “Elements of information theory”S. Mallat, “A wavelet tour of signal processing”S. Verdú and S. McLaughlin, “Information theory: 50 years of

discovery”ET BIEN SÛR: R. MacDonald, “Compresser, transporter et retrouver

vos boeufs avec un nombre de cornes perdues arbitrairement petit” ☺