Compression de Données Ghislain PANDRY Chercheur, Traitement du signal et des i

Compression de Données Ghislain PANDRY Chercheur, Traitement du signal et des images 11 janvier 2022 I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon INTRODUCTION : Alphabet La théorie de l'information donne le cadre mathématique aux codes compresseurs. On rappelle qu'un alphabet est un ensemble ni qui sert à former les messages contenant l'information à coder ou l'information codée. L'ensemble des lettres du message source est l'alphabet source et l'ensemble des lettres du code l'alphabet du code. Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Exemple :Alphabet Par exemple, l'alphabet latin est l'ensemble des lettres que nous utilisons pour écrire, ou {0, 1} est l'alphabet qui sert à écrire les messages qui doivent transiter dans la plupart des canaux numériques. Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Dé nition : Code L'ensemble des séquences sur un alphabet V est noté V +, et l'image de l'alphabet source par la fonction de codage est un sous-ensemble de V + appelé l'ensemble des mots de code, à qui on donne parfois le nom de code. Un code C sur un alphabet V est alors un sous-ensemble ni de V +. Le code est constitué des briques de base à partir desquelles les messages transmis seront construits. Un élément m de C est appelé mot de code. Sa longueur est notée l(m). L'arité du code est le cardinal de V . Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Example : Code C = {0, 10, 110} est un code binaire d'arité 2, sur l'alphabet V = {0, 1}. Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Longueur Tous les mots de code n'étant pas toujours de la même longueur, on utilise une mesure dépendant des fréquences d'apparition pour estimer la longueur des messages qui coderont une source. Une source d'information est constituée d'un alphabet S et d'une distribution de probabilités P sur S. Pour un symbole si d'une source S = (S, P), P(si) est la probabilité d'occurrence de si, et l(m) désigne la longueur d'un mot m (de source ou de code). Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Formule Soient S = (S, P) ou S = {s1, · · · , sn}, et C un code de S, dont la fonction de codage est f (C est l'image de S par f ). La longueur moyenne du code C est : l(C) = n X i=1 l(f (si))P(si) (1) Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Exemple : Longueur d'un mot Soit une source d'information S = (S, P), avec S = {a, b, c, d}, P = {1 2, 1 4, 1 8, 1 8} et V = {0, 1}. Soit C = {f (a) = 00, f (b) = 01, f (c) = 10, f (d) = 11}, quelle est la longueur moyenne de C. Réponse l(C) = 2 ∗1 2 + 2 ∗1 4 + 2 ∗1 8 + 2 ∗1 8 = 2 Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Interrogation : Longueur d'un mot (3 minutes) Soit une source d'information S = (S, P), avec S = {a, b, c, d}, P = {1 2, 1 4, 1 8, 1 8} et V = {0, 1}. Soit C = {f (a) = 0, f (b) = 10, f (c) = 110, f (d) = 1110}, quelle est la longueur moyenne de C. Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Dé nition : L'entropie L'entropie d'une source S = (S, P), P = {p1, · · · , pn} est utilisée comme mesure de la quantité moyenne d'information contenue dans cette source. C'est une mesure de l'incertitude liée à une loi de probabilités. H(S) = n X i=1 pilog2( 1 pi ) (2) Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique I-1 : Alphabet et Code I-2 : Dé nition : Longueur d'un mot I-3 : L'entropie et théorème de Shannon Dé nition : Théorème de Shannon Soit une source S sans mémoire d'entropie H. Tout code uniquement déchirable de S sur un alphabet V de taille q = |V |, de longueur moyenne l, véri e : l ≥ H log2q (3) De plus, il existe un code uniquement déchirable de S sur un alphabet de taille q, de longueur moyenne l, qui véri e : l < H log2q + 1 (4) Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Dé nition Les codages statistiques utilisent la fréquence de chaque caractère de la source pour la compression et, en codant les caractères les plus fréquents par des mots plus courts, se positionnent proches de l'entropie. Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Étape 1 Algorithme de Human Algorithme de Human permet de trouver le meilleur schéma d'encodage d'une source sans mémoire S = (S, P). L'alphabet de codage est V , de taille q. Il est nécessaire à l'optimalité du résultat de véri er que q −1 divise |S| −1 (a n d'obtenir un arbre localement complet). Dans le cas contraire, il est facile de rajouter des symboles à S, de probabilités d'occurrence nulle, jusqu'à ce que q −1 divise |S| −1. Les mots de codes associés (les plus longs) ne seront pas utilisés. Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Étape 1 :Initialisation Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Étape 2 Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Étape 2 Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Étape 3 On recommence ensuite avec les q plus petites valeurs parmi les n÷uds du plus haut niveau (les racines), jusqu'à n'obtenir qu'un arbre (à chaque itération, il y a q −1 éléments en moins parmi les n÷uds de plus haut niveau), dont les mots de S sont les feuilles, et dont les mots de code associés dans le schéma ainsi construit sont les mots correspondant aux chemins de la racine aux feuilles. Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Exemple code Human Soit la source (voir tableau) à coder sur V = {0, 1} Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Correction code Human Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Correction code Human Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Correction code Human Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Correction code Human Ghislain PANDRY Compression de Données I-Théorie de l'information II : Codages statistique II-1 : Codage de Human II-2 : Codage arithmétique Dé nition codage arithmétique En codage arithmétique, chaque caractère peut être codé sur un nombre non entier de bits. L'idée du codage arithmétique est d'encoder les caractères par intervalles. La sortie d'un code arithmétique est un simple réel entre 0 et 1 construit de la manière suivante : à chaque symbole on associe une portion de l'intervalle [0, 1[ qui a pour taille sa probabilité d'occurrence. L'ordre d'association n'importe pas pourvu que soit le même pour uploads/S4/ cours-information-compression-1.pdf

Documents similaires

Réseaux & Protocoles TD 03 : Codage et modulation L3 IUP 2005-2006 Exercice 1 R 0 0

COUTAZ & FANTI AVOCATS AU BARREAU DU VALAIS NOTAIRES SÉBASTIEN FANTI Avocat & N 0 0

Spécialité : Base de données S3 Module : Gestion des bases de données en ligne. 0 0

WAT ATTPAI F 031020222257 410009 AL FLUX MAT 0466237 E - PAGE 1/3 IDX B 1041101 0 0

15/10/2021 1 Chapitre 3: Entity framework Core ENSEIGNANTE: DR. ING. GHOFRANE F 0 0

DROIT DES CONTRATS INFORMATIQUES I-Introduction Le droit des contrats informati 0 0

La signature électronique en droit Algérien à l'épreuve de l'économie numérique 0 0

Théorie de l’information et du Codage Objectifs du Cours Etude de la mesure de 0 0

CONSEIL D'ETAT statuant au contentieux N°s 440442, 440445 __________ ASSOCIATIO 0 0

Débuter avec l’Arduino et Node-RED. Enregistrer et afficher des mesures en JSON 0 0

• Détails
• Publié le Fev 15, 2022
• Catégorie Law / Droit
• Langue French
• Taille du fichier 0.8526MB