Asymptotic analysis on the normalized \(k\)-error linear complexity of binary sequences (Q664386): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:55, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic analysis on the normalized \(k\)-error linear complexity of binary sequences |
scientific article |
Statements
Asymptotic analysis on the normalized \(k\)-error linear complexity of binary sequences (English)
0 references
1 March 2012
0 references
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)].
0 references
stream ciphers
0 references
binary sequences
0 references
linear complexity
0 references
\(k\)-error linear complexity
0 references