rs.html

reed-solomon编码的java实现

m&eacute;thode pour trouver un &eacute;l&eacute;ment primitif, </FONT><FONT FACE="Symbol">a
</FONT><FONT FACE="Arial">n&#146;est pas forc&eacute;ment un &eacute;l&eacute;ment
primitif.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=6><B>2.2.1
<U>Repr&eacute;sentation des &eacute;l&eacute;ments</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Il
existe principalement deux m&eacute;thodes pour repr&eacute;senter
les &eacute;l&eacute;ments d&#146;un corps fini, soit :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-left: 0.4in; margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>i)
F</FONT><SUB>q </SUB><FONT SIZE=4>est un F</FONT><FONT SIZE=2><SUB>p</SUB></FONT><FONT SIZE=4>-espace
vectoriel de dimension k, on choisit une certaine base {b</FONT><SUB>1</SUB><FONT SIZE=4>,...,b</FONT><SUB>k</SUB><FONT SIZE=4>}
de cet espace et on rep&egrave;re chaque &eacute;l&eacute;ment de F</FONT><SUB>q</SUB><FONT SIZE=4>
par ses composantes sur cette base.</FONT></FONT></P>
<P STYLE="margin-left: 0.4in; margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-left: 0.39in; margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">ii)
On prend un &eacute;l&eacute;ment </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
de F</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUP>*</SUP></FONT><FONT SIZE=4>
qui engendre ce groupe et tout &eacute;l&eacute;ment non nul de F</FONT><SUB>q</SUB><FONT SIZE=4>
s&#146;&eacute;crit d&#146;une mani&egrave;re, et d&#146;une seule,
sous la forme </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>m</SUP><FONT SIZE=4>,
avec m = 0,...,q-1.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Pour
d&eacute;crire un &eacute;l&eacute;ment du corps, on utilisera 
exclusivement la premi&egrave;re repr&eacute;sentation, car elle
permet d&#146;associer un nombre &agrave; chaque &eacute;l&eacute;ment
du corps. Mais on prendra soin de tabuler ces deux repr&eacute;sentations,
la raison en est que la repr&eacute;sentation i) se pr&ecirc;te tr&egrave;s
bien pour l&#146;addition et que la repr&eacute;sentation ii) est
bien adapt&eacute;e pour la multiplication. Comme on a besoin de ces
deux op&eacute;rations, on travaillera avec ces deux repr&eacute;sentations
qui seront tabul&eacute;es une fois pour toute.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=4><B>Avertissement
:</B> On ne s&#146;int&eacute;ressera, par la suite, que de corps
finis de caract&eacute;ristique 2, qui sont les seuls utilis&eacute;s
pour les codes de Reed-Solomon.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=6><B>2.2.2
<U>Exemple</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Soit
F</FONT><SUB>2</SUB><FONT SIZE=4> = {0,1} le corps &agrave; deux
&eacute;l&eacute;ments. On v&eacute;rifie que le polyn&ocirc;me P(x)
= x</FONT><SUP>2</SUP><FONT SIZE=4> + x + 1 est bien irr&eacute;ductible
sur F</FONT><SUB>2</SUB><FONT SIZE=4>. Soit </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
une racine de P(x), on aura alors</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">  P(</FONT><FONT FACE="Symbol">a)
= 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 = 0   donc   </FONT><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</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>ce qui
veut dire que l&#146;espace vectoriel engendr&eacute; sur F</FONT><SUB>2</SUB><FONT SIZE=4>
par 1,</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
est alors un corps, et la dimension de cet espace vectoriel est de 2.
Le corps &agrave; 4 &eacute;l&eacute;ments sera alors F</FONT></FONT><FONT FACE="Arial"><SUB>4</SUB><FONT SIZE=4>
= {0,1,</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a , a + 1</FONT><FONT FACE="Arial">}.
Si l&#146;on choisit {1,</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">}
comme base, la repr&eacute;sentation i) sera la suivante :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	0	=
0.</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 0.1 =
(0,0) = 0</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	1	=
0.</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1.1 =
(0,1) = 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	</FONT><FONT FACE="Symbol">a
</FONT><FONT FACE="Arial">	= 1.</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
+ 0.1 = (1,0) = 2</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
+ 1	= 1.</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1.1
= (1,1) = 3</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Cette
repr&eacute;sentation est tr&egrave;s pratique, car elle permet
d&#146;associer un nombre &agrave; chaque &eacute;l&eacute;ment.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">Si l&#146;on
avait choisit {1,</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
+ 1} comme base, on aurait alors la repr&eacute;sentation suivante :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	0	=
0.(</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1) + 0.1
= (0,0) = 0</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	1	=
0.(</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1) + 1.1
= (0,1) = 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
+ 1	= 1.(</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1)
+ 0.1 = (1,0) = 2</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
	= 1.(</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1) +
1.1 = (1,1) = 3</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>On
comprend facilement que le choix de la base est fondamental pour
savoir de quoi l&#146;on parle.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=4>Pour
effectuer une addition sur ce corps, il faut voir que l&#146;on
additionne en fait deux vecteurs, et donc que l&#146;on effectue
l&#146;addition composante par composante, et ceci sur F</FONT><SUB>2</SUB><FONT SIZE=4>.
Soit par exemple,</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	(0,1)
+ (0,1) = (0 + 0,1 + 1) = (0,0)   -&gt;   1 + 1 = 0</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	(1,1)
+ (1,0) = (1 + 1,1 + 0) = (0,1)   -&gt;   3 + 2 = 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	(1,1)
+ (0,1) = (1 + 0,1 + 1) = (1,0)   -&gt;   3 + 1 = 2</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	(0,1)
+ (1,0) = (0 + 1,1 + 0) = (1,1)   -&gt;   1 + 2 = 3</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Sur un
corps de caract&eacute;ristique 2, l&#146;addition revient &agrave;
faire un <B>OU EXCLUSIF (notation ^)</B> entre deux nombres. Soit par
exemple,</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>   3 +
2 = 11 ^ 10 = 01 = 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>   3 +
1 = 11 ^ 01 = 10 = 2</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Cela
nous donne une op&eacute;ration assez simple &agrave; r&eacute;aliser
et &agrave; impl&eacute;menter dans un programme.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Pour la
multiplication, il nous faut trouver un &eacute;l&eacute;ment
primitif qui g&eacute;n&egrave;re le groupe F</FONT><SUB>4</SUB><SUP>*</SUP><FONT SIZE=4>.
Dans notre exemple, </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
est un &eacute;l&eacute;ment primitif, en effet</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	</FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>0</SUP><FONT SIZE=4>	=	1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	</FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>1</SUP><FONT SIZE=4>	=	</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">	</FONT><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</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>ce qui
nous donne les trois &eacute;l&eacute;ments de notre groupe.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT SIZE=4><FONT FACE="Arial">Si
l&#146;on prend {1,</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">}
comme base, on aura alors la table de multiplication suivante :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>  1 * 1
= 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">  1 * 2
= 1 * </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> = </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
= 2</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">  1 * 3
= 1 * (</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1</FONT><FONT FACE="Symbol">)</FONT><FONT FACE="Arial">
= </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1 = 3</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>  2 * 1
= 1 * 2 = 2</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">  2 * 2
= </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> * </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
= </FONT><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 = 3</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">  2 * 3
= </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> * (</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
+ 1</FONT><FONT FACE="Symbol">)</FONT><FONT FACE="Arial"> = </FONT><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">
= </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1 + </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
= 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>  3 * 1
= 1 * 3 = 3</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>  3 * 2
= 2 * 3 = 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">  3 * 3
= (</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1) * (</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
+ 1) = </FONT><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">
+ </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> + 1 = </FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>2</SUP>
+<FONT SIZE=4> 1 = </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
= 2</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>ce qui