Codes polynomiaux

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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 ?

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Staff

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.

Édité par artragis

+0 -0
Auteur du sujet

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 :/

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Staff

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.

+0 -0
Auteur du sujet

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.

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Staff

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

Édité par artragis

+0 -0
Auteur du sujet

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 ? :)

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Auteur du sujet

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…

Université de Bretagne-Sud <3

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

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