# zbMATH — the first resource for mathematics

Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles. (English) Zbl 0934.94013
The linear complexity of a sequence of finite length over a finite field $${\mathbb F}_q$$ is the shortest length of a linear feedback shift register generating the sequence. The linear complexity profile (l.c.p.) of an arbitrary sequence $$\underline{a} = (a_i)_{i=1}^{\infty}$$ from $${\mathbb F}_q^{\infty}$$ is the sequence $$(L_{\underline{a}} (t))_{t=1}^{\infty}$$. A $$d$$ perfect sequence $$\underline{a}$$ has the property $|2 \cdot L_{\underline{a}} (t) -t |\leq d$ for every length $$t \in {\mathbb N}$$. The case of $$d=1$$ corresponds to a perfect l.c.p. in the previous literature.
For any $$d \in {\mathbb N}$$ the set of all $$d$$-perfect sequences over $${\mathbb F}_q$$ has uncountably many elements. On the other hand this set has measure zero in the space $$({\mathbb F}_q^{\infty} , {\mu}^{\infty})$$ where $$\mu$$ is the equidistribution measure on $${\mathbb F}_q$$ i.e. $$\mu (k) = 1/q ~ \forall k \in {\mathbb F}_q$$. The set of interest can be distinguished further by their Hausdorff dimension. Thus the Hausdorff dimension of 1-perfect sequences is 0.5 and the $$d$$-perfect sequences over any $${\mathbb F}_q$$ have higher Hausdorff dimension although less than unity. In addition the number of $$d$$-sequences of length $$t$$, for all $$d$$ and $$t$$, is given for all finite fields $${\mathbb F}_q$$.
The second part considers the case when the condition is relaxed to $$|2 \cdot L_{\underline{a}} (t) -t |\leq d(t)$$ where $$d(t)$$ is a non-decreasing function on the positive integers. It is shown that $$d(t) = 1 +(1+\varepsilon) \cdot {\log}_q (t)$$ gives the threshold between sequences of measure zero ($$\varepsilon =0$$) and positive measure ($$\varepsilon >0$$).

##### MSC:
 94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
Full Text: