How would I finish out this mini project (emitting 1 whenever 101 is read)?

Question

Design a Moore finite state machine that detects 1 0 1 in consecutive digits in the input stream of 0's and 1's received every clock cycle.

The circuit should output a 1 when it detects 1 0 1 as consecutive digits. Implement the FSM using a combination of sequential and combinatorial logic. Draw the truth table for inputs, outputs, and states. Draw the K-map for everything. Indicate how many flip-flops you are going to use. Draw the final circuit with the flip-flops.

Example:
INPUT:  0 1 0 1 0 1 1 0 1 0 0...
OUTPUT: 0 0 0 1 0 1 0 0 1 0 0...

This is my work so far, describing the state machine:

S_i   inp  S_{i+1}
000 -> 0 -> 000
000 -> 1 -> 001
001 -> 0 -> 010
001 -> 1 -> 001
010 -> 0 -> 000
010 -> 1 -> 101
101 -> 0 -> 010
101 -> 1 -> 001

Since there are only 4 states involved ("000", "001", "010", and "101"), I represent them with bits A and B:

     A | B
    -------
s_0  0 | 0    to represent state "000"
s_1  0 | 1    to represent state "001"
s_2  1 | 0    to represent state "010"
s_3  1 | 1    to represent state "101"

I combined this with the previous table to represent the initial states I_A, I_B, with some new input X, and then the destination states D_A and D_B:

I_A  I_B | X | D_A  D_B
________________________
 0    0  | 0 |  0    0
 0    0  | 1 |  0    1
 0    1  | 0 |  1    0
 0    1  | 1 |  0    1
 1    0  | 0 |  0    0
 1    0  | 1 |  1    1
 1    1  | 0 |  1    0
 1    1  | 1 |  0    1

I wrote out the K-maps for (I_A, I_B) vs. X for output D_A, as well as (I_A, I_B) vs. X for output D_B, and got this simplification:

D_A = ¬X * I_B  +  X * I_A * ¬I_B
D_B = X

I'm reasonably sure this is all right so far.

However I am unclear where to go from here. I don't really understand how to model this as an actual circuit using flip-flops. I don't know how to transition the initial states of A and B to their corresponding final states. I don't know how I am supposed to emit a 1 in the event that I end up in the "101" state s_3.

D_A = ¬X * I_B  +  X * I_A * ¬I_B
D_B = X

I don't really know if this is correct but this is how I tried to model the circuit:

I_B ------o-------------------------o
          |                         |
          |                         v
          |                         AND----->OR--------> D_A
          |                         ^        ^
          o---NOT---->A             |        |
                      N---->AND-----|--------o
I_A ----------------->D      ^      |
                             |      |
X --------o---NOT-------------------o
          |                  |
          |                  |                 
          o------------------o-------------------------> D_B

Where do I go from here?

Answer 1

Confession

I'm not classroom-trained on Mealy and Moore. I'm only "book-read" and, prior to that reading, only had lots and lots of basic practice from making things work using state machines (obviously finite) without bothering to assign names to what I did. I just knew some thinking tools, is all, which worked well.

Tony's circuit, so far as I understand it, is a Mealy FSM, not Moore. Except that he "registered" the output, which I think allows it to fit the Moore machine definition. I'll explain why I think this, using definitions I find on the web and his schematic to make the point. But keep in mind I may be wrong in my interpretations and I'm very much open to being taken to task about what follows.

State Diagram

I completely ignored your writing about your approach. It's a lot easier for me to use tools I know and understand well. Here is the result of my first step in thinking about what you wrote -- focusing only on the comment about "101."

The labeling of the states shows the prior two bits. The labeling is most recent bit on the right and prior bit on the left.

This diagram includes some states you didn't include, showing the initial transition from "no bits seen" to "one bit seen" and then to "at least two bits seen." You probably want to ignore those initial states that lead into the inner four states shown above. Which is fine. I just wanted to point out how I "think" about these questions when I first face them.

Here, you can see the four states you arrived at but from a slightly different approach. I'm just tracking the prior two bits as a pair and then showing the incoming bit as a transition between states.

Finally, I've included a red star to indicate the important transition where "101" is recognized. (The prior state pair must be "10" and must be followed by observing a "1" as the transition.)

Here is a distilled version:

Which is probably more like what you want to achieve.

State Pair

The pair of D-type FF required for the most recent and also the immediately prior bits are shown on the upper diagram. The lower diagram shows the completed result that Tony pointed out.

^{simulate this circuit – Schematic created using CircuitLab}

Note that this schematic requires both the current state information (the two FF shown in the upper diagram) as well as the current input (shown in the lower diagram as a wire coming from DATA to one of the inputs of the 3-input AND gate. It is only when the current state and also the input meet some criteria, than the correct output status is latched. Normally, I believe this makes the result qualify as a Mealy machine, not a Moore machine. But the fact that this is a "registered Mealy machine" is what makes it a valid Moore machine.

You could do this more directly as a Moore machine, I suppose. But I think this qualifies.

Answer 2

^{simulate this circuit – Schematic created using CircuitLab}

This Moore sequence only needs 2 previous states of 01 for Reg 12 with the Reg1 inverted to create 11 and combined with present input =1 into the 3in AND to create the D=1 that is clocked with the next state being the sequence of 101.