Detector for three consecutive zeros

No flip-flop type is specified, so J-K flip-flops are used. Output Y of the question is written Z (Y = Z). With overlapping, a run of four 0s gives Y = 1 on the 3rd and 4th zero.

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 000 arrives. Flip-flops: J-K.

States (what has been received so far):

• A: reset / last bit 1
• B: one 0 received
• C: two or more consecutive 0s received

State diagram (Mealy)

Arc label = input/output

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

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

State table

State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (X=0 goes to C, X=1 goes to A), so it is self-starting.

Excitation table of J-K flip-flop

Transition and excitation table

K-maps and simplified equations

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

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

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

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

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

$$\begin{aligned} J_1 &= Q_0 X' \\ K_1 &= X \\ J_0 &= Q_1' X' \\ K_0 &= 1 \\ Z &= Q_1 X' \end{aligned}$$

Logic diagram

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

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

• $J_1$: a 2-input AND for $Q_0 X'$.
• $K_1$: direct line $X$.
• $J_0$: a 2-input AND for $Q_1' X'$.
• $K_0$: tied to logic 1.
• $Z$: a 2-input AND for $Q_1 X'$.

Check: input X = 1000010 gives Z = 0001100; Z = 1 at the 4th and 5th bits (third and fourth consecutive 0).