Site des Oraux

Théorie de codage et de l'information 2005 (8) :: post
Années :: 2004 :: 2006 :: 2007 :: Toutes

Post nº8 (id1573) envoyé par Nicolas  le 11 Sep 2005, 15:18
Grosse question (2/3 exam): AEP
Il est important de savoir dans le détail ce qu'est une séquence typique. Une définition ne lui suffit pas. Il faut bien dire que ce sont des séquences qui ont chacune une probabilité d'apparition faible, mais la probabilité cumulée pour toutes les séquences est élevée. La séquence la plus probable n'est pas une séquence typique.
Puis vient le théorème de l'AEP. Il sert à compresser les données. Etant donné que je n'ai pas réussi à bien répondre, j'ai dévié sur Shannon. Mais cela me semble intéressant de le mettre ici malgré tout. Les données d'une source, une fois codées de manière optimale, se ressemblent et se comportent comme des séquences de variables iid. Cela est utile parce que l'AEP s'applique justement à ces variables et dit que la longueur moyenne des mots-codes peut être arbitrairement proche de l'entropie. De là, on peut faire le parallèle avec Shannon: L(C) >= H(X). On a fait un petit tour du chapitre en vitesse, puis il m'a demandé: "si on ne connait pas la distribution, que peut-on dire de L(C)?" Si on ne connait la distribution, on peut dire adieu à Huffman et compagnie. Il reste néanmoins les codes universels (Lempel-Ziv, ...) pour qui, lorsque n tend vers l'infini, la longeur des mots-codes se rapproche aussi de H(X). Le théorème de Shannon est donc une condition universelle, bien qu'énoncée pour des variables iid.

Question subsidiaire (1/3 exam): Hamming
J'ai du écrire un exemple. Cela veut dire écrire la matrice, choisir des valeurs pour les bits d'info (on y est obligé parce que le système est indéterminé) et trouver un mots-codes. Expliquer qu'on teste la parité d'un sous-ensemble de bits, que l'on doit choisir r bits d'info où r est le rang de la matrice, que la distance et le poids sont deux choses identiques (car le code est linéaire: la somme de deux mots-codes est un mot-code). Il est plus rapide de calculer le poids minimum des mots codes que de calculer la distance entre chaque paire de mots-codes.

Post nº7 (id1569) envoyé par No one is the best  le 08 Sep 2005, 16:49
Alors hier, j'ai eu droit à :

Code instantanté,
Inégalité de Kraft,
Code de Hamming,
Borne de singleton

Je n'ai pas hésité à remettre tout ce qu'il y avait à propos de cela dans le cours mais il est rentré un peu trop vite... je n'ai pas eu le temps de mettre des choses concernant la borne de singleton. ( il ne m'a laissé que 25 min... alors qu'au premier il a laissé 1h... ) Enfin soit, il m'a dit que ce serait suffisant. => Pas de stress. Le post de Mimi est assez bien fait, je ne remets pas ce qu'elle a marqué.

Post nº6 (id1568) envoyé par Shere Khan  le 07 Sep 2005, 23:04

Voilà, j'ai passé Cerf ce matin, et j'ai eu comme questions:
Code correcteur d'erreur:
- Principe;
- Encodeur (juste dire que ca rajoute de la redondance);
- Décodeur (+ décodeur idéal)
- Borne de Hamming
- Canal Binaire à Effacement

