maple implementation of Berlekamp-Massey algorithm

\PMlinkescapetext{
>
# Maple code for the Berlekamp-Massey algorithm
# Adapted from www.cs.wisc.edu/~cs435-1/bermas.m
# Transliteration of
#   Massey, "Shift-Register Synthesis and BCH Decoding,"
#   IEEE Trans. Inform. Theory, 15(1):122-127, 1969.
# Input: P, either 0 or a prime
#           If P>0 then we work over the field K = Z/Z[P] (mod P)
#           else we work over the field K = Q (rationals)
#        N, a positive integer
#        s, a list of >= 2*N terms in K
#        x, a formal variable
# Returns: Unique monic annihilator of minimum degree, over K[x].

 BM := proc(s, N, P, x)
   local C,B,T,L,k,i,n,d,b,safemod;
   ASSERT(nops(s) = 2*N);
   safemod := (exp, P) -> `if`(P=0, exp, exp mod P);
   B := 1;
   C := 1;
   L := 0;
   k := 1;
   b := 1;
   for n from 0 to 2*N-1 do
     d := s[n+1];
     for i from 1 to L do
       d := safemod(d + coeff(C,x^i)*s[n-i+1], P);
     od;
     if d=0 then k := k+1 fi;
     if (d <> 0 and 2*L > n) then
       C := safemod(expand(C - d*x^k*B/b), P);
       k := k+1;
     fi;
     if (d <> 0 and 2*L <= n) then
       T := C;
       C := safemod(expand(C - d*x^k*B/b), P);
       B := T;
       L := n+1-L;
       k := 1;
       b := d;
     fi;
   od;
   return C;
 end:
}

The following test demonstrates usage and verifies that this works:

\PMlinkescapetext{
> P := 103:
  d := 4:
  num := 21+83*x+90*x^2+4*x^3: # degree < d
  den := 1+11*x+23*x^2+58*x^3+69*x^4: # monic, degree <= d
  f := series(num/den, x=0, 2*d) mod P:
  s := [seq(coeff(f, x, i), i=0..2*d-1)]:
  BM(s, d, P, x);}

$$1+11x+23x^2+58x^3+69x^4$$

The annihilator is the same as denominator, as we expect.

Title	maple implementation of Berlekamp-Massey algorithm
Canonical name	MapleImplementationOfBerlekampMasseyAlgorithm
Date of creation	2013-03-22 15:35:27
Last modified on	2013-03-22 15:35:27
Owner	daveagp (6096)
Last modified by	daveagp (6096)
Numerical id	6
Author	daveagp (6096)
Entry type	Algorithm
Classification	msc 11B37
Classification	msc 15A03
Related topic	BerlekampMasseyAlgorithm