← All problems

LFSR

Medium · Sequential · SystemVerilog · VHDL

A premium problem. Subscribe to open it in the editor, run the testbench and see where your design lands.

Design a Fibonacci LFSR pseudo-random number generator.

A linear feedback shift register (LFSR) is a shift register whose next input bit is the XOR of a few of its own bits, the taps. Each cycle it shifts once, so with the right taps a WIDTH-bit register walks through every non-zero value before repeating, which makes it the cheapest hardware source of pseudo-random numbers: a handful of flip-flops and XOR gates, no multiplier. The all-zero value is the one it can never leave, since the XOR of zeros is zero, so an LFSR is reset to all ones and must be seeded with a non-zero value.

The register is WIDTH bits wide and its state is the pseudo-random number: prng_out is the state of the register. The feedback bit is the XOR of the register bits at the positions where TAPS has a 1; a shift moves the register right by one bit and the feedback bit enters at bit WIDTH-1. The default TAPS = 16'hB400 is a maximal-length tap set.

rst_n is a synchronous, active-low reset; the reset value is all ones. load is a synchronous load of seed into the register. en enables a shift of the register. A reset overrides a load and a load overrides a shift; with none of the three asserted the register holds.

valid is asserted only in the cycle after a shift.

  • Encoding

Open this challenge in the editor →