Skip to content

komm.LFSRSequence

Linear-feedback shift register (LFSR) sequence. It is a binary sequence obtained from the output of a LFSR. The LFSR feedback taps are specified as a binary polynomial $p(X)$ of degree $n$, called the feedback polynomial. More specifically: if bit $i$ of the LFSR is tapped, for $i \in [1 : n]$, then the coefficient of $X^i$ in $p(X)$ is $1$; otherwise, it is $0$; moreover, the coefficient of $X^0$ in $p(X)$ is always $1$. For example, the feedback polynomial corresponding to the LFSR in the figure below is $p(X) = X^5 + X^2 + 1$, whose integer representation is 0b100101.

Linear-feedback shift register example.

The start state of the machine is specified by the so called start state polynomial. More specifically, the coefficient of $X^i$ in the start state polynomial is equal to the initial value of bit $i$ of the LFSR.

Maximum-length sequences

If the feedback polynomial $p(X)$ is primitive, then the corresponding LFSR sequence will be a maximum-length sequence (MLS). Such sequences have the following cyclic autocorrelation: $$ \tilde{R}[\ell] = \begin{cases} L, & \ell = 0, \, \pm L, \, \pm 2L, \ldots, \\ -1, & \text{otherwise}, \end{cases} $$ where $L$ is the length of the sequence.

References
  1. https://en.wikipedia.org/wiki/Linear-feedback_shift_register
  2. https://en.wikipedia.org/wiki/Maximum_length_sequence

__init__

Default constructor for the class.

Parameters:

  • feedback_polynomial (BinaryPolynomial | int) –

    The feedback polynomial of the LFSR, specified either as a binary polynomial or as an integer to be converted to the former.

  • start_state_polynomial (Optional[BinaryPolynomial | int]) –

    The start state polynomial of the LFSR, specified either as a binary polynomial or as an integer to be converted to the former. The default value is 0b1.

Examples:

>>> lfsr = komm.LFSRSequence(feedback_polynomial=0b100101)
>>> lfsr.bit_sequence
array([0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1])
>>> lfsr.cyclic_autocorrelation()
array([31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1])

See also the class method maximum_length_sequence for a more convenient way to construct a maximum-length sequence.

maximum_length_sequence classmethod

Constructs a maximum-length sequences (MLS) of a given degree. The feedback polynomial $p(X)$ is chosen according to the following table of primitive polynomials.

Degree $n$ Feedback polynomial $p(X)$ Degree $n$ Feedback polynomial $p(X)$
$1$ 0b11 $9$ 0b1000010001
$2$ 0b111 $10$ 0b10000001001
$3$ 0b1011 $11$ 0b100000000101
$4$ 0b10011 $12$ 0b1000001010011
$5$ 0b100101 $13$ 0b10000000011011
$6$ 0b1000011 $14$ 0b100010001000011
$7$ 0b10001001 $15$ 0b1000000000000011
$8$ 0b100011101 $16$ 0b10001000000001011

Parameters:

  • degree (int) –

    The degree $n$ of the MLS. Only degrees in the range $[1 : 16]$ are implemented.

  • start_state_polynomial (Optional[BinaryPolynomial | int]) –

    See the corresponding parameter of the default constructor.

Examples:

>>> komm.LFSRSequence.maximum_length_sequence(degree=5)
LFSRSequence(feedback_polynomial=0b100101)

feedback_polynomial property

The feedback polynomial $p(X)$ of the LFSR.

start_state_polynomial property

The start state polynomial of the LFSR.