rs.html

reed-solomon编码的java实现

termine notre exemple.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>3.
<U>Technique de codage</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Consid&eacute;rons
un code de Reed-Solomon avec ses symboles dans GF(2</FONT><SUP>k</SUP><FONT SIZE=4>),
o&ugrave; k est le nombre de bits par symbole. Soit </FONT></FONT>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>i(x) =
c</FONT><FONT SIZE=2><SUB>m-1</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>m-1</SUP></FONT><FONT SIZE=4>
+ ... + c</FONT><FONT SIZE=2><SUB>1</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>1</SUP></FONT><FONT SIZE=4>
+ c</FONT><FONT SIZE=2><SUB>0</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>le
polyn&ocirc;me d&#146;information, et soit</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>p(x) =
c</FONT><FONT SIZE=2><SUB>2t-1</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>2t-1</SUP></FONT><FONT SIZE=4>
+ ... + c</FONT><FONT SIZE=2><SUB>1</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>1</SUP></FONT><FONT SIZE=4>
+ c</FONT><FONT SIZE=2><SUB>0</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>le
polyn&ocirc;me de contr&ocirc;le, le code de Reed-Solomon sous sa
forme polyn&ocirc;miale sera alors</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>c(x) =
i(x) . x</FONT><FONT SIZE=2><SUP>2t</SUP></FONT><FONT SIZE=4> + p(x)
= c</FONT><FONT SIZE=2><SUB>n-1</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>n-1</SUP></FONT><FONT SIZE=4>
+ ... + c</FONT><FONT SIZE=2><SUB>1</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>1</SUP></FONT><FONT SIZE=4>
+ c</FONT><FONT SIZE=2><SUB>0</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>avec c</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>
appartenant &agrave; GF(2</FONT><SUP>k</SUP><FONT SIZE=4>) pour i =
0,..,n-1.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Un
vecteur &agrave; n symboles, (c</FONT><FONT SIZE=2><SUB>n-1</SUB></FONT><FONT SIZE=4>,
..., c</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>, c</FONT><FONT SIZE=2><SUB>0</SUB></FONT><FONT SIZE=4>)
est un code de Reed-Solomon si et seulement si son polyn&ocirc;me
correspondant c(x) est un multiple du polyn&ocirc;me g&eacute;n&eacute;rateur
g(x). La m&eacute;thode courante pour construire un tel polyn&ocirc;me,
est de diviser i(x) . x</FONT><FONT SIZE=2><SUP>2t </SUP></FONT><FONT SIZE=4>par
g(x)   et d&#146;additionner le reste &agrave; c(x). En effet,</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>i(x) .
x</FONT><FONT SIZE=2><SUP>2t</SUP></FONT><FONT SIZE=4> = q(x) . g(x)
+ r(x)</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>o&ugrave;
r(x) est le reste de la division de i(x) par g(x),</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>c(x) =
i(x) . x</FONT><FONT SIZE=2><SUP>2t</SUP></FONT><FONT SIZE=4> + p(x)
= q(x) . g(x) + r(x) + p(x) = q(x) . g(x)</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>pour
que c(x) soit un multiple de g(x), soit c(x) = q(x) . g(x), il faut
que p(x) = r(x). Comme on travaille toujours sur des corps de
caract&eacute;ristique 2, l&#146;op&eacute;ration de soustraction
sera toujours &eacute;gale &agrave; l&#146;op&eacute;ration
d&#146;addition, soit de mani&egrave;re alg&eacute;brique -1 = +1.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=4>Cela
nous donne une m&eacute;thode pour construire le polyn&ocirc;me de
contr&ocirc;le, il suffit de prendre le reste de la division du
polyn&ocirc;me i(x) . x</FONT><FONT SIZE=2><SUP>2t</SUP></FONT><FONT SIZE=4>
par g(x).</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Il nous
reste encore &agrave; construire le polyn&ocirc;me g&eacute;n&eacute;rateur
g(x). Il est d&eacute;finit de la mani&egrave;re suivante :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">g(x) =
(x + </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">)(x +
</FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>2</SUP><FONT SIZE=4>)...(x
+ </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>2t</SUP><FONT SIZE=4>)
= x</FONT><FONT SIZE=2><SUP>2t</SUP></FONT><FONT SIZE=4> + g</FONT><FONT SIZE=2><SUB>2t-1
</SUB></FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>2t-1</SUP></FONT><FONT SIZE=4>
+ ... + g</FONT><FONT SIZE=2><SUB>1 </SUB></FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>1</SUP></FONT><FONT SIZE=4>
+ g</FONT><FONT SIZE=2><SUB>0</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>o&ugrave;
les coefficients g</FONT><SUB>i</SUB><FONT SIZE=4> appartiennent &agrave;
GF(2</FONT><SUP>k</SUP><FONT SIZE=4>), et </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
est un &eacute;l&eacute;ment primitif de GF(2</FONT></FONT><FONT FACE="Arial"><SUP>k</SUP><FONT SIZE=4>).</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>3.1
<U>Exemple de codage</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Soit
le code RS(4,3), avec n = 15, et soit un polyn&ocirc;me P(x)
irr&eacute;ductible sur F2, avec P(x) = x</FONT><SUP>4</SUP><FONT SIZE=4>
+ x</FONT><SUP>3</SUP><FONT SIZE=4> + 1. Soit </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
une racine de P(x), qui est &eacute;galement un &eacute;l&eacute;ment
primitif, et sera utilis&eacute; pour construire GF(16). La base
utilis&eacute;e sera alors {</FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>3</SUP><FONT SIZE=4>,</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>2</SUP><FONT SIZE=4>,</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">,1}
= {8,4,2,1}, il y aura donc 16 symboles, qui vont de 0 &agrave; 15.
Maintenant, on d&eacute;sire coder les 9 symboles d&#146;informations
suivants :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>i = [9,
8, 7, 6, 5, 4, 3, 2, 1]   (matrice 1 x 9)   </FONT></FONT>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>soit
sous forme polyn&ocirc;miale :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>i(x) =
9x</FONT><FONT SIZE=2><SUP>8</SUP></FONT><FONT SIZE=4> + 8x</FONT><FONT SIZE=2><SUP>7</SUP></FONT><FONT SIZE=4>
+ 7x</FONT><FONT SIZE=2><SUP>6</SUP></FONT><FONT SIZE=4> + 6x</FONT><FONT SIZE=2><SUP>5</SUP></FONT><FONT SIZE=4>
+ 5x</FONT><FONT SIZE=2><SUP>4</SUP></FONT><FONT SIZE=4> + 4x</FONT><FONT SIZE=2><SUP>3</SUP></FONT><FONT SIZE=4>
+ 3x</FONT><FONT SIZE=2><SUP>2</SUP></FONT><FONT SIZE=4> + 2x + 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>g(x)	=	(x
+ 2)(x + 4)(x + 8)(x + 9)(x + 11)(x + 15)</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	=	x</FONT><FONT SIZE=2><SUP>6</SUP></FONT><FONT SIZE=4>
+ 3x</FONT><FONT SIZE=2><SUP>5</SUP></FONT><FONT SIZE=4> + x</FONT><FONT SIZE=2><SUP>4</SUP></FONT><FONT SIZE=4>
+ 4x</FONT><FONT SIZE=2><SUP>3</SUP></FONT><FONT SIZE=4> + 7x</FONT><FONT SIZE=2><SUP>2</SUP></FONT><FONT SIZE=4>
+ 13x + 15</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>c(x)	=	q(x)
. g(x)</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	=	(9x</FONT><FONT SIZE=2><SUP>8</SUP></FONT><FONT SIZE=4>
+ 10x</FONT><FONT SIZE=2><SUP>7</SUP></FONT><FONT SIZE=4> + 9x</FONT><FONT SIZE=2><SUP>6</SUP></FONT><FONT SIZE=4>
+ x</FONT><FONT SIZE=2><SUP>5</SUP></FONT><FONT SIZE=4> + x</FONT><FONT SIZE=2><SUP>4</SUP></FONT><FONT SIZE=4>
+ 12x</FONT><FONT SIZE=2><SUP>3</SUP></FONT><FONT SIZE=4> + 3x</FONT><FONT SIZE=2><SUP>2</SUP></FONT><FONT SIZE=4>
+ 11x + 4) . g(x)</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	=	i(x)
. x</FONT><FONT SIZE=2><SUP>2t</SUP></FONT><FONT SIZE=4> + r(x) </FONT></FONT>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	=	i(x)
. x</FONT><FONT SIZE=2><SUP>2t</SUP></FONT><FONT SIZE=4> + 6x</FONT><FONT SIZE=2><SUP>5</SUP></FONT><FONT SIZE=4>
+ 15x</FONT><FONT SIZE=2><SUP>4</SUP></FONT><FONT SIZE=4> + 15x</FONT><FONT SIZE=2><SUP>3</SUP></FONT><FONT SIZE=4>
+ 15x</FONT><FONT SIZE=2><SUP>2</SUP></FONT><FONT SIZE=4> + 11x + 14</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>4.
<U>Technique de d&eacute;codage</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Consid&eacute;rons
un code de Reed-Solomon c(x) correspondant au code transmis, et soit
d(x) le code que l&#146;on re&ccedil;oit. Le code d&#146;erreur est
d&eacute;finit par</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>e(x) =
d(x) - c(x) = d(x) + c(x)</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>car -
et + sont &eacute;quivalent dans GF(2</FONT><SUP>k</SUP><FONT SIZE=4>).</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>La
premi&egrave;re op&eacute;ration a faire, est de calculer les
syndromes, qui sont d&eacute;finis de la mani&egrave;re suivante :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">S<SUB>i</SUB>
= e(</FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
= d(</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
+ c(</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
= d(</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
  avec   i = 1, ..., 2t</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">car
c(</FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
= q(</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
. g(</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
= 0 puisque g(</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
= 0 pour i = 1, ..., 2t par d&eacute;finition de g(x). Le syndrome
sous forme polyn&ocirc;miale sera</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>s(x) =</FONT>
<FONT SIZE=4>S</FONT><FONT SIZE=2><SUB>2t . </SUB></FONT><FONT SIZE=4>x</FONT><FONT SIZE=2><SUP>2t-1</SUP></FONT><FONT SIZE=4>
+ ...  + S</FONT><FONT SIZE=2><SUB>3 . </SUB></FONT><FONT SIZE=4>x</FONT><FONT SIZE=2><SUP>2</SUP></FONT><FONT SIZE=4>
+ S</FONT><FONT SIZE=2><SUB>2 </SUB></FONT><FONT SIZE=4>. x + S</FONT><FONT SIZE=2><SUB>1</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Soit M
l&#146;ensemble des positions d&#146;erreurs, on d&eacute;finit le
polyn&ocirc;me de localisation (locator polynomial) par</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">l(x) =
(1 - </FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>p1</SUP><FONT SIZE=4>.x)(1
- </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>p2</SUP><FONT SIZE=4>.x)
... (1 - </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>pj</SUP><FONT SIZE=4>.x)
  avec   p1, ..., pj dans M</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">Si b =
</FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>
est une racine de l(x), donc l(b) = 0, on aura alors un des mon&ocirc;me
qui s&#146;annule, soit (1 - </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>p</SUP><FONT SIZE=4>.b)
= 0. Ce qui nous donne la relation suivante b =  </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>-p</SUP><FONT SIZE=4>
= </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>q-1</SUP><FONT SIZE=4>.</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>-p</SUP><FONT SIZE=4>
= </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>q-p-1</SUP>