Design a generator, to produce the following sequence:

0 → 1 → 1 → 1 → 2 → 2 → 3 → 4 → 5 → 7 → 9 → 12 → 16 → 21 → 28 → 37 → 0 → 1 → 1 → 1 → 2 → …

The diagram below shows the generator circuit. Note the circuit is reset when output reaches 37

1. Suyash Ahluwalia says:

Can you post the explanation about how you achieved that design?

1. chipressian says:

Have you noticed that x[N] = x[N-2] + x[N-3]? If so, you have establish the essence of this interview question.

Obviously, N-3 >= 0, i.e., N has to be at least 3. This also implies we need 3-stage pipeline.

Upon reset, these 3 stages will be initialized to 0, 1, 1. In addition, when output reaches 37, all stages will be reset again.

Hope you get the point 🙂

1. Ldm says:

I don’t agree with the block diagram, since you are using an XOR and 1-bit flip flops. I believe you need 5-bit registers and an addition.
I wrote this verilog code:

module genseq(input clk, input rst, output[5:0] x);

reg[5:0] state0;
reg[5:0] state1;
reg[5:0] state2;

assign x =state2;

always @(posedge clk or negedge rst) begin
if(~rst) begin
state2 <= 5’b0;
state1 <= 5’b00001;
state0 <= 5’b00001;
end
else begin
state2 <= state1;
state1 <= state0;
state0 <= state2 + state1;
end
end
endmodule

2. Ren says:

Hi Ldm,
I think he drew single flops for simplicity.I think they are 3 registers with each having 6 bits.
And that ‘+’ is not an XOR, it’s an ADD operation of the registers.

This site uses Akismet to reduce spam. Learn how your comment data is processed.