On the Properties of Pseudo Noise Sequences with a Simple Proposal of Randomness Test

Maximal length sequences (m-sequences) are also known as pseudo random sequences or pseudo noise sequences for closely following Golomb-s popular randomness properties: (P1) balance, (P2) run, and (P3) ideal autocorrelation. Apart from these, there also exist certain other less known properties of such sequences all of which are discussed in this tutorial paper. Comprehensive proofs to each of these properties are provided towards better understanding of such sequences. A simple test is also proposed at the end of the paper in order to distinguish pseudo noise sequences from truly random sequences such as Bernoulli sequences.

Authors:

• Abhijit Mitra

Keywords:

• Maximal length sequence
• pseudo noise sequence
• punctured de Bruijn sequence
• auto-correlation
• Bernoulli sequence
• randomness tests.

References:

[1] R. J. McEliece, Finite Fields for Computer Scientists and Engineers.
Boston, MA: Kluwer Academic, 1987.
[2] S. Golomb, Shift Register Sequences, Revised edition. Laguna Hills, CA:
Aegean Park Press, 1982.
[3] S. Blackburn, "A Note on Sequences with the Shift and Add Property,"
Designs, Codes, and Crypt., vol. 9, pp. 251-256, 1996.
[4] F. J. MacWilliams and J. A. Sloane, "Pseudo-Random Sequences and
Arrays," Proc. IEEE, vol. 64, no. 12, pp. 1715-1729, Dec. 1976.
[5] S. A. Fredricsson, "Pseudo-Randomness Properties of Binary Shift
Register Sequences," IEEE Trans. Inform. Theory, vol. 21, pp. 115-120,
Jan. 1975.
[6] D. E. Knuth, The Art of Computer Progamming. Reading, MA: Addison-
Wesley, 1968.
[7] F. A. Feldman, "A New Spectral Test for Nonrandomness and the DES,"
IEEE Trans. Soft. Engg., vol. 16, no. 3, pp. 261-267, March 1990.
[8] E. R. Berlekamp, Algebraic Coding Theory. New York: McGraw-Hill,
1968.