Counters and state machines

ACompressed recap

🧾

Shift register: D = neighbour's Q; ring counter n states, Johnson 2n states. Ripple counter: chained clocks, frequency halves per stage, settling n × t_pd, mod-N by clearing at N. Synchronous counter: common clock; up counter Tᵢ = AND of lower bits; analyse with equations, design with excitation tables, check unused states. FSM: Moore (state outputs) vs Mealy (transition outputs); k-bit detector k / k + 1 states; ⌈log₂ s⌉ flip-flops; minimise by partitioning.

BMerged rule card

6.2.1 Registers, shift registers, ring and Johnson counters

• Register: n D flip-flops, common clock. Shift register: D = neighbour's Q; SISO, SIPO, PISO, PIPO; n clocks to load n bits serially.
• Ring counter: feed back Q of the last stage; n states; must be initialised.
• Johnson counter: feed back Q' of the last stage; 2n states; 2ⁿ − 2n unused.

6.2.2 Asynchronous (ripple) counters and mod-N counters

• Ripple up counter: toggling flip-flops, each clocked by the previous output (negative edge); mod-2ⁿ; frequency halves per stage.
• Settling n × t_pd; f_max = 1/(n·t_pd).
• Mod-N: ⌈log₂ N⌉ flip-flops; asynchronous clear when the count reaches N (detect N's 1-bits); brief glitch state N.
• Down counter: clock from Q' (or opposite edge).

6.2.3 Synchronous counters: analysis and design

• Synchronous counter: one clock for all flip-flops. Up counter (T): T₀ = 1, Tᵢ = Qᵢ₋₁ ⋯ Q₀.
• Analysis: input equations → next states → sequence; check unused states (self-starting vs lock-out).
• Design: state table → excitation table → K-maps (unused = don't care) → circuit → check unused states.
• With D flip-flops, Dᵢ = next Qᵢ.

6.2.4 Finite state machines: Mealy and Moore, sequence detectors, state minimisation

• Moore: output = f(state). Mealy: output = f(state, input); usually fewer states.
• k-bit sequence detector: k states (Mealy), k + 1 (Moore). Overlapping vs non-overlapping changes the arrows after a match.
• s states → ⌈log₂ s⌉ flip-flops.
• Minimise by partition: group by outputs, split by next-state groups, repeat.

CInterleaved GATE-style questions

Q1NAT1 markJohnson

How many states does a 7-flip-flop Johnson counter have?

Numerical answer: ________

Q2MCQ1 markRing

A 4-bit ring counter starts at 1000. After 6 clock pulses it holds:

• (A) 0100
• (B) 0010
• (C) 0001
• (D) 1000

Q3NAT1 markMod-N

How many flip-flops does a mod-50 ripple counter need?

Numerical answer: ________

Q4MCQ1 markMod-12

A mod-12 ripple counter with asynchronous clear detects which outputs?

• (A) Q₃ and Q₂
• (B) Q₃, Q₁ and Q₀
• (C) Q₂ and Q₁
• (D) Q₃ and Q₁

Q5NAT2 marksFrequency

A 10 MHz clock drives a 5-bit ripple counter. Frequency of Q₄, in kHz?

Numerical answer: ________

Q6NAT2 marksSynchronous

A 3-bit synchronous up counter uses T flip-flops. How many 2-input AND gates are needed for T₂ (with T₀ = 1 and T₁ = Q₀)?

Numerical answer: ________

Q7NAT2 marksFSM

Minimum number of states for a Moore machine detecting 110 (overlapping)?

Numerical answer: ________

Q8MCQ2 marksMinimisation

In a Moore table, states P and Q have the same output. On input 0 both go to R; on input 1, P goes to S and Q goes to T, where S and T have different outputs. Are P and Q equivalent?

• (A) Only for input 0
• (B) No
• (C) Only if R has output 0
• (D) Yes

DAnswer Vault