Electrical – 2 sequence detector using state machines

digital-logic

I was given a problem to design a 2 sequence detector. I was able to make the State Diagram but don't know how to proceed to make the state table.Can someone please guide me how to make the state table?

Here's the problem-
Design a sequence detector to detect 1101 and 1011, both sequences should be detected with the constraint that overlapping is allowed. There shall be one output. One output should be high when any of these two sequences gets detected. Consider LSB of each stream to be first bit to enter in sequence detector.

Here's what I got to

my state diagram

Input is a data stream for example 00011010110 and would like to the design the circuit using flip-flops and mux.

Best Answer

Since there's two different sequences we need to check for, the easiest thing that comes to mind would be to just have two Finite-state machines working independently. And then you feed the two FSM's output into one OR gate and call this your output.

But I assume that is too simple.

This is your question:

Can someone please guide me how to make the state table?

Here's my take on it:

enter image description here

The circles are formatted accordingly: (output / current state) --- x = input -->

Just try these cases:

010101011
111111101
11011011

You will see that it works for those 3 which I assume is all the cases that needs to be covered.

If you want to optimize it then you should make the states ascend / descend in gray code format. Because going from 011 to 100 requires you to change 3 bits, while going from 011 to 111 requires you to change only 1 bit. Which one do you think requires least number of gates?

I will not continue with the flip-flop and mux designs because you seem to be clever enough to continue from here. Also, this is your assignment. Homework. I will not do your entire assignment. I will however give you a push.

And regarding the State table. I believe this should suffice:

S X | S+ U
0 0 | 0  0
1 0 | 2  0
2 0 | 0  0
3 0 | 2  0
4 0 | 6  1
5 0 | 6  0
6 0 | 0  0
7 0 | 2  1
0 1 | 1  0
1 1 | 5  0
2 1 | 3  0
3 1 | 4  0
4 1 | 5  1
5 1 | 5  0
6 1 | 7  0
7 1 | 4  1

Where:

  • X = input
  • S = current state
  • S+ = next state
  • U = output
Related Topic