GATE CS 2014 Set 2 Q7 — Sequential Circuits

To understand the behavior of the circuit, let us analyze its two components:

1. $n$-bit Binary Counter: An $n$-bit binary counter counts sequentially from $0$ to $2^n - 1$ in binary. Since $k = 2^n$, it has $k$ distinct states ($0, 1, 2, \dots, k-1$).
2. $n$-to-$2^n$ Decoder: A decoder with $n$ input lines has $2^n = k$ output lines ($Y_0, Y_1, \dots, Y_{k-1}$). For any binary input representing the value $i$, only the $i^{\text{th}}$ output line $Y_i$ is active (HIGH), while all other $k-1$ output lines remain inactive (LOW).

As the counter increments on each clock pulse, the active output of the decoder shifts sequentially:

• At count $0$: Output state is $1000\dots0$ (only $Y_0$ is HIGH)
• At count $1$: Output state is $0100\dots0$ (only $Y_1$ is HIGH)
• At count $2$: Output state is $0010\dots0$ (only $Y_2$ is HIGH)
• $\dots$
• At count $k-1$: Output state is $0000\dots1$ (only $Y_{k-1}$ is HIGH)

After reaching $k-1$, the counter resets to $0$, and the sequence repeats. This behavior, where a single active bit (HIGH) circulates through $k$ outputs, is identical to that of a $k$-bit ring counter.

Therefore, the circuit is equivalent to a $k$-bit ring counter.