Publier

INFO-H-300 Information and coding theory

< Retour

INFO-H-300 - 18 Aug 2010

Coucou
Les questions avant que je raconte ma vie ^^:
1) Cin et Cop , définition illustration etc.
2) Application caculer Cin d'un Canal binaire à effacement CBE
3) Exemple, explication , construction , utilisation du code de Hamming
Bon alors je suis passé Mardi soir on va dire car suis passé en dernier , quand je suis sorti il était un truc du genre 7h20 Oo.
Déjà faites gaffe à une chose , si vous passez en dernier vous avez pas mal de chance d'avoir réellement la grosse demi heure qu'il annonce et pas l'heure que l'on a quand on passe en 1ier. Et entre 30 et 60 minutes il y a ... bah çà fait une différence donc trainé pas. Il est venu m'interroger avant que j'ai fini de tout rédiger. Mais il en tient compte donc tout va bien ^^.
1) Cin et Cop
Vous vous en doutez , ne pas se limiter à la formule .
On commence par expliquer le contexte , à quoi se rapporte la capacité, le cheminement de l'information, la nécessité de coder l'information avant de l'introduire dans le canal tout çà . Ensuite,
Faut bien expliquer ce que çà veut dire Cin et Cop dans leur termes respectif . Donc Cin en terme d'information et Cop en terme opérationnel. Oubliez pas les unités , c'est pas les mêmes.
Enchainez sur le 2nd théorème de Shannon, donc l'énoncé et expliquer comment on peut en arriver à dire que Cin =Cop. Donc là, examinez bien la démo et les explications entourant le 2nd théorème de Shannon, çà n'apparait pas texto dans le cours , mais y a de gros clin d'oeil dans la démo du Shannon 2. Construiser votre réponse et ses hypothèses sans dire trop de connerie, il est préférable qu'il vous demande une hypothèse que vous n'avez pas mentionnée plutôt que de lâcher une hypothèse complètement fausse.
2) Calcul Cin sur un CBE .
BIEN poser le problème !! Donc Schéma arbre de probabilité , le schéma avec des flèches reliant les entrées et les sorties avec les probabilité sur les flèches ( le truc des flèches et l'arbre binaire c'est pas la même chose !!!, j'avais tracé que l'arbre et j'ai mis quelques seconde pour comprendre qu'il me demandais l'autre schéma également ).
Une fois le problème bien poser que vous avez bien fait comprendre que vous avez compris ce qu'il se passe dans le problème du CBE, le calcul , il est dans le cours ,rien de D'GRIIIISS !!!! euh..., de sorcier je veux dire ^^.
Une fois le jolie 1-alpha établit, l'interpréter. La seul source d'inéficassité du canal provient de l'effacement. L'évènement " effacement" ne transmet aucune information. Et là il faut évoquer comment on pourrait savoir en pratique qu'un symbole s'est fait effacer, donc le canal avec feedback, on renvoit à la source les symboles qui passent pour vérifier. Là pas besoin de faire le calcul, on peut dire qu'on peut monter que la Cin est la même avec ou sans feedback , on pouvait s'y attendre, expliquer pourquoi ? Entre autre , le canal n'a pas de mémoire donc çà ne change absolument rien pour lui qu'on essaie de lui refaire passer un symbole juste parce qu'il s'est fait effacer à l'essai précédent. Le canal ne change pas de comportement , on lui met juste plus de chose à passer. Donc Cin est la même.
3) Code de Hamming ,
Pas de secret , prenez un exemple que vous connaissez bien , soit du cours , soir des tps.
Expliquer le principe, et utilisation. Avec toujours l'exemple en filigrane. Matrice de Hamming, définition, caractéristique, bit parité et info, calcul des mots codes ( faites pas tous les w , vous en fait 1 , vous résolvez le système d'équation , et vous dites comment on calcul les suivant ) , distance minimal de Hamming , définition interprétation ,utilisation .
Le décodage , la détection d'erreur , nombre d'erreur détectable et corrigeable ou juste détectable, pourquoi ? Sphère de Hamming tout çà.
Comment connaitre e juste en un coup d'oeil sur la matrice H . 2e colonnes linéairement indépendantes.
Si 2 colonnes identiques c'est rapé e = 0.
Tout le chapitre quoi.
Il est TRES patient ! Je compte pas les fois ou j'ai parlé 20 secondes pour décrire un mot qui voulait pas sortir et au final il me le souffle^^ , notement pour "canal à mémoire", le mot voulais pas franchir mes lèvres , j'ai parlé bien 30 seconde à dire ce que çà voulait dire dans pouvoir dire " mémoire " .
Comme d'hab, il ne donne pas la note, mais vous fait comprendre que çà à bien été. Vous demande si Thermo c'est bien passé, les gros cours qu'il vous reste.
C'est effectivement l'oral le plus agréable que j'ai passé de ma vie. Même si j'étais à jeun , qu'il était 7 h du soir et que je suis vraiment pas drillé à écrire à la craie sur un tableau.
Alors imaginer comment çà peut être agréable en situation normale ^^.
May the Force be with you !
Paul

