Linear Feedback Shift Register (LFSR) in Verilog - Step-by-Step Execution

Concept Flow - Linear Feedback Shift Register (LFSR)

Initialize shift register with seed

↓

Shift bits right by 1 position

↓

Calculate feedback bit by XOR of selected bits

↓

Insert feedback bit at leftmost position

↓

Output current register value

↓

Repeat for next clock cycle

The LFSR shifts bits each cycle, calculates a new bit by XORing certain bits, inserts it, and outputs the register value repeatedly.

Execution Sample

Verilog

module lfsr(
  input clk,
  input reset,
  output reg [3:0] q
);
  always @(posedge clk or posedge reset) begin
    if (reset) q <= 4'b1001;
    else q <= {q[3] ^ q[2], q[3:1]};
  end
endmodule

A 4-bit LFSR that shifts bits right and inserts XOR of bits 3 and 2 at left on each clock.

Execution Table

Cycle	Register q (binary)	Feedback bit (q[3]^q[2])	Action	Output q
0	1001	-	Reset sets q to 1001	1001
1	1001	1	Shift right, insert feedback 1	1100
2	1100	1	Shift right, insert feedback 1	1110
3	1110	0	Shift right, insert feedback 0	0111
4	0111	1	Shift right, insert feedback 1	1011
5	1011	1	Shift right, insert feedback 1	1101
6	1101	0	Shift right, insert feedback 0	0110
7	0110	1	Shift right, insert feedback 1	1011
8	1011	1	Shift right, insert feedback 1	1101
9	1101	0	Shift right, insert feedback 0	0110
10	0110	1	Shift right, insert feedback 1	1011
Exit	-	-	Full period is 15 cycles before returning to 1001	-

💡 The LFSR produces a maximum-length sequence of 15 states before repeating.

Variable Tracker

Variable	Start (Cycle 0)	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10
q	1001	1100	1110	0111	1011	1101	0110	1011	1101	0110	1011
feedback bit	-	1	1	0	1	1	0	1	1	0	1

Key Moments - 3 Insights

Why does the feedback bit use XOR of q[3] and q[2]?

The feedback bit is calculated by XORing specific bits (q[3] and q[2]) to create a pseudo-random sequence; this is shown in the execution_table column 'Feedback bit' where each cycle's feedback depends on those bits.

Why does the register value repeat after some cycles?

Because the LFSR has a fixed size and feedback, it cycles through a sequence of states; the full period is 15 cycles before repeating, as shown in the exit note of the execution_table.

What happens on reset in the LFSR?

On reset, the register q is set to the initial seed 1001, as shown in cycle 0 of the execution_table, restarting the sequence.

Visual Quiz - 3 Questions

Look at the execution_table at cycle 3, what is the feedback bit?

A 0

B 1

C Undefined

D 3

💡 Hint

Check the 'Feedback bit' column for cycle 3 in the execution_table.

At which cycle does the register first become 0111?

A Cycle 1

B Cycle 3

C Cycle 2

D Cycle 4

💡 Hint

Look at the 'Register q (binary)' column in the execution_table.

If the feedback was changed to XOR of q[3] and q[1], how would the feedback bit at cycle 1 change?

A It would be undefined

B It would be 1

C It would be same as original

D It would be 0

💡 Hint

Compare bits q[3] and q[1] at cycle 0 from variable_tracker to calculate new feedback.

Concept Snapshot

Linear Feedback Shift Register (LFSR):
- A shift register that shifts bits each clock cycle.
- Feedback bit is XOR of selected bits (e.g., q[3]^q[2]).
- Feedback bit inserted at leftmost position after shift.
- Produces pseudo-random sequence cycling through states.
- Reset initializes register to a seed value.

Full Transcript

This visual execution shows a 4-bit Linear Feedback Shift Register (LFSR) in Verilog. The register q starts at 1001 on reset. Each clock cycle, the bits shift right by one position. The new leftmost bit is the XOR of bits q[3] and q[2]. The execution table traces each cycle's register value, feedback bit, and action. The variable tracker shows how q and feedback bit change over cycles. Key moments clarify why XOR is used for feedback, why the sequence repeats, and the effect of reset. The quiz tests understanding of feedback bit calculation, register values at cycles, and how changing feedback taps affects output. The snapshot summarizes the LFSR behavior and structure for quick reference.

Practice

1.

What is the main purpose of a Linear Feedback Shift Register (LFSR) in digital circuits?

easy

A. To store large amounts of data

B. To perform arithmetic addition

C. To convert analog signals to digital

D. To generate a pseudo-random sequence of bits

Solution

1. Step 1: Understand LFSR function

   An LFSR uses shift and XOR feedback to produce a sequence of bits that appears random.

2. Step 2: Identify main use

   This sequence is used for pseudo-random number generation and testing, not arithmetic or storage.

3. Final Answer:

   To generate a pseudo-random sequence of bits -> Option D

4. Quick Check:

   LFSR = pseudo-random bit generator [OK]

Hint: LFSR creates random-like bits by shifting and XOR [OK]

