An analysis of the structure and complexity of nonlinear binary sequence generators

A method of analysis is presented for the class of binary sequence generators employing linear feedback shift registers with nonlinear feed-forward operations. This class is of special interest because the generators are capable of producing very long "unpredictable" sequences. The period of the sequence is determined by the linear feedback connections, and the portion of the total period needed to predict the remainder is determined by the nonlinear feed-forward operations. The linear feedback shift registers are represented in terms of the roots of their characteristic equations in a finite field, and it is shown that nonlinear operations inject additional roots into the representation. The number of roots required to represent a generator is a measure of its complexity, and is equal to the length (number of stages) of the shortest linear feedback shift register that produces the same sequence. The analysis procedure can be applied to any arbitrary combination of binary shift register generators, and is also applicable to the synthesis of complex generators having desired properties. Although the discussion in this paper is limited to binary sequences, the analysis is easily extended to similar devices that generate sequences with members in any finite field.