📄 rs.ps
字号:
2.584 .258( est cyclique d\325ordre q - 1 = p)Jf187 sf0 -4 rm.955(k)A0 4 rmf93 sf0 -4 rm.563 .056( )J0 4 rm2.477 .248(- 1.)J47 391 :M.857 .086( d\))J82 391 :M3.421 .342(Tout \216l\216ment x de F)Jf148 sf0 -3 rm.631(*)A0 3 rmf93 sf2.817 .282( v\216rifie x)Jf187 sf0 -4 rm.937(q-1)A0 4 rmf93 sf1.867 .187( = 1.)J47 429 :Mf122 sf4.227 .423(Commentaire : )Jf93 sf2.969 .297(Le point c\) nous affirme qu\325il existe un \216l\216ment )Jf221 sf1.198(a)Af93 sf.998 .1(, )J47 448 :M5.834 .583(dit )J75 448 :M6.562 .656(primitif, qui engendre le groupe multiplicatif)J415 448 :M2.118 .212( F)Jf148 sf0 -3 rm.795(*)A0 3 rmf93 sf1.445 .144(. )J446 448 :M3.702 .37(Le point a\) )J47 467 :M2.059 .206(nous dit que )J140 467 :M2.793 .279(F est un espace vectoriel de dimension k sur l)J474 467 :M2.305 .23(e corps )J47 486 :M.958(F)Af148 sf0 2 rm.623(p)A0 -2 rmf93 sf2.62 .262(, le choix d\325une base sera g\216n\216ralement les puissance enti\217re de )J47 509 :M8.634 .863(l\325\216l\216ment primitif, soit)J221 509 :M3.3 .33( 1,)Jf221 sf2.341(a)Af93 sf1.462 .146( , )J269 509 :Mf221 sf1.047(a)Af187 sf0 -4 rm.822(2)A0 4 rmf93 sf.799 .08(, )Jf221 sf1.047(a)Af187 sf0 -4 rm.822(3)A0 4 rmf93 sf1.291 .129(, ..., )J346 509 :Mf221 sf1.408(a)Af187 sf0 -4 rm.921(k-1)A0 4 rmf93 sf4.242 .424(. Un \216l\216ment)J473 509 :M2.863 .286( c de F )J47 528 :M3.157 .316(s\325\216crira alors de la mani\217re suivante :)J76 571 :M1.03 .103(c = c)Jf148 sf0 2 rm.735 .073(k-1 . )J0 -2 rmf221 sf0 3 rm.73(a)A0 -3 rmf148 sf0 -3 rm.398(k-1)A0 3 rmf93 sf0 -4 rm.304 .03( )J0 4 rm.869 .087(+ ... + c)Jf148 sf0 2 rm.478(1)A0 -2 rm.217 .022( )Jf93 sf.557 .056(. )Jf221 sf.73(a)Af148 sf0 -3 rm.478(1)A0 3 rmf93 sf.822 .082( + c)Jf148 sf0 2 rm.597 .06(0 )J0 -2 rmf93 sf1.115 .111(. 1)J76 592 :M2.648 .265(avec c)Jf148 sf0 2 rm.232(i)A0 -2 rmf93 sf2.339 .234( appartenant \210 F)Jf148 sf0 2 rm.582(p)A0 -2 rmf93 sf1.833 .183( pour i = 0,..,k-1.)JgRgS 47 761 481 13 rCgRgS 11 725 553 49 rC261 771 :Mf135 sf.413 .041(Page )Jf148 sf(3)SgRendpshowpage%%Page: 4 4%%BeginPageSetupinitializepage(Benjamin Barras; page: 4 of 24)setjob%%EndPageSetupgS 0 0 576 820 rC47 46 481 728 rC47 46 481 714 rCgRgS 11 10 553 750 rC47 65 :Mf161 sf5.76 .576(2.2 )Jf174 sf24 u174 :p324.602 :m10.116 1.012(Construction d\325un corps fini)J95 103 :Mf93 sf4.463 .446(La construction d\325un corps fini est bas\216e sur le th\216or\217me )J47 122 :M3.218 .322(suivant :)J47 160 :Mf122 sf6.075 .607(Th\216or\217me :)J138 160 :Mf93 sf1.593 .159( Soit )Jf221 sf1.103(a)Af93 sf2.452 .245( un nombre alg\216brique sur F. Soit k le degr\216 de )J47 179 :M4.189 .419(son polyn\231me irr\216ductible sur F. L\325espace vectoriel engendr\216 sur )J47 200 :M2.739 .274(F par 1,)Jf221 sf1.351(a)Af93 sf.844 .084( , )J130 200 :Mf221 sf1.799(a)Af187 sf0 -4 rm1.413(2)A0 4 rmf148 sf0 -3 rm1.526 .153(, ..., )J0 3 rmf221 sf1.799(a)Af187 sf0 -4 rm1.177(k-1)A0 4 rmf93 sf3.883 .388( est alors un corps, et la dimension de cet )J47 219 :M4.421 .442(espace vectoriel est k.)J47 257 :M4.32 .432(Ce th\216or\217me nous donne une m\216thode pour construire un corps )J47 276 :M2.993 .299(avec une base donn\216e, mais ne nous donne pas de m\216thode pour )J47 295 :M6.682 .668(trouver un \216l\216ment primitif, )Jf221 sf2.931 .293(a )J286 295 :Mf93 sf5.235 .524(n\325est pas forc\216ment un \216l\216ment )J47 314 :M1.638(primitif.)A47 357 :Mf161 sf7.574 .757(2.2.1 )Jf174 sf24 u174 :p330.574 :m12.728 1.273(Repr\216sentation des \216l\216ments)J95 395 :Mf93 sf5.736 .574(Il existe principalement deux m\216thodes pour repr\216senter )J47 414 :M3.118 .312(les \216l\216ments d\325un corps fini, soit :)J76 452 :M1.07 .107(i\) F)Jf187 sf0 3 rm.618 .062(q )J0 -3 rmf93 sf1.389 .139(est un F)J167 454 :Mf148 sf.801(p)Af93 sf0 -2 rm3.399 .34(-espace vectoriel de dimension k, on choisit une )J0 2 rm76 474 :M5.604 .56(certaine base {b)J201 477 :Mf187 sf1.38(1)Af93 sf0 -3 rm.939(,...,b)A0 3 rmf187 sf1.242(k)Af93 sf0 -3 rm4.116 .412(} de cet espace et on rep\217re chaque )J0 3 rm76 496 :M2.879 .288(\216l\216ment de F)Jf187 sf0 3 rm.752(q)A0 -3 rmf93 sf2.761 .276( par ses composantes sur cette base.)J75 537 :M2.173 .217(ii\) On prend un \216l\216ment )J248 537 :Mf221 sf1.106(a)Af93 sf1.662 .166( de F)Jf148 sf0 -3 rm.507(*)A0 3 rmf93 sf2.558 .256( qui engendre ce groupe et tout )J75 556 :M4.114 .411(\216l\216ment non nul de F)Jf187 sf0 3 rm1.252(q)A0 -3 rmf93 sf4.06 .406( s\325\216crit d\325une mani\217re, et d\325une seule, )J75 580 :M1.707 .171(sous la forme )Jf221 sf.726(a)Af187 sf0 -4 rm.854(m)A0 4 rmf93 sf1.712 .171(, avec m = 0,...,q-1.)J47 618 :M4.173 .417(Pour d\216crire un \216l\216ment du corps, on utilisera exclusivement la )J47 637 :M4.429 .443(premi\217re repr\216sentation, car elle permet d\325associer un nombre \210 )J47 656 :M4.767 .477(chaque \216l\216ment du corps. Mais on prendra soin de tabuler ces )J47 675 :M3.744 .374(deux repr\216sentations, la raison en est que la repr\216sentation i\) se )J47 694 :M5.774 .577(pr\220te tr\217s bien pour l\325addition et que la repr\216sentation ii\) est )J47 713 :M4.55 .455(bien adapt\216e pour la multiplication. Comme on a besoin de ces )J47 732 :M3.938 .394(deux op\216rations, on travaillera avec ces deux repr\216sentations qui )J47 751 :M3.743 .374(seront tabul\216es une fois pour toute.)JgRgS 47 761 481 13 rCgRgS 11 725 553 49 rC261 771 :Mf135 sf.413 .041(Page )Jf148 sf(4)SgRendpshowpage%%Page: 5 5%%BeginPageSetupinitializepage(Benjamin Barras; page: 5 of 24)setjob%%EndPageSetupgS 0 0 576 820 rC47 46 481 728 rC47 46 481 714 rCgRgS 11 10 553 750 rC47 60 :Mf122 sf9.548 .955(Avertissement :)Jf93 sf.884 .088( )J186 60 :M3.301 .33(On ne s\325int\216ressera, par la suite, que de corps )J47 79 :M5.914 .591(finis de caract\216ristique 2, qui sont les seuls utilis\216s pour les )J47 98 :M3.598 .36(codes de Reed-Solomon.)J47 141 :Mf161 sf6.524 .652(2.2.2 )Jf174 sf24 u174 :p99.252 :m2.587(Exemple)A95 179 :Mf93 sf3.32 .332(Soit F)J139 182 :Mf187 sf1.141(2)Af93 sf0 -3 rm2.191 .219( = {0,1} )J0 3 rm207 179 :M3.539 .354(le corps \210 deux \216l\216ments. On v\216rifie que le )J47 203 :M3.657 .366(polyn\231me P\(x\) = x)Jf187 sf0 -4 rm1.013(2)A0 4 rmf93 sf2.503 .25( + x + 1 est bien irr\216ductible sur F)Jf187 sf0 3 rm1.013(2)A0 -3 rmf93 sf2.09 .209(. Soit )J489 203 :Mf221 sf.17(a)Af93 sf.26 .026( une )J47 225 :M2.354 .235(racine de P\(x\), on aura alors)J47 265 :M.57 .057( P\()Jf221 sf.86 .086(a\) = a)Jf187 sf0 -4 rm.419(2)A0 4 rmf93 sf.436 .044( + )Jf221 sf.534(a)Af93 sf.538 .054( + 1 = 0 donc )Jf221 sf.534(a)Af187 sf0 -4 rm.419(2)A0 4 rmf93 sf.436 .044( = )Jf221 sf.534(a)Af93 sf.648 .065( + 1)J47 303 :M3.068 .307(ce qui veut dire que l\325espace vectoriel engendr\216 sur F)Jf187 sf0 3 rm.887(2)A0 -3 rmf93 sf1.954 .195( par 1,)Jf221 sf1.129(a)Af93 sf1.466 .147( est )J47 325 :M3.68 .368(alors un corps, et la dimension de cet espace vectoriel est de 2. )J47 344 :M2.807 .281(Le corps \210 4 \216l\216ments sera alors F)J301 347 :Mf187 sf.833(4)Af93 sf0 -3 rm2.035 .203( = {0,1,)J0 3 rm361 344 :Mf221 sf.865 .087(a , a + 1)J416 344 :Mf93 sf2.597 .26(}. Si l\325on choisit )J47 366 :M.648({1,)Af221 sf1.009(a)Af93 sf2.696 .27(} comme base, la repr\216sentation i\) sera la suivante :)J69 404 :M(0)S125 404 :M1.676 .168(= 0.)Jf221 sf.839(a)Af93 sf1.333 .133( + 0.1 = \(0,0\) = 0)J69 423 :M(1)S125 423 :M1.676 .168(= 0.)Jf221 sf.839(a)Af93 sf1.333 .133( + 1.1 = \(0,1\) = 1)J69 442 :Mf221 sf.607 .061(a )J125 442 :Mf93 sf1.676 .168(= 1.)Jf221 sf.839(a)Af93 sf1.333 .133( + 0.1 = \(1,0\) = 2)J69 461 :Mf221 sf.39(a)Af93 sf.474 .047( + 1)J125 461 :M1.676 .168(= 1.)Jf221 sf.839(a)Af93 sf1.333 .133( + 1.1 = \(1,1\) = 3)J47 499 :M10.838 1.084(Cette repr\216sentation est tr\217s pratique, car elle permet )J47 518 :M2.764 .276(d\325associer un nombre \210 chaque \216l\216ment.)J47 537 :M5.973 .597(Si l\325on avait choisit {1,)J227 537 :Mf221 sf2.498(a)Af93 sf3.036 .304( + 1)J271 537 :M3.72 .372(} )J285 537 :M5.438 .544(comme base, on aurait alors la )J47 556 :M5.365 .537(repr\216sentation suivante :)J69 594 :M(0)S125 594 :M1.911 .191(= 0.\()Jf221 sf.857(a)Af93 sf1.309 .131( + 1\) + 0.1 = \(0,0\) = 0)J69 613 :M(1)S125 613 :M1.911 .191(= 0.\()Jf221 sf.857(a)Af93 sf1.309 .131( + 1\) + 1.1 = \(0,1\) = 1)J69 632 :Mf221 sf.39(a)Af93 sf.474 .047( + 1)J125 632 :M1.911 .191(= 1.\()Jf221 sf.857(a)Af93 sf1.309 .131( + 1\) + 0.1 = \(1,0\) = 2)J69 651 :Mf221 sf.084(a)Af93 sf( )S125 651 :M1.911 .191(= 1.\()Jf221 sf.857(a)Af93 sf1.309 .131( + 1\) + 1.1 = \(1,1\) = 3)J47 689 :M3.654 .365(On comprend facilement que le choix de la base est fondamental )J47 708 :M3.008 .301(pour savoir de quoi l\325on parle.)JgRgS 47 761 481 13 rCgRgS 11 725 553 49 rC261 771 :Mf135 sf.413 .041(Page )Jf148 sf(5)SgRendpshowpage%%Page: 6 6%%BeginPageSetupinitializepage(Benjamin Barras; page: 6 of 24)setjob%%EndPageSetupgS 0 0 576 820 rC47 46 481 728 rC47 46 481 714 rCgRgS 11 10 553 750 rC47 60 :Mf93 sf5.544 .554(Pour effectuer une addition sur ce corps, il faut voir que l\325on )J47 79 :M7.216 .722(additionne en fait deux vecteurs, et donc que l\325on effectue )J47 98 :M5.566 .557(l\325addition composante par composante, et ceci sur F)Jf187 sf0 3 rm1.388(2)A0 -3 rmf93 sf3.117 .312(. Soit par )J47 120 :M1.135(exemple,)A69 177 :M1.228 .123(\(0,1\) + \(0,1\) = \(0 + 0,1 + 1\) = \(0,0\) -> 1 + 1 = 0)J69 196 :M1.228 .123(\(1,1\) + \(1,0\) = \(1 + 1,1 + 0\) = \(0,1\) -> 3 + 2 = 1)J69 215 :M1.228 .123(\(1,1\) + \(0,1\) = \(1 + 0,1 + 1\) = \(1,0\) -> 3 + 1 = 2)J69 234 :M1.228 .123(\(0,1\) + \(1,0\) = \(0 + 1,1 + 0\) = \(1,1\) -> 1 + 2 = 3)J47 291 :M3.459 .346(Sur un corps de caract\216ristique 2, l\325addition revient \210 faire un )Jf122 sf3.3 .33(OU )J47 310 :M4.669 .467(EXCLUSIF \(notation ^\))Jf93 sf3.23 .323( entre deux nombres. Soit par exemple,)J47 367 :M1.008 .101( 3 + 2 = 11 ^ 10 = 01 = 1)J47 386 :M1.008 .101( 3 + 1 = 11 ^ 01 = 10 = 2)J47 443 :M6.098 .61(Cela nous donne une op\216ration assez simple \210 r\216aliser et \210 )J47 462 :M3.997 .4(impl\216menter dans un programme.)J47 500 :M4.069 .407(Pour la multiplication, il nous faut trouver un \216l\216ment primitif qui )J47 521 :M5.748 .575(g\216n\217re le groupe F)J198 524 :Mf187 sf1.569(4)A0 -7 rm1.097(*)A0 7 rmf93 sf0 -3 rm5.427 .543(. Dans notre exemple, )J0 3 rm393 521 :Mf221 sf2.483(a)Af93 sf5.294 .529( est un \216l\216ment )J47 543 :M6.352 .635(primitif, en effet)J69 602 :Mf221 sf.689(a)Af187 sf0 -4 rm(0)S0 4 rm112 602 :Mf93 sf(=)S146 602 :M(1)S69 623 :Mf221 sf.689(a)Af187 sf0 -4 rm(1)S0 4 rm112 623 :Mf93 sf(=)S146 623 :Mf221 sf(a)S69 644 :M.689(a)Af187 sf0 -4 rm(2)S0 4 rm112 644 :Mf93 sf(=)S146 644 :Mf221 sf.39(a)Af93 sf.474 .047( + 1)J47 701 :M2.95 .295(ce qui nous donne les trois \216l\216ments de notre groupe.)JgRgS 47 761 481 13 rCgRgS 11 725 553 49 rC261 771 :Mf135 sf.413 .041(Page )Jf148 sf(6)SgRendpshowpage%%Page: 7 7%%BeginPageSetupinitializepage(Benjamin Barras; page: 7 of 24)setjob%%EndPageSetupgS 0 0 576 820 rC47 46 481 728 rC47 46 481 714 rCgRgS 11 10 553 750 rC47 60 :Mf93 sf6.75 .675(Si l\325on prend {1,)J181 60 :Mf221 sf2.906(a)Af93 sf6.646 .665(} comme base, on aura alors la table de )J47 79 :M5.575 .557(multiplication suivante :)J47 136 :M1.183 .118( 1 * 1 = 1)J47 155 :M1.056 .106( 1 * 2 = 1 * )Jf221 sf1.147(a)Af93 sf.937 .094( = )Jf221 sf1.147(a)Af93 sf1.394 .139( = 2)J47 174 :M.956 .096( 1 * 3 = 1 * \()Jf221 sf.987(a)Af93 sf1.149 .115( + 1)Jf221 sf.52<29>Af93 sf.806 .081( = )Jf221 sf.987(a)Af93 sf1.174 .117( + 1 = 3)J47 193 :M1.334 .133( 2 * 1 = 1 * 2 = 2)J47 214 :M.88 .088( 2 * 2 = )Jf221 sf.996(a)Af93 sf.674 .067( * )Jf221 sf.996(a)Af93 sf.814 .081( = )Jf221 sf.996(a)Af187 sf0 -4 rm.783(2)A0 4 rmf93 sf.814 .081( = )Jf221 sf.996(a)Af93 sf1.185 .118( + 1 = 3)J47 235 :M.727 .073( 2 * 3 = )Jf221 sf.823(a)Af93 sf.722 .072( * \()Jf221 sf.823(a)Af93 sf.958 .096( + 1)Jf221 sf.434<29>Af93 sf.672 .067( = )Jf221 sf.823(a)Af187 sf0 -4 rm.646(2)A0 4 rmf93 sf.672 .067( + )Jf221 sf.958 .096(a )Jf93 sf.672 .067( = )Jf221 sf.823(a)Af93 sf.818 .082( + 1 + )Jf221 sf.823(a)Af93 sf1 .1( = 1)J47 254 :M1.334 .133( 3 * 1 = 1 * 3 = 3)J47 273 :M1.334 .133( 3 * 2 = 2 * 3 = 1)J47 294 :M.795 .079( 3 * 3 = \()Jf221 sf.838(a)Af93 sf.932 .093( + 1\) * \()Jf221 sf.838(a)Af93 sf.912 .091( + 1\) = )Jf221 sf.838(a)Af187 sf0 -4 rm.658(2)A0 4 rmf93 sf.685 .068( + )Jf221 sf.838(a)Af93 sf.685 .068( + )Jf221 sf.838(a)Af93 sf.834 .083( + 1 = )Jf221 sf.838(a)Af187 sf0 -4 rm.658(2)A0 4 rm.851 .085( +)Jf93 sf.779 .078( 1 = )Jf221 sf.838(a)Af93 sf1.019 .102( = 2)J47 351 :M4.01 .401(ce qui termine notre exemple.)JgRgS 47 761 481 13 rCgRgS 11 725 553 49 rC261 771 :Mf135 sf.413 .041(Page )Jf148 sf(7)SgRendpshowpage%%Page: 8 8%%BeginPageSetupinitializepage(Benjamin Barras; page: 8 of 24)setjob%%EndPageSetupgS 0 0 576 820 rC47 46 481 728 rC47 46 481 714 rCgRgS 11 10 553 750 rC47 65 :Mf161 sf4.125 .412(3. )Jf174 sf24 u174 :p234.537 :m10.864 1.086(Technique de codage)J95 103 :Mf93 sf3.611 .361(Consid\216rons un code de Reed-Solomon avec ses symboles )J47 124 :M3.941 .394(dans GF\(2)Jf187 sf⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -