{VERSION 5 0 "IBM INTEL LINUX" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "" -1 256 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 1 2 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 267 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 272 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 1 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 277 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 282 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 287 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 292 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 297 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 299 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 302 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 304 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 305 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 306 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 307 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 308 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 309 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 310 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 311 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 312 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 313 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 314 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 315 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 316 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 317 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 318 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 319 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 320 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 321 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 322 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 323 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 324 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 325 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 327 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 328 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 329 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 330 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 331 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 332 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 333 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 334 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 335 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 336 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 337 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 338 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 339 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 340 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 341 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 342 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 343 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 344 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 345 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 346 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 347 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 348 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 349 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 350 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 351 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 352 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 353 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 354 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 355 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 356 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 357 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 358 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 359 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 360 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 361 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 362 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 363 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 364 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 365 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 366 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 367 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 368 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 369 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 370 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 371 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 372 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 373 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 374 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 375 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 376 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 377 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 378 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 379 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 380 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1 " -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 257 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 258 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 259 1 {CSTYLE "" -1 -1 "T imes" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } } {SECT 0 {PARA 258 "" 0 "" {TEXT -1 9 "CODES BCH" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 259 "" 0 "" {TEXT -1 385 "Le but de cette feuill e est de fabriquer un code BCH (binaire primitif), et de faire tourner son algorithme de d\351codage bas\351 sur l'algorithme d'Euclide. La \+ r\351f\351rence recommand\351e est le livre de Demazure : Cours d'alg \350bre, editions Cassini, chapitre 9.\nTous les calculs se font modul o 2. Il est conseill\351 de consulter l'aide de Maple sur \"mod\" si l 'on ne sait pas comment \347a fonctionne." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 49 "Cr\351ation du code. Corps engendr\351 pa r les racines " }{TEXT 256 1 "n" }{TEXT -1 21 "-\350mes de l'unit\351 \+ sur " }{TEXT 257 1 "F" }{TEXT -1 3 "_2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT 258 20 "On fixe la longueur " }{TEXT 259 1 "n" }{TEXT 260 19 " du code. L'entier " }{TEXT 274 1 "n" }{TEXT 275 19 " est de la forme 2^" }{TEXT 261 1 "r" }{TEXT 262 3 "-1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 322 8 "Choisir " }{TEXT 323 1 "r" } {TEXT 336 24 " pour fixer la longueur " }{TEXT 337 1 "n" }{TEXT 338 8 " du code" }{TEXT 335 1 "." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "r:= 7: n:=2^r-1;" }}}{PARA 0 "" 0 "" {TEXT -1 8 "Un mot " }{TEXT 263 2 "a_" }{TEXT -1 1 "1" }{TEXT 269 7 "...a_n " }{TEXT -1 62 "(cod \351 comme une liste) est identifi\351 \340 l' \351l\351ment du quotie nt " }{TEXT 264 1 "F" }{TEXT -1 3 "_2[" }{TEXT 265 1 "X" }{TEXT -1 3 " ]/(" }{TEXT 266 1 "X" }{TEXT -1 1 "^" }{TEXT 267 2 "n " }{TEXT -1 31 " -1) represent\351 par le polynome\n" }{TEXT 268 1 "a" }{TEXT -1 3 "_1 \+ " }{TEXT 270 1 "X" }{TEXT -1 2 "^\{" }{TEXT 271 1 "n" }{TEXT -1 13 " - 1\} + ... + " }{TEXT 272 1 "a" }{TEXT -1 1 "_" }{TEXT 273 1 "n" } {TEXT -1 163 " (N.B. : Demazure \351crit le polynome dans l'ordre des puissances croissantes). \nDeux proc\351dures tr\350s simples permett ent de passer du mot au polynome et vice-versa." }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 57 "Pol:=proc(M,n,X)\nlocal k;\nadd(M[k]*X^(n-k), \+ k=1..n);\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "Mot:=proc (P,n,X)\nlocal i;\n[seq(coeff(P,X,n-i),i=1..n)];\nend;" }}}{PARA 0 "" 0 "" {TEXT -1 12 "Le polynome " }{TEXT 276 1 "X" }{TEXT -1 1 "^" } {TEXT 278 1 "n" }{TEXT -1 30 " -1 se d\351compose sur le corps " } {TEXT 281 1 "F" }{TEXT -1 4 "_\{2^" }{TEXT 282 1 "r" }{TEXT -1 54 "\}, dont le groupe multiplicatif est celui des racines " }{TEXT 277 1 "n " }{TEXT -1 71 "-\350mes de l'unit\351. Les calculs de d\351codage von t se faire dans ce corps " }{TEXT 283 1 "F" }{TEXT -1 4 "_\{2^" } {TEXT 284 1 "r" }{TEXT -1 61 "\}. Pour pouvoir calculer, on va choisi r un \351l\351ment primitif " }{TEXT 279 5 "alpha" }{TEXT -1 23 " (une racine primitive " }{TEXT 280 1 "n" }{TEXT -1 41 "-\350me de l'unit \351). Le polynome minimal de " }{TEXT 285 5 "alpha" }{TEXT -1 54 " es t un facteur irr\351ductible du polynome cyclotomique " }{TEXT 324 5 " Phi_n" }{TEXT -1 5 " sur " }{TEXT 286 1 "F" }{TEXT -1 23 "_2, forc\351 ment de degr\351 " }{TEXT 325 1 "r" }{TEXT -1 69 ". On produit d'abord la liste de tous les facteurs irreductibles de " }{TEXT 326 5 "Phi_n " }{TEXT -1 5 " sur " }{TEXT 287 1 "F" }{TEXT -1 3 "_2." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "Prim:=[op(Factor(numtheory[cyclotom ic](n,X)) mod 2)];" }}}{PARA 0 "" 0 "" {TEXT -1 22 "On choisit un fact eur " }{TEXT 288 1 "P" }{TEXT -1 10 " de degr\351 " }{TEXT 289 1 "r" } {TEXT -1 14 " dans la liste" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 327 8 "Choisir " }{TEXT 328 1 "P" }{TEXT 340 25 " (le polynome minimal de " }{TEXT 341 5 "alpha" }{TEXT 342 1 ")" }{TEXT 339 2 ". " }{TEXT -1 33 "La proc\351dure suivante choisit un " }{TEXT 347 1 "P" }{TEXT -1 66 " avec un nombre minimum de termes de fa\347on \340 all\351ger \+ les calculs." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 94 "P:=Prim[1]: \nfor i from 2 to nops(Prim) do \nif nops(Prim[i]) " 0 "" {MPLTEXT 1 0 23 "alias(alph a=RootOf(P));" }}}{PARA 0 "" 0 "" {TEXT -1 45 "On fixe maintenant la c apacit\351 de correction " }{TEXT 292 1 "t" }{TEXT -1 53 " du code BCH (il sera de distance minimum prescrite 2" }{TEXT 293 1 "t" }{TEXT -1 6 "+1). \n" }{TEXT 329 8 "Choisir " }{TEXT 330 1 "t" }{TEXT 344 59 " \+ pour fixer la distance de capacit\351 de correction du code" }{TEXT 343 1 "." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "t:=5;" }}}{PARA 0 "" 0 "" {TEXT -1 28 "Par d\351finition, un polynome " }{TEXT 304 1 " C" }{TEXT -1 42 " appartiendra au code si et seulement si " }{TEXT 305 1 "C" }{TEXT -1 1 "(" }{TEXT 294 5 "alpha" }{TEXT -1 1 "^" }{TEXT 295 1 "i" }{TEXT -1 9 ")=0 pour " }{TEXT 296 1 "i" }{TEXT -1 8 "=1,... ,2" }{TEXT 297 1 "t" }{TEXT -1 110 ". On \351crit une proc\351dure qui calcule le polynome g\351n\351rateur du code. C'est le ppcm des polyn omes minimaux sur " }{TEXT 310 1 "F" }{TEXT -1 8 "_2 des " }{TEXT 306 5 "alpha" }{TEXT -1 1 "^" }{TEXT 307 1 "i" }{TEXT -1 6 " avec " } {TEXT 308 1 "i" }{TEXT -1 13 " entre 1 et 2" }{TEXT 309 1 "t" }{TEXT -1 54 ". On calcule l'ensemble des facteurs irreductibles de " }{TEXT 298 1 "X" }{TEXT -1 1 "^" }{TEXT 299 1 "n" }{TEXT -1 48 " -1 pour tro uver dedans le polynome minimal de " }{TEXT 300 5 "alpha" }{TEXT -1 1 "^" }{TEXT 301 1 "i" }{TEXT -1 6 " avec " }{TEXT 302 1 "i" }{TEXT -1 13 " entre 3 et 2" }{TEXT 303 1 "t" }{TEXT -1 103 ". Pouvez-vous expli quer pourquoi on fait des pas de 2 dans la proc\351dure suivante ? (Se souvenir que si " }{TEXT 311 5 "beta " }{TEXT -1 47 "est racine d'un \+ polynome \340 coefficients dans " }{TEXT 312 1 "F" }{TEXT -1 10 "_2, alors " }{TEXT 313 4 "beta" }{TEXT -1 16 "^2 l'est aussi.)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 316 "Generateur:=proc(alpha,t,X)\nlocal G, SH, f, i ;\nG:= subs(_Z=X,op(alpha)): #recupere le polynome minima l de alpha\nSH:=\{op(Factor(X^n-1) mod 2)\} minus \{G\}:\nif t>1 then \nfor i from 3 by 2 to 2*t-1 do\nfor f in SH do if Eval(f,X=alpha^i) \+ mod 2 = 0\nthen G:=G*f : SH:=SH minus \{f\} : break fi od\nod\nfi:\nEx pand(G) mod 2;\nend;" }{TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 57 "E t voici le polynome g\351n\351rateur du code, et la dimension " } {TEXT 314 1 "d" }{TEXT -1 9 " du code." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "G:=sort(Generateur(alpha,t,X)); d:= n-degree(G,X);" } }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 36 "D\351codage par l'algorithme d 'Euclide." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "Nous allons maintenan t \351crire les proc\351dures de l'algorithme de d\351codage. " }} {PARA 0 "" 0 "" {TEXT -1 61 "On commence par calculer le \"polynome sy ndrome\" d'un mot re\347u" }{TEXT 380 2 " R" }{TEXT -1 13 " de longueu r " }{TEXT 348 1 "n" }{TEXT -1 20 ". C'est le polynome " }}{PARA 0 "" 0 "" {TEXT 349 1 "S" }{TEXT -1 5 "_1 + " }{TEXT 350 1 "S" }{TEXT -1 3 "_2 " }{TEXT 351 1 "Z" }{TEXT -1 7 " +...+ " }{TEXT 352 1 "S" }{TEXT -1 3 "_\{2" }{TEXT 353 1 "t" }{TEXT -1 2 "\} " }{TEXT 354 1 "Z" } {TEXT -1 3 "^\{2" }{TEXT 355 1 "t" }{TEXT -1 8 "-1\}, o\371 " }{TEXT 356 1 "S" }{TEXT -1 1 "_" }{TEXT 357 1 "i" }{TEXT -1 3 " = " }{TEXT 358 1 "R" }{TEXT -1 1 "(" }{TEXT 359 5 "alpha" }{TEXT -1 1 "^" }{TEXT 360 1 "i" }{TEXT -1 2 ")." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 91 "Syndi:=proc(P,i,alpha)\nlocal beta;\nbeta:=Normal(alpha^i) mod 2: \nEval(P, X=beta) mod 2;\nend;" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 104 "Syndrome:=proc(R,alpha,t,n,X,Z)\nlocal i,P;\nP: =Pol(R,n,X):\nadd(Syndi(P,i,alpha)*Z^(i-1), i=1..(2*t))\nend;" }{TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 84 "On calcule ensuite le polynome localisateur d'erreurs \340 partir du polynome syndrome " }{TEXT 361 1 "S" }{TEXT -1 43 ", en utilisant l'algorithme d'Euclide avec " } {TEXT 362 3 "\nP_" }{TEXT -1 2 "0 " }{TEXT 371 4 "= Z" }{TEXT -1 3 "^ \{2" }{TEXT 363 1 "t" }{TEXT -1 5 "\} et " }{TEXT 364 2 "P_" }{TEXT -1 1 "1" }{TEXT 372 5 " = S " }{TEXT -1 43 "et en s'arretant d\350s qu e le degr\351 du reste " }{TEXT 366 4 "P_i " }{TEXT -1 18 "est plus pe tit que" }{TEXT 367 1 " " }{TEXT -1 0 "" }{TEXT 365 2 "t." }{TEXT -1 69 " C'est l'algorithme d'Euclide \"semi-\351tendu\": ce qu'on cherche est le " }{TEXT 375 4 "B_i " }{TEXT -1 6 "dans \n" }{TEXT 370 4 "P_i \+ " }{TEXT -1 2 "= " }{TEXT 368 7 "A_i * Z" }{TEXT -1 3 "^\{2" }{TEXT 369 1 "t" }{TEXT -1 4 "\} + " }{TEXT 373 4 "B_i " }{TEXT -1 2 "* " } {TEXT 374 1 "S" }{TEXT -1 35 " . Il est donc inutile de calculer " } {TEXT 376 4 "A_i." }{TEXT -1 45 " Le vrai polynome localisateur d'erre urs est " }{TEXT 377 3 "B_i" }{TEXT -1 3 " / " }{TEXT 378 4 "B_i " } {TEXT -1 69 "(0) (voir Demazure), mais il est inutile de diviser par l a constante " }{TEXT 379 3 "B_i" }{TEXT -1 83 " (0) puisqu'on ne s'int eressera qu'aux racines du polynome localisateur d'erreurs." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 218 "Localisateur:=proc(S,t,Z)\n local P, Q, R, BB, B, C;\nP:=Z^(2*t): Q:=S: BB:=0: B:= 1:\nwhile degre e(Q,Z) >= t\ndo C:=BB-B*Quo(P,Q,Z) mod 2 : R:=Rem(P,Q,Z) mod 2:\nP:=Q: Q:=R: BB:=B: B:=C:\nod:\nNormal(collect(B,Z)) mod 2;\nend;" }}}{PARA 0 "" 0 "" {TEXT -1 112 "Enfin, la proc\351dure suivante permet de retr ouver le vecteur d'erreur \340 partir du polynome localisateur. Le bi t " }{TEXT 315 3 "r_i" }{TEXT -1 13 " du mot re\347u " }{TEXT 316 1 "R " }{TEXT -1 31 " est erron\351 si et seulement si " }{TEXT 317 5 "alph a" }{TEXT -1 1 "^" }{TEXT 318 1 "i" }{TEXT -1 113 " est racine du poly nome localisateur d'erreurs. (Si on suit le livre de Demazure, cela se rait si et seulement si " }{TEXT 345 5 "alpha" }{TEXT -1 3 "^(-" } {TEXT 346 1 "i" }{TEXT -1 157 ") est racine; c'est parce que, contrair ement \340 ce qui est fait ici, Demazure identifie un mot \340 un po lynome \351crit dans le sens des puissances croissantes.)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "Testz:=proc(L,i,alpha,Z)\nif Eval(L , Z=alpha^i) mod 2 =0 then 1 else 0 fi;\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "Erreur:=proc(L,alpha,n,Z)\nlocal i;\n[seq(Testz( L,i,alpha,Z),i=1..n)]\nend;" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 7 "E ssais." }}{PARA 0 "" 0 "" {TEXT -1 114 "On va passer \340 des essais. On \351crit un g\351n\351rateur de mots de code au hasard. On multipl ie le polynome g\351n\351rateur " }{TEXT 320 1 "G" }{TEXT -1 38 " par \+ un polynome au hasard de degr\351 < " }{TEXT 319 2 "d " }{TEXT 334 23 "(la dimension du code)." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 117 "Motcode:=proc(G,n,X)\nlocal CC, d;\nd:= n-degree(G,X):\nCC:=Expand((R andpoly(d-1,X) mod 2) * G) mod 2:\nMot(CC,n,X);\nend;" }}}{PARA 0 "" 0 "" {TEXT -1 200 "On \351crit un g\351n\351rateur de vecteurs d'erre urs al\351atoire, en fonction d'un nombre d'erreurs NE. (Le nombre r \351el d'erreurs peut etre moindre si l'on tire au hasard deux fois la meme position d'erreur)." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 108 "Bruit:=proc(NE,n,X)\nlocal BB, EXP, i;\nEXP:=rand(0..(n-1)):\nBB: =add(X^EXP(),i=1..NE) mod 2:\nMot(BB,n,X);\nend;" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 332 28 "Choisir le nombre d'erreurs " }{TEXT 333 3 "NE." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "NE:=5;" }}}{PARA 0 "" 0 "" {TEXT -1 203 "Maintenant on exp\351rimente : on g\351n\350re u n mot de code C au hasard, on y ajoute une erreur al\351atoire B, et o n passe au d\351codage. Normalement, si le poids du \"bruit\" B ajout \351 lors de la transmission est <= " }{TEXT 331 0 "" }{TEXT 321 3 "t, " }{TEXT -1 24 "le d\351codage est correct." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 170 "C:= Motcode(G,n,X);\nB:= Bruit(NE,n,X);\nR:=C+B m od 2;\nS:=Syndrome(R,alpha,t,n,X,Z);\nL:=Localisateur(S,t,Z);\nERR:=Er reur(L,alpha,n,Z);\nDECODE:=R+ERR mod 2;\nevalb(C=DECODE);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "5" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }