rs.html

reed-solomon编码的java实现

<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>On
&eacute;value toujours un polyn&ocirc;me ainsi que sa d&eacute;riv&eacute;e
&agrave; l&#146;aide d&#146;un sch&eacute;ma d&#146;Horner, et ceci
afin de minimiser le nombre de calculs.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>4.4
<U>Sch&eacute;ma d&#146;Horner</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	On
donne ici, le sch&eacute;ma d&#146;Horner pour &eacute;valuer un
polyn&ocirc;me et sa d&eacute;riv&eacute;e &agrave; une valeur
donn&eacute;e.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Soit
p(x) =  a</FONT><FONT SIZE=2><SUB>n</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>n</SUP></FONT><FONT SIZE=4>
+ a</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>
+ ... + a</FONT><FONT SIZE=2><SUB>1</SUB> </FONT><FONT SIZE=4>. x +
a</FONT><FONT SIZE=2><SUB>0</SUB></FONT><FONT SIZE=4>, on d&eacute;sire
&eacute;valuer notre polyn&ocirc;me et sa d&eacute;riv&eacute;e &agrave;
x = </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">b</FONT><FONT FACE="Arial">,
soit p(</FONT><FONT FACE="Symbol">b</FONT><FONT FACE="Arial">) et
p&#146;(</FONT><FONT FACE="Symbol">b</FONT><FONT FACE="Arial">).</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>I)	<U>Initialisation</U></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	b</FONT><FONT SIZE=2><SUB>n</SUB></FONT><FONT SIZE=4>	=	a</FONT><FONT SIZE=2><SUB>n</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	a</FONT><FONT SIZE=2><SUB>n</SUB></FONT><FONT SIZE=4>	=	b</FONT><FONT SIZE=2><SUB>n</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	k	=	n</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>II)	<U>It&eacute;ration</U></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	b</FONT><FONT SIZE=2><SUB>k</SUB></FONT><FONT SIZE=4>
= a</FONT><FONT SIZE=2><SUB>k</SUB></FONT><FONT SIZE=4> + </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">b</FONT><FONT FACE="Arial">
. b</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUB>k+1</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	si k &gt;
0 alors c</FONT><FONT SIZE=2><SUB>k</SUB></FONT><FONT SIZE=4> = b</FONT><FONT SIZE=2><SUB>k</SUB></FONT><FONT SIZE=4>
+ </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">b</FONT><FONT FACE="Arial">
. c</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUB>k+1</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>III)	<U>Contr&ocirc;le</U></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Si k
est diff&eacute;rent de 0, on d&eacute;cr&eacute;mente k et on
retourne au point II, sinon l&#146;agorithme est termin&eacute;.</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">On aura
alors p(</FONT><FONT FACE="Symbol">b</FONT><FONT FACE="Arial">) = b</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUB>0</SUB></FONT><FONT SIZE=4>
et p&#146;(</FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">b</FONT><FONT FACE="Arial">)
= c</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>4.5
<U>Exemple 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>	Reprenons
notre exemple 3.1 ci-dessus, soit notre code de Reed-Solomon :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>c(x)	=	9x</FONT><FONT SIZE=2><SUP>14</SUP></FONT><FONT SIZE=4>
+ 8x</FONT><FONT SIZE=2><SUP>13</SUP></FONT><FONT SIZE=4> + 7x</FONT><FONT SIZE=2><SUP>12</SUP></FONT><FONT SIZE=4>
+ 6x</FONT><FONT SIZE=2><SUP>11</SUP></FONT><FONT SIZE=4> + 5x</FONT><FONT SIZE=2><SUP>10</SUP></FONT><FONT SIZE=4>
+ 4x</FONT><FONT SIZE=2><SUP>9</SUP></FONT><FONT SIZE=4> + 3x</FONT><FONT SIZE=2><SUP>8</SUP></FONT><FONT SIZE=4>
+ 2x</FONT><FONT SIZE=2><SUP>7</SUP></FONT><FONT SIZE=4> + 1x</FONT><FONT SIZE=2><SUP>6</SUP></FONT><FONT SIZE=4>
+</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><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"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Choisissons
un polyn&ocirc;me d&#146;erreur, soit</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>e(x)	=	7x</FONT><FONT SIZE=2><SUP>11</SUP></FONT><FONT SIZE=4>
+ 10x</FONT><FONT SIZE=2><SUP>2</SUP></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Notre
code re&ccedil;u sera alors,</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>d(x)	=	c(x)
+ e(x)</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>d(x)	=	9x</FONT><FONT SIZE=2><SUP>14</SUP></FONT><FONT SIZE=4>
+ 8x</FONT><FONT SIZE=2><SUP>13</SUP></FONT><FONT SIZE=4> + 7x</FONT><FONT SIZE=2><SUP>12</SUP></FONT><FONT SIZE=4>
+ 1x</FONT><FONT SIZE=2><SUP>11</SUP></FONT><FONT SIZE=4> + 5x</FONT><FONT SIZE=2><SUP>10</SUP></FONT><FONT SIZE=4>
+ 4x</FONT><FONT SIZE=2><SUP>9</SUP></FONT><FONT SIZE=4> + 3x</FONT><FONT SIZE=2><SUP>8</SUP></FONT><FONT SIZE=4>
+ 2x</FONT><FONT SIZE=2><SUP>7</SUP></FONT><FONT SIZE=4> + 1x</FONT><FONT SIZE=2><SUP>6</SUP></FONT><FONT SIZE=4>
+</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><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>
+ 5x</FONT><FONT SIZE=2><SUP>2</SUP></FONT><FONT SIZE=4> + 11x + 14</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">On
calcule les syndromes, soit S<SUB>i</SUB> = d(</FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>)
= d(2</FONT><SUP>i</SUP><FONT SIZE=4>) avec i = 1, ..., 6, ce qui
nous donne le syndrome 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>s(x)	=	1x</FONT><FONT SIZE=2><SUP>5</SUP></FONT><FONT SIZE=4>
+ 15x</FONT><FONT SIZE=2><SUP>4</SUP></FONT><FONT SIZE=4> + 7x</FONT><FONT SIZE=2><SUP>3</SUP></FONT><FONT SIZE=4>
+ 8x</FONT><FONT SIZE=2><SUP>2</SUP></FONT><FONT SIZE=4> + 11 </FONT></FONT>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>On pose
a(x) = x</FONT><SUP>6</SUP><FONT SIZE=4> et b(x) = s(x), et on
applique l&#146;algorithme d&#146;Euclide, cela nous donne :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>L(x)	=	
6x</FONT><FONT SIZE=2><SUP>2</SUP></FONT><FONT SIZE=4> + 9x + 1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>W(x)	=	
5x + 11</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>U(x)	=	
6x</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>On
cherche les 2 racines pour l(x), on trouve :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>b</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>
= 9 = </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUP>4</SUP></FONT><FONT SIZE=4>
et b</FONT><FONT SIZE=2><SUB>2</SUB></FONT><FONT SIZE=4> = 6 = </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUP>13</SUP></FONT><FONT SIZE=4>
d&#146;o&ugrave; l&#146;on tire :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>p</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>
= 15 - 4 = 11 et p</FONT><FONT SIZE=2><SUB>2</SUB></FONT><FONT SIZE=4>
= 15 - 13 = 2.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=4>Il
nous reste &agrave; trouver la valeur de l&#146;erreur &agrave; ces
positions. Pour cela, on calcule</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>e</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>
= W(9) / L&#146;(9) = 13 / 9 = 7</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>e</FONT><FONT SIZE=2><SUB>2</SUB></FONT><FONT SIZE=4>
= W(6) / L&#146;(6) = 12 / 9 = 10</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Ce qui
nous donne un polyn&ocirc;me de correction :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>v(x) =
7x</FONT><FONT SIZE=2><SUP>11</SUP></FONT><FONT SIZE=4> + 10x</FONT><FONT SIZE=2><SUP>2</SUP></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>On
remarquera que l&#146;on a v(x) = e(x), et que si l&#146;on effectue
la correction, cela nous donne</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>c&#146;(x)
= d(x) + v(x) = c(x) + e(x) + v(x) = c(x)</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>et que
l&#146;on retrouve notre code de d&eacute;part, ce qui bien le but
recherch&eacute;.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>4.6
<U>D&eacute;tection d&#146;erreurs &gt; t</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Voici
les principaux contr&ocirc;les qu&#146;ils faut effectuer afin de
d&eacute;tecter un nombres d&#146;erreurs &gt; t.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Apr&egrave;s
avoir terminer l&#146;algorithme d&#146;Euclide, deux cas peuvent se
pr&eacute;senter :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>A1)  
x</FONT><SUP>t</SUP><FONT SIZE=4> | s(x)   =&gt;   W(x) = 0.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>A2)  
s(x) = w(x)   =&gt;   l(x) = 1 et donc pas de racine.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Lors de
la recherche des racines de l(x), trois cas peuvent se pr&eacute;senter
:</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>B1)   0
est racine de l(x).</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>B2)  
l(x) a des racines multiples.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>B3)  
l(x) ne se d&eacute;compose pas en produit de facteur lin&eacute;aire.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>       
    On trouve donc moins de racine qu&#146;il ne devrait y en avoir.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Lors de
la recherche de la position de l&#146;erreur, un cas peu se pr&eacute;senter
:</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial">