G6.9.2 Galois to Fibonacci

MediumImplementIcarus Verilog + Yosys · serverReview the topic

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

SignalWidthRole
kind1input of each check
value64input of each check
Full specification
Given: the Galois LFSR (read-only; the check runs it beside yours)
// 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
Your module (keep the name and the ports)
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
RuleRequired
ShiftWith load = 0, f[6:0] takes f[7:1] at each edge: a right shift. Its output bit is f[0].
Feedbackf[7] takes the XOR of a fixed set of bits of f: your taps.
LoadWith load = 1, f takes the value whose output matches galois8 loaded with the same seed.
OutputAfter 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

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Seed 00000001

Input
load seed 00000001
Expected 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.

Run samples executes all 3 public checks. Check all tests runs 18 checks on the server.

Icarus Verilog + Yosys · server