Randomness and Representation of Span n sequences

Abstract. Any span n sequences can be regarded as filtering sequences. From this observation, new randomness criteria for span n sequences are proposed. It is proved that the feedback function of a span n se-quence can be represented as a composition of its trace representation, or equivalently, its discrete Fourier transform, and a permutation from the state space of the sequence to the multiplicative group of the finite field GF (2n), and vice versa. Significant enhancements for randomness of span n sequences, so that de Bruijn sequences, are illustrated by some examples. Index Terms. Nonlinear feedback shift register sequences, span n se-quences, de Bruijn sequences, randomness, discrete Fourier transform.