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(n2) bit operations. In addition to the analysis of LFSR's, this algorithm is used in Error Control Codes.
Here's a simple algorithm:
s(X) = 1, I = 0, b(x) = 0
for m = 1 to 2t
compute d = aI0*si*S*m-i
where the coefficient, si, corresponds to Xi 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)
else d = 0 do:
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 for this more concise algorithm.