INFO-H-300 - 18 Aug 2010

Salut !
Alors moi j'ai eu :
- Equipartition Asymptotique (définition et explications)
- Ensemble typique
- Compression
- Huffman par un exemple et expliquer... + s'il est optimal, etc etc...
Il souhaite qu'on ait compris la matière et pas le fait de la retenir.
Sinon le prof est vraiment cool et relax !
BOn courage !

INFO-H-300 - 18 Aug 2010

Salut,
J'ai passé l'examen oral ce matin. Il m'a demandé 3 questions :
1°/ AEP + séquences typiques + propriétés (en démontrer une seule)
2°/ Démonstration pour la compression des données
3°/ Donner exemple de code de Huffman
J'ai eu un peu moins d'une heure pour préparer au tableau (y a 3) les questions avec toutes mes notes :
1°/ J'ai donné l'énoncé du théorème AEP et la définition des séquences et ensembles typiques. Il m'a demandé d'où venait l'expression de l'AEP --> il faut appliquer la loi des grands nombres à l'expression de l'incertitude (comme dans les notes de JVC). J'ai énoncé les 3 propriétés et démontrer la deuxième (la taille de l'ensemble typique est bornée supérieurement) --> comme j'ai expliqué chaque étape de la démo, il n'a pas fait de remarques particulières. Enfin, en faisant tendre n vers l'infini et epsilon vers 0, on montre que la probabilité que concentre les séquences typiques est arbitrairement proche de 1 et sur un intervalle de séquences arbitrairemnt proche de 2^(nH). J'ai fait le petit schéma avec chaque sous-ensemble, il m'a demandé d'un peu expliqué --> un nombre restreint de séquences par rapport à l'ensemble des séquences possibles concentre toute la probabilité. Il m'a demandé s'il existe une distribution pour laquelle les séquences typiques ne permettent pas la compression : c'est la distribution uniforme pour laquelle toutes les séquences sont typiques, j'ai dû le montrer à partir d'un petit calcul de l'entropie pour une telle source et la comparé avec l'expression de la taille de l'ensemble typique et de l'ensemble des séquences possibles qui sont alors égales.
2°/ J'ai retapé toute la démo comme dans les notes. Il m'a demandé comment on obtient un majorant pour la longueur des mots-code pour coder les séquences typiques et atypiques. Il m'a demandé pourquoi on a rajouté 2 bits supplémentaires --> 1 bit de "flag" pour différencier le cas typique et atypique, et 1 bit pour avoir un nombre entier (passage à la puissance de 2 supérieur). Une fois la démo terminée, il m'a demandé est-ce que l'entropie est un minorant de la taille moyenne des longueurs des mots-code. J'ai dit oui, mais j'ai pas su l'expliquer. Il fallait en fait parler du 1e théorème de Shannon.
3°/ J'ai donné un exemple de code de Huffman comme dans les notes. Il m'a d'abord demandé que fait ce conde --> il fait de la compression. J'ai expliqué ce que j'ai mis au tableau. Il m'a demandé si le code était instantané, optimal et m'a demandé de parler de l'inégalité de Kraft. Celle-ci doit être respectée pour qu'il soit instantané et même saturée pour être optimale. J'ai donc fait le petit calcul à partir des résultats de l'exemple que j'ai donné pour le montrer. Il m'a ensuite expliqué qu'une propriété de ce code est que les 2 derniers mots-code de l'arbre ont la même taille et ne diffère que par un bit. Il m'a demandé en quoi est-ce fondamentale --> si on ajoute un bit à l'un deux, le code n'est plus optimal car le précédent avait en moyenne une longueur des mots-code plus petits. Si on enlève un bit, le code n'est plus instantané car le mot-code devient préfixe d'un autre. Il m'a demandé quand on rajoute un bit si le code continue d'être instantané --> oui.
Voilà, il est très sympa, quand on est approximatif, il donne des explications plus précise pour qu'on comprenne bien. Certaines sous-questions reviennent presque toujours mais il en pose d'autres pour s'assurer que vous aillez compris. Pour étudier ce cours, je vous conseille de le lire au moins une fois entièrement, de bosser à fond toutes les questions qui se trouvent sur IR2008 et de bien comprendre les démos sans les étudier par coeur puisqu'on a largement le temps des les écrire au tableau.
Bonne chance.

