State Machine Interview Vault and Revision

The machine needs to remember one fact: is the number of 1s so far even or odd? That gives two states.

A 0 changes nothing, and a 1 flips the state. In hardware this is a single T flip-flop with T = x, and z is simply its output - a Medvedev machine.

The machine must remember two facts: is the lamp on, and is the button already down? Two yes-or-no facts give four states.

The lamp changes only when the machine moves from a "button up" state to a "button down" state. Holding the button keeps the machine in ON1 or OFF1, so nothing more happens.

There is a handy rule for two's complement. Starting from the right, copy the bits up to and including the first 1, then invert every bit after it. For example, 0110 1000 becomes 1001 1000.

So the machine needs to remember whether the first 1 has gone by yet. Entries read next state / output:

In COPY the output equals the input, and in INVERT it is the opposite. It must be a Mealy machine, because each output bit depends on the input bit arriving in the same cycle.

When you add by hand, you work from the right and remember one thing between columns: the carry. So the state is the carry, and a serial adder needs only two states. In each cycle:

• the sum bit is s = a XOR b XOR carry - a Mealy output, because it uses the inputs now
• the next carry is 1 when at least two of a, b and the carry are 1

One flip-flop and a full adder can add numbers of any length. After the last pair of bits, the state holds the final carry.

Mealy: 2 states. The machine remembers the last value of x, in state L0 or L1. The output is z = x XOR last value, so it comes out in the same cycle as the change.

Moore: 4 states. A Moore output belongs to a state, so each state must also say whether a change has just happened:

The Moore output also arrives one cycle later, in the state after the change. This is the usual trade: Mealy is smaller and quicker, while Moore is steadier.

First, the next state for every present state and every value of u:

For a D flip-flop, D is simply the next value.

• Bit 0 changes at every step, up or down: D0 = NOT Q0.
• Bit 1 flips when counting up from Q0 = 1, or counting down from Q0 = 0. So it flips exactly when Q0 equals u: D1 = Q1 XOR (Q0 XNOR u).

A K-map of D1 shows a checkerboard pattern - the sign of an XOR.

A T flip-flop flips when T = 1, so T must be 1 exactly when a bit has to change. We already know when each bit changes:

• T0 = 1, because bit 0 changes at every step
• T1 = Q0 XNOR u, because bit 1 changes when Q0 equals u

That is why T flip-flops suit counters so well. Each equation simply answers the question "when does this bit flip?"

Remember the JK rules: J = 1 and K = 1 flips; J = 0 and K = 1 clears; J = 1 and K = 0 sets; J = 0 and K = 0 holds.

The counter goes 00, 01, 10 and back to 00, as it should. From the unused state 11 it reaches 00 in one step, so it can never get stuck there. A counter like this is called self-correcting.

module lamp_toggle (
  input  wire clk,
  input  wire rst,
  input  wire b,            // the button: already debounced and synchronised
  output wire lamp
);
  // Gray codes round the loop; bit 0 is the lamp
  localparam [1:0] OFF0 = 2'b00, ON1 = 2'b01, ON0 = 2'b11, OFF1 = 2'b10;
  reg [1:0] state, next_state;

  always @(posedge clk)
    if (rst) state <= OFF0;
    else     state <= next_state;

  always @(*) begin
    next_state = state;                  // default: stay
    case (state)
      OFF0: if (b)  next_state = ON1;    // pressed: lamp on
      ON1:  if (!b) next_state = ON0;    // released
      ON0:  if (b)  next_state = OFF1;   // pressed again: lamp off
      OFF1: if (!b) next_state = OFF0;   // released
    endcase
  end

  assign lamp = state[0];                // ON1 = 01 and ON0 = 11
endmodule

The codes were chosen with care. Round the loop they form a Gray sequence, so one bit changes per step. And bit 0 is 1 in exactly the two ON states, so the lamp comes straight from a flip-flop and cannot glitch. That is output encoding, from Volume 05. All four codes are used, so there is no illegal state to guard against.

