Designing a Mealy State Machine for Input Sequences and Output Functions

[paul_harris77]

Electronics: Mealy State Machine Design

I'm having trouble with designing the Mealy state machine below:

Homework Statement

A state machine is to have two inputs X and Y and an output Z. The output should stay at a constant value unless one of the input sequences occurs below:

a) Input sequence XY = 00 followed by 11 - Output Z becomes 0
b) Input sequence XY = 01 followed by 11 - Output Z becomes 1
c) Input sequence XY = 10 followed by 11 - Output Z toggles

Draw a Mealy model state diagram for this function.

The Attempt at a Solution

I have no idea where to start. I'm not sure what states I should use and what they should represent. I initially assumed that you would use a state to represent a certain input occurring, however I cannot get this to work.

Any ideas would be greatly appreciated.

Paul

 

[berkeman]

I'm having trouble with designing the Mealy state machine below:

Homework Statement

A state machine is to have two inputs X and Y and an output Z. The output should stay at a constant value unless one of the input sequences occurs below:

a) Input sequence XY = 00 followed by 11 - Output Z becomes 0
b) Input sequence XY = 01 followed by 11 - Output Z becomes 1
c) Input sequence XY = 10 followed by 11 - Output Z toggles

Draw a Mealy model state diagram for this function.

The Attempt at a Solution

I have no idea where to start. I'm not sure what states I should use and what they should represent. I initially assumed that you would use a state to represent a certain input occurring, however I cannot get this to work.

Any ideas would be greatly appreciated.

Paul

Well since a Mealy machine is different from the traditional Moore machine, the right place to start is with the state diagram:

http://en.wikipedia.org/wiki/Mealy_machine

Since the output depends on the inputs as well as the state, try sketching a few state diagrams to get a feel for how many states you will need...

 

[Phrak]

This requires, at most, eight states for XYZ = 000 through 111, plus an initial state for a total of nine. In fact, it doesn't seem to simplify to any less.

Label each state S₀₀₀, S₀₀₁ through S₁₁₁. Label the initial state S_I.

S_xyz signifies that the last inputs XY had the values xy, and the output Z had the value z.

If I haven't missed anything, this results in a lot of lines and bubbles, so be prepared to use a whole sheet of paper.

 

[Filip Larsen]

This requires, at most, eight states for XYZ = 000 through 111, plus an initial state for a total of nine. In fact, it doesn't seem to simplify to any less.

This doesn't sound right to me. The maximum number of states is in general clearly not bound by the number combinations of input states but on the number of sequences that the machine must recognize (like if you want a machine that recognized the first 100 binary digit of pi you need around 100 states for that, even though the input alphabet of 0 and 1 only has two combinations).

Regarding a minimum, I get (on the back of my envelope) a machine with 4 states plus one initial that seems to do the job.

 

[paul_harris77]

Thanks for the replies!

I have managed to get a working state machine with 8 states plus and initial like phrak said. However, I am concerned this is not the most efficient way of doing it if Filips 5 state way works.

Filip, would it be possible to explain or scan in and attach your diagram of the machine with 5 states?

Thank you!

Paul

 

[berkeman]

Thanks for the replies!

I have managed to get a working state machine with 8 states plus and initial like phrak said. However, I am concerned this is not the most efficient way of doing it if Filips 5 state way works.

Filip, would it be possible to explain or scan in and attach your diagram of the machine with 5 states?

Thank you!

Paul

That's great, Paul. Could you please show us your solution so far?

 

[Phrak]

This doesn't sound right to me. The maximum number of states is in general clearly not bound by the number combinations of input states but on the number of sequences that the machine must recognize (like if you want a machine that recognized the first 100 binary digit of pi you need around 100 states for that, even though the input alphabet of 0 and 1 only has two combinations).

Yeah, in this case, the max is 8+1 because--well, that's what I could do it in.

Regarding a minimum, I get (on the back of my envelope) a machine with 4 states plus one initial that seems to do the job.

Good job. I couldn't find a simplification to less than 9.

 

[paul_harris77]

I will post the state table up soon as the diagram I have draw is VERY messy what with all the transitions between the 9 states and labelling!

Can anyone else do it in 4 and an initial state?

Thanks
Paul

 

[berkeman]

I will post the state table up soon as the diagram I have draw is VERY messy what with all the transitions between states and labelling!

Can anyone else do it in 4 and an initial state?

Thanks
Paul

Yes, Filip has done it with just a few states. His solution is hidden for now -- see what you can come up with. He may provide you with some hints, if he's able to stop back by over the Holiday weekend.

 

[Filip Larsen]

As berkeman said, I provided a bit too much solution and not enough hints in my previous post, which is why its being hidden for the time being. So let's get back to some hints.

One way to model a state machine is to base states on what the machine is supposed to remember, that is, let each each state represent the equivalence class of input history combined with the associated last output. The trick to make a state machine with minimal states using this approach is to make the equivalence class as small as possible.

