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