INFO-H-300 - 26 Aug 2009

Codage de source : Principe général + explication des codes instantanés et parler de leurs bornes inférieures.
Code de Huffman : Expliquer le principe sur un exemple
Bon alors c'est pas très compliqué, comme prévu, il dit qu'on a 1/2h de préparation et finalement c'est 1h ..
et effectivement, au bout de 40 min, on commence un peu à tourner en rond. Donc bien noter au tableau toute la partie du cours correspondante. Et se préparer aux questions. J'ai eu droit pour la premiere partie, entre autre ..
* Comment reconnaitre un code DFU ? (Il faut dire qu'on peut pas vrmt les repérer direct mais qu'il faut analyser toute une séquence de mots code et de regarder la parité des suites de 1 ou de 0 et de les comparer avec le codage des mots..
* Expliquer en quoi l'inégalité de Kraft traduit l'encombrement de l'arbre du codage. (Prendre un exemple et expliquer que les termes de la somme (de l'inégalité de K) vont représenter la partie de l'arbre non utilisé (ex. pour un mot code de longueur li=1 codé en binaire, ce sera 1/2, donc la moitié de l'arbre restera vide..)
Ensuite pour le code de Huffman, j'ai pris un exercice dans un des tps. Bien expliquer l'algorithme de construction et dire comment on trouve le codage (en parcourant l'arbre à partir de la droite..) Bien dire que le codage est optimal.. alors bien sur, il va direct vous demander, pourquoi ? qu'est ce qui permet de dire ca ? Il faut alors considérer les deux mots codé les plus long, remarquer qu'ils ont la meme longueur et ne diffèrent que d'un bit (et que c'est pour ca que le code est optimal) Raisonner alors par l'absurde, dire que si l'on ajoute un bit de code à l'un des deux, un code moins lourd existe (le précédent!) donc c'est pas optimal.. inversement, si on veut retirer un bit, on se retrouve avec de forts risques que le code ne soit plus instantané (principe du préfixe n'est plus respecté).
Voilà, j'ai pas tout mentionné mais il pose pas mal de questions même sur des parties du cours qui peuvent paraître simple. Donc bien maîtriser les notions et insister sur les liens entre les parties et une compréhension de fond du cours.
Pour finir le prof est vrmt sympathique, donc il n'y a vrmt pas lieu de stresser. Il explique qd on bloque et reformule souvent qd on ne saisit pas ses questions. Il ne donne pas les cotes.
Bon courage aux suivants.

INFO-H-300 - 25 Aug 2009

salut.
1 et 2 :Capacité d'un canal : op et inf
a l'aide du second th. de shannon expliquer pourquoi elles sont égales. réciproque forte et petit graphique cf cours (pas démontrer : comprendre le résultat)
démo pour le CBE : tout taper , résultat : (1-a) comprendre et expliquer pourquoi on pouvait s'y attendre
il m'a posé des questions sur l'entropie mutuel, l'entropie H(a) dans la démo etc ... (pour être sur qu'on sache de quoi on parle)
3 : code de hamming. principe ( n m k t etc...)
exemple
différente question sur la distance, le vecteur syndrome, les erreurs qu'on peut corrigé ou/et détecté et a peu près tout ce qui a a dire la dessus.
prof toujours aussi sympa, pas de stress de ce coté la.
il m'a posé d'autre sous question dont je me rappelle plus ...
à ouai le temps : il dit 30 minutes j'ai eu droit aux 90 minutes de la solitude en passant avant dernier :/
on pourrait penser que c'est cool mais au bout d'1/2 h on se surprend à balancer des craies par la fenêtre et a faire des avions de papier.... (éviter de passer près des fenêtre du A coté square G)

INFO-H-300 - 24 Aug 2009