Voilà, y a pas vraiment grand choses à raconter si ce n'est qu'il est très sympa, les questions se suivent exactement comme dans le cours (du genre "et donc maintenant, forcément, je dois vous parler du point suivant"), il aide si jamais, (moi il m'a aidé deux fois et après il m'a dit que c'était très bon,...) donc voilà!

Bonne merde aux suivants...

Post nº5 (id1566) envoyé par Smoon  le 07 Sep 2005, 11:28
Voila moi j'ai eu:

Capa op et inf: quelle sont les différences (dans l'un on tient compte les prob erreur pas dans l'autre) + faire un lien avec 2e théoreme Shannon.
Bien souvent quand on lui Donne C=max I(X:Y) il demande re redéfinir I(X:Y)et meme de donner un lien avec la distance de Kullback (I(X:Y)=D(p(x,y)|| p(X).p(y))il aime bien le diagramme de Venn.

Puis, parler-moi de la capacité du CBS: les petites question qu'il pose c'est pourquoi c'est symétrique par rapport a 1/2, il faut lui répondre que si la prob d'inversion est de 95%, il suffit d'inverser tout les bits a la sortie du canal pour retrouver un prob d'inversion de 5%.

Et enfin, Code Huffman (principe et construction): Il faut bien lui dire que c'est un code instantané Optimal (dans le cas du binaire en tout cas) et qu'il permet un codage de source pour comprimer des données.
puis le petit exemple binaire qu'il a donner au cours, comparer L avec H on voit que L>H ce qui est conforme au Théoreme du codage. puis il va surrement vous demander s'il existe une borne supérieur et il faut lui dire Oui, H+1...Et il m'a demander comment réduire cette borne supérieure, il faut lui parler du second Théorème de Shannon avec le H+1/n et le codage par bloc. Il demande ensuite comment coder le codage par bloc avec Huffman.
La je savais pas lui répondre (enfin si mais il a pas compris ce que je voulais dire;-))il faut lui dire qu'au lieu d'avoir des a, b, c, d, e, on code un bloc de symbole: aaa, bbb, ccc, ddd, eee . Moi je lui ai parlé de Kraft et apparemment ca lui a plus.

Voila en effet il est très sympa, mais le probleme a ca c'est qu'on sait vraiment pas ce qu'il pense de votre prestation (moi il ne ma RIEN dit, a part bonnes vacances). Aussi il faut savoir qu'en général on a plus qu'une demi-heure pour tout écrire (contrairement a ce qu'il dit) moi j'ai eu une petite heure. Donc ne stressez pas.


Post nº4 (id1562) envoyé par Margot  le 06 Sep 2005, 18:43
Questions: But des codes corecteurs d'erreurs, décodeur idéal, lien entre distance minimale et nombre d'erreur, Borne de Hamming. Et rien a voir, code de Huffman à l'aide d'un exemple.
Rien de spécial à dire, sauf que de temps en temps, il demande une tite illustration de codes (codes à répétition, code avec 1bit de parité).

Voili voilou
Margot

Post nº3 (id1559) envoyé par Mimi  le 05 Sep 2005, 19:38
Alors cette apres midi, il m’a demande :
- Definition capacite informationnelle et operationnelle, la difference entre les deux et le rapport avec le 2eme th. De Shannon
- CBS (details des calculs)
- CBE
- Borne de singleton (demo + application, a quoi ca sert etc)

La difference entre la capacite informationnelle et operationnelle, c’est qu’en gros on ne tient pas compte de la probabilite d’erreur pour l’operationnelle. Il m’a demande d’expliquer I(X :Y) ce que j’ai fait avec le diagramme de Venn. Il m’a demande d’exprimer I(X :Y) en faisant la relation avec la distance de Kullback. Je ne voyais pas trop et il m’a mis sur la voix en me faisant dire que I(X :Y) est nulle qd X et Y sont independants => p(x,y)=p(x).p(y) Pour finalement : I(X :Y) s’exprime en termes de proba –Somme(x) Somme(y) p(x ;y) log [p(x).p(y)]/p(x ,y) => D(p(x,y)||p(x).p(y))
Pour le second theoreme de Shannon, c’est Cinfo=Coper. Je devais lui dire que c’etait parce que la proba d’erreur tendait vers 0 parce qu’on faisait tendre n (la longueur du mot code) vers l’infini (je lui ai fait le diagramme Pe en fonction de R en prime)

Pour le CBS, il pose un peu tout, mais celle ou j’ai eu un peu de mal a repondre c’est qd il m’a demande pourquoi j’avais pris ½ pour P(y=0) et P(y=1). Il faut lui repondre ca : on prend max I(X :Y) et donc le max H(Y), qui est 1 et forcement qd on remplace ds la definition par ½ l’entropie de Y, on trouve bien 1. Il faut une distribution UNIFORME donc ! Il m’a demande aussi pourquoi sur le graphique de C en fonction de p, apres ½ ca remonte ?? Si on prend en p=1 par exemple, tous les bits sont inverses, ca ne nous pose aucun probleme vu qu’on sait que la proba des bits inversee est max et donc il ne faut qu’inverser la sortie pour ravoir les bonnes sequences. La transmission dans le canal est aussi bien que pour p=0 et donc on a bien une symetrie par rapport a 1/2.Je sais pas si c’est clair, mais bon ne vous inquietez pas qd il voit que vous avez du mal a vous exprimer, il vous aide oufff !!!

