Generates a maximum-length sequence (\(m\)-sequence) from a Fibonacci linear feedback shift register (LFSR).

Parameters:¶

degree: int¶

The degree \(m\) of the LFSR.

poly: PolyLike | None = None¶

The characteristic polynomial of the LFSR over \(\mathrm{GF}(q)\). The default is None, which uses the primitive polynomial of degree \(m\) over \(\mathrm{GF}(2)\), galois.primitive_poly(2, degree).

index: int = 1¶

The index \(i\) in \([1, q^m)\) of the \(m\)-sequence. The index represents the initial state of the LFSR. The index dictates the phase of the \(m\)-sequence. The integer index is interpreted as a polynomial over \(\mathrm{GF}(q)\), whose coefficients are the shift register values. The default is 1, which corresponds to the \([0, \dots, 0, 1]\) state.

output: 'decimal' = 'decimal'¶

output: 'field' = 'decimal'

output: 'bipolar' = 'decimal'

The output format of the \(m\)-sequence.

• "decimal" (default): The \(m\)-sequence with decimal values in \([0, q^m)\).

• "field": The \(m\)-sequence as a Galois field array over \(\mathrm{GF}(q^m)\).

• "bipolar": The \(m\)-sequence with bipolar values of 1 and -1. Only valid for \(q = 2\).

Returns:¶

The length-\(q^m - 1\) \(m\)-sequence.

References

• https://en.wikipedia.org/wiki/Maximum_length_sequence

Examples

Generate a maximum-length sequence of degree-4 over \(\mathrm{GF}(2)\).

In [1]: sdr.m_sequence(4)
Out[1]: array([1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1])

In [2]: sdr.m_sequence(4, output="bipolar")
Out[2]: 
array([-1.,  1.,  1.,  1., -1.,  1.,  1., -1., -1.,  1., -1.,  1., -1.,
       -1., -1.])

In [3]: sdr.m_sequence(4, output="field")
Out[3]: GF([1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1], order=2)

Compare the sequence with index 1 to the sequence with index 2. They are just phase shifts of each other.

In [4]: sdr.m_sequence(4, index=2)
Out[4]: array([0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0])

Generate a maximum-length sequence of degree-4 over \(\mathrm{GF}(3^2)\).

In [5]: c = galois.primitive_poly(3**2, 4); c
Out[5]: Poly(x^4 + x + 5, GF(3^2))

In [6]: x = sdr.m_sequence(4, poly=c); x
Out[6]: array([1, 0, 0, ..., 5, 4, 6])

In [7]: x.size
Out[7]: 6560

Plot the auto-correlation of a length-63 \(m\)-sequence. Notice that the linear correlation produces sidelobes for non-zero lag. However, the circular correlation only produces magnitudes of 1 for non-zero lag.

In [8]: x = sdr.m_sequence(6, output="bipolar")

In [9]: plt.figure(); \
   ...: sdr.plot.correlation(x, x, mode="circular"); \
   ...: plt.ylim(0, 63);
   ...: 

The cross-correlation of two \(m\)-sequences with different indices is low for zero lag. However, for non-zero lag the cross-correlation is very large.

In [10]: x = sdr.m_sequence(6, index=1, output="bipolar")

In [11]: y = sdr.m_sequence(6, index=30, output="bipolar")

In [12]: plt.figure(); \
   ....: sdr.plot.correlation(x, y, mode="circular"); \
   ....: plt.ylim(0, 63);
   ....: