0
\$\begingroup\$

How do I implement a specific digital design using mealy model and then implement the same design again using Moore model ? Can anyone provide detailed steps ? Thanks.

Update:

In the digital logic class we learned what is the difference between Mealy and Moore machines theoretically and on analysis, but I don't know the difference between them in the design process.

The steps we learned for sequential circuit design:

  1. Making a state table that shows present state, input, next state and output combinations.
  2. Coding the binary state in the table and determining the number of flip flops.
  3. Use the excitation table for determining the values of the flip flops needed to generate the next state from the present state.
  4. Find the Boolean expression for the flip flop input and outputs.
  5. Build the circuit.

From these steps I just don't know how to specify the design to be based on Mealy or Moore.

\$\endgroup\$
  • \$\begingroup\$ It is like implemting a state machine, just follow the steps. I would suggest design a step wise algorithm first and implement. Are you using a HDL? \$\endgroup\$ – dDebug Jan 8 '15 at 12:18
  • \$\begingroup\$ I will be using HDL for practical things once I fully understand this issue. My problem is with the design of sequential circuits, From the steps I learned I don't know how to differentiate between the two models. I will update the question for more info \$\endgroup\$ – 3bdalla Jan 8 '15 at 12:20
1
\$\begingroup\$

At its simplest, for every state machine you have three variables:

  1. Inputs - Driven to the state machine. Not directly controlled by the FSM design.
  2. State - Internal information about the current state the machine is in.
  3. Outputs - Driven out of the state machine.

The state machine design about how it defines State and Outputs based on a series of Inputs over time. The State is registered, so on every cycle, you are trying to figure out the next State. The output is combinatorial, so you need to figure out the current output.

For both Mealy and Moore, the next State is determined by some combination of the inputs, current state, and current output. So it's a bunch of things like:

if (current_state == 5) 
    next_state = 6;
else if (current_state == 4 && input[3] == 1) 
    next_state = 5;
etc...

The output is typically not sequential, but rather combinatorial. And what is used to calculate this output defines whether it is Mealy or Moore.

The more general case is the Mealy FSM which calculates the output with some combination (i.e. AND/OR/NOT, comparators, etc.) of Input and (current) State.

So again, things like:

if (current_state == 5) 
    output = 1;
else if (current_state == 4)
    if (input[3] == 1) 
        output = 2;
    else
        output = 3;
etc..

But if we restrict ourselves to only calculating based on State, it is a Moore FSM. In this case, it would look like:

if (current_state == 5) 
    output = 1;
else if (current_state == 4)
    output = 2;
else if (current_state == 2 || current_state == 3)
    output = 3;
etc..

That really is it. Nothing else. And to top it off, you can convert one form to an equivalent form of the other.

One question that is often unasked is "Why do we separate them into two classes and give them names? Why is it so important?"

The answer is because as you try to create FSMs in real practical circuits, you will find that you are generally able to get better performance from a Moore machine. (They usually can run at higher frequencies). However, for many people intuition leads them to think about state machine problems more closely to the Mealy model.

By classifying them, we can teach ourselves to think about state machines problems in both models. This allows you to pick the correct model for the problem you are trying to solve. The details about why Moore runs faster and the tradeoffs between when to choose the two designs comes with experience and knowledge about digital design.

\$\endgroup\$
  • \$\begingroup\$ I have two questions. Regarding this line "And what is used to calculate this output defines whether it is Mealy or Moore", are you implying that the problem itself or the design procedure does specify that the design is mealy or moore based and that we don't explicitly require that it's mealy or moore ? Second question is regarding this line "This allows you to pick the correct model for the problem you are trying to solve", How do I specify the design procedure or the design itself to be moore or mealy ? \$\endgroup\$ – 3bdalla Jan 8 '15 at 15:46
  • \$\begingroup\$ The way you model your problem defines it. By this I mean, how you define what each state is and how they transition. Any problem can be done with either model. If you pick states such that you can determine your output solely from the states, then you are making a Moore state machine. If you need to know the current input as well, then it is a Mealy \$\endgroup\$ – caveman Jan 8 '15 at 16:08
1
\$\begingroup\$

