On the Construction of m-Sequences via Primitive Polynomials with a Fast Identification Method

Authors: Abhijit Mitra

Abstract:

The paper provides an in-depth tutorial of mathematical construction of maximal length sequences (m-sequences) via primitive polynomials and how to map the same when implemented in shift registers. It is equally important to check whether a polynomial is primitive or not so as to get proper m-sequences. A fast method to identify primitive polynomials over binary fields is proposed where the complexity is considerably less in comparison with the standard procedures for the same purpose.

Keywords: Finite field, irreducible polynomial, primitive polynomial, maximal length sequence, additive shift register, multiplicative shift register.

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

References:

[1] S. Blackburn, "A Note on Sequences with the Shift and Add Property," Designs, Codes, and Crypt., vol. 9, pp. 251-256, 1996.
[2] I. D. Alanen and D. E. Knuth, "Tables of Finite Fields," Sankhya, Series A, vol. 26, pp. 305-328, 1964.
[3] E. R. Berlekamp, Algebraic Coding Theory. New York: McGraw-Hill, 1968.
[4] E. J. Watson, "Primitive Polynomials (mod 2)," Mathematics of Computation, vol. 16, pp. 368-369, 1962.
[5] R. J. McEliece, Finite Fields for Computer Scientists and Engineers. Boston, MA: Kluwer Academic, 1987.
[6] D. E. Carter, "On the Generation of Pseudo-Noise Codes," IEEE Trans. Aerosp. Electron. Sys., vol. 10, pp. 898-899, 1974.
[7] S. Golomb, Shift Register Sequences, Revised edition. Laguna Hills, CA: Aegean Park Press, 1982.
[8] D. E. Knuth, The Art of Computer Progamming. Reading, MA: Addison- Wesley, 1968.
[9] K. Krogsgaard and T. Karp, "Fast Identification of Primitive Polynomials over Galois Fields: Results from a Course Project," in Proc. 2005 IEEE Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), Philadelphia, PA, USA, 2005, pp. V553-V556.
[10] H. Tijms, Understanding Probability: Chance Rules in Everyday Life. Cambridge: Cambridge University Press, 2004.