⏱️ Counters, Registers & State Machines
Why it matters: A counter or sequential circuit shows up in almost every paper: find the modulus, the sequence of states, the number of flip-flops or the machine behaviour.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 5 done.
1Shift registers, ring and Johnson counters
2Asynchronous (ripple) counters and mod-n design
3Synchronous counter design
4Mealy and Moore machines
5State minimisation
Formulas
Ripple counter modulus
n flip-flops → 2ⁿ states; Qᵢ has frequency f / 2ⁱ⁺¹
Flip-flops for N states
⌈log₂ N⌉
Ring counter
n flip-flops, n states (one-hot)
Johnson counter
n flip-flops, 2n states
T flip-flop binary up counter
T₀ = 1, T₁ = Q₀, T₂ = Q₁Q₀, Tᵢ = Q₀Q₁…Qᵢ₋₁
Ripple counter max clock
f_max ≈ 1 / (n · t_pd + t_decode)
Moore vs Mealy
Moore: output = f(state); Mealy: output = f(state, input)
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Modulus or state sequence of a counter circuit
Trace a ring/Johnson/ripple counter with feedback and read the cycle length.
★★★
Next state and output of a clocked sequential circuit
Given flip-flops and gates, give the state after a few clocks or the output sequence.
★★★
Design a synchronous counter / detector
Find the flip-flop inputs, the number of states or flip-flops.
★★★
Mealy vs Moore and state minimisation
Count states, identify equivalent states, decide which machine type is described.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
10 real questions from the official GATE CSE papers (2014 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
10 questions · 0 correct of 0 attempted · marks 0 / 16
Year:
GATE 2025 CS2 · Q34NAT1 mark
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______. (Answer in integer)
GATE 2025 CS1 · Q60NAT2 marks
Consider the given sequential circuit designed using D flip-flops. Four D flip-flops D0, D1, D2, D3 share one clock; D1 = Q0, D2 = Q1, D3 = Q2, and D0 is fed by Q3′ (the complement output of the last flip-flop). The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is ______. (Answer in integer)
GATE 2023 · Q43MCQ2 marks
Consider a sequential digital circuit consisting of T flip-flops and D flip-flops. CLKIN is the common clock input. The first flip-flop (output Q1) is a T flip-flop whose T input is Q3′ (the output of the last flip-flop, inverted); the second (output Q2) is a D flip-flop with D = Q1; the third (output Q3) is a T flip-flop with T = Q2. At the beginning, Q1, Q2 and Q3 have values 0, 1 and 1, respectively. Which one of the given values of (Q1, Q2, Q3) can NEVER be obtained with this digital circuit?
GATE 2021 Set 1 · Q28MCQ2 marks
Consider a 3-bit counter, designed using T flip-flops. All three flip-flops (outputs P, Q, R) share one clock pulse. The T inputs are connected as T_P = R, T_Q = P′ and T_R = Q′. Assuming the initial state of the counter given by PQR as 000, what are the next three states?
GATE 2021 Set 2 · Q28MCQ2 marks
Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Example: input sequence 00100011000011100, output sequence 00000001000001100. A Mealy machine is a state machine where both the next state and the output are functions of the present state and the current input. The circuit can be designed as a two-state Mealy machine, with states represented by Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit by s, t, b and y respectively. The initial state is 0. What are the Boolean expressions corresponding to t and y in terms of s and b?
GATE 2018 · Q22NAT1 mark
Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops. The input "in" feeds the first flip-flop, the output of the first flip-flop feeds the second, and the output of the second flip-flop is "out" (both share the clock). The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of "in" is ______.
GATE 2017 Set 2 · Q42MCQ2 marks
The next state table of a 2-bit saturating up-counter is given below. Q₁Q₀ → Q₁⁺Q₀⁺: 00 → 01, 01 → 10, 10 → 11, 11 → 11. The counter is built as a synchronous sequential circuit using T flip-flops. The expressions for T₁ and T₀ are
GATE 2016 Set 1 · Q8NAT1 mark
We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is ______.
GATE 2014 Set 2 · Q7MCQ1 mark
Let k = 2ⁿ. A circuit is built by giving the output of an n-bit binary counter as input to an n-to-2ⁿ bit decoder. This circuit is equivalent to a
GATE 2014 Set 3 · Q45MCQ2 marks
A synchronous sequential circuit is built using three JK flip-flops with outputs Q₂, Q₁, Q₀ and a common clock. Connections: J₂ = Q₀′, K₂ = Q₀; J₁ = Q₂, K₁ = Q₂′; J₀ = Q₁, K₀ = Q₁′. The circuit is initialized with Q₂Q₁Q₀ = 000. The state sequence for this circuit for the next 3 clock cycles is
Common traps
A Johnson counter of n flip-flops has 2n states, a ring counter only n.
The asynchronous clear of a mod-N counter fires at N, so the visible sequence stops at N − 1.
A Moore machine's output is valid after the clock edge; a Mealy output can change mid-cycle with the input.
A counter with don't-cares may be non-self-starting: check the unused states.