TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

Interview Question: Finding the Combination of an FSM Padlock

Murugavel Ganesan
by
0
Share Facebook X LinkedIn WhatsApp Email

Hello All:
In fact it has been a long time since we had posted any sort of interview questions or puzzles and so here we are with a very practical problem.

Let's see how many of you can crack it! The puzzle is stated below as it was first posted in 2008. The answer, with a full worked solution, now follows it, so stop reading at the question if you want to try it first.

The problem

The Sheel lock Company has recently received an order from Mr. Manmohan Singh for their all-digital Perfectly Perplexing Padlock (P3). The P3 has two buttons ("0" and "1") that when pressed cause the FSM controlling the lock to advance to a new state. In addition to advancing the FSM, each button press is encoded on the B signal (B=0 for button "0", B=1 for button "1").

The padlock unlocks when the FSM sets the UNLOCK output signal to 1, which it does whenever the last N button presses correspond to the N-digit combination. Unfortunately the design notes for the P3 are incomplete. Using the specification above and clues gleaned from the partially completed diagrams below fill in the information that is missing from the state transition diagram with its accompanying truth table.

When done

  • each state in the transition diagram should be assigned a 2-bit state name S1S0 (note that in this design the state name is not derived from the combination that opens the lock),
  • the arcs leaving each state should be mutually exclusive and collectively exhaustive,
  • the value for UNLOCK should be specified for each state, and
  • the truth table should be completed.














What is the combination for the lock?

The puzzle is adapted from a finite state machine tutorial problem used in MIT's digital design courses; the original version is Problem 2 in the MIT 6.111 (Fall 2005) FSM tutorial problems.

What the puzzle is really testing

The lock is a sequence detector: a finite state machine that watches a stream of bits and raises an output whenever the most recent bits match a pattern. Sequence detectors are among the most common FSM interview questions because they test three skills at once:

  • Turning a word description into states that each mean something ("I have seen the first digit", "I have seen the first two digits").
  • Handling overlap: when a wrong press arrives, the machine must not always go back to the start, because the wrong press may itself be the start of the combination.
  • Writing the next-state and output logic as a truth table and then as equations or RTL.

The two-bit state name is a strong clue. Two bits give at most four states, and a detector for an N-digit combination needs N + 1 states (nothing matched, 1 digit matched, ..., all N matched). So the combination has at most three digits.

The answer

The combination is 100, as given in the MIT 6.111 answer set for this problem. The deep dive below builds a complete detector for 100 from scratch, so you can check it against the clues in the diagram.

Deep dive: the numbers and details

This part holds the state diagram in table form, the truth table, the logic equations and RTL for a "100" detector. Skip it if the answer is all you need.

States and their meaning

A Moore machine (output depends only on the state) with four states. The state names below are one valid assignment; the diagram in the puzzle uses its own names, which, as the problem says, are not derived from the combination.

StateMeaningUNLOCK
ANo useful progress0
BLast press was "1"0
CLast two presses were "1 0"0
DLast three presses were "1 0 0": open1

Transitions, including overlap

Current stateB = 0B = 1
AAB
BCB
CDB
DAB

The overlap cases are the interesting ones. From B, another "1" keeps us in B, because the latest "1" is still a valid first digit. From C, a "1" breaks "1 0" but starts a new attempt, so we go to B, not A. From D (unlocked), a "0" leaves the last presses as "0 0", which matches no prefix of 100, so we go to A; a "1" starts a new attempt in B. Every state has exactly one arc for B = 0 and one for B = 1, so the arcs are mutually exclusive and collectively exhaustive, as the problem requires.

Truth table with a state encoding

Choose A = 00, B = 01, C = 10, D = 11 (any one-to-one assignment works; this one keeps the equations short).

S1S0BS1'S0'UNLOCK
000000
001010
010100
011010
100110
101010
110001
111011

Logic equations

Reading the table (with ~ for NOT, & for AND, | for OR):

S1'    = ~B & (S1 ^ S0)          // from B (01) or C (10) on a 0
S0'    = B | (S1 & ~S0)          // any 1, or C (10) on a 0
UNLOCK = S1 & S0                  // state D

Check one row: state C (S1 = 1, S0 = 0) with B = 0 gives S1' = 1 & (1 ^ 0) = 1 and S0' = 0 | (1 & 1) = 1, so the next state is 11 = D. Correct.

The same machine in Verilog

module p3_lock (
  input  wire clk,
  input  wire rst_n,
  input  wire press,   // one-cycle pulse per button press
  input  wire b,       // 0 for button "0", 1 for button "1"
  output wire unlock
);
  reg [1:0] s;
  always @(posedge clk or negedge rst_n)
    if (!rst_n)     s <= 2'b00;
    else if (press) s <= { ~b & (s[1] ^ s[0]), b | (s[1] & ~s[0]) };
  assign unlock = s[1] & s[0];
endmodule

The press input reflects the specification: the FSM advances only when a button is pressed, not on every clock.

Test sequence

Pressing 1, 1, 0, 0 walks A, B, B, C, D and opens on the fourth press, because the last three presses are 1 0 0. Pressing 1, 0, 1, 0, 0 walks A, B, C, B, C, D and opens on the fifth press. Pressing 1, 0, 0, 0 opens on the third press and locks again on the fourth.

Interview follow-ups

  • Mealy version: a Mealy machine can raise UNLOCK on the arc from C with B = 0, needing only three states, at the cost of an output that depends directly on the input.
  • Longer combinations: an N-digit combination needs N + 1 states in a Moore detector, so a 4-digit code would need a 3-bit state register.
  • Security: because the lock checks only the last N presses, an attacker can try codes back to back without any reset, which is a good discussion point about real lock design.
Murugavel Ganesan
About the Author
Murugavel Ganesan
Product Director | SerDes · IVN · Edge AI · Compute | Ex Intel · Infineon

A semiconductor product leader working across product architecture, definition, strategy, and silicon and software execution, from concept through volume production. He has worked with teams across Asia, Europe and the USA, including at Intel, Infineon and ArrayComm.

His work covers ASICs, SoCs, FPGAs and chiplets for wireless, wireline, automotive, IoT and AI, including PCIe, CXL and DDR interfaces alongside RF and mixed-signal design.

Share Facebook X LinkedIn WhatsApp Email

Post a Comment

0 Comments

Your comments will be moderated before it appears here.

Post a Comment (0)

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!