How to design this synchronous circuit?

Question

I have seen this model question on synchronous circuit , but i could not understand the logic, can anyone please help me?

"Develop the state diagram for a synchronous sequential circuit which will recognize the bit sequence 1101 (ie, every time the sequence 1101 is detected in the input bit stream, the circuit has to output a 1 and otherwise a 0)."

What is the question here?? do we have consider all possible combinations ( 2^4 - 16 ) to do this ? if so , according to the question , do we have only one occasion where we get the output 1??

please explain it. -Regards

Answer 1

The question asks for a circuit which is given a sequence of bits, one in each round, and is supposed to output $1$ each time that the last $4$ bits form the subsequence $1101$; otherwise $0$ should be output. For example, if the input is $110110101$ then the output should be $000100100$. Naturally, the circuit will have to retain some memory.

Answer 2

You will only need to remember the state you are in. There are 4 possible states you can be in when matching "1101":

• State 1: Initial state, and after seeing an unexpected zero.
• State 2: After matching "1".
• State 3: After matching "11"
• State 4: After matching "110"

The transitions are as follows:

State   Input   Output  Next
S1      0       0       S1
S1      1       0       S2
S2      0       0       S1
S2      1       0       S3
S3      0       0       S4
S3      1       0       S3
S4      0       0       S1
S4      1       1       S2

The output of 1, is only done when in the last state ("110") and another one is detected.

To translate this into sequential circuits, you can encode the state either as four distinct memory-elements, or as a combination of two (00, 01, 10 or 11).