Draw the Moore graph. I need help.

Thread Starter

Ems1s7

Joined Nov 21, 2014
11
Hi everyone,

I need help with this problem:

Draw the Moore graph of states of a sequential circuit, with one input (E) - 1 bit and one output (S) - 2 bits.
The circuit have to detect the sequences 1 0 1, 0 1 1 and 1 0 0, and detection should be performed with overlap.
The output should be 1 0 if the first sequence is detected (1 0 1), or 1 1 if the second sequence
is detected (0 1 1), or 0 1 if the third sequence is detected (1 0 0).
In all other cases the output should be 0 0.

Thanks advance! Waiting for your answers.
 

Thread Starter

Ems1s7

Joined Nov 21, 2014
11
For the first 2 sequences I'll need from 5 states, because we have 1 0 1 and 0 1 1, but with overlap we'll have 1 0 1 1,
i.e. the machine start to search the second sequence, before to finish the first.
I'm not sure how to integrate the third sequence... may be 1 0 1 1 0 0? But in this case the machine start to search the third sequence
when the second finish.
 

MikeML

Joined Oct 2, 2009
5,444
How about a simple three-stage shift register? (Theoretically, that is eight states).

Three 3-input NAND gates to decode the states you are looking for, followed by a couple of NOR gates to create the S outputs...
 

WBahn

Joined Mar 31, 2012
26,398
I agree that the 3-bit shift register is the most straightforward solution (at least in general) as I see it with a quick glance, but if the problem is to draw a Moore Diagram (which I'm assuming means to draw the state diagram for a Moore machine that implements this system), then you need no more than three bits of state, though the number of states may be lower and it is possible that you might not need all three bits of state.

Start with you initial state (probably an assumption that you have seen nothing but zeros, but that that's a guess) and then walk through the possibilities. At each stage, ask what information you know about which sequence fragments you have seen and what each possible next input tells you. Just keep in mind that, as a Moore machine, ALL of the information that is retained in what the current state is and NOT on what the current input is, too.
 
Top