Editing Maximum length sequence (section)

==Generation==
[[File:MLS shiftregisters L4.png|thumbnail|350px|right|Figure 1: The next value of register ''a''<sub>3</sub> in a feedback shift register of length 4 is determined by the modulo-2 sum of ''a''<sub>0</sub> and ''a''<sub>1</sub>.]]

MLS are generated using maximal [[linear-feedback shift register]]s.  An MLS-generating system with a shift register of length 4 is shown in Fig. 1.  It can be expressed using the following recursive relation:

:<math>\begin{cases}
a_3[n+1] = a_0[n] + a_1[n]\\
a_2[n+1] = a_3[n] \\
a_1[n+1] = a_2[n] \\
a_0[n+1] = a_1[n] \\
\end{cases}
</math>

where ''n'' is the time index and <math>+</math> represents [[Modular arithmetic|modulo-2]] addition. For bit values 0 = FALSE or 1 = TRUE, this is equivalent to the XOR operation.

As MLS are periodic and shift registers cycle through every possible binary value (with the exception of the zero vector), registers can be initialized to any state, with the exception of the zero vector.

===Polynomial interpretation===
A [[polynomial]] over [[Galois field|GF(2)]] can be associated with the linear-feedback shift register. It has degree of the length of the shift register, and has coefficients that are either 0 or 1, corresponding to the taps of the register that feed the [[xor]] gate. For example, the polynomial corresponding to Figure 1 is <math>x^4+x+1</math>.

A necessary and sufficient condition for the sequence generated by a LFSR to be maximal length is that its corresponding polynomial be [[Primitive polynomial (field theory)|primitive]].<ref>"Linear Feedback Shift Registers-Implementation, M-Sequence Properties, Feedback Tables"[http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm], New Wave Instruments (NW), Retrieved 2013.12.03.</ref>

===Implementation===
MLS are inexpensive to implement in hardware or software, and relatively low-order feedback shift registers can generate long sequences; a sequence generated using a shift register of length 20 is 2<sup>20</sup>&nbsp;&minus;&nbsp;1 samples long (1,048,575 samples).