📄 rs.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"><HTML><HEAD> <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-1"> <TITLE></TITLE> <META NAME="GENERATOR" CONTENT="StarOffice/5.2 (Solaris Sparc)"> <META NAME="CREATED" CONTENT="20001102;19154206"> <META NAME="CHANGED" CONTENT="16010101;0"> <META NAME="SDFOOTNOTE" CONTENT=";;;;C"></HEAD><BODY><DIV TYPE=HEADER> <P STYLE="margin-bottom: 0in"><BR> </P></DIV><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=7><U><B>Index</B></U></FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>1. <B>Codesde Reed-Solomon . . . . . . . . . . . . . . . . . . .</B> 2</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>1.1 Définition<B> . . . . . . . . . . . . . . . . . . . . . . .. . . . . .</B> 2</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>1.2 Information<B>. . . . . . . . . . . . . . . . . . . . . . . . . . . . </B> 2</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>1.3 Exemple<B>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. </B> 2</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>2. <B>Corpsde Galois . . . . . . . . . . . . . . . . . . . . . . . . .</B> 3</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>2.1 Propriétés d’un corps fini<B> . . . . . . . . .. . . . . . . . . . </B>3</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>2.2 Construction d’un corps fini<B> . . . . . . . . . . . . . . .. .</B> 4</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>2.2.1 Représentation des éléments <B>. . . . . . . .. . . . . . .</B> . 4</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>2.2.2 Exemple<B> . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .</B> 5</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>3. <B>Techniquede codage . . . . . . . . . . . . . . . . . . . . .</B> 8</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>3.1 Exemple<B> . . . . . . . . . . . . . . . . . . . . . . . . . . . ..</B> 10</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>4. <B>Techniquede décodage . . . . . . . . . . . . . . . . . . .</B> 11</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>4.1 Equation fondamentale<B> . . . . . . . . . . . . . . . . . . . . </B>12</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>4.2 Algorithme d’Euclide<B> . . . . . . . . . . . . . . . . . . .. . . </B>13</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>4.3 Reed-Solomon algorithme<B> . . . . . . . . . . . . . . . . . . .</B>14</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>4.4 Schéma d’Horner<B> . . . . . . . . . . . . . . . . . .. . . . . .</B> 15</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>4.5 Exemple de décodage<B> . . . . . . . . . . . . . . . . . . .. . </B>16</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>4.6 détection d’erreurs > t<B> . . . . . . . . . . . . .. . . . . . . </B>18</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>5. <B>Présentationdu programme . . . . . . . . . . . . . . . .</B> 19</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>5.1 Classes<B> . . . . . . . . . . . . . . . . . . . . . . . . . . . .. </B> 19</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>5.2 Liste de fichiers<B> . . . . . . . . . . . . . . . . . . . . . . ..</B> 20</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>6. <B>Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . .</B> 21</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>A.1 <B>Tables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . </B>22</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>A.2 <B>Références . . . . . . . . . . . . . . . . . . . . . . . . . . .</B> 24</FONT></FONT></P><P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>1.<U>Codes de Reed-Solomon</U></B></FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=6><B>1.1<U>Définition</U></B></FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> Lescodes de Reed-Solomon RS(k,t) sont formés de n symboles, avecn = q - 1 au maximum et q = 2</FONT><SUP>k</SUP><FONT SIZE=4>, chaquesymbole appartenant à GF(q) qui est le corps de Galois (GaloisField) à q éléments, k représente donc lenombre de bits par symbole. Le nombre t représente le nombrede symboles d’erreurs que ce code sera capable de corriger.</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=6><B>1.2<U>Information</U></B></FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> Lenombre de symboles de contrôle est de 2t. Par conséquent,le nombre de symboles d’information que l’on peut transmettre est de m = n - 2t.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=6><B>1.3<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> Soitle code RS(4,3) formé de n = 15 symboles, chaque symbole étantcontenu dans GF(16), donc 4 bits par symbole. Soit sous formepolynômiale :</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4><B> </B>w(x)= w</FONT><FONT SIZE=2><SUB>14</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>14</SUP></FONT><FONT SIZE=4>+ w</FONT><FONT SIZE=2><SUB>13</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>13</SUP></FONT><FONT SIZE=4>+ ... + w</FONT><FONT SIZE=2><SUB>1</SUB> </FONT><FONT SIZE=4>. x</FONT><FONT SIZE=2><SUP>1</SUP></FONT><FONT SIZE=4>+ w</FONT><FONT SIZE=2><SUB>0</SUB></FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> avecw</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4> contenu dansGF(16) pour i = 0,..,14.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4>Lescoefficients w</FONT><FONT SIZE=2><SUB>0</SUB>,</FONT><FONT SIZE=4>w</FONT><FONT SIZE=2><SUB>1</SUB>,</FONT><FONT SIZE=4>...</FONT><FONT SIZE=2>,</FONT><FONT SIZE=4>w</FONT><FONT SIZE=2><SUB>5</SUB></FONT><FONT SIZE=4>sont les symboles du contrôle de parité (parity check),et les coefficients w</FONT><FONT SIZE=2><SUB>6</SUB>,</FONT><FONT SIZE=4>w</FONT><FONT SIZE=2><SUB>7</SUB>,</FONT><FONT SIZE=4>...</FONT><FONT SIZE=2>,</FONT><FONT SIZE=4>w</FONT><FONT SIZE=2><SUB>14</SUB></FONT><FONT SIZE=4>représente les symboles d’information àtransmettre.</FONT></FONT></P><P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>2.<U>Corps de Galois</U></B></FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> Lanotation pour la suite, sera la suivante :</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> - Freprésente un corps fini (Field).</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> - F</FONT><FONT SIZE=2><SUB>p</SUB></FONT><FONT SIZE=4>représente le corps fini à p éléments.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> - F</FONT><SUP>*</SUP><FONT SIZE=4>représente le groupe multiplicatif du corps F.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=6><B>2.1<U>Propriétés d’un corps fini</U></B></FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> Onrappelle ici, quelques propriétés utiles des corpsfinis. Soit F un corps fini de caractéristique p ayant qéléments. Alors,</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> a) Fest un F</FONT><FONT SIZE=2><SUB>p</SUB></FONT><FONT SIZE=4>-espacevectoriel de dimension k, avec q = p</FONT><SUP>k</SUP><FONT SIZE=4>.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> b) Legroupe additif de F est isomorphe au groupe (Z/pZ,+)</FONT><SUP>k</SUP><FONT SIZE=4>.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> c) F</FONT><FONT SIZE=2><SUP>*</SUP></FONT><FONT SIZE=4>est cyclique d’ordre q - 1 = p</FONT><SUP>k<FONT SIZE=4> </FONT></SUP><FONT SIZE=4>-1.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> d) Tout élément x de F</FONT><FONT SIZE=2><SUP>*</SUP></FONT><FONT SIZE=4>vérifie x</FONT><SUP>q-1</SUP><FONT SIZE=4> = 1.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial"><B>Commentaire: </B>Le point c) nous affirme qu’il existe un élément</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">, dit primitif,qui engendre le groupe multiplicatif F</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUP>*</SUP></FONT><FONT SIZE=4>.Le point a) nous dit que F est un espace vectoriel de dimension k surle corps F</FONT><FONT SIZE=2><SUB>p</SUB></FONT><FONT SIZE=4>, lechoix d’une base sera généralement les puissanceentière de l’élément primitif, soit 1,</FONT></FONT><FONT SIZE=4><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><FONT FACE="Arial"><SUP>3</SUP><FONT SIZE=4>,..., </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>k-1</SUP><FONT SIZE=4>.Un élément c de F s’écrira alors de lamanière suivante :</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> c =c</FONT><SUB><FONT SIZE=2>k-1 . </FONT></SUB></FONT><SUB><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT></SUB><FONT FACE="Arial"><SUP><FONT SIZE=2>k-1</FONT><FONT SIZE=4></FONT></SUP><FONT SIZE=4>+ ... + c</FONT><FONT SIZE=2><SUB>1</SUB></FONT><FONT SIZE=4>. </FONT></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><FONT SIZE=2><SUP>1</SUP></FONT><FONT SIZE=4>+ c</FONT><FONT SIZE=2><SUB>0 </SUB></FONT><FONT SIZE=4>. 1</FONT></FONT></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> avecc</FONT><FONT SIZE=2><SUB>i</SUB></FONT><FONT SIZE=4> appartenant àF</FONT><FONT SIZE=2><SUB>p</SUB></FONT><FONT SIZE=4> pour i =0,..,k-1.</FONT></FONT></P><P STYLE="margin-bottom: 0in; page-break-before: always"><FONT FACE="Arial"><FONT SIZE=6><B>2.2<U>Construction d’un corps fini</U></B></FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT FACE="Arial"><FONT SIZE=4> Laconstruction d’un corps fini est basée sur le théorèmesuivant :</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial"><B>Théorème:</B> Soit </FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial"> unnombre algébrique sur F. Soit k le degré de sonpolynôme irréductible sur F. L’espace vectorielengendré sur F par 1,</FONT><FONT FACE="Symbol">a</FONT><FONT FACE="Arial">, </FONT><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>2<FONT SIZE=2>,..., </FONT></SUP></FONT><FONT SIZE=4><FONT FACE="Symbol">a</FONT></FONT><FONT FACE="Arial"><SUP>k-1</SUP><FONT SIZE=4>est alors un corps, et la dimension de cet espace vectoriel est k.</FONT></FONT></P><P STYLE="margin-bottom: 0in"><BR></P><P STYLE="margin-bottom: 0in"><FONT SIZE=4><FONT FACE="Arial">Cethéorème nous donne une méthode pour construireun corps avec une base donnée, mais ne nous donne pas de⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -