Variantes de l’algorithme de Berlekamp–Massey

L’algorithme de Berlekamp-Massey usuel

Suites récurrentes linéaires

On consid`ere une suite a = (ak)k∈N d’éléments de K et un entier n ∈ N. Une relation récurrente linéaire d’ordre n pour cette suite est définie par la donnée de n+ 1 éléments c0, c1, . . . , cn (cn 6= 0) de K vérifiant : ∀k ≥ 0 c0ak + c1ak+1 + · · · + cnak+n = 0 (3.1) Le polynˆome G(X) = Pn i=0 ciXi est alors appelé un polynˆome générateur de la suite a. Définition 3.1.1. On appelle suite récurrente linéaire, toute suite a pour laquelle il existe un polynˆome générateur G(X). Les polynˆomes générateurs pour une suite récurrente linéaire donnée a forment un idéal de K[X] dont le générateur unitaire P = Pa est appelé le polynˆome générateur minimal de la suite a. Si on note d le degré de Pa (d ≤ n) et S(X) = P∞ i=0 aiXi , on obtient dans l’anneau des séries formelles K[[X]] les deux égalités : S(X) Gb(X) = F(X) avec F ∈ K[X] et deg F < n . S(X) Pb(X) = N(X) avec N ∈ K[X] et deg N < d . Variantes de l’algorithme de Berlekamp–Massey 64 3. Variantes de l’algorithme de Berlekamp–Massey ou encore, S(X) = F(X) Gb(X) = N(X) Pb(X) avec deg N < d := deg P . Pour calculer Pa `a partir des 2n premiers termes de la suite récurrente linéaire (sachant qu’il existe un polynˆome générateur de degré n) l’idée directrice est qu’on peut calculer le développement en fraction continue de 1/S(X) dans K[X]. En effet ce développemnt est le mˆeme que celui de Pb(X) N(X) et s’arrˆete au bout d’un nombre fini d’étapes : 1 S(X) = Pb(X) N(X) = q1(X) + 1 q2(X) + 1 q3(X) + · · · . (3.2) Mais on peut faire les calculs seulement modulo X2n , `a condition de bien contrˆoler le moment o`u on s’arrˆete.

L’algorithme de Berlekamp-Massey

Rappelons bri`evement l’algorithme de Berlekamp-Massey. On donne dans un corps K les 2n premiers éléments d’une suite récurrente linéaire a = (ak)k∈N pour laquelle on sait qu’il existe un polynˆome générateur de degré n. Le probl`eme est de calculer son polynˆome générateur minimal Pa . Une telle solution est donnée par l’algorithme de Berlekamp-Massey qui donne en sortie le degré d ainsi que les coefficients d’un polynˆome f = cd P a associé au polynˆome Pa . Ce polynˆome P a est alors obtenu en divisant f par cd. Cet algorithme a été inventé par Berlekamp en 1968 [6] dans le but de décoder les codes BCH [21], mais sous une forme o`u la relation avec l’algorithme d’Euclide étendu était invisible. L’algorithme a été ✭✭ expliqué ✮✮ une année plus tard par Massey [28] et Dornstetter [14] qui ont montré qu’on pouvait le voir comme une variante de l’algorithme d’Euclide étendu. Voici ce que cela donne. L’algorithme utilise les propriétés de la suite des triplets (Ri , Ui , Vi) formée des restes et des multiplicateurs de Bézout successifs dans l’algorithme d’Euclide étendu pour le couple de polynˆomes (R−1, R0) o`u R−1 = X2n et R0 = P2n−1 k=0 akXk . Posant V−1 = U0 = 0 et U−1 = V0 = 1, ces triplets vérifient, pour tout i ≥ 0, les relations : Ri−1 = Ri Qi + Ri+1 o`u deg Ri+1 < deg Ri Ui+1 = Ui−1 − Qi Ui , Vi+1 = Vi−1 − Qi Vi , d’o`u : Ri = Ui R−1 + Vi R0 . De plus : Ui Vi−1 − Vi Ui−1 = (−1)i+1 et : deg Ri < 2n − deg Vi . Les deux derni`eres relations se vérifient facilement par récurrence sur i. On arrˆete le processus au premier reste, disons Rm, de degré plus bas que n, pour obtenir : Um X 2n + Vm R0 = Rm avec degRm < n. Posons d = sup(degVm, 1+degRm) et P = XdVm(1/X). Alors on peut montrer que P divisé par son coefficient dominant est le polynˆome générateur minimal de la suite (ak) (voir [19] et [14]). Par exemple dans le cas o`u deg Vm = n et Vm(0) 6= 0, en écrivant que les termes de degré 3.1. L’algorithme de Berlekamp-Massey usuel 65 compris entre n et 2n − 1 du polynˆome Vm(X) R0(X) sont nuls, on constate que P(X) est bien un polynˆome générateur de la suite (ak). Ceci donne précisément l’algorithme 3.1 (dans lequel cd(P) désigne le coefficient dominant de P).