TD - Creatis

Source, Entropie et Débit Exercice n° 1.1
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 :
[pic], [pic], [pic], [pic]
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.
[pic]
a) 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 ? Transinformation et capacité Exercice n° 2.1 : un peu de calcul
Calculez l'équivoque H(X/Y) et l'erreur moyenne H(Y/X) en supposant que
l'on connaisse la matrice des probabilités conjointe du système [P(X,Y)] :
[pic]
Exercice n° 2.2 : Canal binaire symétrique
Le schéma suivant représente la forme générale d'un canal binaire
symétrique et permet d'obtenir la matrice de bruit [P(Y/X)].
[pic] a) Calculez la capacité C de ce canal. Que remarquez vous ?
b) Représentez la courbe C=f(p). Commentez les points d'intérêt.
c) Pour quelles valleurs de p(x) et de p(y) la transinformation est elle
maximale ?
d) Application numérique Avec la matrice de bruit suivante :
[pic] et [pic] Calculez :
- l'entropie du champ à l'entrée du canal
- l'entropie du champ à la sortie du canal
- l'entropie conjointe
- l'erreur moyenne et l'équivoque
- la transinformation
- la capacité du canal
- la redondance et l'efficacité de ce canal.
- Comment faut il modifier P[X] pour utiliser au mieux le canal. Exercice n° 2.3
Deux canaux binaires symétriques, ayant la même capacité C sont reliés en
cascade.
[pic]
a) Quel est la valeur de la capacité résultante ? c) Calculez la capacité d'un seul canal et celle du canal résultant pour
p=0,1. Exercice n° 2.4 : Canal en Z
On donne le canal en Z représenté ci-dessous. On note u=Pr(X=0)
[pic]
a) 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 transinformation 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. Codage de source Exercice n° 3.1 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. b) 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 ? b) Quelle est cette efficacité ? Exercice n° 3.5 : Codage LZW d'une source binaire
Une source binaire S génère de manière indépendante 2 symboles '0' et '1'.
Voici un début de message émis par cette source et qui est codé par un
codeur LZW.
01000100100101101010100101010100100 ..... a) Donnez les 10 premiers mots du dictionnaire de ce codeur et proposez un
codage des mots du dictionnaire. b) Donnez alors le code de ce message. Exercice n° 3.6 : 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. Codage de Canal Exercice n° 4.1 : Code de Hamming
Soient la source S qui émet les cinq symboles suivants et leur code associé
: |Si |Ci |
|A |000|
|B |001|
|C |010|
|F |011|
|E |100|
a) Détermine les codes associés à chaque lettre lorsque l'on met en ?uvre
un codeur de Hamming systématique.
b) Donnez l'expression des correcteurs.
c) Quelle est la distance minimale de ce code ?
d) Quel est son taux d'émission R = (Nbre de symboles d'info) / (longueur
de mot-code) ?
e) On désire en plus de la correction d'une erreur, détecter toutes les
erreurs affectant un nombre impair de bits. Proposez une solution et les
mots-codes associés. Quel sont le nouveau taux d'émission et la distance
minimale de ce nouveau code ?
f) Commentez les différents scénarios possibles au décodage. Exercice n° 4.2 : Code cyclique
Le '(n-k) stage shift register encoding circuit' est un circuit de codage
par division utilisé dans les satellites pour son faible coût de mise en
?uvre. Un schéma général de ce type de circuit est donné ci-dessous.
[pic] Durant l'introduction des k symboles d'information, la porte P1 reste
ouverte et le circuit calcule le reste de la division qui apparaît au coup
d'horloge k+1, lorsque la porte P2 est ouverte tandis que la porte P1 est
fermée. La porte P2 reste ouverte durant m coups d'horloge pour permettre
d'évacuer le registre, plus exactement les symboles de contrôle. Ces
derniers sont placés, par le truchement de la porte P3, à la suite des
symboles d'information pour former un mot-code systématique. Soit un codeur à circuit de division par le polynôme g(x)=x3+x2+1 avec n=7,
conformément au schéma précédant :
a) Tracer le schéma particulier pour le cas étudié.
b) Trouver au moyen de ce schéma , les valeurs des symboles de contrôle a0,
a1 et a2 en fonction des symboles d'information a3, a4, a5 et a6. (a6 étant
le symbole d'information qui entre au premier top d'horloge) c) Soit le mot d'information I=[1 0 0 1], donner le mot-code obtenu avec
g(x)=x3+x2+1 par codage par division.
d) En utilisant un codage par division, donnant les expressions générales
liants caractères de contrôle et d'information. e) Même question que c) en effectuant un codage par multiplication.
Remarques par rapport au mot obtenu en c) ? f) Avec le même polynôme g(x), pour un codage par multiplication, donnez
l'expression générale