Compression de message et correction d'erreurs : comprendre les codes de Fano Shannon, Huffman et Hamming
5 views 0 purchase
Course
Théorie de l\'information
Institution
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller r00tme. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.21. You're not tied to anything after your purchase.