Common Mistakes:

• Confusing LFSR with memory storage
• Thinking LFSR does arithmetic
• Assuming LFSR converts analog signals

2.

Which of the following is the correct Verilog syntax to declare a 4-bit register named lfsr?

easy

A. reg [3:0] lfsr;

B. reg lfsr[3:0];

C. wire [4:1] lfsr;

D. reg (3:0) lfsr;

Solution

1. Step 1: Recall Verilog register declaration

   Registers are declared with reg [msb:lsb] name; syntax.

2. Step 2: Check each option

   reg [3:0] lfsr; uses correct syntax reg [3:0] lfsr;. reg lfsr[3:0]; uses wrong array style. wire [4:1] lfsr; uses wire, not reg. reg (3:0) lfsr; has invalid parentheses.

3. Final Answer:

   reg [3:0] lfsr; -> Option A

4. Quick Check:

   Correct reg syntax = reg [3:0] lfsr; [OK]

Hint: Use reg [msb:lsb] name; to declare registers [OK]

Common Mistakes:

• Using wire instead of reg for registers
• Incorrect bit range order or syntax
• Using parentheses instead of brackets

3.

Given this Verilog snippet for a 3-bit LFSR with taps at bits 3 and 2:

reg [2:0] lfsr = 3'b001;
always @(posedge clk) begin
  lfsr <= {lfsr[1:0], lfsr[2] ^ lfsr[1]};
end

What is the value of lfsr after 1 clock cycle?

medium

A. 3'b011

B. 3'b010

C. 3'b110

D. 3'b100

Solution

1. Step 1: Calculate first clock cycle

   Initial lfsr = 001. Feedback = lfsr[2]^lfsr[1] = 0^0=0.
   New lfsr = {lfsr[1:0], feedback} = {0,1,0} = 010.

2. Step 2: Confirm value

   After 1 clock cycle, lfsr = 3'b010, which matches 3'b010.

3. Final Answer:

   3'b010 -> Option B

4. Quick Check:

   Shift and XOR feedback = 010 after 1 cycle [OK]

Hint: Track bits step-by-step for each clock cycle [OK]

Common Mistakes:

• Mixing bit order in concatenation
• Calculating feedback incorrectly
• Confusing initial and next states

4.

Identify the error in this Verilog LFSR code snippet:

reg [3:0] lfsr = 4'b0000;
always @(posedge clk) begin
  lfsr <= {lfsr[2:0], lfsr[3] ^ lfsr[0]};
end

medium

A. The register size declaration is wrong

B. The feedback XOR taps are incorrect for 4-bit LFSR

C. Initial value can't be all zeros in LFSR

D. The concatenation order is reversed

Solution

1. Step 1: Check initial value

   LFSRs must not start with all zeros because they will stay stuck at zero forever (no feedback).

2. Step 2: Verify other parts

   Feedback taps and concatenation are valid for a 4-bit LFSR. Register size is correctly declared as 4 bits.

3. Final Answer:

   Initial value can't be all zeros in LFSR -> Option C

4. Quick Check:

   All-zero start = stuck LFSR [OK]

Hint: Never start LFSR with all zeros [OK]

Common Mistakes:

• Using zero initial value
• Misunderstanding feedback tap positions
• Incorrect bit concatenation order

5.

You want to design an 8-bit LFSR in Verilog that cycles through all 255 non-zero states before repeating. Which of the following tap combinations is a valid maximal-length feedback polynomial?

hard

A. Taps at bits 8 and 5 (lfsr[7] and lfsr[4])

B. Taps at bits 8 and 7 (lfsr[7] and lfsr[6])

C. Taps at bits 8 and 6 (lfsr[7] and lfsr[5])

D. Taps at bits 8 and 4 (lfsr[7] and lfsr[3])

Solution

1. Step 1: Recall maximal-length tap sets for 8-bit LFSR

   Common maximal-length taps for 8-bit LFSR are bits 8 and 5 (1-based indexing).

2. Step 2: Match options with known polynomials

   Taps at bits 8 and 5 (lfsr[7] and lfsr[4]) matches a valid maximal-length set. Taps at bits 8 and 7 (lfsr[7] and lfsr[6]), 8 and 6 (lfsr[7] and lfsr[5]), and 8 and 4 (lfsr[7] and lfsr[3]) are not maximal-length taps.

3. Step 3: Check indexing in Verilog (0-based)

   Bits 8 and 5 correspond to lfsr[7] and lfsr[4], which is Taps at bits 8 and 5 (lfsr[7] and lfsr[4]).

4. Final Answer:

   Taps at bits 8 and 5 (lfsr[7] and lfsr[4]) -> Option A

5. Quick Check:

   Maximal taps for 8-bit LFSR = bits 8 and 5 [OK]

Hint: Use known maximal taps like bits 8 and 5 for full cycle [OK]

Common Mistakes:

• Choosing non-maximal tap positions
• Confusing bit indexing (1-based vs 0-based)
• Assuming any two taps produce maximal length