Linear complexities of self-shrinking and related generators, and
some related complexities
William Chambers
Department of Electronic and Electrical Engineering, Kings
College London
In a shrinking generator a binary sequence t determines
whether the corresponding bit from another binary sequence
u is to be output. In a self-shrinking generator both
sequences are derived from the same maximal length linear
feedback shift register with n stages. When t and u are
both linearly derived the output sequence has period
2^(n-1) and the linear complexity is upper-bounded by
2^(n-1)-(n-2). Similar results are derived for the case
when t and/or u are non-linear functions of the register
contents. In many cases the upper bounds are attained.
However computer trials suggest that for some primitive
feedbacks with particular structures the linear
complexities have a smaller upper bound. Most surprisingly
of all, it seems that if t is an m-sequence and u is the
same m-sequence cyclically shifted by s steps, then there
are two consecutive values of s for which the output has
the form ...010101..., with linear complexity 2.