Hardware Design Interview Question:

How do you detect a sequence of "1101" arriving serially from a signal line?

Submitted by: Administrator

Sequence detector : A sequence detector gives an output of 1 on detecting the given sequence else the output is zero.

Ex : if the given sequence to be detected is 111
and input stream is 1 1 0 1 1 1 0 0 1 0 1 1 1 1 1
the output should be 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1.

Soln:
One of the different possible ways to detect a sequence is using a Mealy type FSM.

Using the following table the State machine can be designed.
since the number of bits in the sequence 1101 is 4 we have 4 states

------------------------------------------------------
|PS | Seq detected by the state | NS/output |
| | |---------------|
| | | X=0 | X=1 |
|-----------------------------------------------------
| S1 | - | S1/0 | S2/0 |
|----------------------------------------------------|
| S2 | 1 | S1/0 | S3/0 |
|----------------------------------------------------|
| S3 | 11 | S4/0 | S3/0 |
|----------------------------------------------------|
| S4 | 110 | S1/0 | S2/1 |
|----------------------------------------------------|

when in state S4 (PS),and input(X) from the sequence is 1,the sequence "1101" has been detected once and (to find the next state select the longest "seq identified by a state" column that matches part of the sequence 1101--ie.,1 or 01 or 101 ....)the NS is S2 since the sequence detected by the state S2 is 1(in 1101- 01 or 101 ,etc are not present in the seq identified by the state column ,)
Submitted by: Administrator