Workplace FSM Design Challenge: Minimum States and Registers

The workplace FSM challenge asks for a three-state machine (S0, S1, S2) that drives y combinationally in S0 and drives z in the cycle after S0, while using as few states, edges, transient states and registers as possible. The minimum answer is three clocked states, four edges, no transient states and two flip-flops: y is a multiplexer of j and k selected by a in S0, and z is simply m in S1 and n in S2, because the state the machine moves to already remembers whether b was true. The solution originally posted here put z in the wrong cycle and inferred latches; a corrected design, tested in simulation, is below.

You are part of the "Chakra" design team, building a combined smart watch and goggles. A senior manager is coming for a design review in the afternoon. Your project leader has to go out to lunch with the manager, and has left you to design the last state machine in the system before the design review.

Key takeaways

• Requirements 8 to 11 fix the state graph: S0 goes to S1 or S2, S1 goes to S2, S2 goes to S0. Three states and four edges are the minimum.
• "In the next clock cycle assign m to z" can be met without an extra register: entering S1 only happens when b was true, so S1 itself is the memory.
• y depends on the current state and current inputs, so it is a Mealy output: y = a ? j : k in S0.
• Assign every output in every branch of a combinational process, or synthesis infers latches.
• The minimum register count is two flip-flops for the state (binary encoding of three states) and none for the outputs.

The problem

The functional requirements of the state machine are given below, where a means that a is true (in VHDL, equal to '1') and !a means that a is false (not equal to '1').

Functional requirements

1. The inputs are a, b, j, k, m and n.
2. The outputs are y and z.
3. The initial state is S0.
4. If the current state is S0 and a, then in the current clock cycle assign j to y.
5. If the current state is S0 and !a, then in the current clock cycle assign k to y.
6. If the current state is S0 and b, then in the next clock cycle assign m to z.
7. If the current state is S0 and !b, then in the next clock cycle assign n to z.
8. If the current state is S0 and b, then the next state shall be S1.
9. If the current state is S0 and !b, then the next state shall be S2.
10. If the current state is S1, then the next state shall be S2.
11. If the current state is S2, then the next state shall be S0.

Rules and goals

1. You may choose y and z to be either registered or combinational. Both may be combinational, both registered, or one of each. One of the optimisation goals below is to minimise the number of registers.
2. Your design shall satisfy the functional requirements.
3. Your goals, in order of decreasing importance, are:
   1. minimum number of clocked (real) states
   2. minimum number of edges
   3. minimum number of transient states
   4. minimum number of registers

Working out the answer

Step 1: states and edges

Requirements 8 to 11 already describe the graph. S1 and S2 cannot be merged, because S1 must go to S2 and S2 must go to S0. S0 cannot be merged with either, because it has different outputs and a branching next state. So three clocked states is the minimum, and the edges are S0 to S1, S0 to S2, S1 to S2 and S2 to S0: four in total. There is no reason to add a transient (unclocked) state, so that count is zero.

Step 2: output y

y must follow j or k in the same cycle the machine is in S0. That needs a combinational (Mealy) output: y = a ? j : k when the state is S0. Registering y would delay it by one cycle and break requirements 4 and 5. In S1 and S2 the value of y is not specified, so it is a don't care.

Step 3: output z, and why no extra register is needed

This is the trick in the question. z must take m in the cycle after S0 if b was true, and n in the cycle after S0 if b was false. But when b is true the machine goes to S1, and when b is false it goes to S2. So in the next cycle the current state already tells you which branch was taken:

• In S1, z = m.
• In S2, z = n.

S2 is also reached from S1, and in that cycle z is not specified, so driving n then is allowed. z is a Moore-style selection by state of a live input, and needs no flip-flop of its own.

One caveat worth raising in an interview: if "assign m to z in the next cycle" is read as "the value m had in S0 must appear on z one cycle later", then z must be registered (z_reg captures b ? m : n while in S0). That costs one extra flip-flop. Under the usual reading of this puzzle, z equals m during the next cycle, so the combinational answer wins on goal (d).

Step 4: registers

Three states need at least two flip-flops with binary encoding (one-hot would use three). With both outputs combinational, the total is two registers.

Goal	Result	Why it is minimal
Clocked states	3	S0, S1 and S2 have different next states or outputs
Edges	4	Exactly the transitions in requirements 8 to 11
Transient states	0	None needed
Registers	2	ceil(log2 3) = 2 state bits; y and z combinational

Cycle-by-cycle example

Input values here are illustrative.

Cycle	State	a	b	j, k, m, n	y	z
1	S0	1	1	1, 0, 0, 1	1 (j)	don't care
2	S1	0	0	0, 1, 1, 0	don't care	1 (m)
3	S2	1	0	1, 1, 0, 0	don't care	don't care
4	S0	0	0	1, 0, 1, 1	0 (k)	don't care
5	S2	1	1	0, 0, 0, 1	don't care	1 (n)

