On the linear complexity of feedback registers
Agnes Hui Chan, Mark Goresky, Andrew Klapper · IEEE Transactions on Information Theory · 1990
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/sub 1/+h(x/sub 2/, . . . , x/sub n/) can generate long periodic sequences with high linear complexities only if its linear and quadratic terms have certain specific forms.>