State of a 4-bit synchronous up-counter after 13 clock pulses
BlinkNBuild practice problem · GATE standard, authored and verified in-house
A 4-bit synchronous binary up-counter is built from T flip-flops, all clocked by the same edge. The initial state is $Q_3Q_2Q_1Q_0 = 0000$. Determine the state after 13 clock pulses.
Show the step-by-step derivation
Step-by-step derivation
- An $n$-bit binary counter has $2^n$ distinct states. Here $n = 4$, so the counter is modulo $2^4 = 16$ and its states run $0, 1, 2, \ldots, 15$ before wrapping back to $0$.
- Each clock pulse advances the count by exactly one. Starting from state $S_0$, the state after $N$ pulses is therefore $$S_N = (S_0 + N) \bmod 16.$$
- Substituting $S_0 = 0$ and $N = 13$: $$S_{13} = (0 + 13) \bmod 16 = 13.$$ Since $13 < 16$ there is no wrap-around.
- Convert $13_{10}$ to 4-bit binary by repeated division by 2: $13 \div 2 = 6$ r $1$; $\;6 \div 2 = 3$ r $0$; $\;3 \div 2 = 1$ r $1$; $\;1 \div 2 = 0$ r $1$. Reading the remainders bottom-to-top gives $1101_2$.
- Check by place value: $1101_2 = 8 + 4 + 0 + 1 = 13$. ✓ Hence $Q_3Q_2Q_1Q_0 = \mathbf{1101}$.
The idea behind this question
An $n$-bit binary counter is a modulo-$2^n$ counter: it counts $0, 1, \ldots, 2^n - 1$ and wraps to $0$. After $N$ clock pulses from state $S_0$ it is in state $(S_0 + N) \bmod 2^n$, so a question about the state after many pulses is really a question about remainders.
Try a variation
The same counter starts at $0000$. What is its state after $21$ clock pulses?
Show the answer
Answer: $0101$
$21 \bmod 16 = 5$, and $5 = 0101_2$.
Other mistakes to avoid
- Counting the initial state as the first pulse, which gives an answer one too high.
- Forgetting the wrap-around when $N$ is larger than $2^n - 1$.