Sequence detector 1001 using SR flip-flops

The machine has one serial input X and one output Z; Z = 1 in the clock period in which the last bit of 1001 arrives. S-R flip-flops are used.

A Mealy machine is used (output depends on the present state and the input), so fewer states are needed. Overlapping sequences are allowed: after a detection, the machine keeps the useful tail of the input.

States (what has been received so far):

• A: reset / no useful bits
• B: "1" received
• C: "10" received
• D: "100" received

State diagram (Mealy)

Arc label = input/output

 A --1/0--> B --0/0--> C --0/0--> D --1/1--> B

 A --0/0--> A  (self loop)
 B --1/0--> B  (self loop)
 C --1/0--> B
 D --0/0--> A

State table

State assignment

A = 00, B = 01, C = 10, D = 11 (flip-flop outputs $Q_1 Q_0$).

Excitation table of S-R flip-flop

(x = don't care)

Transition and excitation table

K-maps and simplified equations

S1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       1    0
Q1Q0=11       0    0
Q1Q0=10       x    0

R1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       0    x
Q1Q0=11       1    1
Q1Q0=10       0    1

S0          X=0  X=1
Q1Q0=00       0    1
Q1Q0=01       0    x
Q1Q0=11       0    x
Q1Q0=10       1    1

R0          X=0  X=1
Q1Q0=00       x    0
Q1Q0=01       1    0
Q1Q0=11       1    0
Q1Q0=10       0    0

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       0    1
Q1Q0=10       0    0

$$\begin{aligned} S_1 &= Q_1' Q_0 X' \\ R_1 &= Q_1 Q_0 + X \\ S_0 &= Q_1 Q_0' + X \\ R_0 &= Q_0 X' \\ Z &= Q_1 Q_0 X \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two S-R flip-flops with a common clock; complements are taken from the $Q'$ outputs or from NOT gates):

• $S_1$: a 3-input AND for $Q_1' Q_0 X'$.
• $R_1$: a 2-input AND for $Q_1 Q_0$, combined with the direct line $X$ in a 2-input OR gate.
• $S_0$: a 2-input AND for $Q_1 Q_0'$, combined with the direct line $X$ in a 2-input OR gate.
• $R_0$: a 2-input AND for $Q_0 X'$.
• $Z$: a 3-input AND for $Q_1 Q_0 X$.

Check: input X = 01001001 gives Z = 00001001; Z = 1 at the 5th and 8th bits, so both overlapping 1001s are detected.