Code correcteur

[caroline21]

bonjour,

pouvez-vous m'aider à répondre au problème suivant:

Exercice 1:
soit
g=
(1 0 1 0 1 1)
(0 1 1 0 0 1)
(0 0 0 1 1 1)
la matrice 3x6 génératrice d'un code linéaire binaire C.

1. Calculer la matrice de parité de C

2. Calculer l'élément de poids minimal de chacun des 8 translatés de C.

3. Décoder les vecteurs reçus 111101, 000100, 101101


Exercice2:

Le (15,12) code de Reed Solomon sur GF(16) à une distance minimale d=4 et peut corriger 3 effacements (noté ?) ou un effacement et une erreur.
sa matrice de parité H est:
H=
(1 1 1 ... 1 1)
(1 a^1 a^2 ... a^13 a^14)
(1 a^2 a^4 ... a^26 a^28)


1. Décoder le mot (y0,...,y14) = (A,3,1,0,1,2,3,4,5,3,5,4,3,2,1), dont le syndrome est (B,2,7).


Notre but est maintenant de décoder le mot
y=(y0,...,y14)= (B,8,B,2,7,6,8,7,D,B,9,7,5,3,1)
dont on sait qu'il possède une erreur et un effacement, en supposant que le calcul du syndrome de y a donné s=(C,B,3).


2. Notons E_i = a^u le localisateur d'effacement correspondant au i-ème effacement. On appelle polynôme des localisateurs d'effacement le polynôme P(x)=Produit(1-x*E_i, i allant de 1 à p). Calculer le polynôme P(x) des localisateurs d'erreurs de y.


3. On appelle polynôme partiel des syndromes le polynôme S(x) = s_0+s_1x+...+s_{n-k} x^{n-k} où s=(s_0,s_1,...,s_{n-k}) est le syndrome du mot x. Calculer S(y) en remplaçant l'effacement par 0.


4. On note Q(x) le polynôme des localisateurs d'erreurs de x défini par Q(x)=Produit(1-Q_i*x^i, i allant de 1 à PartieEntiere((d-1)/2) ) où Q_i=a^u est l'emplacement de la i-ème erreur. Développer le polynôme R(y)=S(y)P(x)Q(y) mod y^(d-1) en fonction de x, E_1 et Q_1.


5. Notons T(y)=T_0+T_1y+T_2y^2 le polynôme P(y)Q(y). Sachant que l'équation s_0T_2 + s_1T_1+s_2=0 est satisfaite, donner une expression de Q_1 en fonction de de s_1, E_1, s_2, s_0 puis calculer Q_1 en fonction de a. Cette valeur correspond, après calcul du logarithme en base a, à la position de l'erreur de y.


6. On rappelle que s_0 désigne l'amplitude de l'erreur ajoutée au mot transmis pour obtenir y, c'est-à-dire, ici, la somme de l'amplitude Y_1 de l'erreur commise sur l'un des bits de y avec l'amplitude U_1 de l'erreur provenant de l'effacement. On rappelle encore que s_1 est égale à a^7Y_1+a^4U_1. En déduire U_1 et Y_1 puis la valeur du mot transmis.



Note:
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
a^i 1 2 4 8 3 6 C B 5 A 7 E F D 9

b 1 2 3 4 5 6 7 8 9 A B C D E F
log b 0 1 4 2 8 5 10 3 14 9 7 6 13 11 12



Merci.

[zephira]

Salut,
Aère un peu parce que la on a qu'une envie c'est de partir en courant

[caroline21]

Voilà c'est fait :).
Peux-tu m'aider à démarrer? Je ne vois pas bien par où commencer...

[zephira]

le problème c'est que je ne connais pas les définitions des termes que tu emplois

[caroline21]

Lesquels?
La plupart sont sur wikipedia. Ce sont des notions nouvelles pour moi aussi, donc j'y vais aussi pour chercher des infos, mais je ne vois toujours pas comment démarrer. Peut-être y arriverez-vous?

Merci en tout cas de vous intéresser à mes questions.