Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31108
On the Construction of m-Sequences via Primitive Polynomials with a Fast Identification Method

Authors: Abhijit Mitra


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):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3589


[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.