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.

Log in or register to write something here or to contact authors.