Complexity analysis of Geffe's generator

Abstract EN

A method of analysis is presented for the class of binary sequence generators employing the product of outputs of two or more linear feedback shift registers with maximum period.

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 operation inject additional roots into the representation.

The number of roots required to represent a generator is a measure of its complexity, and 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 registers, and is also applicable to the synthesis of complex generators having desire properties.

Although the discussion in this paper is limited to binary sequences, the analysis is easily extended to similar devices that generate sequences with numbers in any finite field.