Algèbre T1
trois suites r j , u j et v j telles que r j (x)x 2t + u j (x)S(x) = v j (x) pour tout j, à
partir de (r 0 , u 0 , v 0 ) = (1, 0, x 2t ) et (r 1 , u 1 , v 1 ) = (0, 1, S(x)), en effectuant les
divisions euclidiennes v i−1 = v i q i + v i+1 puis les soustractions r i+1 = r i−1 − r i q i
et u i+1 = u i−1 − u i q i jusqu’à obtenir deg v i < t et deg v i−1 t.
Proposition 3. L’algorithme de Berlekamp-Massey donne (à facteur constant près)
le couple (u(x), v(x)) recherché, avec deg u t et deg v < t, vérifiant la
congruence (XV.2).
Démonstration. Comme deg v i+1 < deg v i , la suite (deg v i ) est strictement décroissante pour i 1. Il existe donc j tel que deg v j < t et deg v j−1 t.
On a également deg q i = deg v i−1 − deg v i pour i 1. Regardons la suite
(deg u i ) : on a u 2 = −u 1 q 1 , d’où deg u 2 deg u 1 , puis u 3 = u 1 − u 2 q 2 ,
d’où deg u 3 = deg u 2 + deg q 2 > deg u 2 . On démontre par récurrence que la
suite est strictement croissante à partir de i = 2 : si deg u i > deg u i−1 , alors
deg u i+1 = deg u i + deg q i , donc deg u i+1 > deg u i . On obtient également, en
sommant les égalités deg u i+1 − deg u i = deg q i = deg v i−1 − deg v i , pour i 1 :
deg u j = deg u j − deg u 1 = deg v 0 − deg v j−1 = 2t − deg v j−1 t.
Donc (u j , v j ) répond au problème. De plus, on a pour tout i 1 :
r i
u i
r i+1 u i+1
0
1
1 −q i
=
r i−1 u i−1
r i
u i
,
d’où r i u i+1 − r i+1 u i = −(r i−1 u i − r i u i−1 ) puis r i u i+1 − r i+1 u i = (−1) i par récurrence (i 0). Cela montre que pgcd(r j , u j ) = 1.
Soit maintenant (u, v) la solution recherchée correspondant à l’erreur de décodage : on écrit rx 2t + uS = v. Noter que les polynômes localisateur et évaluateur
d’erreur sont premiers entre eux par définition, donc pgcd(r, u) = 1. On va prouver que r j u = ru j , ce qui implique la proportionalité (dans K[x] puis dans K par
primalité) des deux couples (r, u) et (r j , u j ), donc également de (u, v) et (u j , v j ).
Dans le cas contraire où r j u − ru j = 0, les formules de Cramer pour le système
r j u j
r
u
x 2t
S
=
v j
v
nous donneraient x 2t =
v j u−vu j
r j u−ru j
. Comme
deg(v j u − vu j ) max(deg v j + deg u, deg v + deg u j ) < 2t,
cela est impossible.
On obtient donc u et v en divisant au besoin les polynômes obtenus pr u(0)
pour les rendre unitaires.
396
trois suites r j , u j et v j telles que r j (x)x 2t + u j (x)S(x) = v j (x) pour tout j, à
partir de (r 0 , u 0 , v 0 ) = (1, 0, x 2t ) et (r 1 , u 1 , v 1 ) = (0, 1, S(x)), en effectuant les
divisions euclidiennes v i−1 = v i q i + v i+1 puis les soustractions r i+1 = r i−1 − r i q i
et u i+1 = u i−1 − u i q i jusqu’à obtenir deg v i < t et deg v i−1 t.
Proposition 3. L’algorithme de Berlekamp-Massey donne (à facteur constant près)
le couple (u(x), v(x)) recherché, avec deg u t et deg v < t, vérifiant la
congruence (XV.2).
Démonstration. Comme deg v i+1 < deg v i , la suite (deg v i ) est strictement décroissante pour i 1. Il existe donc j tel que deg v j < t et deg v j−1 t.
On a également deg q i = deg v i−1 − deg v i pour i 1. Regardons la suite
(deg u i ) : on a u 2 = −u 1 q 1 , d’où deg u 2 deg u 1 , puis u 3 = u 1 − u 2 q 2 ,
d’où deg u 3 = deg u 2 + deg q 2 > deg u 2 . On démontre par récurrence que la
suite est strictement croissante à partir de i = 2 : si deg u i > deg u i−1 , alors
deg u i+1 = deg u i + deg q i , donc deg u i+1 > deg u i . On obtient également, en
sommant les égalités deg u i+1 − deg u i = deg q i = deg v i−1 − deg v i , pour i 1 :
deg u j = deg u j − deg u 1 = deg v 0 − deg v j−1 = 2t − deg v j−1 t.
Donc (u j , v j ) répond au problème. De plus, on a pour tout i 1 :
r i
u i
r i+1 u i+1
0
1
1 −q i
=
r i−1 u i−1
r i
u i
,
d’où r i u i+1 − r i+1 u i = −(r i−1 u i − r i u i−1 ) puis r i u i+1 − r i+1 u i = (−1) i par récurrence (i 0). Cela montre que pgcd(r j , u j ) = 1.
Soit maintenant (u, v) la solution recherchée correspondant à l’erreur de décodage : on écrit rx 2t + uS = v. Noter que les polynômes localisateur et évaluateur
d’erreur sont premiers entre eux par définition, donc pgcd(r, u) = 1. On va prouver que r j u = ru j , ce qui implique la proportionalité (dans K[x] puis dans K par
primalité) des deux couples (r, u) et (r j , u j ), donc également de (u, v) et (u j , v j ).
Dans le cas contraire où r j u − ru j = 0, les formules de Cramer pour le système
r j u j
r
u
x 2t
S
=
v j
v
nous donneraient x 2t =
v j u−vu j
r j u−ru j
. Comme
deg(v j u − vu j ) max(deg v j + deg u, deg v + deg u j ) < 2t,
cela est impossible.
On obtient donc u et v en divisant au besoin les polynômes obtenus pr u(0)
pour les rendre unitaires.
396