  Registers with Non-Linear Update (RNLUs) are a generalization of Non-Linear
Feedback Shift Registers (NLFSRs) in which both, feedback and feedforward,
connections are allowed and no chain connection between the stages is required.
In this paper, a new algorithm for constructing RNLUs generating a given binary
sequence is presented. Expected size of RNLUs constructed by the presented
algorithm is proved to be O(n/log(n/p)), where n is the sequence length and p
is the degree of parallelization. This is asymptotically smaller than the
expected size of RNLUs constructed by previous algorithms and the expected size
of LFSRs and NLFSRs generating the same sequence. The presented algorithm can
potentially be useful for many applications, including testing, wireless
communications, and cryptography.
