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.