Sequence detector 1001 using D flip-flops

The machine has one input A and one output Y; Y = 1 when the last four bits received on A are 1, 0, 0, 1. Only D flip-flops are used.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 4 bits, 4 states are needed, so 2 D flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 5 states.)

Step 1: States

Step 2: State diagram

 Main path (label = A/Y):
 S0 -1/0-> S1 -0/0-> S2 -0/0-> S3 -1/1-> S1
 Other transitions:
 S0 -0/0-> S0    S1 -1/0-> S1
 S2 -1/0-> S1    S3 -0/0-> S0

Step 3: State assignment

Step 4: Excitation table

D excitation: $D = Q^+$ (D equals the next state).

Step 5: K-maps (rows $Q_1$, columns $Q_0A$)

Step 6: Equations

$$\begin{aligned} &D_1 = Q_1\overline{Q_0}\overline{A} + \overline{Q_1}Q_0\overline{A} \\ &D_0 = Q_1\overline{Q_0} + A \\ &Y = Q_1Q_0A \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
D0>|D   Q|-Q0 D1>|D   Q|-Q1
   | FF0 |       | FF1 |
   |     |       |     |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
A = serial input, common to the gates
D1 = Q1.Q0'.A' + Q1'.Q0.A'
D0 = Q1.Q0' + A
Y = Q1.Q0.A

The gates for each flip-flop input are built from the equations; the output gate gives Y directly (Mealy output).

Check with an input stream

Y = 1 appears exactly on the clock in which the last bit of 1001 arrives; overlapping sequences are also detected.

Note: $D_1 = \overline{A}\,(Q_1 \oplus Q_0)$, so FF1 needs one XOR and one AND gate.