m-sequence

m-sequence A periodic sequence of symbols generated by a linear feedback shift register whose feedback coefficients form a primitive polynomial. A q-ary register (with q prime) whose generating polynomial is of degree n will have period qⁿ – 1, provided that the initial state is nonzero, and its contents will proceed through all the nonzero q-ary n-tuples. The termwise modulo-q sum of two m-sequences is another m-sequence: the m-sequences (of a given generating polynomial), together with the zero sequence, form a group.

The term is short for maximum-length sequence. It is so called because the generating shift register only has qⁿ states, and so such a register (with arbitrary feedback logic) cannot generate a sequence whose period exceeds qⁿ. But with linear logic the zero state must stand in a loop of its own (see Good–de Bruijn diagram) and so the period of a linear feedback register cannot exceed qⁿ – 1. This period, which can be achieved when and only when the polynomial is primitive, is therefore the maximum that can be achieved.

m-sequences have many useful properties. They are employed as pseudorandom sequences, error-correcting codes (as they stand, or shortened, or extended), and in determining the time response of linear channels (see convolution). See also simplex codes.