The number of nonlinear shift registers that produce all vectors of weight >or=t

摘要

It has been shown that it is possible to generate a cycle on a nonlinear shift register to contain all vectors of length n and Hamming weight >or=t. It is shown how to count the number of different ways this can be done on a truth table of minimum density. Specifically, it is shown how a theorem on spanning subtrees on a graph can be used to evaluate the number of sequences that contain vectors of a given length and Hamming weight.