To start, try think about what you want your state machine to remember and model it one state at a time and add transitions to that state. If you are in doubt whether or not a transition should go to a new state or not, introduce a new state to being with. After all transitions have been added to the new states, check to see if you can combine any two existing states, that is, check if all transition sequences with a common start and end state that pass the two states in question will have indistinguishable output. If so you can combine the two states into one.

If you get stuck, please feel free to describe your solution up to the point where you get stuck so we can provide you with relevant hints.

 

[paul_harris77]

Hi everyone

Thanks for your inputs. I think I have managed to do it with 4 states (an initial state being included within another state). I did it by simplifying my initial 9 state model by drawing out the state table and realising quite a few states were identical.

I've attached the original state table, the simplified version and the final state diagram.
Unfortunately, by simplifying it, it is no longer easy to follow the logic/reasoning behind the states since they no longer correspond to single previous inputs/outputs. So I labelled the simplified states with generic names A, B, C and D, A being the initial state as well as a normal state.

The non-simplified states are in the form Sxyz where xy is the previous input and z the previous output.

Sorry, I realize the table I've hand drawn is messy but I hope you will be able to read it.
I think it is all correct.
[URL]http://homepage.ntlworld.com/beehive77/images/state.png[/URL]

[URL]http://homepage.ntlworld.com/beehive77/images/statediagram.png[/URL]

 

[jegues]

I don't have the time to check your work right now, but I thought I'd mention a more formal method of eliminating redundant states.

The method is known as the partioning method, if you do some googling you should find a lot more information as well as step by step procedure.

 

[Filip Larsen]

Thanks for your inputs. I think I have managed to do it with 4 states (an initial state being included within another state). I did it by simplifying my initial 9 state model by drawing out the state table and realising quite a few states were identical.

Looks good to me.

 

[berkeman]

Looks good to me.

And here is Filip's solution that has been hidden for a bit:

Start with a state representing the constant output of 0, let's call that s0. Since there are 4 different input combinations there are 4 different transitions out of s1, all emitting a 0. Two of these transitions go back to s0 and two (with input 01 and 10) go to a new state s01 that represent the state where a switch to the part of the state machine that output 1 may be possible. In short notation that is

s0 -- 00/0 --> s0
s0 -- 01/0 --> s01
s0 -- 10/0 --> s01
s0 -- 11/0 --> s0

From the s01 state there are again four transitions:

s01 -- 00/0 --> s0
s01 -- 01/0 --> s01
s01 -- 10/0 --> s01
s01 -- 11/1 --> s1

Note that the inputs that has a s0 -> s01 transitions are repeated as s01 -> s01 transitions to allow recognizing inputs like 01 01 11 (with output 0 0 1). Also, I read the problem descriptions such that 11 in this case should output a 1 at once, so its the only transition out of s0 and s01 that output 1.

Except for variation in the input pattern and an opposite output, the transitions for the s1 and s10 states is a mirror image of the above state and transitions. The initial state seems unspecified in the problem description so pick either s0 or s1.


Happy new year to all! (its 3 am here, so I'm already in 2011).

 

[D H]

This four state solution is a Moore machine. It does not take advantage of the fact that in a Mealy machine the system output is a function of state and input. A [STRIKE]three[/STRIKE] two state Mealy machine is possible by incorporating feedback (the output of step n is fed back as an input to step n+1) into the design.

 

[Phrak]

This four state solution is a Moore machine. It does not take advantage of the fact that in a Mealy machine the system output is a function of state and input. A [STRIKE]three[/STRIKE] two state Mealy machine is possible by incorporating feedback (the output of step n is fed back as an input to step n+1) into the design.

In the sketch given by paul_harris the labeled edges indicate a Mealy machine, where the output is dependent upon both state and input.

However, the motivation to generate either of these two models, though interesting, evades me. The target device is patch of memory, a latch, and perhaps some decoding.

 

[D H]

The output in paul_harris' diagram depends on state only. The output is zero if the system is in states A or B, one if the system is in states C or D.

 

[paul_harris77]

Once again thanks for everyone's replies. They've all been really helpful! Shame I wasn't good enough to think the same way as fillip and do it with 4 states from the start but I got there in the end :)

I realize my diagram is quite messy but the bottom half of the state table does show that the outputs for states B and C do change with the input 11 to 1 and 0 respectively so it should be a mealy machine if I am not mistaken.

Best wishes

Paul

 

[Phrak]

Once again thanks for everyone's replies. They've all been really helpful! Shame I wasn't good enough to think the same way as fillip and do it with 4 states from the start but I got there in the end :)

I realize my diagram is quite messy but the bottom half of the state table does show that the outputs for states B and C do change with the input 11 to 1 and 0 respectively so it should be a mealy machine if I am not mistaken.

Best wishes

Paul

I noticed that paul_harris. It's not so messy at all. I liked the tables. Good work.