module serial_adder (
  input  wire clk,
  input  wire rst,          // clears the carry before a new sum
  input  wire a, b,         // one bit of each number per cycle, LSB first
  output wire s             // one bit of the sum per cycle
);
  reg carry;                // the whole state: one flip-flop

  assign s = a ^ b ^ carry; // Mealy output: uses the inputs now

  always @(posedge clk)
    if (rst) carry <= 1'b0;
    else     carry <= (a & b) | (a & carry) | (b & carry);
endmodule

With only two states, there is no need for named states or a case statement. The carry flip-flop is the state register, and the two equations are the whole machine.

• Binary and Gray: 4. Three bits give only 8 codes; four give 16, which is enough.
• One-hot: 12. One flip-flop per state.
• Johnson: 6. A Johnson code with n flip-flops has 2n codes, so 6 flip-flops give 12.

Fewer flip-flops usually means more decoding logic. One-hot spends flip-flops to save logic.

Use a Gray code: A = 00, B = 01, C = 11 and D = 10. Every step changes one bit, including the step from D back to A.

With one bit changing at a time, gates that decode the state never see a false code in between, so decoded outputs cannot glitch (Volume 13). Fewer flip-flops toggle, too, which saves power.

Keep one state for each prefix of the pattern that the input might be in the middle of: S0 (nothing useful yet), S1 (seen 1) and S11 (seen 11). Entries read next state / output:

Two entries deserve a second look. In S11, another 1 keeps the machine in S11, because the last two bits are still 11. And after a match the input ends in 0, which starts no new match, so the machine returns to S0.

Five: one for each prefix of the pattern, from nothing up to the whole of it. S1001 is the only state with z = 1.

The hard part is where each state goes when a bit breaks the pattern. Use the longest-prefix rule from Volume 06: find the longest ending of the input that is still a prefix of 1001. From S1001, a 0 makes the input end in ...10010, which ends with 10, so go to S10. From S100, a 0 makes ...1000. No ending of that is a prefix of 1001, so go back to S0.

Use the prefixes of both patterns as states: S0 (nothing), S1 (1), S10 (10) and S11 (11). The two patterns share their first bit, so four states cover both. Entries read next state / output:

After 101 is found, the input ends in 1, so the machine goes to S1. After 110, it ends in 10 - the start of 101 - so the machine goes to S10, ready for a 1.

Number the bits from 1 to 10.

• Overlapping: 3 matches, ending at bits 4, 7 and 10. Each match shares its last 1 with the next one.
• Non-overlapping: 2 matches, ending at bits 4 and 10. After the first match the detector starts afresh at bit 5. The match ending at bit 7 needs bit 4, so it does not count.

In the machine, the only difference is where it goes after a match. An overlapping detector goes to the state for the longest prefix; a non-overlapping one goes back to S0.

Keep the remainder after dividing by 5: five states, R0 to R4. Each new bit doubles the number and adds the bit, so the new remainder is (2 × r + x) mod 5.

Try it with 1010, which is ten: R0 → R1 → R2 → R0 → R0. It ends in R0, so z = 1, and ten is indeed divisible by 5.

Only 3 - and the machine from Volume 06, with states R0, R1 and R2, works without any change. This is a favourite trick question.

Here is why. The place values in binary are 1, 2, 4, 8, 16 and so on. Divided by 3, they leave remainders 1, 2, 1, 2, 1 ... and when counting in threes, 2 is the same as −1. So a number's remainder is the number of 1s in the places worth 1, 4, 16 ... minus the number of 1s in the places worth 2, 8, 32 ... Reading the bits in the opposite order either keeps both groups as they are, or swaps them. At worst the remainder changes sign - and a remainder of 0 stays 0.

This needs a special property of 3, so do not expect it in general. For 5 it fails. 19 is 10011 in binary. Fed in backwards, the bits 1, 1, 0, 0, 1 look like 11001, which is 25, so the machine would wrongly call 19 divisible by 5.

Think of two small machines running side by side. One counts the 1s in threes: A, B or C for 0, 1 or 2 ones so far, after taking away every full three. The other tracks whether the number of 0s is even (0) or odd (1). The combined machine is a product machine, with one state for each pair: 3 × 2 = 6 states.

A 0 flips the digit, and a 1 moves the letter on: A → B → C → A. Only A0 has z = 1. No two of these states are equivalent, so 6 is the minimum.

