Synchronous counters and finite state machine design
State transitions before gate equations
A sequential specification says how stored state changes when an input is sampled. Start with that transition rule, then choose an encoding and derive flip-flop inputs. Guessing gate equations first can hide missing states, ambiguous output timing and incorrect reset behavior.
Prerequisites: D/T/JK characteristic equations, excitation tables, Boolean simplification and synchronous timing. All examples use a shared rising-edge clock, valid setup/hold and a stated reset state. Reset is inactive during traces unless mentioned. We design small counters and finite-state machines, not asynchronous control systems or a complete state-minimization algorithm.
Binary synchronous counter
A three-bit modulo-8 counter has states Q_2Q_1Q_0 and repeatedly follows 000,001,010,011,100,101,110,111,000. It uses three flip-flops because it must distinguish eight states. Modulo means the state wraps after the specified number of distinct counts; it does not mean adding an extra ninth state.
For T flip-flops, the lowest bit toggles every count. Bit 1 toggles when old Q_0=1. Bit 2 toggles when both old lower bits are 1. Thus T_0=1, T_1=Q_0, T_2=Q_1Q_0. Substituting Q_i,next=Q_i⊕T_i yields exactly the sequence above.
With count-enable E, use T_0=E, T_1=EQ_0, T_2=EQ_1Q_0. When E=0 every T is 0 and the entire state holds. At old state 011 with E=1, all three T inputs are 1, so the next state is 100. Using a newly updated Q_0 in T_1 would be incorrect; all controls are computed from old state.
In a ripple counter, one storage output may serve as another stage's clock, and intermediate transitions do not occur at one common clock event. Its settled counting direction depends on the actual edge polarities and connections. A synchronous counter avoids that ripple-clock construction, but still has finite clock-to-Q and combinational delays. Neither design is instantaneous.
Design a modulo-3 counter including its unused state
Two bits can represent four states, enough for three counts. Specify 00→01→10→00. The unused state 11 also needs a policy: here it goes to 00 at the next rising edge, so the circuit recovers in one edge from that Boolean state. Reset also establishes 00. This is not a physical guarantee against every fault or metastable state.
| Current Q_1Q_0 | Next Q_1Q_0 | D_1 | D_0 |
|---|---|---|---|
| 00 | 01 | 0 | 1 |
| 01 | 10 | 1 | 0 |
| 10 | 00 | 0 | 0 |
| 11 | 00 | 0 | 0 |
With D flip-flops, next-state bits are the data inputs. The table gives D_1=Q_1′Q_0 and D_0=Q_1′Q_0′. Check all four rows, including 11. Treating 11 as a don't-care during simplification would be valid only if the specification genuinely allowed arbitrary behavior there; it would no longer prove the chosen recovery rule.
Worked example 1: starting at 00, five active edges produce 01,10,00,01,10. Starting instead at 11, the first edge produces 00, followed by 01. A state count of three needs two storage bits in a binary encoding, but a different encoding such as one-hot may deliberately use more.
Finite-state machine contract
A finite-state machine (FSM) has a finite set of states, an input alphabet, a next-state function and an output rule. A Moore output depends only on current state: y=g(Q). A Mealy output depends on current state and current input: y=g(Q,x). Both can have next-state function Q_next=f(Q,x).
This is a dependency distinction, not a promise of physical glitch immunity. A Mealy output may respond to an input change between edges; a Moore output formed from multiple state bits may also glitch briefly while those bits settle. If a specification requires registered or glitch-free output, implement and check that separately. State exactly whether an output trace is observed before or after an edge.
Worked Moore machine for parity
Keep the parity of the input bits seen so far. State E means an even number of ones; state O means an odd number. Reset to E before receiving any input, since zero ones is even. On input 0 hold the state; on input 1 switch E↔O. Output y=0 in E and y=1 in O.
Encode E=0,O=1 in one D flip-flop. Then D=Q⊕x and y=Q. With sampled input sequence 1,0,1,1, the states after edges are O,O,E,O and outputs after edges are 1,1,0,1. Before the first edge y=0. The state stores the necessary history; it need not store the entire input string.
Worked Mealy detector for adjacent 01
Let state Q=1 mean the last sampled bit was 0, and Q=0 mean no previous zero is available. Reset Q=0, so a first input 1 does not falsely claim a preceding zero. When sampling a new input x, assert y=1 exactly if the old Q=1 and x=1. Thus y=Qx and D=x′, because after this input the remembered condition is “the new bit was 0.”
| Old Q | Input x | Output y for this sample | Next Q |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
For inputs 0,1,0,1,1, the outputs evaluated using old state and the current input are 0,1,0,1,0. State after each sample is 1,0,1,0,0. If instead y is recomputed from the updated Q and the same x, it is always zero because x′x=0: that is the wrong observation convention. A receiving register can sample the valid pre-edge Mealy output subject to timing. This model does not claim the combinational y remains high for a full cycle after a detection.
A reusable design and checking sequence
- Define what each state means, when inputs are sampled, when outputs are observed, and how reset works.
- List every state/input transition. Mark unspecified states only if the contract permits them.
- Choose encoding and storage type. For N distinguishable states, at least ceil(log2 N) bits are needed under binary encoding; one state can use no state bits in a pure combinational realization.
- Derive D inputs directly from next-state columns, or use T/JK excitation rules.
- Simplify without breaking specified recovery behavior; verify every row and representative traces.
- Check setup/hold and physical output requirements separately from the state table.
Common mistakes include counting bits rather than states, losing the wrap transition, updating bits sequentially in a synchronous model, assuming every unused state is a don't-care, and using after-edge state to report a pre-edge Mealy output.
Original practice
These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.
C01. A binary encoding must distinguish five FSM states. What is the minimum number of state bits?
A. 2 B. 5 C. 3 D. 4
Answer: C
A is incorrect: two bits encode only four states.
B is incorrect: five bits may be used in one-hot encoding but are not the binary minimum.
C is correct: 2²<5≤2³, so three bits suffice and two do not.
D is incorrect: four bits suffice but are not minimal.
C02. A 3-bit synchronous up-counter uses T_0=1,T_1=Q_0,T_2=Q_1Q_0. At old state 011, what is next state?
A. 100 B. 000 C. 111 D. 010
Answer: A
A is correct: all three T inputs are 1 at old 011, so all bits toggle.
B is incorrect: the high bit must toggle from 0 to 1.
C is incorrect: both low bits also toggle from 1 to 0.
D is incorrect: this toggles only Q_0 and ignores the carries encoded by T_1,T_2.
C03. A modulo-3 counter uses D_1=Q_1′Q_0,D_0=Q_1′Q_0′. What happens from unused state 11 at the next valid edge?
A. It stays 11. B. It goes to 01. C. The equations do not define this state. D. It goes to 00.
Answer: D
A is incorrect: Q_1′=0 makes both D inputs 0.
B is incorrect: D_0 is also zero, not one.
C is incorrect: the equations are defined for all four binary states.
D is correct: both next-state bits are 0, implementing the stated recovery.
C04. Which statement defines a Moore output?
A. It depends only on current external input. B. It depends only on current state. C. It depends on current state and input in every implementation. D. It is guaranteed to have no physical glitches.
Answer: B
A is incorrect: that does not define a state-based Moore output.
B is correct: y=g(Q) is the Moore dependency rule.
C is incorrect: direct dependence on input describes a Mealy output in general.
D is incorrect: Boolean dependency alone does not establish glitch-free hardware timing.
C05. A parity Moore machine starts even and samples 1,1,0,1. What are its output bits after the four edges?
A. 1,1,0,1 B. 0,1,1,0 C. 1,0,0,1 D. 0,0,0,1
Answer: C
A is incorrect: the second 1 returns the state to even, so the second output is 0.
B is incorrect: the first sampled 1 makes odd parity, so the first output is 1.
C is correct: the accumulated parities are odd, even, even, odd.
D is incorrect: it misses the odd state after the first input.
C06. A Mealy 01 detector uses initial Q=0, output y=Qx from old Q, and Q_next=x′. For inputs 1,0,1, what outputs are associated with those samples?
A. 1,0,1 B. 0,0,1 C. 0,1,0 D. 0,0,0
Answer: B
A is incorrect: reset Q=0 prevents a false detection on the first 1.
B is correct: first 1 gives 0; 0 gives 0 and sets Q=1; final 1 gives 1.
C is incorrect: a detection needs current input 1, not the middle 0.
D is incorrect: it may result from using updated Q=x′ in y rather than the specified old Q.
Scope and sources
This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.
Sources checked 14 October 2026.
Sign in to keep your progress. Sign in