A Survey of Full Length Nonlinear Shift Register Cycle Algorithms

Shift registers have been used to generate sequences of 0’s and 1’s for over thirty years. A wide variety of applications has been made of these sequences. Principally, communications have made use of the sequences generated. One particular class of shift register sequences for which applications exist is the full length nonlinear shift register sequences. These sequences are periodic and of length 2ⁿ and all 2ⁿ different binary n-tuples appear exactly one time in a periodic portion of the sequence. In this paper we discuss various algorithms which have been suggested for generating these sequences.