Compression de message et correction d'erreurs : comprendre les codes de Fano Shannon, Huffman et Hamming
5 vues 0 fois vendu
Cours
Théorie de l\'information
Établissement
Grenoble I - Université Joseph-Fourier
Ce cours présente une introduction à la compression de données et à la correction d'erreurs de transmission en utilisant les codes de Fano Shannon, Huffman et Hamming. Nous explorerons les concepts fondamentaux de la théorie de l'information tels que l'entropie, les codes préfixes, les arbres...
La numérisation a facilité la collecte, la manipulation et la diffusion de grandes quantités de
données, mais cela a également créé de nouveaux défis. Comment gérer ces données à grande
échelle, les conserver dans le temps, être capable de les retrouver rapidement et faire face à
l'obsolescence des programmes et des technologies qui les supportent ? Ces défis ont été exacerbés
par l'urgence climatique actuelle, qui nous oblige à repenser les moyens que nous utilisons pour
stocker et accéder à ces données tout en réduisant notre impact environnemental.
Le texte de James Baker, Rachel MacGregor et Anna McNally aborde cette question en se
concentrant sur la numérisation des archives et la manière dont elle contribue à la crise climatique.
Ils soulignent la nécessité de repenser les moyens que nous utilisons pour stocker et accéder aux
données, en se posant des questions difficiles telles que "doit-on vraiment tout numériser ?" et
"l'accès instantané est-il nécessaire pour toutes les données ?". Ils proposent de nouvelles pratiques
pour gérer les archives numériques de manière plus durable et pour contribuer à la justice
climatique.
Dans ce contexte, les méthodes de compression de données telles que les codes de Huffman et de
Fano-Shannon jouent un rôle important en permettant de stocker les données de manière plus
efficace. De même, les codes de correction d'erreur tels que le code de Hamming sont utilisés pour
s'assurer que les données sont transmises et stockées de manière fiable.
I. Compression de documents
Il existe deux types de compression de documents : la compression avec perte et la compression
sans perte. La compression avec perte est utilisée pour les fichiers multimédias tels que les images,
les vidéos ou les fichiers audio : cela réduit la taille du fichier en éliminant les informations qui ne
sont pas perceptibles à l'œil ou à l'oreille humaine. La compression sans perte, quant à elle, est
utilisée pour les fichiers texte et autres types de données où la perte d'informations est inacceptable.
Cette méthode de compression réduit la taille du fichier en utilisant des algorithmes pour éliminer
les données redondantes.
II. Codes de Huffman
L’idée du code de Huffmann consiste à grouper les deux événements les moins probables en un
unique événement et à renouveler l’opération avec le nouvel ensemble d’événements ainsi obtenu.
L’algorithme de Huffman (1952) est un algorithme glouton, c’est-à-dire un algorithme qui enchaîne
des procédures localement optimales en vue d’un résultat global optimal. Cet algorithme construit
un code instantané optimal. En pratique, il conduit à des réductions de longueur de l’ordre de 20 à
90% et il peut être associé à d’autres formes de codage.
Il modélise le code par une forêt composée d’arbres qui possèdent des noeuds dont le poids est la
somme des poids de leurs enfants (le poids d’un arbre est celui de sa racine).
Initialement, les arbres (à 1 seul noeud) sont les états de la source, le poids de chacun de ces arbres
est la probabilité de l’état associé.
A chaque étape, l’algorithme groupe deux des arbres de plus faible poids en un arbre unique dont
ils sont les enfants.
Au final, l’algorithme produit un arbre unique de poids 1.
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur r00tme. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €2,99. Vous n'êtes lié à rien après votre achat.
