rs.html

reed-solomon编码的java实现

<FONT SIZE=4>= </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP>
(</FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>q-1</SUP><FONT SIZE=4>
= 1</FONT>)<FONT SIZE=4>, la position de l&#146;erreur sera alors
donn&eacute; par p = q-1-i qui est positif et que l&#146;on connait,
puisque l&#146;on connait b = </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>i</SUP><FONT SIZE=4>,
racine de l(x). Il nous faudra donc chercher toutes les racines de
l(x). Il ne faut pas oublier que </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">
est un &eacute;l&eacute;ment primitif, et que tout &eacute;l&eacute;ment
de GF(2</FONT></FONT><FONT FACE="Arial"><SUP>k</SUP><FONT SIZE=4>)<SUP>*</SUP>
s&#146;exprime comme une puissance de l&#146;&eacute;l&eacute;ment
primitif, qui est un g&eacute;n&eacute;rateur du groupe GF(2</FONT><SUP>k</SUP><FONT SIZE=4>)<SUP>*</SUP>.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>4.1
<U>Equation fondamentale</U></B></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; calculer l(x). Pour cela, on fait usage de
la relation fondamentale suivante :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4><B>l(x)
. s(x) = w(x) + u(x) . x<SUP>2t</SUP></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Comme
l&#146;on travaille dans GF(2</FONT><SUP>k</SUP><FONT SIZE=4>), on
peut l&#146;&eacute;crire sous la forme</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><B><FONT SIZE=4>l(x)
. s(x) + u(x) . x<SUP>2t</SUP> = w(x)</FONT></B></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>On peut
voir cette &eacute;quation comme la relation de Bezout avec des
nombres, soit</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>v . b +
u . a = w</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>o&ugrave;
a et b sont des nombres donn&eacute;s, et w est le plus grand
diviseur commun des nombres a et b. u et v sont deux nombres qui
satisfont cette relation. Notre &eacute;quation ci-dessus est
identique, sauf qu&#146;elle s&#146;applique &agrave; des polyn&ocirc;me.
</FONT></FONT>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>On pose
b = s(x), a = x</FONT><FONT SIZE=2><SUP>2t</SUP></FONT><FONT SIZE=4>
et on applique l&#146;algorithme d&#146;Euclide pour trouver
u(x),l(x),w(x), et les racines de l(x) sont utilis&eacute;es pour
trouver la position de l&#146;erreur. Soit b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>
une racine de l(x), la valeur de l&#146;erreur &agrave; la position
p</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4> se calcule de
la mani&egrave;re suivante :</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>i</SUB></FONT><FONT SIZE=4>
= w(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>) / l&#146;(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>)
  o&ugrave; l&#146;(x) est la d&eacute;riv&eacute;e du polyn&ocirc;me
l(x).</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>En
fait, l&#146;algorithme d&#146;Euclide ne donne pas l(x),v(x),w(x)
mais K.l(x), K.v(x), K.w(x), c&#146;est-&agrave;-dire &agrave; une
constante K pr&egrave;s. Mais pour trouver les racines de l(x), qu&#146;on
aie l(x) ou K.l(x) cela nous donne le m&ecirc;me r&eacute;sultat, et
comme la valeur de l&#146;erreur est calcul&eacute;e par le rapport
K.w(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>) /
K.l&#146;(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>), on
obtient le bon r&eacute;sultat.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>4.2
<U>Algorithme d&#146;Euclide</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	On
rappelle ici, le principe de l&#146;algorithme d&#146;Euclide
appliqu&eacute; &agrave; l&#146;&eacute;quation v . b + u . a = w.</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>	q</FONT><FONT SIZE=2><SUB>0</SUB></FONT><FONT SIZE=4>
= -	r</FONT><FONT SIZE=2><SUB>0</SUB></FONT><FONT SIZE=4> =
a	u</FONT><FONT SIZE=2><SUB>0</SUB></FONT><FONT SIZE=4>=1	v</FONT><FONT SIZE=2><SUB>0</SUB></FONT><FONT SIZE=4>=0</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	q</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>
= -	r</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4> =
b	u</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>=0	v</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>=1</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>II)
	<U>Calcul de q</U></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	On
