Sequences with almost perfect linear complexity profile
[For the entire collection see Zbl 0635.00022.] For a given sequence S of elements \(s_ 1,s_ 2,..\). of a field F let L(n) be the linear complexity of the first n terms of S. The sequence L(1),L(2),... is called the linear complexity profile (LCP) of S. We identify S with its generating function \(S=\sum^{\infty}_{i=1}s_ ix^{-i}\) viewed as an element of the field of formal Laurent series in \(x^{-1}\) over F. Let \(S=[A_ 0,A_ 1,...]\) be the continued fraction expansion of S, so that \(A_ j\in F[x]\) for \(j\geq 0\) and \(\deg (A_ j)\geq 1\) for \(j\geq 1\). Define \(Q_{-1}=0\), \(Q_ 0=1\), and \(Q_ j=A_ jQ_{j-1}+Q_{j-2}\) for \(j\geq 1\). Then it is shown that \(L(n)=\deg (Q_ j)\), where \(j\geq 0\) is uniquely determined by \(\deg (Q_{j- 1})+\deg (Q_ j)\leq n<\deg (Q_ j)+\deg (Q_{j+1})\), and all nth minimal polynomials of S are characterized. This yields a criterion for S to have a perfect LCP and a short proof for the Wang-Massey characterization of binary sequences with a perfect LCP. The class of sequences with an almost perfect LCP is introduced and an algorithm for the generation of sequences with an arbitrarily prescribed LCP is given.
- Keystream Sequences with a Good Linear Complexity Profile for Every Starting Point
- Sequences with almost perfect linear complexity profiles and curves over finite fields
- Perfect linear complexity profile and apwenian sequences
- Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles
- scientific article; zbMATH DE number 4211964
- Linear complexity of generalized cyclotomic binary sequences of order 2
- Polynomials with odd orthogonal multiplicity
- Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles
- Orthogonal sequences of polynomials over arbitrary fields
- An algorithm for shifted continued fraction expansions in parallel linear time
- On the \(N\)th linear complexity of automatic sequences
- Multi-sequences with \(d\)-perfect property
- Constructions of sequences with almost perfect linear complexity profile from curves over finite fields
- Perfect linear complexity profile and apwenian sequences
- Criteria for apwenian sequences
- Jump and hop randomness tests for binary sequences
- Pseudorandom sequences derived from automatic sequences
- Linear recurring sequences and subfield subcodes of cyclic codes
- Enumeration results on linear complexity profiles and lattice profiles
- Multi-continued fraction algorithm and generalized B--M algorithm over \(\mathbb F_{q}\)
- Continued fraction for formal Laurent series and the lattice structure of sequences
- Linear complexity over \(\mathbb F_q\) and over \(\mathbb F_{q^m}\) for linear recurring sequences
- Counting functions and expected values for the lattice profile at \(n\)
- On distribution properties of sequences with perfect linear complexity profile
- Sequences With High Nonlinear Complexity
- scientific article; zbMATH DE number 4211964 (Why is no real title available?)
- Keystream Sequences with a Good Linear Complexity Profile for Every Starting Point
- Generalized Joint Linear Complexity of Linear Recurring Multisequences
- scientific article; zbMATH DE number 4044991 (Why is no real title available?)
- The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequence
- Numeration and discrete dynamical systems
- The independence of two randomness properties of sequences over finite fields
- scientific article; zbMATH DE number 1071799 (Why is no real title available?)
- Sequences with almost perfect linear complexity profiles and curves over finite fields
- On sequences, rational functions and decomposition
- On the \(k\)-error linear complexity of sequences from function fields
- On the joint linear complexity profile of explicit inversive multisequences
- Multisequences with almost perfect linear complexity profile and function fields over finite fields
- A lower bound on a quantity related to the quality of polynomial lattices
- Rational approximations, multidimensional continued fractions, and lattice reduction
- On the limit of maximal density of sequences with a perfect linear complexity profile
- On the binary sequence \((1,1,0,1,0^3,1,0^7,1,0^{15},\dots)\)
- On a family of automatic apwenian sequences
- A combinatorial approach to probabilistic results on the linear- complexity profile of random sequences
This page was built for publication: Sequences with almost perfect linear complexity profile
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3797089)