LFSR Circulant Matrix

class fastmat.LFSRCirculant

Bases: Matrix

Linear Feedback Shift Registers (LFSR) as implemented in this class are finite state machines generating sequences of symbols from the finite field \(F=[-1, +1]\). A shift register of size \(N\) is a cascade of \(N\) storage elements \(a_n\) for \(n = 0,\dots,N-1\), each holding one symbol of \(F\). The state of the shift register is defined by the states of \(a_0,\dots,a_{N-1}\). [5]

The next state of the register is generated from the current state by moving the contents of each storage element to the next lower index by setting \(a_{n-1} = a_n\) for \(n \geq 1\), hence the name shift register. The element \(a_0\) of the current state is discarded completely in the next state. A subset \(T\) of all storage elements with cardinality of 1 or greater is used for generating the next symbol \(a_{N-1}\) by multiplication within \(F\). \(T\) is called the tap configuration of the shift register.

The output sequence of the register is the sequence of symbols \(a_0\) for each state of the register. When the shift register repeats one of its previous states after \(L\) state transistions, the output sequence also repeats and thus is periodic with a length \(L\). Evaluation of the sequence starts with all storage elements set to an initial state \(I\). Only periodic sequences of length \(L > 1\) are considered if they also repeat all states including the initial state and thus form a hamilton circle an the graph corresponding to the chosen shift register size \(N\) and tap configuration \(T\).

Instanciation of this matrix class requires supplying the requested register size \(N\), the tap configuration and the initial state. The latter two are required to be supplied as binary words of up to \(N\) bits. A one bit on position \(i\) in the tap configuration adds \(a_i\) as *feedback tap* to \(T\). At least one feedback tap must be supplied. The bits in the given initial state word \(r\) will be mapped to the initial register state, where \(r_n = 0\) sets \(a_n = +1\) and \(r_n = 1\) sets \(a_n = -1\). If no \(r\) is given, it is assumed to be all-ones.

>>> # import the package
>>> import fastmat as fm
>>>
>>> # construct the parameter
>>> polynomial = 0b11001
>>> start = 0b1010
>>>
>>> # construct the matrix
>>> L = fm.LFSRCirculant(polynomial, start)
>>> s = L.vecC

This yields a Circulant matrix where the column-definition vector is the output of a LFSR of size 4, which is configured to generate a maximum length sequence of length 15 and a cyclic shift corresponding to the given initial state.

\[s = [+1, -1, +1, -1, -1, +1, +1, -1, +1, +1, +1, -1, -1, -1, -1]\]

\[\begin{split}L = \begin{bmatrix} +1 & -1 & -1 & & -1 \\ -1 & +1 & -1 & \dots & +1 \\ +1 & -1 & +1 & & -1 \\ & \vdots & & \ddots & \\ -1 & -1 & -1 & & +1 \\ \end{bmatrix}\end{split}\]

This class depends on Hadamard.

__init__()

Initialize a LFSR Circulant matrix instance.

The definition vector of the circulant matrix is defined by the output [+1/-1] of a binary Linear Feedback Shift Register (LFSR) with the given defining parameters over one period.

Parameters

polynomialint

The characteristic polynomial corresponding to the shift register sequence. Every set bit k in this value corresponds to one feedback tap at storage element k of the register or the monome x^k of the characterisctic polynomial that forms a cycle in the galois field GF2 of the order corresponding to the highest non-zero monome x^K in the polynomial.

startint

The initial value of the storage elements of the register.

**optionsoptional

Additional keyworded arguments. Supports all optional arguments supported by fastmat.Matrix.

All optional arguments will be passed on to all fastmat.Matrix instances that are generated during initialization.

order

period

polynomial

size

Deprecated. Will be removed in future releases

start

states

Return the internal register states during the sequence.

(read-only)

taps

Deprecated. See .polynomial

vecC

Return the sequence defining the circular convolution.

(read only)