Séance de cours

Entropie conditionnelle: Codage Huffman

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

COM-102: Advanced information, computation, communication II

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain? ...

Description

Cette séance de cours de l'instructeur couvre le concept d'entropie conditionnelle, en mettant l'accent sur le codage Huffman pour une compression efficace des données. En commençant par l'observation des arbres ternaires, la séance de cours progresse pour discuter de l'entropie commune, des codes Shannon-Fano, et de la compression des longues cordes à l'aide des codes Huffman. L'instructeur explique comment calculer l'entropie conditionnelle et l'attente conditionnelle, en utilisant des exemples comme le 'Bit Flipper Channel'. La séance de cours se termine par une discussion sur le comportement de la longueur des mots de code à mesure que le nombre de symboles augmente et la complexité de trouver des stratégies de codage optimales. Les élèves apprendront des techniques efficaces de compression des données et des compromis liés aux stratégies de codage.

Enseignant·e·s (2)

Bixio Rimoldi

Enseignement et PhD A dirigé les thèses EPFL de Nicolae Chiurtu, Ninoslav Marina, Prasenjit Dey, Raja Manakkal, Peter Allan Berlin, Marius Kleiner, Vojislav Gajic, Saeid Haghighatshoar, Adrian Dan Tarniceriu A co-dirigé les thèses EPFL de Michael Gastpar, Tarik Tabet

Michael Christoph Gastpar

Michael Gastpar is a (full) Professor at EPFL. From 2003 to 2011, he was a professor at the University of California at Berkeley, earning his tenure in 2008. He received his Dipl. El.-Ing. degree from ETH Zürich, Switzerland, in 1997 and his MS degree from the University of Illinois at Urbana-Champaign, IL, USA, in 1999. He defended his doctoral thesis at EPFL on Santa Claus day, 2002. He was also a (full) Professor at Delft University of Technology, The Netherlands. His research interests are in network information theory and related coding and signal processing techniques, with applications to sensor networks and neuroscience. He is a Fellow of the IEEE. He is the co-recipient of the 2013 Communications Society & Information Theory Society Joint Paper Award. He was an Information Theory Society Distinguished Lecturer (2009-2011). He won an ERC Starting Grant in 2010, an Okawa Foundation Research Grant in 2008, an NSF CAREER award in 2004, and the 2002 EPFL Best Thesis Award. He has served as an Associate Editor for Shannon Theory for the IEEE Transactions on Information Theory (2008-11), and as Technical Program Committee Co-Chair for the 2010 International Symposium on Information Theory, Austin, TX.

Source officielle

Proximité ontologique

Information engineering

Théorie de l'information: Capacité d'un canal

Concepts associés (31)

Entropie croisée

En théorie de l'information, l'entropie croisée entre deux lois de probabilité mesure le nombre de bits moyen nécessaires pour identifier un événement issu de l'« ensemble des événements » - encore appelé tribu en mathématiques - sur l'univers , si la distribution des événements est basée sur une loi de probabilité , relativement à une distribution de référence . L'entropie croisée pour deux distributions et sur le même espace probabilisé est définie de la façon suivante : où est l'entropie de , et est la divergence de Kullback-Leibler entre et .

Entropie conjointe

vignette|Entropie conjointe. En théorie de l'information, l'entropie conjointe est une mesure d'entropie utilisée en théorie de l'information, qui mesure la quantité d'information contenue dans un système de deux variables aléatoires (ou plus de deux). Comme les autres entropies, l'entropie conjointe est mesurée en bits ou en nats, selon la base du logarithme utilisée. Si chaque paire d'états possibles des variables aléatoires ont une probabilité alors l'entropie conjointe de et est définie par : où est la fonction logarithme en base 2.

Compression de données

La compression de données ou codage de source est l'opération informatique consistant à transformer une suite de bits A en une suite de bits B plus courte pouvant restituer les mêmes informations, ou des informations voisines, en utilisant un algorithme de décompression. C'est une opération de codage qui raccourcit la taille (de transmission, de stockage) des données au prix d'un travail de compression. Celle-ci est l'opération inverse de la décompression.

Entropie de Rényi

L'entropie de Rényi, due à Alfréd Rényi, est une fonction mathématique qui correspond à la quantité d'information contenue dans la probabilité de collision d'une variable aléatoire. Étant donnés une variable aléatoire discrète à valeurs possibles , ainsi qu'un paramètre réel strictement positif et différent de 1, l' entropie de Rényi d'ordre de est définie par la formule : L'entropie de Rényi généralise d'autres acceptions de la notion d'entropie, qui correspondent chacune à des valeurs particulières de .

Entropie min

En probabilités et en théorie de l'information, l'entropie min d'une variable aléatoire discrète X prenant n valeurs ou sorties possibles 1... n associées au probabilités p1... pn est : La base du logarithme est juste une constante d'échelle. Pour avoir un résultat en bits, il faut utiliser le logarithme en base 2. Ainsi, une distribution a une entropie min d'au moins b bits si aucune sortie n'a une probabilité plus grande que 2-b. L'entropie min est toujours inférieure ou égale à l'entropie de Shannon; avec égalité si toutes les valeurs de X sont équiprobables.

Afficher plus

Séances de cours associées (64)

Entropie et compression de données: techniques de codage Huffman

Discute de l'entropie, de la compression des données et des techniques de codage Huffman, en mettant l'accent sur leurs applications pour optimiser les longueurs de mots de code et comprendre l'entropie conditionnelle.

Compression: Codes sans préfixe

Explique les codes sans préfixe pour une compression efficace des données et l'importance des codes décodables de manière unique.

Théorème de codage des sources

Explore le théorème de codage source, l'entropie, le codage Huffman et l'impact du conditionnement sur la réduction de l'entropie.

Concepts d'entropie conditionnelle et de théorie de l'information

Discute de l'entropie conditionnelle et de son rôle dans la théorie de l'information et la compression des données.

Théorèmes de codage de source : modèles d'entropie et de source

Couvre les théorèmes de codage de source, l'entropie et divers modèles de source dans la théorie de l'information.

Afficher plus

Concepts associés (31)

Entropie croisée

Entropie conjointe

Compression de données

Entropie de Rényi

Entropie min

Afficher plus