### On the Linear Complexity of Feedback Registers

IEEE Transactions on Information Theory ** 36 ** (1990) 640-645.
Authors:

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science,
University of Kentucky, Lexington, KY, 40506-0046, klapper at cs.uky.edu.
www.cs.uky.edu/~klapper/andy.html

Agnes Chan, Northeastern University

Mark Goresky, Institute for Advanced Study

**Abstract**
In this paper, we study sequences generated by arbitrary feedback registers
(not necessarily feedback shift register) with arbitrary feedforward
functions. We generalize the definition of linear complexity of a sequence 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. We prove that a feedback shift
register whose feedback function is of the form x_1 + h(x_2,...,x_n) can
generate long periodic sequences with high linear complexities only if its
linear and quadratic terms have certain forms.