Source, Entropie et Débit

Dans un processus d’automatisation, une source génère de façon indépendante quatre niveaux de tension : x1=1 V, x2=2 V, x3=3 V, x4=4 V. La durée du niveau x1 est t1=1ms, celle du niveau x2 est t2=0,5 ms, celle du niveau x3 est t3=0,1 ms et enfin, celle du niveau x4 est t4=1 ms. Les niveaux ci-dessus sont générés avec les probabilités suivantes : , , , a) Après une succession de 10 symboles, la source se met au repos (émet le niveau 0) pendant 15 ms. Quel est le débit d’information de cette source ? Exercice n° 1.2 Un signal vidéo est transmis au travers un filtre idéal passe-bas ayant la fréquence de coupure de 5 MHz, après quoi il est échantillonné à la fréquence de Nyquist (2xFc=10 MHz). Les échantillons sont quantifiés uniformément par un dispositif de quantification uniforme possédant 256 niveaux et codés sur 8 bits. a ) Calculez le débit de la source vidéo ainsi numérisée ? Exercice n° 1.3 Une image de télévision noir et blanc est décomposée en 625 lignes horizontales et chaque ligne est décomposée à son tour en 625 points dont les intensités lumineuses correspondent à la source représentée. Ces intensités sont uniformément quantifiée par 256 niveaux de probabilité égale.

On considère que les luminosités de tous les points sont indépendantes et que 25 images indépendantes sont transmises par seconde. a ) Calculez le débit de cette source d’images ? Exercice n° 1.4 (Hors programme !) Soit une source de Markov à deux symboles x1 et x2 ayant le graphe de transition représenté ci dessous. Les probabilités initiales des deux états sont égales. Déterminer les probabilités avec lesquelles la source va générer les symboles x1 et x2 après 4 coups d’horloge. b) Montrez comment faut-il modifier les probabilités de transition p21 et p22 pour que la source devienne stationnaire. c) Calculez l’entropie de la source stationnaire. d) Quelles sont les conditions sur pij pour que l’entropie soit maximale ?L’erreur moyenne H(Y/X) a une expression simple, que l’on déterminera, en employant la fonction entropie binaire notée H2. b) Calculer l’entropie H(Y) et en déduire une expression de l’information mutuelle moyenne I(X;Y) en fonction de q, de u et de H2. c) Sachant que la transformation est une fonction convexe, pour quelle valeur u0 de u atteint-on la capacité ? Donner la valeur numérique de u0 pour q=½ et la valeur de la capacité du canal ? d) Vers quelle limite la probabilité u0 (pour laquelle la capacité est atteinte) tend-elle lorsque q tend vers 1 ? Commentaires.

Code irréductible Soient deux codes A et B qui ont respectivement la constitution suivante : Le code A est constitué de 2 mots de longueur 1, 1 mot de longueur 2, 2 mots de longueur 3, 4 mots de longueur 4 et un mot de longueur 5. Le code B est constitué de 2 mots de longueur 1, 2 mots de longueur 2, 2 mots de longueur 3, 3 mots de longueur 4 et un mot de longueur 5. Les deux codes ont un alphabet constitué de 3 symboles {0,1,2}. a) Lequel de ces deux codes est irréductible ? b) Construire le code irréductible. Exercice n° 3.2 : Codage optimal Une source S génère 7 symboles si avec les probabilités suivantes : p(s1)=1/3, p(s2)=1/3, p(s3)=1/9, p(s4)=1/9, p(s5)=1/27, p(s6)=1/27, p(s7)=1/27. a) Construire un code optimal ayant l’alphabet X={A,B,C} et calculer son efficacité. b) Construire un code binaire optimal et calculer son efficacité et sa redondance. Exercice n° 3.3 : Codage de source Qaire Une source binaire S1 génère les symboles s1 et s2 avec les probabilités p(s1)=0,9 et p(s2)=0,1. Les deux symboles sont indépendants. a) Calculer l’entropie de la source S1 puis celle des sources S2 et S3 respectivement constituées de n=2 puis n=3 symboles de la source S1.

Calculer les codes de Huffman associés à S1, S2, S3 ainsi que leur efficacité et la longueur moyenne des mots-codes. Conclusion. Exercice n° 3.4 : Efficacité Une source S génère de manière indépendante 6 symboles si avec les probabilités suivantes : p(s1)=0.40, p(s2)=??, p(s3)=0.25, p(s4)=??, p(s5)=0.15, p(s6)=0.1. a) Quelles sont les valeurs des probabilités p(s2) et p(s4) qui permettront d’avoir le codeur binaire d’Huffman le plus efficace ?Code Huffman ternaire Une source S génère 6 symboles si avec les probabilités suivantes : p(s1)=0.30, p(s2)=0.25, p(s3)=0.20, p(s4)=0.10, p(s5)=0.10, p(s6)=0.05. a) Coder par Huffman les symboles de cette source par des mots composés avec un alphabet à D=3 lettres X={0,1,2}. Calculer l’efficacité de ce code. b) Même question avec un alphabet binaire. Note : Pour le codage de Huffman à D symboles, il faut prendre en considération qu’après le premier groupement, on obtient une source à N-D+1=N-(D-1) symboles, et qu’après n groupements, on obtient une source à N-n(D-1) symboles. Afin de pouvoir effectuer le codage, la dernière source doit avoir D éléments, donc D=N-n(D-1), d’où il s’ensuit : n = (N-D)/(D-1) et si n ainsi obtenu n’était pas un nombre entier, on accroîtra N par l’introduction de symboles fictifs de probabilité nulle.