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
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
Can you post the explanation about how you achieved that design?
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 🙂
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
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.