|
=== Algorisme de Berlekamp-Massey ===
Un LFSR de taillemida <math>n</math> produisantprodueix dessuccessions suitesrecurrents récurrentes linéaireslineals d'ordre <math>n</math>, lael connaissanceconeixement de <math>n</math> termes consécutifsconsecutius d'uneuna suitesuccessió eti de l'équationequació linéairelineal -- ouo bienbé deel que manièreés équivalenteequivalent ledel polynômepolinomi de rétroactionretroacció -- déterminedetermina toutetota la suitesuccessió.
Si arase nosuposa es creu més conegutdesconegut el polinomi de retroacció, que es pot deduir de l'observació d'una part de la sortida del LFSR ,? per exemple els termes <math>u_{t_0},u_{t_0+1},.,u_{t_0+L-1}</math> ? L'algoritme de Berlekamp-Massey respon a aquesta pregunta de la manera següent : si <math>L</math> és superior ono igual a dues vegades la mida del més petit LFSR generantque genera la successió <math>(u_i)</math> ▼Un LFSR de mida <math>n</math> produint successions recurrents lineals d'ordre <math>n</math>, el coneixement de <math>n</math> termes consecutius d'una successió i de l'equació lineal -- o bé de manera equivalent el polinomi de retroacció -- determina tota la successió.
llavors es poden trobar el polinomi de retroacció i la inicialització del registre. En abreviat Abreviant: tot. Es veu aixíAixí, aparèixerapareix la complexitat lineal com el paràmetre que permet considerar la quantitat d'informació necessària per recrear una successió en forma de LFSR. ▼Si maintenant on ne suppose plus connu le polynôme de rétroaction, que peut-on déduire de l'observation d'une partie de la sortie du LFSR, par exemple les termes <math>u_{t_0},u_{t_0+1},...,u_{t_0+L-1}</math> ? L'algorithme de Berlekamp-Massey répond à cette question de la façon suivante : si <math>L</math> est supérieur où égal à deux fois la taille du plus petit LFSR générant la suite <math>(u_i)</math>
L' algoritmealgorisme de Berlekamp-Massey va ser introduït el 1969 per [[James Massey]] (Massey, J l "Shift-Register Synthesis and BCH Decoding." IEEE Trans. Informació Th. 15, 122-127, 1969.). És una adaptació d'un algoritmealgorisme, de l'a [[Elwyn Berlekamp]], de descodificació de [[codi corrector|codis correctors]] -- els codis de Bose-Chaudhuri-Hocquenghem. ▼▲Si ara no es creu més conegut el polinomi de retroacció, que es pot deduir observació d'una part de la sortida del LFSR, per exemple els termes <math>u_{t_0},u_{t_0+1},.,u_{t_0+L-1}</math> ? L'algoritme de Berlekamp-Massey respon a aquesta pregunta de la manera següent : si <math>L</math> és superior on igual a dues vegades la mida del més petit LFSR generant la successió <math>(u_i)</math>
alors on peut retrouver le polynôme de rétroaction et l'initialisation du registre. En abrégé : tout. On voit ainsi apparaître la complexité linéaire comme le paramètre permettant d'estimer la quantité d'information nécessaire pour recréer une suite sous forme de LFSR.
▲llavors es poden trobar el polinomi de retroacció i la inicialització del registre. En abreviat : tot. Es veu així aparèixer la complexitat lineal com el paràmetre que permet considerar la quantitat d'informació necessària per recrear una successió en forma de LFSR.
L'algorithme de Berlekamp-Massey fut introduit en 1969 par [[James Massey]] (Massey, J. L. "Shift-Register Synthesis and BCH Decoding." IEEE Trans. Information Th. 15, 122-127, 1969.). C'est une adaptation d'un algorithme, du à [[Elwyn Berlekamp]], de décodage de [[code correcteur|codes correcteurs]] -- les codes de Bose-Chaudhuri-Hocquenghem.
▲L'algoritme de Berlekamp-Massey va ser introduït el 1969 per [[James Massey]] (Massey, J l "Shift-Register Synthesis and BCH Decoding." IEEE Trans. Informació Th. 15, 122-127, 1969.). És una adaptació d'un algoritme, de l'a [[Elwyn Berlekamp]], de descodificació de [[codi corrector|codis correctors]] -- els codis de Bose-Chaudhuri-Hocquenghem.
== Utilització ==
| 