On the computation of the linear complexity and the k-error linear complexity of binary sequences with period a power of two | IEEE Journals & Magazine | IEEE Xplore

On the computation of the linear complexity and the k-error linear complexity of binary sequences with period a power of two


Abstract:

The linear Games-Chan algorithm for computing the linear complexity c(s) of a binary sequence s of period /spl lscr/=2/sup n/ requires the knowledge of the full sequence,...Show More

Abstract:

The linear Games-Chan algorithm for computing the linear complexity c(s) of a binary sequence s of period /spl lscr/=2/sup n/ requires the knowledge of the full sequence, while the quadratic Berlekamp-Massey algorithm requires knowledge of only 2c(s) terms. We show that we can modify the Games-Chan algorithm so that it computes the complexity in linear time knowing only 2c(s) terms. The algorithms of Stamp-Martin and Lauder-Paterson can also be modified, without loss of efficiency, to compute analogs of the k-error linear complexity for finite binary sequences viewed as initial segments of infinite sequences with period a power of two. We also develop an algorithm which, given a constant c and an infinite binary sequence s with period /spl lscr/=2/sup n/, computes the minimum number k of errors (and an associated error sequence) needed over a period of s for bringing the linear complexity of s below c. The algorithm has a time and space bit complexity of O(/spl lscr/). We apply our algorithm to decoding and encoding binary repeated-root cyclic codes of length /spl lscr/ in linear, O(/spl lscr/), time and space. A previous decoding algorithm proposed by Lauder and Paterson has O(/spl lscr/(log/spl lscr/)/sup 2/) complexity.
Published in: IEEE Transactions on Information Theory ( Volume: 51, Issue: 3, March 2005)
Page(s): 1145 - 1150
Date of Publication: 31 March 2005

ISSN Information:


References

References is not available for this document.