Choose 9-bit LFSR taps that visit all 511 nonzero states, and make sure the register can never lock at zero.
Hardware context: A self-test pattern generator and a link scrambler, each built from a linear-feedback shift register. Find maximal-length taps for a 9-bit LFSR that cannot lock at zero.
A built-in self-test block needs 511 different 9-bit test words from a cheap generator. The starter LFSR repeats after 73 words, and a glitch to all zeros would stop it for good.
This is an Implement problem. Change the taps of lfsr9 so that its loop is maximal. Then make it leave the all-zeros state.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
kind | 2 | input of each check |
value | 72 | input of each check |
Full specification
module lfsr9 (
input logic clk,
input logic rst, // synchronous reset, active high: q becomes 000000001
output logic [8:0] q // the state itself: q is the register, written in always_ff
);
...
endmodule
| Rule | Required |
|---|---|
| Shift | At each edge, q[8:1] takes q[7:0]: a left shift. |
| Feedback | q[0] takes the XOR of a fixed set of bits of q: your taps. |
| Length | From the reset value 000000001, q visits all 511 nonzero values before it returns. |
| No lock | From 000000000, q becomes 000000001 at the next edge. Every other state follows the shift and the feedback. |
q must be the register itself: the check loads values straight into q between edges. It finds your taps by loading each one-hot value, then checks the same XOR on other loaded values.
Examples
Example 1
From Reset Around the Whole Loop- Input
reset, then edges until q is 000000001 again
- Output
reset_value_is_000000001 = yes, edges_until_000000001_again = 511, edges_that_shifted_left = 511, times_q_was_all_zeros = 0
A maximal 9-bit LFSR returns to 000000001 after exactly 511 edges. Every edge is a left shift, and q is never all zeros. The starter returns after 73.
Example 2
Out of the All-Zeros State- Input
reset, 3 edges, load 000000000
- Output
q_after_the_edge_from_zero = 'b000000001, next_edge_shifted_left = yes
The check loads 000000000 into q. At the next edge q must be 000000001, and the edge after that is an ordinary shift.
Example 3
The Taps, Then Eight Loaded States- Input
load each one-hot state, then 100000000, 111111111, 010101010, 000000011, 110000001, 001110100, 011111111, 100000001
- Output
every_edge_shifted_left = yes, new_bit_was_the_xor_of_the_same_taps = yes, q8_is_a_tap = yes
The check loads each one-hot value to learn your taps. Then it loads eight other values: each new bit must be the XOR of the same taps.
Constraints and Contract
- Keep the module name and the ports. Assign q in one always_ff block. The design must synthesize with no latches.
Hints
Hint 1
Run the first example after each change: it shows how many edges the loop takes.
Hint 2
For 9 bits, q8 is always a tap. Try each second tap from q7 down to q0, or look up a primitive polynomial of degree 9.
Hint 3
Term x^k of a polynomial is the tap on q[k-1]. For zero, detect q == 0 and treat it on its own.
What the grader checks: One full loop from reset (up to 600 edges). Taps measured from the nine one-hot states and checked on 40 other loaded states. Loads of zero after 0, 3 and 40 edges, and resets from three loaded states.
The submitted design must synthesize with 0 latches and no combinational loop. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.
13 checks on Icarus Verilog + Yosys · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 2 steps and the final capstone