Bonjour,
Alors, le prof arrive 15 petites minutes en retard, fais entrer le premier étudiant. Environ 30min après, j'entre 2ème, dans une autre salle que le premier vu que je ne l'ai pas vu sortir entre-temps.
Il demande notre nom, et c'est lui qui choisi nos questions. Il m'annonce que j'ai une grosse demi-heure pour préparer avec mon cours, c'était finalement proche d'une heure.
Ce qu'il faut faire : recopier toute la partie du cours concernant vos questions. Pour moi 30 minutes aurait été un peu juste, mais en 1h j'ai eu le temps de tout recopier et de réfléchir plusieurs fois à ce que j'allais dire. (Il y avait une horloge au dessus du tableau, ça aide à se repérer.)
Il revient donc, et nous demande d'expliquer. Pour les questions, j'ai eu :
Tout le chapitre sur l'AEP. J'ai vraiment recopié toutes les demo.
J'ai bien entendu commencer par poser le problème, source qui envoie des séquences, n qui tend vers l'infini, variables aléatoires IID, etc.
Ensuite, je lui ai expliqué comment je passais d'une ligne à l'autre dans la demo, pour arriver au résultat final.
De là on tire la définition de séquence typique, et bien entendu l'explication de ce que c'est avec des mots. Il m'a demandé également d'illustrer par un exemple, n = 1000, p 0 = 900, p 1 = 100, comment sont les séquences typiques : séquences contenant 900 zéros et 100 uns. J'ai aussi dû parler à un moment du passage sur la binomiale, pour donner le nombre et la probabilité de ses séquences typiques je crois.
Ensuite les propriétés d'ensemble typique, j'avais recopié toutes les démo, il m'a fait en expliquer une seule (il a choisi au hasard celle qui dit que l'ensemble est borné supérieurement).
Ensuite, avec les propriétés, conclure que l'ensemble est très petit mais contient pratiquement toute la probabilité.
De là, enchainer sur la compression (c'est un peu le but de tout ça...), avec la dernière démo utilisant les résultats précédents, pour au final arriver à une longueur moyenne qui est plus petite que la longueur moyenne sans avoir fait tout ça, d'où compression.
Il m'a posé quelques questions intermédiaires et finales, genre énoncer le premier théorème de Shannon, savoir si on peut descendre sous l'entropie, dire dans quel cas la compression est impossible (séquence typique = toutes les séquences = source équiprobable), la probabilité de chacune séquence typique par rapport à une autre (elles sont équiprobables), ce qu'était le "x barre" que j'avais noté pour remplacer (x1, ..., xn), et encore d'autres petites questions dont les réponses sont évidentes dans le cours ou déjà précisées dans les questions des années précédentes. Aucune question surprise, pourtant je ne pouvais vraiment pas dire que je connaissais tout par coeur, donc il y a vraiment moyen.
Il est très sympa et comme déjà dit, ça suit naturellement le développement dans le cours, il n'y a pas vraiment de piège. Si il voit qu'on bloque un peu, il pose une question pour nous guider ou nous dit carrément ce qu'il veut entendre, il suffit de suivre ce que vous avez recopié.
Ce qui n'est pas compris ou formulé de manière pas claire dans votre explosé, il le reformule lui-même pendant l'examen pour être sûr que ce soit bien compris.
Ma deuxième question (il donne les deux en même temps au début; au cas où ça serait pas clair dans mon message) était un exemple de code de Huffman. Donc j'ai bêtement recopié l'exemple du cours pour D=2 avec a,b,c,d,e, avec les mêmes probabilités et tout.
Je lui explique comment marche le principe de construction, bien entendu il demande c'est quoi ce code en général (c'est le code instantané optimal). Il m'a interrogé sur les codes instantanés, savoir c'était quoi, et comment reconnaitre (pas de mot-code préfixe d'un autre).
Ensuite, dans mon arbre, je lui explique la suite de question oui/non. Il me pose la question de savoir si on rajoute une feuille tout au bout de la plus longue branche par exemple si 110 deviendrait 1101 (code n'est plus optimal car la longueur change - il m'a fait parlé juste avant ça de l'inégalité de kraft, énoncer et dire à quoi ça sert - et montrer que c'était =1 dans mon code de Huffman, d'où optimal justement), ou si on retire cette dernière branche donc 110 devient 11, et bien dans ce cas le code n'est plus instantané car 11 est préfixe de 111 (code d'une autre branche que j'avais).
Voilà, je pense que c'est à peut-être tout, en gros il faut tout recopier sur le chapitre donné et savoir à quoi correspond tout ce qu'on écrit, et connaitre les résultats du cours, et puis savoir répondre à toutes les petites questions comme ça qui sont dans le cours ou reprise dans tous les examens précédents.
Ça parait peut-être gros de dire "tout connaitre comme ça", mais après-coup ça m'a semblé plus simple qu'il n'y paraissait, je ne m'attendais pas a si bien réussir au vu de ce que j'avais préparé avant (en gros lire le cours et les questions ici, et essayer de comprendre un maximum, même sans jamais avoir été à un seul cours ou tp).
Comme déjà dit par tout le monde, il ne donne pas de note, mais il m'a clairement dit que j'avais compris et que c'était réussi. Puis au vu de mon oral, il m'a demandé comment ça se fait qu'en juin j'avais foiré autant que ça. 😛

INFO-H-300 - 24 Aug 2009

Yop yop, voici le résumé de l'examen oral de ce matin
Tout d'abord, l'attente: ne vous étonnez pas si vous ne voyez pas le prof arriver c'est normal. Il prend son temps...
Au niveau des questions: Développer les CCE, approfondir le décodeur idéal, expliquer la notion de Distance de Hamming et terminer sur un exemple.
=> toutes les questions se suivent, s'enchainent, et le prof ne vous ennuyera pas à vous balader de gauche à droite dans le cours. (tout le chapitre 6 pour ceux qui ont les notes de cours)
Au niveau des questions qu'il pose:
- théorème de Bayes: expliquer ce que représentent les probabilités + s'en servir pour faire le lien avec la distance de Hamming
//!\\ bien comprendre cette démo, elle est super importante pour comprendre l'interet des distances de Hamming!!!
- distance de Hamming: tout (les sphères, l'équation avec les proba etc) pas besoin de refaire la démo
- quid de la borne de Hamming? (bien dire que cela represente le volume de l'espace/volume d'une sphère.
Attention, c'est une condition nécessaire mais non suffisante, pas oublier de le dire.
- exemple: comment construire une matrice de Hamming? (codes cycliques), comment savoir directment cb d'erreurs un code corrige (nb de colonnes linéairement indépendantes)
Il demande aussi les liens entre les vecteurs (H.w + H.z = 0 avec H.z = C, C représentant la colonne du bit incriminé (désolé si je suis pas clair, c'est mieux expliqué dans le cours)=> interet de la matrice canonique et du montage logique... il aime bien ça)
Il est super sympa, faut pas s'en faire.
Pendant la prépa relisez bien calmement. Pas besoin de s'affoler pour tout ecrire super vite au tableau de toute manière vous avez une heure...
Il ne donnera pas les points mais il ne faut pas stresser il a l'air sympa pour ça aussi 🙂
Bonne chance à tous!!!!

INFO-H-300 - 28 Aug 2007

Yosh tout le monde !
J'ai eu :
- Code source
- Code instantanné
- Borne inférieure de L(C)
- Code de Hamming
En gros pour code source et code instanné, y a rien de particulier. Il m'a juste demandé à quoi ça servait et d'expliquer en quoi un code est instantanné.
Pour les codes instatannés, il m'a demandé d'expliquer l'inégalité de Kraft donc expliquer à partir de l'arbre. Il m'a ensuite demandé ce que ça impliquait si on saturait cette inégalité.
Pour la borne inférieure de L(C), il faut juste retaper la démo, j'ai ensuite enchaîné sur le code de Shannon (cf. les posts précédents, ça aide vraiment). Puis il demande comment on peut minimiser le bit qu'on perd >> Shannon par bloc.
Pour le code de Hamming, lui donner un exemple en expliquant bien tout !
Voilà, en fait faut pas du tout stresser pour cet exam. Cet oral de Cerf fut vraiment l'oral le plus cool que j'ai pu passé ^^
Bonne chance !!!

INFO-H-300 - 30 Aug 2007

Pour les electromec, je ne crois pas que Cerf interroge sur la partie modulation !!!
J'ai eu théorème de l'AEP, les sequences typiques, l'application dans
la compression de donnée et la matrice de Hamming.
Ils s'intéressent beaucoup à la compréhension!!
Les petites questions que je me souviens:
Quand nous voulons atteindre la borne entropique avec un epsylon fixé, sur quel paramètre allons nous jouer? La taille n. Dans quel cas l'ensemble typique est égale à l'ensemble de toutes les séquences ( réponse : distribution uniforme). Dans l'exemple de matrice de Hamming (voir exemple du cours), comment peut-on dire juste en regardant
la matrice que ce code ne corrige pas d'erreur? Il y a deux colonnes identiques!

INFO-H-300 - 1 Sep 2007

Bon, donc il faut savoir une chose primordiale :
De tous les oraux que j'ai eu jusqu'ici, c'est pour CE cours-CI que consulter le site oraux.be est le plus important. Et ce n'est pas pour rire, je m'explique : comme vous savez, vous avez largement le temps de préparer votre question. Il vous dit 20 min, mais cest plutôt le double... Bref recopier les démos du cours au tableau, relire attentivement le chapitre, tout ca vous avez le temps.
Mais ca, il le sait très bien 🙂 C'est pourquoi ses questions vont porter essentiellement sur du détail assez pointu, ca va très en profondeur. Tellement que bien souvent, la réponse ne se trouve même pas dans le cours (jai bossé dans le bloc dactylographié de 80 pages (de Verlouch je crois. Thx à lui, on le repetera jamais assez ^^). Donc soit vous vous appreter à refaire tout le raisonnement pour répondre(et prendre le risque de vous planter), soit vous lisez oraux.be ^^
Bon, passons à mes questions :
1) définir les deux capacités, expliquer physiquement chacune d'elles, donner la déf de I(X:Y) (cf.diag de venn) et donner la formule qui lie I(X:Y) avec la distance relative (genre le truc rien à voir avec les capacités, me souvenait pas de la relation). Dire ce que le 2eme théoreme de Shannon nous permet de conclure : elles sont toutes les deux égales. Faut expliquer pourquoi, je savais pas trop mais jai trouver une explication potable avec la réciproque forte du 2ème théo de Sh. Ca semble bien être ca.
2)CBE. Pas de grandes surprises. Comprendre pq H(Y|X) = H2(alpha). On passe directement au feedback : il ne regarde pas les calculs (un peu bête, faut avouer). Il demande pourquoi C avec feedback ou sans sont égales, si on pouvait s'attendre à ce résultat, et expliquer le feedback (je lui ai dit que la source renvoyait le bit quand il n'était pas passé, il m'a répondu "oui mais comment elle sait qu'il n'est pas passé hein?". En fait des bits du récepteurs sont envoyés à la source. D'où le nom feedback.
3)Dernière question : code de huffman (D=2 lui suffit): donner un exemple de construction. Relisez les propriétés même si la question ne le demande pas explicitement, ca aidera à répondre à ses sous-questions (optimalité de huffman sur les DFU, les 2 mots-codes les plus long ont même longueur, etc).
Enfin il demande ce qu'il se passe si pour un des deux mot-codes les plus long, on rajoute un bit (instantané : encore, optimalité : non car on peut lassocier au noeud père de longueur + courte). Et si on retire un bit? (instantané ? Non car préfixe d'un autre (en plus on tombe sur le code d'un noeud déjà traité dans l'arbre), optimalité : la question se pose pas, le code n'étant plus viable).
Voila. Il est très sympathique,et si vous avez bien bossé le cours, il le remarquera et vous aurez vos points. No stress et bonne chances aux suivants 😉

INFO-H-300 - 27 Aug 2007

Comme déjà marqué :
1. CCE
-Principe
-Encodage/Décodage
-Décodeur idéal
2.Distance
-Pourquoi c'est important pour un CCE
3.Code de Huffman
-Exemple
-A partir de cet exemple expliquer le principe

INFO-H-300 - 1 Sep 2006

- qu'est ce qu'un codage de source
- expliquer ce qu'est un code instantané
- énoncer et démontrer l'inégalité de Kraft
- Expliquer et donner un exemple du code de Huffman
Il pose des ptites questions pas trop compliqué, et toutes ses questions ce sont des ptites remarques qu'il a fait au cours et qui sont dans les notes disponibles sur internet. Ce bon cieu cerf est très sympa et pas stressant du tout!
courage a tous!

INFO-H-300 - 31 Aug 2006

Yop, voici mes questions :
-Theoreme AEP, ennoncer et demontrer, definir sequence typique, et finalement arriver grace à tout ça au theoreme du codage.
-Expliquer le codage Huffman (exemple).
Tout cela avec moultes petites questions plutot cool (N'hesitez pas à potasser toutes ces petites question en relisant les post des précédentes années. Ca aide bcp pour le bluffer 😀 )
Sinon il est tres peace et vous explique vraiment bien quand vous vous perdez. Du point de vue du tps, il m'a annoncé que j'avais 30 min pour rediger mes reponses, au final c'etait 1h20 ... ( + 20 min de blabla avec lui )

INFO-H-300 - 11 Sep 2005

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.

INFO-H-300 - 8 Sep 2005

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é.

INFO-H-300 - 7 Sep 2005

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...

INFO-H-300 - 7 Sep 2005

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.

INFO-H-300 - 6 Sep 2005

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

INFO-H-300 - 5 Sep 2005

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 !!!!

INFO-H-300 - 5 Sep 2005

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.

INFO-H-300 - 5 Sep 2005

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.

INFO-H-300 - 1 Sep 2004

J'ai du parler brièvement de ce qu'était le codage de source (à quoi ça sert en gros... à savoir compresser les données émises par la source)
Puis dire ce qu'était un code instantané, en donner un exemple et montrer en quoi c déchiffrable "instantanément"
Ca ct les 2 ptites questions.
Viens l'inégalité de Kraft + démonstration (l'inégalité est une CNS de code instantané mais j'ai juste du démontrer que ct une CN)
Puis j'ai dû déterminer la longueur moyenne optimale d'un code instantané pour une source donnée
(c'est l'histoire avec les multiplicateur de Lagrange)
Et donc on montre que la borne inférieur à la longueur moyenne est l'entropie de shannon. H(X)=< L
Il m'a demandé si on pouvait atteindre cette borne.
En toute généralité, non pcq on trouve que l_i = -log_d_(p_i) qui n'est pas entier en toute généralité et donc on doit prendre le plafond des l_i ce qui donne le code de shannon.
Mais dans le cas particulier où les p_i sont dse puissances de d (d étant le nombre de symboles de l'alphabet du code), alors oui les l_i sont des entiers. on peut atteindre la longueur moyenne minimale. On dit alors que le code est dia ... qqch
Puis il m'a demandé de lui donner une borne supérieure pour cette longueur dans le cas général.
Comme on a: l_i =< plafond de l_i =< l_i + 1
Quand on somme, on trouve: H(X) =< L =< H(X) + 1 (en tenant compte ke la somme des p_i vaut 1)
Il m'a demandé si on pouvait réduire cette borne supérieure.
Oui en codant par bloc (par extension d'ordre n de la source). Dans ce cas ce "bit de pénalité" se répartit sur les n symboles du bloc et on a une pénalité de 1/n bit par symbole qui tend vers 0 pour n très grand.
Enfin il m'a demandé un exemple de code de Hamming.
Mais ça je savais pas cmt on faisait. Il l'a pas trop mal pris.
Et à la fin il donne pas de cote, il m'a juste dit que ct bon, même sans le code de Hamming.
Il est donc pas méchant et il aide un peu.
Mais j'dois avouer que j'ai eu du bol sur les questions.

INFO-H-300 - 1 Sep 2004

Résumé des questions déjà tombées:
I. ENTROPIE DE SHANON
- Entropie (déf)
II. ASYMPTOTIC EQUIPARTITION PROPERTY (AEP)
- Séquences Typiques
- Théorème d'AEP
III. DATA COMPRESSION (CODAGE DE SOURCE)
- Principe de compression de données
- Principe de codage de source
- Longueur moyenne d'un code
- Codes instantanés (déf)
- Inégalité de Kraft (+démo)
- Longueur optimale L* (code optimal)
- Code de Shanon
- Premier théorème de Shannon
- Code d'Huffman (Construction+principe)
IV. CAPACITE DE CANAL
- Capacité informationnelle + opérationnelle (déf)
- Canal Binaire Symétrique (CBS)
- Canal Binaire à effacement (CBE)
- Second Théorème de Shanon
- Séquences conjointement typiques et théorème de Shannon
V. CCE:
- Principe
- Décodeur idéal (+demo Bayes)
- Différence entre poids min & distance minimale
- Distance minimum (+démo avec sphères)
- Code de Hamming (+exemple)
- Code de Hamming Canonique (Encodage + Décodage)
- Borne de Hamming (+démo)

INFO-H-300 - 31 Aug 2004

Voici la suite:
- il m'a demandé dans quoi s'insérait mes trois prmière question: compression de données.
- ex de fonctionnement de code de Hamming.
ccl: il est trés sympas mais il faut tt savoir justifier, il est très pointilleux. mais il faut aussi connaitre le coiurs dans son ensemble: les grands théorèmes etc.
bonne me... pour la suite

INFO-H-300 - 31 Aug 2004

Je suis passé cette après midi et j'ai ey:
- code instantanné: déf et à quoi ca sert? Il m'a en plus baladé sur les code dfu.
- inégalité de Kraft: démo. il faut tt savoir justifier.
- calcul de la longueur optimal de mots codes: bien justifier et il m'a demandé de faire le lien avec le premier théorème de Shanon. +donner le code de Shanon et comparer à l'entropie.

INFO-H-300 - 31 Aug 2004

Je suis passé ce matin et j'ai eu :
- CCE : principe
- CCE : décodeur idéal
- CCE : distance minimum d'un CCE
- CCE : borne de Hamming
- Comment utilise-t-on les séquences conjointement typiques dans le second théorème de Shannon

INFO-H-300 - 30 Aug 2004

donc t entre, t as ton cours il te laisse seul tu remplis tes tableaux et t explique hésite pas a mettre le plus possible
moi g eu (tout le monde a eu ca cette aprem je pense)
code correcteur d 'erreur dans tous les sens :
expliquer en gros le principe d un CCE
principe du décodeur idéal
distance entre mots code <--> nb erreur (à démontrer avec les shpère)
borne de hamming démontrer
exemple d'utilisation du code de Hamming

INFO-H-300 - 30 Aug 2004

jai passé cerf aujourd'hui. il est tres sympa comme tout le monde le dit, et il insiste vraiment sur la comprehension.
Donc ta mission en passant cet examen, c'est d'une part de recopier toute la partie du cours qui concerne les question (elles se suivent, c facile a retrouver). Veille donc a avoir un poignet bien degourdi, et ne perds pas trop de temps a contempler ton oeuvre au tableau.
Ensuite, apres une demi-heure, il arrive et te dis avec son plus beau sourire "je t'ecoute!". Tu dois donc etre capable de lui expliquer TOUT ce que tu as ecrit (chacun de tes traits!). Et il ne demande rien d'autre que ce qui a un rapport direct avec la question.
jai eu:
- capacite (def informationnelle et operationnelle)
- 2e theoreme de Shannon
- CBS et CBE (je lui ai parlé du feedback alors qu'il l'a pas demandé. ca lui a plu!)
- lien entre sequences conjointement typiques et le theoreme de Shannon
il ne cote vraiment pas vache, faut juste tout expliquer et si ya des trucs flous, il reexplique tout gentillement!

INFO-H-300 - 22 Aug 2004

Voila un medley des questions qui se trouvent sur la mailing list 2005,
amusez vous bien
Paille
Cerf :
1. CCE principe, code idéal, distance d'un CCE
2. Borne de Hamming principe plus démo
3. Exemple avec une matrice qcq de Hamming
Il est vraiment super sympa et il s'intéresse principalement à la compréhension
J'ai passé l'exam de Cerf et il n'est pas tres complique... Il vous pose plusieurs petites que vous notez au tableau. Il vous laisse 1/2 heure avec votre cours et ous préparez la question au tableau.Vous écrivez ce que vous voulez. Il revient ensuite et vous lui expliquez tout ce que vous avez écrit. Il pose des petites quesions en plus pour voir si vous avez bien compris son cours... J'ai discuté 45 min avec lui probablement pcq j'étais tt seul à passer.
A part ca, il est très sympa mais ne donne pas la cote finale, juste une petite estimation.
En fait l'exercice qu'il donne c'est plutôt un exemple traité au cours.Rien ne vient des TP.
Principe des CCE
Decodeur Idéal: Définition & Démo des formules ( Cf Bayes... )
Différence entre poids min & distance minimale
Bornes de Hamming :Déf & Démo...
Application : Codes de Hamming ( Canonique : Encodage et décodage )-Cest la partie exercice pour celui qui veut savoir.
Tous ceux qui passent n'ont en général pas la même question.
Je ne sais pas le détail des questions des autres.Mais en tout cas il y en a qui ont été interrogés sur l'équipartition asymptotique...
Alors mes quetions
CCE
but et principe
decodeur ideal
distance de Hamming (distance d'un code correcteur d'erreur)
bornes de Hamming (démonstration)
Huffman
Construction
Principe
Je suis entré, j'ai eu 4 questions à écrire au tableau.
- Code source: objectifs et classes.
- Inegalité de Kraft = demo.
- En déduire qqch sur les codes optimaux. ( ineglaité saturé )
- Exemple au choix d'un algo de Hauffman.
Il m a laissé une demi heure pour écrire ce que je voulais au tableau, puis il est revenu et j'ai exposé mes explications.
Tout se suivait dans le cours. Pas de piège, il demande d'expliquer le cours. Il met sur la voie si on cale. Si on est bon, il ose qq questions bonus comme:
"Comment appelle t on une source dont les longeurs des codes sont entieres?" Je ne me rappelle plus , ca commence par "dia"...
Cerf
1. CCE
2. Borne de Hamming
3. Exemple avec une matrice qcq de Hamming
Pour ceux que ça intéresse.J'ai eu 4 questions:
-équipartition asymptotique
-séquence typique
-compression des données
-canal binaire symétrique
il donne une approximation du style plus de 12 ou moins.
J'ai eu :
Codage de source
Longueur moyenne d'un code
Code de Shannon
exemple de Huffman

INFO-H-300 - 3 Jun 2004

Questions de cerf (septembre 2003)
- Codage de source
- Longueur moyenne d'un code
- Code de Shannon
- exemple de Huffman
- équipartition asymptotique
- séquence typique
- compression des données
- canal binaire symétrique
- CCE principe, code idéal, distance d'un CCE
- Borne de Hamming principe plus démo
- Exemple avec une matrice qcq de Hamming
Il donne les points en comparant les étudiants. Il faut donc attendre qu'il termine d'interroger. Mais il donne une approximation du style plus de 12 ou moins.
Il est vraiment super sympa et il s'intéresse principalement à la compréhension


Il n'y a pas de publications plus anciennes.
Post Views: 14,021