Design Interview Questions 2 :

Question 1 : How do you combine different states in an FSM?. Is there any benefit in combining States?.

FSM states can be combined if the State transitions from/to the States are same. By combining various FSM States we can save on following things:

1. Design Space for Verification: With fewer states we have lesser State transitions to verify hence Verification is easier and faster.

2. Power: With Lesser States less Flops can be needed saving more power. Specifically when we are using.

3. Area & Complexity : With lesser States complexity of combinational logic to calculate next-state logic is simpler and also lesser gates are needed saving area.

Question 2: Design a Fixed Priority Arbiter and Round-Robin Arbiter?

logic [3:0] req;
logic [3:0] grnt;
logic [3:0] mask;
logic [3:0] mask_comb;
logic [3:0] mask_comb_q;
logic [3:0] last_grnt_ff;


//Round-Robin Arbiter version-1 (Masking based- Same cycle Grant)
always_comb begin
 if(|req[3:0]) begin
  casez(last_grnt_ff[3:0])
    4'b0001 : mask_comb = 4'b1110;
    4'b0010 : mask_comb = 4'b1100;
    4'b0100 : mask_comb = 4'b1000;
    4'b1000 : mask_comb = 4'b1111;
    default : mask_comb = 4'b1111;
  endcase
 end
end

assign mask_comb_q = (mask_comb == 4'h0) ? req : (req & mask_comb);

always_comb begin
  casez(mask_comb_q[3:0]) 
    4'b0001 : grnt = 4'b1110;
    4'b0010 : grnt = 4'b1101;
    4'b0100 : grnt = 4'b1011;
    4'b1000 : grnt = 4'b0111;
    default : grnt = 4'b0000;
  endcase
end

always_ff @(posedge clk or negedge rst) begin
 if(!rst)
   last_grnt_ff <= 4'h0;
 else if (|req)
   last_grnt_ff <= grnt;
 else
   last_grnt_ff <= grnt;
end

//Round-Robin Arbiter version-2 (FSM based- Next Cycle Grant)
always_ff @(posedge clk or negedge rst) begin
  if(!rst)
    grnt_pstate <= 4'h0;
  else
    grnt_pstate <= grnt_nstate;
end

always_comb begin
  casez (grnt_pstate)
    4'b0000 : begin
               casez(req)
               4'b???1 : grnt_nstate = 4'b0001;
               4'b??10 : grnt_nstate = 4'b0010;
               4'b?100 : grnt_nstate = 4'b0100;
               4'b1000 : grnt_nstate = 4'b1000;
               default : grnt_nstate = 4'b0000;
              endcase
              end
    4'b0001 : begin 
               casez(req)
                4'b??1? : grnt_nstate = 4'b0010;
                4'b?10? : grnt_nstate = 4'b0100;
                4'b100? : grnt_nstate = 4'b1000;
                4'b0001 : grnt_nstate = 4'b0001;
                default : grnt_nstate = 4'b0001;
               endcase 
              end
    4'b0010 : begin 
               casez(req)
               4'b?1?? : grnt_nstate = 4'b0100;
               4'b10?? : grnt_nstate = 4'b1000;
               4'b00?1 : grnt_nstate = 4'b0001;
               4'b0010 : grnt_nstate = 4'b0010;
               default : grnt_nstate = 4'b0010;
               endcase
              end
   4'b0100 : begin
              casez(req)
               4'b1??? : grnt_nstate = 4'b1000;
               4'b0??1 : grnt_nstate = 4'b0001;
               4'b0?10 : grnt_nstate = 4'b0010;
               4'b0100 : grnt_nstate = 4'b0100;
               default : grnt_nstate = 4'b0100;
              endcase
             end
   4'b1000 :  begin
               casez(req)
               4'b???1 : grnt_nstate = 4'b0001;
               4'b??10 : grnt_nstate = 4'b0010;
               4'b?100 : grnt_nstate = 4'b0100;
               4'b1000 : grnt_nstate = 4'b1000;
               default : grnt_nstate = 4'b1000;
              endcase
             end
    default : grnt_nstate = gnrt_pstate;
 endcase
end

//Fixed Priority Arbiter version-1 (Priority Mux)
always_comb begin
  grnt[3:0] = 4'b0;
  for (int i = 0; i < 4; i++) 
    if(req[i] == 1'b1) begin
      grnt[i] = 1'b1;
      break;
    end  
  end
end

//Fixed Priority Arbiter version-2 (Priority Mux- Synthesis Friendly)
always_comb begin
  grnt[3:0] = 4'b0;
  casez(req[3:0])
    4'b???1 : grnt = 4'b0001;
    4'b??10 : grnt = 4'b0010;
    4'b?100 : grnt = 4'b0100;
    4'b1000 : grnt = 4'b1000;
    default : grnt = 4'b0000;
  endcase
end

Question 3: What is advantages of using one-hot encoding for FSM ?

One hot Coding simplifies combinational logic and reduces multi-bit Transitions to 2.

For E.g in below State, in any State Transition, one bit goes 1->0 and other goes from 0->1 in a State change. This also reduces power required by the logic.

State0 : 4'b0001
State1 : 4'b0010
State2 : 4'b0100
State3 : 4'b1000

However, if the number of States are more for E.g =>8 then more logic is required and combinational logic and number of Flops can increase Area and Power & in that case binary or Gray coding is preferred.

In some cases, Synthesis Tool can actually optimize the encoding depending on the Trade-off specified in Tool.