On the linear complexity of feedback registers

Sequences generated by arbitrary feedback registers (not necessarily feedback shift registers) with arbitrary feedforward functions are studied. The definition of linear complexity of a sequence is generalized to the notions of strong and weak linear complexity of feedback registers. A technique for finding upper bounds for the strong linear complexities of such registers is developed. This technique is applied to several classes of registers. It is shown that a feedback shift register in which the feedback function is of the form x ₁+h(x₂, . . . , x_n ) can generate long periodic sequences with high linear complexities only if its linear and quadratic terms have certain specific forms