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

• Published in: IEEE transactions on information theory 2005-03, Vol.51 (3), p.1145-1150
• Main Author: Salagean, A.
• Format: Article
• Language: English
• Subjects: Algorithms; Analogs; Application software; Applied sciences; Binary sequences; Coding, codes; Complexity; Computation; Computer applications; Computer science; Cryptography; Decoding; Encoding; Errors; Exact sciences and technology; Game theory; Information, signal and communications theory; linear complexity; Linear feedback shift registers; Mathematical analysis; repeated-root codes; Segments; Signal and communications theory; stream cipher; Telecommunications and information theory
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2004.842769

The linear Games-Chan algorithm for computing the linear complexity c(s) of a binary sequence s of period lscr=2 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 lscr=2 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(lscr). We apply our algorithm to decoding and encoding binary repeated-root cyclic codes of length lscr in linear, O(lscr), time and space. A previous decoding algorithm proposed by Lauder and Paterson has O(lscr(loglscr) 2 ) complexity