## A Linear Feedback Shift Register Implementation

[Note: here is an article which provides a tutorial introduction to programming the IcoBoard using Migen/Python and the IceStorm tools]

Pseudo-random bit sequences can be generated using a linear feedback shift register. We use the following logic (taken from the Wikipedia article, and modified slightly):

int main(void)
{
/*any non-zero start state will work*/
uint16_t start_state = 0xACE1u;
uint16_t lfsr = start_state;
uint16_t bit;

while (1){
bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^
(lfsr >> 3) ^ (lfsr >> 5) ) & 1;
lfsr =  (lfsr >> 1) | (bit << 15);
}

return 0;
}


Each iteration of the loop rotates the register to the right by one position; but what is stored in the MSB is not the value of the LSB but the value obtained by taking xor of the 0th, 2nd, 3rd and 5th bit positions.

Here is a Python program which implements this idea; the random bit sequence is visualized by feeding it to an LED on the IcoBoard.

from migen import  *
from migen.fhdl import verilog

MAX_PERIOD = 5000000

def new_val(lfsr):
bit = ((lfsr >> 0) ^ \
(lfsr >> 2) ^  \
(lfsr >> 3) ^  \
(lfsr >> 5)) & 1

return (lfsr >> 1)  | (bit << 15)

m = Module()

lfsr = Signal(16, reset=0xACE1)
counter = Signal(max=MAX_PERIOD)
period = Signal(max=MAX_PERIOD, reset=MAX_PERIOD)

led1 = Signal()

m.comb += led1.eq(lfsr[0])

m.sync += If(counter == 0,
counter.eq(period),
lfsr.eq(new_val(lfsr))
).Else(counter.eq(counter-1))

print(verilog.convert(m, ios={led1}))



The linear feedback shift register (lfsr in the above code) is initialized as a 16 bit register with reset value equal to 0xACE1. The LED is connected to the LSB of the lfsr. By default, Signal creates an unsigned register - so we need not worry about the nature of the right shift operation.

The statement:

counter = Signal(max=MAX_PERIOD)



creates a counter register with enough bits to hold the maximum value of MAX_PERIOD.

The statement:

period = Signal(max=MAX_PERIOD, reset=MAX_PERIOD)



creates a register called period with enough bits to hold the maximum value of MAX_PERIOD; this register will also get a reset value of MAX_PERIOD.

We will rotate the lfsr once every MAX_PERIOD cycles of the 100MHz clock. Here is the statement which performs this action:

m.sync += If(counter == 0,
counter.eq(period),
lfsr.eq(new_val(lfsr))
).Else(counter.eq(counter-1))



The “If” that you see here is simply a Migen class; the “Else” is simply a method on an “If object”. The “If” object will contain a statement which checks a condition, a set of “actions” to be taken if the condition is true and another set of actions to be taken if the condition is false. During Verilog code generation, these are mapped to proper Verilog constructs.

You can watch the random bitstream below: