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

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.

Authors:

• Abhijit Mitra

Keywords:

• Finite field
• irreducible polynomial
• primitive polynomial
• maximal length sequence
• additive shift register
• multiplicative shift register.

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.