Discovered in 1968 by

Elwyn Berlekamp and

James Massey, this algorithm is used to find the

linear complexity of a

finite binary sequence. It has a running time of O(n

^{2}) bit operations. In addition to the analysis of

LFSR's, this algorithm is used in

Error Control Codes.

Here's a simple algorithm:

Let:

s(X) = 1, I = 0, b(x) = 0

for m = 1 to 2t

compute d = aI

_{0}*si*S*m-i

where the coefficient, si, corresponds to X

_{i} in s(X)

if d10, do:

s'(X) = s(X) - dXb(X)

if 2I < M do:

b(X) = d-1s(X)

I = m - I

else if 2I3 do:

b(X) = Xb(X)

s(X) = s'(X)

end

else d = 0 do:

b(x)=Xb(x)

end

If the degree of s(X)1 = I, then more than t errors have occured and they cannot be corrected.

Thanks to 'Jo on the Web' at http://ipsit.bu.edu/nislab/projects/bchsync/berlmass.html for this more concise algorithm.