Asymptotic analysis on the normalized \(k\)-error linear complexity of binary sequences (Q664386): Difference between revisions

For a sequence \(S\) over a finite field \(\mathbb F_q\), the \(n\)th linear complexity is the length of the shortest linear recurrence relation the first \(n\) terms of the sequence satisfy. The \(n\)th \(k\)-error linear complexity of \(S\) is the smallest linear complexity one can obtain by changing up to \(k\) terms among the first \(n\) terms of \(S\). Addressing one of the problems suggested in [\textit{H. Niederreiter}, Lect. Notes Comput. Sci. 2904, 1--17 (2003; Zbl 1123.94331)], the authors analyse the asymptotic behaviour of the \(n\)th \(k\)-error linear complexity for random sequences over \(\mathbb F_2\). The authors distinguish two cases. Firstly they analyse the expected behaviour of the \(n\)th \(k\)-error linear complexity when \(n\) and \(k\) tend to infinity at a fixed ratio, secondly for a fixed \(k\) when \(n\) tends to infinity. Similar results for the more general case of multisequences over arbitrary finite fields \(\mathbb F_q\) are to be found in [\textit{W. Meidl}, \textit{H. Niederreiter} and \textit{A. Venkateswarlu}, J. Complexity 23, No. 2, 169--192 (2007; Zbl 1128.94007)].