Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Td10 reponses Probabilités ?? TD n ? Entropie de Shannon et codage Exercice Entropie de Shannon et codage Soit A D un alphabet et M x xk un ensemble d ? objets appelés messages Un codage est une application de M dans A ? qui à un message xi associe son co

Probabilités ?? TD n ? Entropie de Shannon et codage Exercice Entropie de Shannon et codage Soit A D un alphabet et M x xk un ensemble d ? objets appelés messages Un codage est une application de M dans A ? qui à un message xi associe son code ci de longueur li Un codage est dit pré ?xe s ? il ne contient pas deux mots dont l ? un est pré ?xe de l ? autre Inégalité de Kraft Montrer que si le codage h est pré ?xe alors k D ??li i Supposons l ? inégalité précédente satisfaite Montrer que pour tout alphabet A de D lettres et tout ensemble de k messages il existe un codage h pré ?xe et dont les codes sont de longueurs li Borne de Shannon sur la longueur moyenne d ? un code pré ?xe Supposons maintenant que les messages proviennent d ? une source aléatoire le message xi ayant la probabilité pi La longueur moyenne de codage est alors dé ?nie par k L h pili i Soit Linf la plus petite de ces longueurs pour un code pré ?xe Nous allons estimer Linf Shannon dé ?nit l ? entropie d ? un événement comme la quantité de surprise ?? log pi qu ? aurait un observateur lorsqu ? il découvre la réalisation de cet événement Plus cet événement est improbable plus l ? observateur sera surpris Si on fait la moyenne sur tous les événements possibles on obtiendra l ? entropie du système k HD p ?? pi logD pi i C ? est la quantité d ? information relative à la distribution p p pk Montrer que H Linf H Solution a a On peut représenter un codage pré ?xe sur un alphabet à D lettres par un arbre D- bc aire pas nécessairement complet L ? ensemble de mots est l ? ensemble des étiquettes d ? un chemin de la racine à une feuille À chaque feuille correspond donc un mot du c code Les profondeurs des feuilles sont les longueurs des codes a b bb a bc baa bab bac On montre par induction sur un tel arbre que l ? inégalité de Kraft est véri ?ée ?? le cas de base une feuille est trivial kj ?? Considérons un arbre ?ni o? l ? inégalité est véri ?ée pour les ?ls de la racine ??j D ??li j k Dans l ? arbre de départ les profondeurs sont augmentées de D ??li j ?? i j i D D j Pour établir la réciproque soit L max i et considérons un arbre D- aire complet de profondeur L On prend les i un i par et pour chacun ?? on choisit arbitrairement un n ?ud à profondeur i et le mot étiquetant le chemin de la racine à ce n ?ud ?? on supprime tous les ?ls de ce n ?ud ce qui supprime une proportion D ?? i des n ?uds de