Registers and Counters

A register is a bank of flip-flops sharing a clock, often with load, clear and shift controls. A counter is a register whose state sequence follows a counted order.

GATE asks for the state sequence and modulus of a given counter circuit (for example a shift register with feedback), ripple versus synchronous designs and their maximum clock rates, ring and Johnson counters with their unused states, mod-$N$ counters by reset or load, and shift-register contents after a number of clocks.

A counter with $m$ distinct states in cycle has modulus $m$. An $n$-FF binary counter naturally has modulus $2^n$; forcing a reset/load at a chosen code yields a smaller modulus (for example mod-6, mod-10 BCD). A mod-$N$ counter needs at least $\lceil \lg N \rceil$ flip-flops.

$T_0=1$; $T_i = Q_0 Q_1 \cdots Q_{i-1}$ for $i>0$. Down-count uses complemented conditions: $T_i = Q_0' Q_1' \cdots Q_{i-1}'$. An up/down counter with control $U$ uses $T_i = U\,Q_0\cdots Q_{i-1} + U'\,Q_0'\cdots Q_{i-1}'$.

In an up ripple counter the bits change one after another. Going from $0111$ to $1000$, $Q_0$ falls first, which clocks $Q_1$, and so on. The outputs pass through $0110$, $0100$ and $0000$ before reaching $1000$. A decoder on the outputs can glitch on those transient codes.

Detect the unwanted state (for example 1010 for decade after 1001) and asynchronously clear, or synchronously load 0000 on the next clock. With an asynchronous clear the unwanted state appears briefly, for the clear-path delay, before the reset. Synchronous clear is preferred to avoid short glitch states. With synchronous load, the detector watches the last wanted state (1001), not the first unwanted one.

Write each flip-flop's next state from its inputs, then step from the reset state until a state repeats; the cycle length is the modulus. Then check every unused state: if each one reaches the main cycle, the counter is self-starting; if some unused states cycle among themselves, it can lock out.

A typical 4-bit universal shift register uses two mode bits $s_1 s_0$:

Draw the 4:1 MUX in front of each $D_i$ with those four sources. If a figure omits a mode, recover it from the MUX wiring.

States $0000$ to $1001$ then back to $0000$. Toggle enables follow binary up-count until the detect of $1001$, which synchronously loads zero. Asynchronous clear on $1010$ is a common textbook alternative; it briefly produces $1010$ for a hazard window, so synchronous designs are preferred in questions that mention glitch-free decimal outputs.

Arrays are 0-indexed; <- is assignment.

The analysis visits each of the $2^n$ states at most $2^n$ times, $O(4^n)$ steps, trivial for exam sizes.

Counters are cyclic FSMs. Binary counting implements $+1 \bmod 2^n$ in the state encoding. Bit $i$ toggles exactly when bits $0$ to $i-1$ are all 1, which is when adding 1 carries into position $i$; this is the synchronous $T_i$. It also means bit $i$ has period $2^{i+1}$ clocks.

Johnson codes are $2n$ of the $2^n$ possible patterns, and successive codes differ in exactly one bit, including the step from the last back to the first. For $n\ge3$, unused patterns exist and cannot reach the valid cycle on their own, because the Johnson next-state map is a bijection: each pattern has exactly one predecessor, so the state graph is a set of disjoint cycles.

$000,001,010,011,100,101,110,111,000,\ldots$

$000,100,110,111,011,001,000,\ldots$ (six states). The two unused patterns, $010$ and $101$, map to each other: $010 \to 101 \to 010$.

Count $0..5$; when state is 5, next load 0. Natural 3-FF codes use 000..101; 110 and 111 unused (lock detection may force reset). With an asynchronous clear instead, the detector is $\overline{Q_2 Q_1}$ driving an active-low clear: state 110 appears for the clear delay and then becomes 000.

If each FF has $t_{cQ}=5\,\mathrm{ns}$, a 4-bit ripple needs up to $20\,\mathrm{ns}$ after the clock before all bits settle, so the clock must not exceed $50\,\mathrm{MHz}$ if the count is decoded every cycle. A synchronous 4-bit counter with $t_{cQ} = 5$, a 2 ns AND and $t_{su} = 3$ ns runs at $1/10\,\mathrm{ns} = 100\,\mathrm{MHz}$.

Three D flip-flops form a shift register $Q_2 \leftarrow Q_1$, $Q_1 \leftarrow Q_0$, with $Q_0 \leftarrow \overline{Q_1 + Q_2}$. From $000$ (written $Q_2Q_1Q_0$) the states are $000 \to 001 \to 011 \to 110 \to 100 \to 000$: modulus 5. The unused states $010$, $101$ and $111$ go $010 \to 100$, $101 \to 010$ and $111 \to 110$, all into the main cycle, so the counter is self-starting.

A 4-bit shift-right register holds $1011$ (MSB on the left) with serial input 0. After two clocks it holds $0010$; after four clocks, $0000$. Feeding the serial output back to the input instead (a rotate) returns $1011$ after four clocks.

The valid cycle is $0000, 1000, 1100, 1110, 1111, 0111, 0011, 0001$. Starting from the unused $0100$: $0100 \to 1010 \to 1101 \to 0110 \to 1011 \to 0101 \to 0010 \to 1001 \to 0100$, a second cycle of 8 that never meets the valid one.

Common misconceptions.