Additional information was obtained from Wolfram MathWorld and Wikipedia. The project was inspired by this assignment from the Princeton COS 126 course. The code contains the main LFSR class, as well as a short demonstration of the functionality. This code is an emulator, meaning that it does not operate on actual bits, but on a Python list of 0s and 1s symbolizing the bits. That means, that there should be an even number of taps, and they should all be relatively prime, i.e. for it to have the longest period (the number of steps before it returns to inital state), the polynomial should be primitive. In order to maximize the length of the LFSR, i.e. It has to satisfy several properties - it is expressed as a polynomial modulo 2, meaning all the coefficients must be either 1 or 0.Įxample: a register with taps at positions 11, 10, 7, 3 will have a feedback polynomial: The location and number of the taps is determined by the register's reciprocal characteristic polynomial. Other linear functions can be used as well. For the convolutional encoder shown in Figure 2. The shift registers store the state information of the convolutional encoder and the constraint length relates the number of bits upon which the output depends.
This constitutes one step of the feedback shift register. where m is the maximum number of stages (memory size) in any shift register. It operates by taking the bits of the inital value (called fill or seed), shifting them one position to the left and replacing the leaving bit with exclusive-or of the leaving bit and bits at special locations in the register called the taps.
A simple emulator of a linear-feedback shift register (LFSR).
