Asymptotic analysis on the normalized k-error linear complexity of binary sequences
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)].
- The \(k\)-error linear complexity distribution for \(2^n\)-periodic binary sequences
- Asymptotic Behavior of Normalized Linear Complexity of Ultimately Nonperiodic Binary Sequences
- Asymptotic Behavior of Normalized Linear Complexity of Multi-sequences
- Structure analysis on the \(k\)-error linear complexity for \(2^n\)-periodic binary sequences
- On the k-error linear complexity of -sequences
- On the Computation of the Linear Complexity and the k-Error Linear Complexity of Binary Sequences with Period a Power of Two
- An algorithm for the k-error linear complexity of binary sequences with period 2/sup n/
- Thek-error linear complexity and the linear complexity forpq n-periodic binary sequences
- Modified Berlekamp-Massey Algorithm for Approximating the k-Error Linear Complexity of Binary Sequences
- An algorithm for the k-error linear complexity of binary sequences with period 2p^m
- An algorithm for the k-error linear complexity of binary sequences with period 2/sup n/
- Analysis and design of stream ciphers
- Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm
- Asymptotic Behavior of Normalized Linear Complexity of Multi-sequences
- Asymptotic Behavior of Normalized Linear Complexity of Ultimately Nonperiodic Binary Sequences
- Counting functions and expected values for the \(k\)-error linear complexity
- scientific article; zbMATH DE number 1250549 (Why is no real title available?)
- scientific article; zbMATH DE number 1740050 (Why is no real title available?)
- Progress in Cryptology - INDOCRYPT 2003
- The asymptotic behavior of \(N\)-adic complexity
- The asymptotic normalized linear complexity of multisequences
- The stability theory of stream ciphers
- A complexity measure for families of binary sequences
- On the \(k\)-error linear complexity of binary sequences derived from the discrete logarithm in finite fields
- The asymptotic behavior of \(N\)-adic complexity
- Asymptotic Behavior of Normalized Linear Complexity of Ultimately Nonperiodic Binary Sequences
- Asymptotic Behavior of Normalized Linear Complexity of Multi-sequences
- The asymptotic behavior of the joint linear complexity profile of multisequences
This page was built for publication: Asymptotic analysis on the normalized \(k\)-error linear complexity of binary sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q664386)
