More Like This

Show all results sharing this subject:

  • Computing


Show Summary Details

Quick Reference

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 ′) whose generating polynomial is of degree n will have period qn − 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 qn states, and so such a register (with arbitrary feedback logic) cannot generate a sequence whose period exceeds qn. 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 qn − 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.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.