Jump to content
Sign in to follow this  
Lilian HEDEVIN

TP 1CPA - Année 2014/2015

Recommended Posts

Bonsoir,

 

J'ouvre ce post pour savoir si quelqu'un avait réussi à trouver une solution plausible et simple au problème posé lors du premier TP de 1CPA.

 

Pour rappel, le sujet était :

 

Une entreprise veut envoyer des mots via son réseau informatique. Pour réaliser les transferts, l’entreprise doit constituer des mots numériques en utilisant des codes binaires à partir de ses mots de lettres. Vous êtes donc en charge de proposer le codage et le décodage des lettres en binaire et inversement.

Nous fixons et disposons d’un ensemble L constitué de 5 lettres : L = {a, b, c, d, e}. Par exemple, un mot de lettres sera : aaaeeddeecc.

Question 2.1 : Donnez l’ensemble B des plus petits codes binaires pour coder les lettres de L. La valeur des codes doit respecter l’ordre lexicographique. Justifiez vos réponses. En d’autres termes, chaque lettre doit avoir un code binaire, mais lequel ?

Question 2.2 : Avec votre codage binaire de la question 2.1, pouvez-vous coder une suite de n lettres de L : L1, …, Ln juste en juxtaposant les codages des lettres de la suite, comme dans l’exemple proposé au début de l’exercice ? Justifier votre réponse. Modifiez votre codage si vous ne pouvez pas le faire. Justifiez vos réponses.

Question 2.3 : A l’aide de votre codage, décodez la suite : 110011101010110110000100101001102. Justifiez vos réponses.

Question 2.4 : Codez en binaire (avec votre codage) la suite de lettres : baccabe. Justifiez votre réponse.

 

 

J'avais trouvé une solution, un peu complexe et qui ne résolvait pas la questions 2.3.

 

En vous remerciant par avance,

Share this post


Link to post
Share on other sites

Bonjour Lilian,

 

Le tout est de comprendre la demande de l'entreprise.

En fait, ici nous avons 5 lettres toutes différentes, il faut donc trouver 5 codages binaires tous différents qui permettent de traduire les lettres en chiffes et inversement. Par exemple si 0 vaut a, et b vaut 1 alors l'octet 00110101 et vaut aabbabab par décodage est vaut 00110101 par codage. Et comme a et b sont les lettres différentes et que 0 et 1 sont des chiffres différents, la séquence par codage/décodage n'est jamais altérée est vaut bien toujours les mêmes valeurs.

 

Attention le 2 après les 0 et 1 de la question 2.3 est la signification de la base binaire et non un chiffre du mot.

 

Bonnes révisions,

Cyril P.

Share this post


Link to post
Share on other sites

Merci pour cette réponse.

 

Le rattrapage est passé (assez bien pour moi d'ailleurs).

 

Je reste curieux sur la résolution de cet exercice.

 

Voici les pistes que j'avais utilisé :

 

2.1. Pour coder les lettres de L, et en utilisant les plus petits codes binaires, nous pouvons utilisé l’ensemble B = {001,010,011,100,101} correspondant à l’ensemble L = {a,b,c,d,e}. Chaque lettre aura donc son codage binaire, et il n’existe pas de plus petit codage possible ; nous avons ici besoin de 3 bits pour coder ces 5 lettres.

 

2.2. Oui, grâce à mon codage, je peux coder une suite de n lettres de L ; juste en juxtaposant les codages des lettres à la suite.

Si nous reprenons l’exemple au début de l’exercice, nous avons pour aaaeeddeecc : 001 001 001 101 101 100 100 101 101 011 011.

 

2.4. D’après mon codage, baccabe serait : 010 001 011 011 001 010 101 en reprenant  la table des ensembles donnée précédemment (question 2.1)

 

Ces trois questions sont donc cohérentes, le problème arrive à la troisième :

2.3. 11001110101011011000010010100110 ne donnerait rien avec mon codage car il y aurait des caractères ayants pour valeur : 110, or cette valeur n’est pas dans mon codage.

 

Quel serait donc le codage parfait pour résoudre cette troisième question ?

Share this post


Link to post
Share on other sites

Bonjour Lilian,

 

C'est bien que le rattrapage se soit bien passé, tout le travail fourni va porter ses fruits.  

 

Effectivement votre codage est approchant pour la question 3, mais pas encore optimisé. Vous vous êtes concentré sur un codage normé à 3 bits, mais ce n'est pas le plus petit codage pour résoudre la question 3. Il faut un codage hétérogène en termes de bits. 

 

Une piste est d'avoir 2 codages à 2 bits et 3 codages à 3 bits et tous différents.

 

Bonne réflexion,

Share this post


Link to post
Share on other sites

Utiliser un codage hétérogène ? Pourquoi ? Cela ne risque-t-il pas de provoquer des quiproquos et des problèmes de déchiffrage ?

 

Je ne vois pas comment avoir 2 codages à 2 bits (si je simplifie ma méthode j'en trouve 3 : 01=a , 10=b, 11=c) et 3 codages à 3 bits.

 

Un autre indice ? Ou quel résultat donnerait "11001110101011011000010010100110" (que je puisse remonter pour trouver le codage) ?

Share this post


Link to post
Share on other sites

D'accord, avec analyse on trouve donc :

 

110 01 110 101 01 101 100 00 100 101 00 110
 
    e   b    e     d    b    d      c   a     c     d   a    e

 

Ce qui nous donne par correspondance :

 

a =   00

b =   01

c = 100

d = 101

e = 110

 

Quand même un peu tordu comme résolution, merci pour cette résolution.

 

PS : Pour les corrections de RESIT, qui est/sont le(s) correcteur(s) ?

Share this post


Link to post
Share on other sites

Bonjour Lilian,

 

La solution n'est pas "tordue", elle est applicable et optimisée. N'oublier pas que c'est une demande entreprise (certes, il s'agit d'un exercice, mais réaliste pour une vraie entreprise). Attention , aujourd'hui, nous parlons d'éco-participatrion et de systèmes embarqués. La moindre économie de circuits de stockage de transferts fait gagnée du temps et de l'énergie. 

 

Encore pour cette année, les resit sont corrigés et notés pas les Full prof.

 

Bonne continuation, 

Share this post


Link to post
Share on other sites

Bonjour Samuel-Henri,

 

Et quelle serait la valeur du 5ième code ?

 

Si nous utilisons 00, 01, 10, 11, il nous faudrait utiliser un des préfixes définis par l'un des 4 codes pour créer le 5ième et donc nous créons une ambiguïté par le préfixe.

 

Il faut réaliser des codages uniques pour décoder la séquence. Donc, si nous utilisons, par exemple 11, nous obtenons 2 nouveaux codes soit 110 et 111. Le lecteur de séquences lit 11 puis 0 ou 1 donc pas d’ambiguïté. Par contre si nous avions 11 comme code, le lecteur donnerait toujours la valeur initiale et nous n'aurons pas de 5ième code possible.

 

Bonnes révisions.

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
Sign in to follow this  

×