0
\$\begingroup\$

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)

enter image description here

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?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Why do you think it should be 4? Show your attempts to answer the question and we're more likely to help. \$\endgroup\$
    – Finbarr
    Jan 17, 2018 at 11:03
  • 2
    \$\begingroup\$ No, your question is not whether it can be implemented by the diagram. Your question is whether it is sufficient with 4 flip-flops, and you have not shown any effort to decide if this actually is the case or not. Like @Finbarr said; "Show your attempts to answer the question and we're more likely to help." \$\endgroup\$
    – MrGerber
    Jan 17, 2018 at 11:18
  • 2
    \$\begingroup\$ Please quickly realize that this is not a free design house, homework-answering service or an on-line technical encyclopedia, copied out to you on demand. People will help you take the next step if your question shows that you've done as much as you possibly could on your own \$\endgroup\$
    – MrGerber
    Jan 17, 2018 at 11:41

2 Answers 2

Reset to default
3
\$\begingroup\$

\$ 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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ "\$n\$ flip-flops can represent \$2^n\$ states", Isn't it 8 states => n = 3 => 3 flip-flops? \$\endgroup\$
    – Harry Svensson
    Jan 17, 2018 at 12:31
  • 1
    \$\begingroup\$ Yea. But one of the states in the SM has 4 bits representation (1001). That causes one extra flip-flop for this implementation. That's what the second sentence is about. \$\endgroup\$
    – Mitu Raj
    Jan 17, 2018 at 12:34
  • 1
    \$\begingroup\$ The 4th bit can be made with combinatorial logic. \$\endgroup\$
    – Harry Svensson
    Jan 17, 2018 at 12:35
  • 2
    \$\begingroup\$ How ? "state" has to be synchronous. \$\endgroup\$
    – Mitu Raj
    Jan 17, 2018 at 12:39
  • 2
    \$\begingroup\$ Then we can use combinatorial logic for all 4 bits. How about that ? \$\endgroup\$
    – Mitu Raj
    Jan 17, 2018 at 12:42
0
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.