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.