Pour le CBE, il faut preciser qu’on a une sortie ternaire et qu’on a pas une distribution equiprobable pour le calcul de H(Y). Je lui ai parle de l’axiome de groupement pour le calcul de H(Y) et ca lui a fait plaisir :-) Il m’a demande graphiquement comment on voyait que CBE et mieux que CBS. Ca c’est en lui expliquant que si alpha vaut 1 => aucun bit n’est transmis ( efface) et donc on sait quel bit n’a pas ete transmis tandis que dans CBS comme c’est tres aleatoire, le bit n’est pas forcement bien transmis (inverse). Je lui ai explique aussi le feedback et il m’a demande si la capacite CBE et feedback etaient tjrs egaux ? Non car c’est seulemnt parce qu’il n’y a pas de memoire, mais il y a qd meme bcp d’applications de canaux sans memoire. En quoi une memoire est avantageuse ?? Elle retient chaque mirco seconde le bit qui a ete transmis ou efface. Puis j’ai du lui donner la formule : p(yk| xk) = produit p(yk|xk) car les proba sont independantes. (k en indice en haut pour les termes a gauche du « egal » et en bas pour les termes a droite du « egal »)

Pour la borne de singleton, je lui ai ecrit tout ce qu’il y avait dans le cours et je lui ai dit direct que j’avais pas trop compris, mais je lui ai explique tout ce que j’avais compris. Il m’a explique ce qui etait pas tres clair. Pour n-e’>=k, il faut lui expliquer que les bits non effaces doivent forcement contenir au moins toute l’info pour etre transmis sinon ca sert a rien ! Donc ils doivent etre forcement superieur ou egal au nombre de bit d’info donc k ! J’ai du lui explique la saturation de d par le code Reed Solomon : utilise par la NASA car la distance etant maximum, on peut corriger au mieux les erreurs ou les effacements.
Si j'ai bien compris la borne de singleton sert a corriger efficacement des mots codes en imposant une condition sur la distance.

Voila je crois que c’est tout, il m’a dit que c’etait tres bien, mais m’a pas dit de cote :( En tout cas, quand je calais il me mettait sur la voie et il explique vrmt tout pour que vous compreniez bien.
Bon courage pour la suite et BONNES VACANCES a TOUS apres !!!!

Post nº2 (id1557) envoyé par Olivier  le 05 Sep 2005, 16:42
J'ai eu tout sur le chapitre 4: la compression de données.

Question 1: qu'est ce qu'un code source? a quoi ca sert (=> canal, longueur moyenne etc). Sous-question: qu'est ce qu'un code instantané? à quoi ca sert? (=> utile car on peut le décoder en un seul passage).

Question 2: Inégalité de Kraft: démontrer (sur la base de l'arbre de décodage).

Question 3: Les codes instantanés optimaux. Trouver les li qui minimisent la longueur moyenne du code => multiplicateurs de Lagrange etc...Application au code de Shannon => démontrer H < L < H + 1 et la même inégalité pour le codage par blocs.

Question 4: expliquer le code de Huffmann sur base d'un exemple (très court, il demande que le binaire).


En résumé, il faut tout comprendre en détail (on s'y attend un peu vu que les notes sont autorisées). Mais les questions sont vraiment faciles (enfin j'ai eu un chapitre facile aussi ^^).
Il n'y a aucune raison de stresser, le prof est très sympa (même s'il ne donne pas la cote :P).
Voilà je pense que j'ai tout dit, GL et (HF) all :P.

Post nº1 (id1555) envoyé par aymeric  le 05 Sep 2005, 11:51
CCE:
- Principe
- Décodeur idéal (+demo Bayes)
- Différence entre poids min & distance minimale
- Distance minimum (+démo avec sphères)
- Borne de Hamming (+démo)
- Code de Hamming (+exemple)
Ca se sont les question qu'il m'a demande de preparer
Pis apres lors de l'oral a proprement parlé, il a suivi l'ordre du cours et m'a posé des questions sur tout ce qu'il y a dans le cours.


oraux.pnzone.net - infos - 1ms