Codes polynomiaux

Le problème exposé dans ce sujet a été résolu.

Bonjour à tous,

Je ne suis pas très doué pour les intros donc j'en viens au fait !

Soit un code polynomial de $\{0 ; 1\}^m \rightarrow \{0 ; 1\}^n$, de polynôme générateur G de degré $n - m = r$

Apparemment le nombre de mots du code serait $m$, mais je ne comprends pas pourquoi. En effet, un code polynomial est une application injective : plusieurs mots du code peuvent être associés à une même donnée. Donc le nombre de mots du code n'est PAS $m$ mais est supérieur ou égal à $m$.

Est-ce bien cela ?

+0 -0

Je vais tenter de décrire ça sous forme d'ensemble pour que tu comprennes que $m$ n'est même pas la bonne comparaison. Prenons n=3, m=2, le polynome générateur et $G = X + 1$

Ensemble de départ

Ensemble d'arrivé

$$0 0$$

$$ 0 0 0 $$

$$ 0 0 1 $$
Cas erreur

$$0 1$$

$$ 0 1 0 $$
Cas erreur

$$ 0 1 1 $$

$$1 0$$

$$ 1 0 0 $$
Cas erreur

$$ 1 0 1 $$

$$1 1$$

$$ 1 1 0 $$

$$ 1 1 1 $$
Cas erreur

Donc selon ton prof a compté les choses, soit il y a $2^m$ codes (tels que générés par G) soit $2^n$ résultats possibles dont une partie qu'il faudra corriger.

+0 -0

Oups j'ai rien dit, je réfléchis à ta réponse :)

heum qu'appelles-tu "cas d'erreur" ? Comment sais-tu qu'il y a une erreur et pourquoi ? Pour la donnée 11, j'ai effectué le calcul et je retrouve bien le mot du code 110, je ne vois pas en quoi c'est un cas d'erreur :/

+0 -0

heum qu'appelles-tu "cas d'erreur" ? Comment sais-tu qu'il y a une erreur et pourquoi ? Pour la donnée 11, j'ai effectué le calcul et je retrouve bien le mot du code 110, je ne vois pas en quoi c'est un cas d'erreur :/

Le mot "cas d'erreur" c'est l'ensemble des codes qui retombent sur la donnée initiale quand on les décode sans pour autant être le code généré quand on code la donnée initiale.

heum qu'appelles-tu "cas d'erreur" ? Comment sais-tu qu'il y a une erreur et pourquoi ? Pour la donnée 11, j'ai effectué le calcul et je retrouve bien le mot du code 110, je ne vois pas en quoi c'est un cas d'erreur :/

Le mot "cas d'erreur" c'est l'ensemble des codes qui retombent sur la donnée initiale quand on les décode sans pour autant être le code généré quand on code la donnée initiale.

artragis

Comment les as-tu trouvés ? :o Juste en permutant les r bits ?

C'est marrant que ces derniers n'influencent pas le décodage… je ne comprends pas trop pourquoi.

+0 -0

heu. EN fait c'est du gros pif, j'avais cru me souvenir de cette table par coeur mais bon voilà quoi. Après c'est "juste une supposition à partir d'un truc (presque) logique" : X + 1 signifie "décale le polynome initial puis ajoute la somme bit à bit du polynôme" donc j'ai supposé que les cas d'erreur c'était "le polynôme décalé mais on a un mauvais bit de somme à la fin". c'est basique, peut être faux, mais pour la compréhension (et surtout la rédaction rapide) ça suffit.

PS : par contre y'a peut être une ou deux cases qui ne suivent pas ce profil, j'ai fait un copier/foiré.

+0 -0

Ok merci ahah :)

Alors du coup pour résumer :

  1. Le nombre de mots du code générés par G est égal à 2^m puisque pour une donnée, un et un seul mot du code est généré par G (via la technique de la division euclidienne) ;

  2. Pour construire un code polynomial, on construit une application injective de Bm vers Bn. Le mot "injective" est justifié par le fait qu'un mot du code n'est associé qu'à au plus une donnée. Et une donnée peut être associée à plusieurs mots du code (c'est ce que tu m'as montré avec ton tableau).

J'ai tout bon ? :)

+0 -0

Ok, merci.

J'ai une autre question à poser concernant les polynômes générateurs (l'énoncé ne change pas).

La voici : dénombrer les multiples de G de degré inférieur ou égal à n.

"dénombrer"… j'imagine qu'il faut donner une quantité ?

En tout cas si je ne me trompe pas, il faut rechercher tous les polynomes qui peuvent s'écrire sous la forme : $P(X) = G(X)A(X)$

en ne retenant que les $P$ dont le degré est $<= n$. Mais après je bloque complètement…

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte