How many flip-flops are required for the implementation of this Mealy diagram?

Question

I'm trying to create a circuit diagram that corresponds to the Mealy diagram I created for the following problem, but I'm not sure how many flip-flops I should use.

Problem:

A data stream receives serial data of 1 bit, synchronised by a clock pulse. Create a Mealy State Diagram that:

1. Starts from an initial state (IS).
2. Outputs xy = 01 when it recognises the bit-sequence 1001 and returns to IS.
3. Outputs xy = 10 when it recognises the bit-sequence 011 and returns to IS.
4. In any other case, the system should return xy = 00.

Mealy Diagram (Corrected):
^{_{(This is the diagram I came up with)}}

Based on the Mealy diagram above, I would say 3 flip-flops are needed, because 100 needs 3 bits to be represented. Is there, however, a way to implement it with less? If so, why?

Answer 1

\$ n \$ flip-flops can represent \$ 2^n \$ states. The number of bits needed to represent all the states will be the number of flip-flops needed to implement that state machine. So for this state diagram, 4 flip-flops are needed because one of the states is 1001, which needs 4 bits. However through state reduction techniques like row matching method, successive partitioning method, implication chart, and state assignment/encoding techniques, no. of states (and no.of bits/state) to implement a state machine can be reduced. Consequently no. of flip-flops needed are reduced.

Answer 2

The names of the states do not determine the number of FFs required. The number depends on how many states there are and what kind of encoding you choose to use (e.g., binary vs. one-hot). Binary encoding requires \$\lceil{log_2N}\rceil\$ FFs, while one-hot requires \$N\$ FFs.

A Mealy machine also needs a FF for each output.

---

In any case, your diagram is incorrect. It only recognizes the sequences 10011 and 0111. It also fails to find either of the sequences if the initial bit is incorrect — for example, the sequence 11011 contains 011, but your machine won't find it.