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

Authors: Abhijit Mitra

Abstract:

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.

Keywords: Maximal length sequence, pseudo noise sequence, punctured de Bruijn sequence, auto-correlation, Bernoulli sequence, randomness tests.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1335488

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.