Moore FSM design. Need some help.

[crazyeng0]

Hello, I am working on a sequence detector problem for Moore machine. It will have one Input and TWO outputs. The outputs, y1 = 1 for the sequence of 1011 and output y2=1 for the sequence of 1101. For the first case the state diagram will be like bellow:

I can also find the state diagram for the second case (1101). But how can I depict the states for both TWO outputs in one state diagram ? I
learned this topic few days ago. So, I'm sorry if I sound stupid!
Need some help.

Thank you.

 

[permute]

its basically a combination of the two.
start in state "0,0". where "m,n" is the number of matched bits of sequence m,n.

if you see a 0, you transition to the same state (no progress made on either sequence), on a 1, you transition to state "1,1"
from state 1,1 you will see either a 0 (2,0) or a 1. (1,2)
from state 2,0, a 0 will put you back in state 0,0 -- neither sequence has two zeros in a row. a 1 will move you to 3,1
from 1,2 a 0 wil move you to state 2,3 (eg, you have seen "10, which is part of the first sequence, and 110 which is part of the second). a 1 moves to 1,2. (the input 111 still matches 1 from seq1, or 11 from seq2)
at 3,1 a 0 moves you to 2,0. a 1 moves to 4,2
at 2,3, a 1 moves to 1,4. a 0 to 0,0
4,2 can move to 2,3 or 1,2
4,1 moves to 2,3 or 1,2

this process continues. There is logical savings if you end up with less than 25 states. in the above it looks like there are only 8 states. eg, there is no pattern of bits that would place you in the 3,3 state. in this case, 3b can be used to encode the 8 states, as opposed to 3b (for 5 states) for two state machines.

(there may be some logical issues with the above state machine. I haven't double checked it.)

 

[crazyeng0]

Thank you a LOT. I really appreciate your help. I have worked out the problem here:

In this problem, I had to make the state diagram from a moore machine which has 2 outputs like the previous one. Output y1=1 for 1101 input sequence
and output
y2=1 for 0111 input sequence. Overlap in inputs may happen. I am trying to minimize the states and so far I used 7 states. The numbers inside the circles (i.e. (0,0), (1,0)) etc depicts the two outputs (y1,y2). Would you please have a look at the
image. I am not sure whether I made any mistakes or not. Please suggest any improvement.

Thanks.

 

[permute]

it is easier to see if you name the states, the manner I used seems like a good choice, but isn't the only one. It is a bit hard to read otherwise.

There is a problem as well. try the input "11111111"

 

[crazyeng0]

it is easier to see if you name the states, the manner I used seems like a good choice, but isn't the only one. It is a bit hard to read otherwise.

There is a problem as well. try the input "11111111"

I can see. I need to modify it any idea?

 

[permute]

basically, start with what I've previously said. name each state based on the progress towards each goal. starting at 0,0 with transitions to 1,0 and 0,1. then go to 1,0 and place the transitions to 2,0 and 0,1. etc... With meaningful names for the states, it should be easy to draw a diagram and then double check the transitions.

 

[crazyeng0]

Thanks. I did this again for 1101 and 0111 sequence. It tool 9 states. Do you think that 9 states is too large and it's possible to do it in less number of states ?

 

[vlsi_whiz]

You can do this with 8 states , one state will be common.

 

[crazyeng0]

You can do this with 8 states , one state will be common.

I also think so. I was able to came up with this diagram:

Can you suggest any improvement ? I tried to make one state common but in this case the output doesn't corroborate with the input string.
o/p y1 =1 for i/p = 1101
op y2 = 1 for i/p = 0111 including overlapping input sequences.

 

[permute]

10111 fails.

again, very easy to see if you name the states meaningfully.

 

[crazyeng0]

Hi permute, I corrected it. Thanks man! Appreciate it. The thing is, as I am a newbie, I don't want to change this style right now. I was taught in this way I hope
that I will be able to overcome all the deficiency soon.

Do you think that I can improve this diagram to minimize the number of states?

 

[vlsi_whiz]

How about this FSM... seems to work for all input combinations for me.. with 8 states..

 

[crazyeng0]

@vlsi, it is okay for 1101 and 1011 input strings. Now I am talking about 1101 and 0111 i/p strings. I am finding it hard to merge two states in order to minimize
total number of states.

 

[vlsi_whiz]

Well, For those input combinations, you will need 9 states to make sure that the FSM doesnt lock-up or give the output for the wrong input combinations.

 

[crazyeng0]

For two states, if the outputs are same then they are equivalent.. right ?

 

[vlsi_whiz]

Yes, if the outputs are the same, then the states are equivalent.

 

[crazyeng0]

hmm thanks. Another thing, suppose I want to make the transition to state S0 if I receive 0 or 1 in the input sequence. Can I do that ? Or I need to make two states- one for input 1 and another for input 0.

 

[vlsi_whiz]

You can do that also.. if you are at a particular state in the FSM and irrespective of the input you want to go back to the first state or anyother state, you can make the transition to that state when the inputs are '0' or '1'.