Build a Fibonacci LFSR whose output bit matches a given 8-bit Galois LFSR at every edge, from the same seed.
Hardware context: A self-test pattern generator and a link scrambler, each built from a linear-feedback shift register. Build the Fibonacci LFSR with the same output as a given Galois LFSR, seed mapping included.
A transmitter scrambles with the Galois LFSR galois8. The receiver team wants a Fibonacci LFSR that puts out the same bit stream. It must start from the seed the transmitter uses.
This is an Implement problem. Complete fib8. After a load with the same seed, f[0] must equal galois8's g[0] at every edge. The starter copies the Galois seed and mask as they are.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
kind | 1 | input of each check |
value | 64 | input of each check |
Full specification
// galois8: the given Galois LFSR (read-only). Its output bit is g[0].
module galois8 (input logic clk, load, input logic [7:0] seed, output logic [7:0] g);
always_ff @(posedge clk)
if (load) g <= seed;
else g <= {1'b0, g[7:1]} ^ (g[0] ? 8'b1011_1000 : 8'b0000_0000);
endmodule
module fib8 (
input logic clk,
input logic load, // 1: start at this edge from the same seed as galois8
input logic [7:0] seed, // the seed given to galois8
output logic [7:0] f // the Fibonacci register; its output bit is f[0]
);
...
endmodule
| Rule | Required |
|---|---|
| Shift | With load = 0, f[6:0] takes f[7:1] at each edge: a right shift. Its output bit is f[0]. |
| Feedback | f[7] takes the XOR of a fixed set of bits of f: your taps. |
| Load | With load = 1, f takes the value whose output matches galois8 loaded with the same seed. |
| Output | After a load, f[0] equals g[0] at the load edge and at every edge after it. |
f must be the register itself: the check also loads values straight into f and reads the next value.
Examples
Example 1
Seed 00000001- Input
load seed 00000001
- Output
f_after_the_load = 'b01110001, f_after_edge1 = 'b00111000, f_after_edge2 = 'b00011100, f_after_edge3 = 'b10001110, f_after_edge4 = 'b01000111, f_after_edge5 = 'b00100011, f_after_edge6 = 'b10010001, f_after_edge7 = 'b01001000, f_after_edge8 = 'b10100100, f0_equalled_g0_for_608_edges = yes, every_edge_shifted_right = yes
galois8 loaded with 00000001 gives the output bits 1, 0, 0, 0, 1, 1, 1, 0, starting at the load. So f must load 01110001, read from f[0] upward.
Example 2
Seed 10100101- Input
load seed 10100101
- Output
f_after_the_load = 'b00010101, f_after_edge1 = 'b10001010, f_after_edge2 = 'b11000101, f_after_edge3 = 'b01100010, f_after_edge4 = 'b00110001, f_after_edge5 = 'b00011000, f_after_edge6 = 'b00001100, f_after_edge7 = 'b00000110, f_after_edge8 = 'b10000011, f0_equalled_g0_for_608_edges = yes, every_edge_shifted_right = yes
Another seed. The check also compares f[0] with g[0] for 608 edges and checks that every edge shifts f right.
Example 3
A New Seed While Running- Input
5 edges from seed 00000001, then load seed 00111100
- Output
f_after_the_load = 'b01111100, f_after_edge1 = 'b10111110, f_after_edge2 = 'b11011111, f_after_edge3 = 'b01101111, f_after_edge4 = 'b10110111, f_after_edge5 = 'b11011011, f_after_edge6 = 'b11101101, f_after_edge7 = 'b11110110, f_after_edge8 = 'b01111011, f0_equalled_g0_for_608_edges = yes, every_edge_shifted_right = yes
Both run for 5 edges from 00000001, then load 00111100. A load must restart f from the new seed, whatever f held.
Constraints and Contract
- Keep the module name and the ports. Assign f in one always_ff block, so that every bit of f comes straight from a flip-flop. The design must synthesize with no latches.
Hints
Hint 1
f[0] is the output now, f[1] the output one edge later, and so on. So after a load, f must hold the next 8 output bits of galois8.
Hint 2
Those 8 bits can be worked out from the seed in logic: a function can run the Galois step 8 times.
Hint 3
For the taps, compare which bits the Galois mask XORs with the bits a Fibonacci register must XOR. The lesson's 4-bit pair shows the pattern.
What the grader checks: Seeds 00000000, 00000001, 00000010, 10000000, 11111111, the mask and eight random seeds, two loaded while running. Each is compared for 608 edges. Twenty-four values are loaded straight into f and stepped once.
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.
18 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