At 50 MHz there are 50,000,000 cycles per second, so 50,000 per millisecond. Count 0, 1, 2 ... 49,999 and back to 0, and make a one-cycle tick when the count is 49,999. The largest value, 49,999, needs 16 bits, because 2¹⁶ = 65,536.

A common slip is to count up to 50,000. That is 50,001 different values, so the tick comes once every 50,001 cycles.

5 ms at 25 MHz is 0.005 × 25,000,000 = 125,000 cycles. A counter that reaches 125,000 needs 17 bits: 2¹⁶ = 65,536 is too small, and 2¹⁷ = 131,072 is enough.

The counter restarts whenever the input differs from the accepted level. Only an input that stays steady for the whole 5 ms lets it reach the end.

000, 100, 110, 111, 011, 001, and back to 000: six states from three flip-flops. A Johnson counter with n flip-flops always has 2n states.

Each state is recognised by a single 2-input gate. And since only one bit changes per step, these decoded outputs do not glitch. Those are two good reasons to use a Johnson counter for a simple sequencer.

The machine must remember how much has been paid: 0, 5 or 10. That gives three states. When a coin brings the total to 15 or more, the outputs fire in the same cycle and the machine goes back to S0.

With no coin, the machine stays where it is. You can check that no money is ever lost. Every coin adds to the amount the state stands for, and every drink (15) and every change (5) takes it back to 0.

• One bit: 50,000,000 ÷ 115,200 = 434.03, so 434 cycles. The real rate is then 115,207 baud - only 0.006% fast, far inside what a UART tolerates.
• One character: 10 bits, so 4,340 cycles.
• Characters per second: at most 115,200 ÷ 10 = 11,520.
• First look: half a bit, 217 cycles, after the start bit's falling edge. That is the middle of the start bit. The receiver checks that the line is still 0, then samples every 434 cycles, in the middle of each data bit.

The machine remembers whose turn it is when both ask: state P0 (requester 0 goes first) or P1.

The rule is simple: whoever is served goes to the back of the queue. The grants are Mealy outputs, because they depend on the requests. When both ask all the time, the grants alternate g0, g1, g0, g1 and so on. A requester that keeps asking never waits more than one cycle. This is a round-robin arbiter, and the same idea works for more requesters.

(48, 18) → (30, 18) → (12, 18) → (12, 6) → (6, 6). That is four subtractions, and the answer is 6.

The controller only chooses what happens in each cycle, from the comparison results. The datapath does the actual subtracting. That split is what makes an FSMD easy to design.

Use the partition method from Volume 10. First, group the states by output: P0 = {A, B, C, E} {D, F}.

Next, see which group each state's arrows lead to:

• A goes to B and C, which are both in the first group.
• B, C and E go to the second group on 0, and to the first group on 1.
• D and F go to the first group on both inputs.

A behaves differently from B, C and E, so it splits off: P1 = {A} {B, C, E} {D, F}. Checking again changes nothing, so the machine needs only 3 states:

Count the bits in which 01111 differs from each code: 4 from S0, 1 from S1, 3 from S2 and 2 from S3. The nearest is S1, one bit away, so correct to S1. Every pair of codes is at least 3 bits apart, so after one flipped bit the right code is always the strictly nearest.

The voter takes the majority of each bit: 0110. The second copy has one bad bit and the third has another, in a different place. So every bit still has two correct copies.

The detector has 3 states × 2 inputs = 6 arrows, but 6 inputs are not enough. Look at S0: three arrows come into it (from S0, S1 and S11), but only two go out. The walk is in S0 at the start and after each of those three arrows, which makes four visits. Every visit except the last needs a way out, so S0 must be left at least three times. With only two arrows out, one of them must be used twice, so at least 7 inputs are needed.

Seven are enough: 0, 1, 0, 1, 1, 1, 0.

• Before: 0.2 + 7 × 0.3 + 0.1 = 2.4 ns, so fmax = 1 ÷ 2.4 ns, about 417 MHz.
• After: 0.2 + 3 × 0.3 + 0.1 = 1.2 ns, so fmax is about 833 MHz - twice as fast.

The flip-flops did not change. All the gain came from shallower next-state logic.