0
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ isnt that just gating 1101 OR 1011 on a 4 bit shift register? \$\endgroup\$ Dec 5 '17 at 5:19
  • 1
    \$\begingroup\$ @TonyStewart.EEsince'75 You will get the same result. But that is not a state machine. \$\endgroup\$ Dec 5 '17 at 6:01
  • \$\begingroup\$ Reminds me back in '77 when I designed a synchronous 24 channel ADC link and I wanted to invent a unique pattern for frame sync. How I arrived at it turned out to be a fluke using a cross-correlation pattern to ensure no loss of sync , if there was only 1 bit error in the sync pattern. (no CRC,ECC) \$\endgroup\$ Dec 5 '17 at 7:29
1
\$\begingroup\$

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
\$\endgroup\$

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.