← ProblemsCircuits / Sequential Logic / Finite State Machines

FSM: count 1s in 3-cycle windows

5%fsmfsm-design

Design an FSM with two inputs, s and w, and one output z, that behaves as follows:

  1. After reset the machine is in state A. It stays in A as long as s = 0. When s = 1 at a clock edge, it moves to state B. (Once in B it never returns to A except by reset — s is ignored from then on.)
  2. In state B the machine examines w over consecutive, non-overlapping windows of exactly 3 clock cycles. The first window consists of the first three cycles spent in B (i.e., it starts in the cycle after the cycle in which s = 1 was observed).
  3. At the end of each 3-cycle window, if w was 1 in exactly two of the three cycles, then z = 1 for one clock cycle — the cycle immediately following the window. Otherwise z = 0 in that cycle.
  4. Windows are back-to-back: the cycle in which z reports the result of one window is simultaneously the first cycle of the next window, and its w value counts toward that next window.

reset is synchronous and active-high, returning the machine to state A with z = 0.

You may implement the 3-cycle window with explicit states or with a small position counter plus a ones counter — both are fine as long as the timing above is met exactly.