In addition to the answer of caveman. @caveman: I didn'f find these images with English labels, maybe you have a source and can include them into your answer :)

Here are two images describing the layout of moore and mealy automata:

Moore automate:

Moore http://www.rz.e-technik.fh-kiel.de/~dispert/digital/digital6/img00009.gif

VN1 is a function of:
- (external) inputs \$x_i\$ and
- (internal) inputs / loopback normally called \$z_i\$
This functions calculates the state transitions / next state.

Speicher (en: Memory)
is a set of flip flops, storing the current state \$z_i\$. Delay flip flops (D-FF) are typical for this block.

VN2 is a function of:
- current state \$z_i\$,
which generates the required output signals. In most cases the choosen state encoding is equivalent to the output encoding so VN2 implements the 'identity' function.

Another example:
VN1 implements a counter modulo 16 (so counting from 0 to 15). It uses 4 bits and a binary state encoding. The required output is a 7 bit 7-segment display control.

In this case VN2 would implement the BCD decoder function from internal 4 bit binary code to the 7 bit 7-seg encoding.

7-segmentdisplay

Mealy automata:

Mealy http://www.rz.e-technik.fh-kiel.de/~dispert/digital/digital6/img00010.gif

As you can see the image has an additional connection from inputs \$x_i\$ to function VN2.

VN2 is a function of:
- current state \$z_i\$ and
- (external) inputs \$x_i\$ which generates the required output signals.

Pros:
- faster output generation
- sometimes less states

Cons:
- outputs are not decoupled from inputs
- => long critical path
- => reduces maximum circuit frequency (\$F_{max}\$)
- chaining Mealy automates can reduce \$F_{max}\$ from 200 MHz to 10 kHz

Conclusions:

  1. Every Moore automate is also a Mealy automate
  2. It's not possible to transform every mealy automate into a Moore automate.
\$\endgroup\$
  • \$\begingroup\$ It is actually not true that it is not possible to transform every Mealy into a Moore. (For standard synchronous design, at least). It seems counter intuitive, but it is actually always possible. See this for a step by step process: cs.uml.edu/~lechner/FSModels/sld003.htm \$\endgroup\$ – caveman Jan 8 '15 at 16:58
  • \$\begingroup\$ I believe your answer is from the analysis part, I look at the circuit, extract equation and see whether it is mealy or moore. My question is, When I face a design problem, should I care that I must design it as mealy or moore ? or at the end of the procedure this will be specified ?. \$\endgroup\$ – 3bdalla Jan 8 '15 at 17:03
  • \$\begingroup\$ And, How do I design the same circuit using Mealy and moore ? The steps I mentioned in the question shows that only after you write the output equation. \$\endgroup\$ – 3bdalla Jan 8 '15 at 17:12
  • \$\begingroup\$ @caveman Can you present a equivalent Moore automate for the following Mealy automate, which achieves the same timing behavior? External Code example \$\endgroup\$ – Paebbels Jan 8 '15 at 18:00
  • \$\begingroup\$ @Paebbels You are right. That is a good example. The requirement that I believe I forgot was that the output must be registered. If the external user is using the raw output as in your example, then you are correct that it cannot be done because an input passing without a clock to the output is possible in a raw Mealy machine of this type. \$\endgroup\$ – caveman Jan 8 '15 at 18:49
0
\$\begingroup\$

A Mealy machine has outputs that depend on the state and input (the FSM has the output written on edges) whereas a Moore machine has outputs that depend on state only (the FSM has the output written in the state itself).

The only real difference in Mealy and Moore machines is how you fill out the outputs. Other than that, it behaves the same. Recall from the Moore machine, you look at the current state, and then check what the output is from the FSM, and then copy the output bits for each occurrence of that state. To implement create a state transition table, decide how many flip flops you need, use the flip flop excitation table to fill out the rest of the chart, implement the circuit using a ROM.

\$\endgroup\$
  • \$\begingroup\$ "The only real difference in Mealy and Moore machines is how you fill out the outputs". Can you further explain ? this is the bottle neck for me. Or simply, can I say that the design or the problem statement itself is specified as Mealy or Moore ? \$\endgroup\$ – 3bdalla Jan 8 '15 at 12:56

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.