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.