Counters and Shift Registers

Counters and registers are the most common sequential circuits: a CPU's program counter, timers, frequency dividers and serial links are all built from them.

Ripple (asynchronous) counters

In a ripple counter, only the first flip-flop gets the clock; each following flip-flop is clocked by the output of the previous one. With T flip-flops (T = 1, so each toggles) every stage divides the frequency by 2, and n flip-flops count from 0 to 2ⁿ − 1.

• Simple: no extra logic.
• Slow: the last flip-flop changes only after the change has rippled through all n stages, n × t_pd. The counter must settle before the next clock, so f_max = 1 / (n × t_pd).
• While it ripples, the outputs pass through wrong intermediate values (glitches).

Synchronous counters

All flip-flops share the same clock, and logic decides which ones toggle. In a binary up counter, bit i toggles when all lower bits are 1: T₀ = 1, T₁ = Q₀, T₂ = Q₁Q₀, T₃ = Q₂Q₁Q₀, ... All bits change together, so f_max = 1 / (t_pd + t_gate + t_su), independent of the number of bits.

Mod-N counters

A mod-N counter goes through N states and repeats. It needs ⌈log₂ N⌉ flip-flops. A decade (mod-10) counter needs 4 flip-flops and uses 10 of the 16 states. In a ripple counter, mod-N is often made by resetting all flip-flops as soon as the count reaches N (for mod-10, detect 1010 with a NAND of Q₃ and Q₁).

Designing a synchronous counter

1. Draw the state sequence and the state table (present state → next state).
2. For each flip-flop and each transition, read the required inputs from the excitation table.
3. Simplify each input with a K-map (unused states are don't cares).

Example: a 3-bit counter with the sequence 0 → 2 → 3 → 5 → 6 → 0 using T flip-flops. For each bit, T = 1 exactly when that bit changes: from 000 to 010 only Q₁ changes, so T₁ = 1 and T₂ = T₀ = 0 in state 000, and so on.

Ring and Johnson counters

Both are shift registers whose output feeds back to the input:

Both decode their states with simple gates and have no glitches, but they use flip-flops less efficiently than a binary counter.

Shift registers

A shift register is a chain of D flip-flops: at each clock edge every bit moves one place. Depending on where data enters and leaves:

A universal shift register can shift left, shift right, load in parallel or hold, chosen by control inputs.

Analysing a sequential circuit

Given the flip-flop input equations, find the state sequence by computing the next state from each present state. A small simulator does this mechanically. Here are a 3-bit Johnson counter and a circuit with D flip-flops whose inputs are D₂ = Q₁ ⊕ Q₀, D₁ = Q₀′ and D₀ = Q₂:

def trace(next_state, start, limit=16):
    states = [start]
    while len(states) <= limit:
        s = next_state(states[-1])
        if s in states:
            return states, s
        states.append(s)
    return states, None

fmt = lambda s: "".join(map(str, s))

johnson = lambda s: (1 - s[2], s[0], s[1])             # (Q2, Q1, Q0): Q2+ = Q0', shift right
circuit = lambda s: (s[1] ^ s[2], 1 - s[2], s[0])     # D2 = Q1 xor Q0, D1 = Q0', D0 = Q2

for name, f in [("Johnson", johnson), ("circuit", circuit)]:
    states, back = trace(f, (0, 0, 0))
    print(f"{name}: {' -> '.join(fmt(s) for s in states)} -> {fmt(back)} ({len(states)} states)")

Johnson: 000 -> 100 -> 110 -> 111 -> 011 -> 001 -> 000 (6 states)
circuit: 000 -> 010 -> 110 -> 111 -> 001 -> 100 -> 011 -> 000 (7 states)

The second circuit cycles through 7 of the 8 states; state 101 is never reached from 000. Checking what happens from such unused states (does the circuit fall back into the main cycle, or get stuck?) is part of a complete design. A counter that always returns to its main sequence is called self-starting.

Practice questions

s = (0, 0, 0)
for _ in range(3):
    s = (s[1] ^ s[2], 1 - s[2], s[0])
print("".join(map(str, s)))