Counters

definitions
computer-systems
digital-logic
sequential-logic

A counter is a multi-bit register that goes through a determined sequence of states (values) upon the application of input (clock) pulses. It is a [[sequential-circuits|synchronous sequential circuit]] built from [[flip-flops-and-latches|D flip-flops]] plus some combinational logic in the feedback path.

Binary counters

A counter which follows the binary number sequence is a binary counter.

An \(n\)-bit binary counter:

  • has \(n\) flip-flops;
  • has \(2^n\) different states;
  • counts from \(0\) to \(2^n - 1\), then wraps back to \(0\).

For example, a 2-bit binary counter counts

\[00 \to 01 \to 10 \to 11 \to 00 \to \ldots\]

i.e. \(0 \to 1 \to 2 \to 3 \to 0 \to \ldots\)

4-bit binary counter — counting sequence

Bit 3 Bit 2 Bit 1 Bit 0 Value
0 0 0 0 0
0 0 0 1 1
0 0 1 0 2
0 0 1 1 3
0 1 0 0 4
0 1 0 1 5
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8
1 0 0 1 9
1 0 1 0 10
1 0 1 1 11
1 1 0 0 12
1 1 0 1 13
1 1 1 0 14
1 1 1 1 15
0 0 0 0 0

Note how each bit toggles at half the rate of the bit to its right — bit 0 changes every count, bit 1 every second count, bit 2 every fourth, bit 3 every eighth.

Key points

  • The next state is a function of the present state (and possibly of external inputs).
  • The count sequence can be the binary numbers but does not have to be — if it is, the counter is a binary counter; otherwise it is just some arbitrary cycle through states.
  • These circuits are synchronous: all flip-flops share the same clock.
  • Asynchronous counters exist too, but are not discussed in this course.

State: the design idea

This is the whole trick, and it is what makes counter design mechanical:

  • The values stored in the flip-flops are the current (present) state of the circuit.
  • The \(D\) inputs to the flip-flops are the next state — whatever is sitting on \(D\) at the clock edge becomes the new state.
  • The \(D\) inputs are some combinational function of the current state (and of any external inputs).

So for a counter with state bits \(Q_{n-1} \ldots Q_1 Q_0\), designing the counter means finding \(n\) Boolean expressions

\[D_i = f_i(Q_{n-1}, \ldots, Q_1, Q_0)\]

and building each one out of gates.

Design recipe

  1. Write down the count sequence you want, as a cycle of state values.
  2. Build a present-state / next-state table. One row per possible state — all \(2^n\) of them, not just the ones in your sequence. Columns: present state \(Q_{n-1}\ldots Q_0\), then next state \(D_{n-1}\ldots D_0\). Fill each next-state entry by reading off what follows that state in your sequence.
  3. Handle unused states. If your sequence doesn’t use all \(2^n\) states, the next state for the unused ones is a don’t-care (X). You may set each X to whatever makes the algebra simplest — but check afterwards where the unused state actually goes, because a self-correcting counter (one whose unused states lead back into the cycle) is nicer than one that can get stuck.
  4. Read each \(D\) column as a Boolean function of the \(Q\)s. The table is a truth table with the \(Q\)s as inputs and \(D_i\) as the output, so write it in sum-of-products form: OR together one AND term per row where \(D_i = 1\). See boolean-algebra.
  5. Simplify each expression using the Boolean algebra laws (and the don’t-cares), then draw the circuit: the combinational logic for \(D_i\) feeding flip-flop \(i\), with every flip-flop on a common clock. See circuit-schematics for schematic conventions and device-pinouts for the 74HCT74 / 74HCT175 D flip-flop packages.

The smallest case falls straight out of the recipe: a 1-bit counter counts \(0 \to 1 \to 0 \to \ldots\), so its next state is always the complement of its present state, giving \(D = \bar Q\) — a single flip-flop with its \(\bar Q\) output wired back to its own \(D\) input (a toggle).

Worked example — a 2-bit counter for \(00 \to 10 \to 01 \to 00\)

Note

This example is posed on the lecture slides but left blank (“to be worked through in class”). The derivation below is reconstructed, not copied from the slides.

Step 1–2 — present-state / next-state table. The sequence uses three of the four states; \(11\) is unused, so its next state is a don’t-care.

\(Q_1\) \(Q_0\) \(D_1\) \(D_0\) comment
0 0 1 0 \(00 \to 10\)
0 1 0 0 \(01 \to 00\)
1 0 0 1 \(10 \to 01\)
1 1 X X unused state

Step 4 — read off the columns.

\(D_1\) is 1 only in the row \(Q_1Q_0 = 00\). Making the don’t-care 1 would give \(Q_1 \odot Q_0\) (XNOR), which is no simpler, so take the don’t-care as 0:

\[D_1 = \bar Q_1 \bar Q_0\]

\(D_0\) is 1 only in the row \(Q_1Q_0 = 10\), which gives \(D_0 = Q_1\bar Q_0\). Here the don’t-care does help: setting it to 1 makes \(D_0 = 1\) for both rows with \(Q_1 = 1\), so

\[D_0 = Q_1\]

Step 5 — the circuit. Two D flip-flops on a common clock. Flip-flop 0’s \(D\) input is wired directly to flip-flop 1’s \(Q_1\) output — no gate at all. Flip-flop 1’s \(D\) input is driven by a 2-input NOR of \(Q_1\) and \(Q_0\) (since \(\bar Q_1 \bar Q_0 = \overline{Q_1 + Q_0}\)), or equivalently by an AND of the two \(\bar Q\) outputs.

Check, including the unused state:

present \(D_1 D_0\) next
00 1 0 10
10 0 1 01
01 0 0 00
11 0 1 01

The cycle is right, and the unused state \(11\) falls into the cycle at \(01\) on the next clock edge, so the counter is self-correcting. (Choosing \(D_0 = Q_1\bar Q_0\) instead — don’t-care set to 0 — would send \(11 \to 00\), also fine, at the cost of one more gate input.)

Applied exercise

week4-lab-lab-7-exercises is exactly this recipe at \(n = 3\): design a 3-bit synchronous counter that steps through an allocated 7-state sequence, with the eighth (missing) state treated as a don’t-care.