Théorie de linformation PDF 25 Nov 2020 Entre deux

THEORIE DE LINFORMATION CORRIGES

Exercice 2. Information moyenne. 1. L'alphabet ici ne contient que le symbole « pile ». On remarque que « pile » est un

Théorie de linformation

Exercice C.1 : Code de Hamming. Soient la source S qui émet les cinq symboles suivants et leur code associé : a) Détermine les codes associés

Théorie de linformation

25 Nov 2020 Entre deux faces adjacentes ? Page 19. 2.4. EXERCICES. 19. Exercice 6. Entropie maximale à espérance ...

Théorie de lInformation (2)

Exercices. Théorème de la source binomiale. Codage. Codage de source. Déchiffrabilité. Notion de code préfixe. Théorie de l'Information (2). Philippe Duchon.

Théorie du signal et de linformation Exercices et problèmes

Lesquels peuvent être corrigés ? Les corriger grâce au décodage par syndrome. Exercice 3.15 (??). Décodage par syndrome On considère un canal binaire

Théorie et Codage de lInformation (IF01) — exercices —

Exercice 1. On dispose d'un jeu de 52 cartes dans lequel on effectue un tirage au hasard avec remise. Calculer la probabilité d'obtenir

Exercices et problèmes de statistique et probabilités

Corrigés des exercices . 4.1 Éléments de théorie de l'information . ... La théorie des probabilités repose sur l'étude de phénomènes aléatoires.

Corrigé type « Théorie de linformation »

Exercice 01: (14 points). 1- Dessiner le modèle de ce canal. Montrer qu'il est un canal binaire symétrique. Ce canal est symétrique parce que les

Exercices de théorie de linformation — entropie et codage

THÉORIE DE L'INFORMATION. Entropie et codage. Antoine CHAMBERT-LOIR / Guillaume GARRIGOS. •. EXERCICE 1. — Second principe de la thermodynamique.

THEORIE DE LINFORMATION

La théorie de l'information trouve ses origines dans les débuts des communications Exercice 1. Exemple. Corrigé. ? Distributions marginales de X.

Université Paris 8 Année 2020-2021

Master Mathématiques et applications

Parcours AAC (Arithmétique, Codage et Cryptologie) Parcours CSSD (Cyber Sécurité et Sciences des Données)

Théorie de l"information

Notes de cours (en construction)

Julien Lavauzelle

julien.lavauzelle@univ-paris8.fr

25 novembre 2020

Table des matières

1 Introduction5

1.1 Systèmes de communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Autres applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Grandeurs en théorie de l"information 7

2.1 Rappels sur les probabilités discrètes . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Codage de source 21

3.1 Encodage d"un alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2 Codes à longueur fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3 Codes à longueur variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.4 Code de Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Codage de canal 33

4.1 Canaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1.1 Définitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1.2 Capacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2 Codes en blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.3 Codes convolutifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.3.1 Définition et représentations . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.3.2 Algorithme de décodage de Viterbi . . . . . . . . . . . . . . . . . . . . . . . 42

4.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5 Autour de la compression de données 47

5.1 Processus stochastiques et codage universel . . . . . . . . . . . . . . . . . . . . . . . 47

5.2 Algorithmes de Lempel et Ziv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2.2 Algorithme de Lempel-Ziv-Welch . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2.3 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.3 Compression sans perte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.3.1 Un premier algorithme de compression : RLE . . . . . . . . . . . . . . . . . 53

5.3.2 Autour de bzip2 : la transformée de Burrows-Wheeler . . . . . . . . . . . . 53

5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6 Applications en cryptographie 59

6.1 Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.1.1 Modèle et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.1.2 Chiffrement parfait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.2 Fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.3 Retrait confidentiel d"information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Quelques références utiles

[Rio07] Olivier Rioul.Théorie de l"information et du codage. 2007 [CT01] Thomas M. Cover and Joy A. Thomas.Elements of Information Theory. Wiley, 2001 [HP10] William Cary Huffman and Vera Pless.Fundamentals of Error-Correcting Codes. Cambridge

University Press, 2010

[Mac03] David JC MacKay.Information Theory, Inference, and Learning Algorithms. 2003 3

4TABLE DES MATIÈRES

Chapitre 1

Introduction

1.1 Systèmes de communication

La théorie des communications a pour but d"étudier les moyens de transmission de l"information

à travers un canal, depuis une source jusqu"à un récepteur. Cette théorie a été introduite par

Claude Shannon en 1948 dans un article précurseur [Sha48] qui pose les fondements de la théorie

de l"information. Shannon propose un modèle simple et générique dans lequel unesourced"information produit

un message. Ce message est ensuite encodé par un codeur, puis transite à travers un canal sujet à

un bruit. Le message potentiellement altéré est fourni à un décodeur qui retourne l"information

obtenue au récepteur.récepteurdécodeursourcecodeur canal Figure1.1 - Modèle générique d"un système de communication Les codeurs et décodeurs mentionnés plus haut entrent dans le domaine ducodage de source. Le plus souvent, ils ont pour but d"interpréter le message comme une suite numérique.

On peut raffiner le modèle présenté ci-dessus en intégrant descodeurs et décodeurs de canal. Leur

objectif est de corriger de potentielles erreurs induites par bruit du canal. Ce modèle est illustré

en Figure 1.2. Enfin, dans le domaine d"application des communications, le canal est concrètement vu comme

un opérateur aléatoire agissant sur des signaux continus (par exemple, une interférence entre

ondes électro-magnétiques). Il faut donc transformer le signal numérique issu du codeur de canal en signal analogique continu. On ajoute donc desmodulateur et démodulateurde données aux schémas précédents, voir Figure 1.3. 5

6CHAPITRE 1. INTRODUCTIONrécepteurdécodeur

de sourcedécodeur de canalsourcecodeur de canalcodeur de sourcecanal

Figure1.2 - Modèle d"un système de communication avec distinction des codeurs/décodeursrécepteurdécodeur

quotesdbs_dbs2.pdfusesText_3

[PDF] Théorie de linformation 25 Nov 2020 Entre deux