divise r</FONT><FONT SIZE=2><SUB>i-1</SUB></FONT><FONT SIZE=4> par
r</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>, ce qui nous
donne un quotient q et un reste r, soit r</FONT><FONT SIZE=2><SUB>i-1</SUB></FONT><FONT SIZE=4>
= q . r</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4> + r et on
pose q</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4> = q. </FONT></FONT>
</P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>III)
	<U>Calculs</U></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	r</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4>
= r</FONT><FONT SIZE=2><SUB>i-1</SUB></FONT><FONT SIZE=4> - q</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4>
. r</FONT><FONT SIZE=2><SUB>i</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	u</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4>
= u</FONT><FONT SIZE=2><SUB>i-1</SUB></FONT><FONT SIZE=4> - q</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4>
. u</FONT><FONT SIZE=2><SUB>i</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	v</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4>
= v</FONT><FONT SIZE=2><SUB>i-1</SUB></FONT><FONT SIZE=4> - q</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4>
. v</FONT><FONT SIZE=2><SUB>i</SUB></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>IV)
	<U>Test</U></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Si
r</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4> est diff&eacute;rent
de 0, on incr&eacute;mente i et on retourne au point II, et si  r</FONT><FONT SIZE=2><SUB>i+1</SUB></FONT><FONT SIZE=4>
= 0 l&#146;agorithme est termin&eacute;.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>On a
alors,</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>a)  r</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>
est le plus grand diviseur commun entre a et b. </FONT></FONT>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>b)  r</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>
= v</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4> . b + u</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>
. a.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>En
fait, la relation b) est valable pour tout i.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>4.3
<U>Reed-Solomon algorithme</U></B></FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	L&#146;algorithme
de d&eacute;codage des codes de Reed-Solomon sera le suivant :</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4><B>1)</B>	Calcul
du polyn&ocirc;me syndrome s(x).</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Si
s(x) = 0, il n&#146;y a pas d&#146;erreurs : <B>STOP</B>.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4><B>2)</B>	On
applique l&#146;algorithme d&#146;Euclide avec</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	a(x) =
x</FONT><SUP>2t</SUP><FONT SIZE=4> et b(x) = s(x).</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	L&#146;algorithme
se termine d&egrave;s que  le degr&eacute; de r</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>(x)
est &lt; t.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	Si
r</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>(x) = 0, il y a
plus que t erreurs : <B>STOP</B>.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4><B>3)</B>	On
pose L(x) = K . l(x) = v</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>(x).</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	On
cherche toutes les racines de L(x) : b</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>,
..., b</FONT><FONT SIZE=2><SUB>r</SUB></FONT><FONT SIZE=4>.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4><B>4)</B>	Pour
chaque racine b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4> =
 </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>j</SUP><FONT SIZE=4>,
la position p</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4> de
l&#146;erreur est</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>i</SUB></FONT><FONT SIZE=4>
= q - j - 1 = 2</FONT><SUP>k</SUP><FONT SIZE=4> - j - 1.</FONT></FONT></P>
<P STYLE="margin-bottom: 0in"><BR>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4><B>5)</B>	On
pose W(x) = K . w(x) = r</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>(x).
</FONT></FONT>
</P>
<P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>	La
valeur de l&#146;erreur &agrave; la position p</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>
est donn&eacute;e par</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>i</SUB></FONT><FONT SIZE=4>
= W(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>) / L&#146;(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>)
= K . w(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>) / K .
l&#146;(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>) =
w(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>) / l&#146;(b</FONT><FONT SIZE=2><SUB>i</SUB></FONT><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
nouvelle valeur &agrave; la position p</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>
sera alors c</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4> = d</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>
+ e</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4>.</FONT></FONT></P>