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

Parameters:¶

degree: int¶

The degree \(n\) of the LFSR.

poly: PolyLike | None = None¶

The feedback polynomial of the LFSR over \(\mathrm{GF}(q)\). Note, the feedback polynomial is the reciprocal of the characteristic polynomial that defines the linear recurrence relation. The default is None which uses the reciprocal primitive polynomial of degree \(n\) over \(\mathrm{GF}(2)\), galois.primitive_poly(2, degree).reverse().

index: int = 1¶

The index \(i\) in \([1, q^{n})\) 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^n)\).

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

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

Returns:¶

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

References¶

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

Examples¶

Generate a maximal-length sequence of degree-4 over \(\mathrm{GF}(2)\). Compare the sequence with index 1 to the sequence with index 2. They are just phase shifts of each other.

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, index=2)
Out[2]: array([0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0])

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

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

# Feedback polynomial
In [4]: f = c.reverse(); f
Out[4]: Poly(5x^4 + x^3 + 1, GF(3^2))

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

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