0
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Who gave you the input example? The way it is written right now it is mealy and it is impossible for it to be moore. - Also, what do you expect your goal to be? A physical circuit with actual IC's? A physical circuit with transistors and resistors? Some code that does it on a microcontroller? - "Where do I go from here?" is very broad, when you don't tell us what your end goal is. - One could say that you are technically done, if your circuit does what it is supposed to be doing (haven't checked it yet). - Btw, where is your output? \$\endgroup\$ – Harry Svensson Dec 22 '18 at 4:22
  • \$\begingroup\$ @HarrySvensson It was built into the problem, just an example of how the output displays a 1 every time we've reached a 101-state, to make clear what was going on. \$\endgroup\$ – user525966 Dec 22 '18 at 4:25
  • \$\begingroup\$ And yes I believe the goal is to draw the circuit with the ICs and the flip flops, translating this state machine into something we could model on hardware \$\endgroup\$ – user525966 Dec 22 '18 at 4:32
4
\$\begingroup\$

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."

enter image description here

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:

enter image description here

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.

schematic

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.

\$\endgroup\$
  • \$\begingroup\$ How did you make those amazing state diagrams? \$\endgroup\$ – user525966 Dec 24 '18 at 22:44
  • \$\begingroup\$ @user525966 I used Microsoft's Paint program. Nothing special. I have been looking for a decent data flow diagram (which can be used for state diagrams, too) program for more than 20 years. So far, they either cost a fortune unworthy of their meager abilities or else were free but still far too limited to do much. So I use Paint. If someone has a good, flexible tool, especially one that permits leveled diagramming with top level diagrams descending into more detailed ones, as needed, I'd love to hear about it. \$\endgroup\$ – jonk Dec 25 '18 at 1:00
1
\$\begingroup\$

schematic

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I can't tell how this works exactly? What's what here? \$\endgroup\$ – user525966 Dec 22 '18 at 7:15
  • 1
    \$\begingroup\$ I should add that I'm a beginner just trying to learn this stuff, this isn't homework or anything and I'm not in a class, so I am more interested in the process and how you get there, not just the end result \$\endgroup\$ – user525966 Dec 22 '18 at 17:29
  • \$\begingroup\$ Looking for a serial pattern is like a long unique SYNC pattern at the beginning of a long frame of synchronous data to define the edge of the 1st bit of the 1st word that comes next. . So I just created a shift register of 3 D's and "AND'd" the pattern 101 to create the output.. \$\endgroup\$ – Sunnyskyguy EE75 Dec 22 '18 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.