What was wrong with the original solution

The original post gave a VHDL design with a synchronous process for the state register and a combinational process for outputs. The structure was right, but the code had four problems:

1. z in the wrong cycle: it assigned z <= m or n while in S0, which is the current cycle, not the next one as requirements 6 and 7 demand.
2. Latches: y and z were not assigned in S1 and S2, so the combinational process had to remember their old values. Synthesis infers latches, which adds storage elements and breaks the register goal.
3. Incomplete sensitivity list: process(current_state, a, b) omitted j, k, m and n, so simulation would not update y when j or k changed. Synthesis ignores the list, so simulation and hardware would disagree.
4. Non-standard packages: std_logic_arith and std_logic_unsigned are vendor packages, not IEEE standard, and are not needed here at all.

Corrected VHDL

library ieee;
use ieee.std_logic_1164.all;

entity chakra_fsm is
  port (clk, rst          : in  std_logic;   -- rst: synchronous, active high
        a, b, j, k, m, n  : in  std_logic;
        y, z              : out std_logic);
end entity chakra_fsm;

architecture rtl of chakra_fsm is
  type state_type is (S0, S1, S2);
  signal state, next_state : state_type;
begin
  -- State register: the only flip-flops in the design
  state_reg : process (clk)
  begin
    if rising_edge(clk) then
      if rst = '1' then
        state <= S0;
      else
        state <= next_state;
      end if;
    end if;
  end process;

  -- Next state and outputs, all combinational
  comb : process (state, a, b, j, k, m, n)
  begin
    next_state <= S0;      -- defaults stop latch inference
    y          <= '0';     -- don't care outside S0
    z          <= '0';     -- don't care in S0
    case state is
      when S0 =>
        if a = '1' then y <= j; else y <= k; end if;
        if b = '1' then next_state <= S1; else next_state <= S2; end if;
      when S1 =>
        z          <= m;
        next_state <= S2;
      when S2 =>
        z          <= n;
        next_state <= S0;
    end case;
  end process;
end architecture rtl;

The same design in Verilog

module chakra_fsm (
  input  wire clk,
  input  wire rst,              // synchronous, active high
  input  wire a, b, j, k, m, n,
  output reg  y,
  output reg  z
);
  localparam [1:0] S0 = 2'd0, S1 = 2'd1, S2 = 2'd2;
  reg [1:0] state, next_state;

  // State register: the only flip-flops in the design
  always @(posedge clk) begin
    if (rst) state <= S0;
    else     state <= next_state;
  end

  // Next state and outputs, all combinational
  always @* begin
    next_state = S0;            // also recovers from the unused code 2'd3
    y = 1'b0;                   // don't care outside S0
    z = 1'b0;                   // don't care in S0
    case (state)
      S0: begin
            y          = a ? j : k;    // requirements 4 and 5
            next_state = b ? S1 : S2;  // requirements 8 and 9
          end
      S1: begin
            z          = m;            // requirement 6: cycle after S0 with b
            next_state = S2;           // requirement 10
          end
      S2: begin
            z          = n;            // requirement 7: cycle after S0 with !b
            next_state = S0;           // requirement 11
          end
      default: next_state = S0;
    endcase
  end
endmodule

A self-checking testbench drove 2,000 random input vectors and checked y in every S0 cycle, and z and the state in every cycle after S0, then forced the unused state code 2'd3 and confirmed the machine returned to S0 on the next clock.

How interviewers probe this question

• "Do you need a register for z?" The answer they want is no, with the reason: the destination state encodes b.
• "Is y Moore or Mealy?" Mealy, because it depends on a, j and k in the current cycle.
• "What happens to y and z in states where they are not specified?" They are don't cares; assigning a default avoids latches and lets synthesis simplify.
• "What about the unused fourth code?" With two bits there is one illegal code. A default branch to S0 makes the machine recover. One-hot encoding would avoid nothing here and costs a third flip-flop.
• "What if y had to be registered?" Then it would appear one cycle late and requirements 4 and 5 could not be met, so registering y is not a valid option.

Common mistakes

• Adding a state S0b or S0nb to remember b, which increases the state count when the existing states already hold the information.
• Registering z with an extra flip-flop when the combinational answer meets the requirement.
• Leaving outputs unassigned in some branches and getting latches.
• Writing an incomplete sensitivity list in VHDL-93 (use process(all) in VHDL-2008, or always @* in Verilog).

FAQ

Why are there only four edges and not five?

The requirements define exactly four transitions. There is no self-loop on any state, because every state moves on every clock.

Could the machine be built with one flip-flop?

No. Three distinct states need at least two bits. One bit can only distinguish two states.

Would one-hot encoding be better?

It would use three flip-flops instead of two and so lose on the register goal. One-hot can give faster next-state logic in FPGAs, but that is not one of the goals here.