Sequences with almost perfect linear complexity profile

From MaRDI portal





[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.




Cited in
(39)








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)