10.7 Mod-N Counter

Calculate the minimum flip-flop count for a given modulus N, and explain the two standard design techniques for forcing a binary counter to use exactly N states instead of a full power of two.

A Mod-N counter is a counter deliberately designed to have exactly N valid states in its count sequence, rather than using all 2^n states naturally available to its flip-flops — for example, a decade (Mod-10) counter that counts 0 through 9 and then returns to 0, even though its 4 flip-flops could technically represent 16 different values. It exists because real-world counting needs are rarely a convenient power of two: a digital clock needs to count seconds 0-59, a decimal display needs digits 0-9, and both require a counter whose modulus is explicitly chosen and enforced rather than left at whatever 2^n happens to be.

Core concept: minimum flip-flops and unused states

The minimum number of flip-flops needed to build a Mod-N counter is n = ceil(log2(N)) — the smallest integer number of bits whose 2^n possible states is at least N. For example, Mod-10 (a decade counter) requires ceil(log2(10)) = ceil(3.32...) = 4 flip-flops, since 3 flip-flops only offer 2^3 = 8 states (not enough for 10), while 4 flip-flops offer 2^4 = 16 states (comfortably enough, with 6 states left unused).

This is precisely the spec's tricky point: a 4-bit counter has 16 possible binary combinations available to it, but a decade (Mod-10) counter deliberately uses only 10 of them (states 0000 through 1001) and never lets the remaining 6 (1010 through 1111) persist as valid counting states — those combinations are simply not part of the intended count sequence, and a well-designed Mod-N counter either avoids generating them at all or corrects itself out of them immediately if it ever does.

• n = ceil(log2(N)) is the minimum number of flip-flops needed for a Mod-N counter. • Mod-10 (decade counter) needs ceil(log2(10)) = 4 flip-flops, since 2^3 = 8 is not enough but 2^4 = 16 is. • The 2^n - N 'extra' states available to the flip-flops but not part of the intended sequence are deliberately unused/invalid.

Step-by-step: two standard design techniques

The first, simpler technique is the reset/decode method: build an ordinary n-bit binary counter (n = ceil(log2 N)), then add a combinational decoder (an AND/NAND gate) that detects the state equal to N (the first state just past the intended range) and uses that detection to asynchronously clear every flip-flop back to 0. Practically, this means the counter very briefly, transiently touches state N for roughly one gate-propagation delay before the clear forces it back to 0 — a narrow glitch on the decode line that downstream logic must be designed to tolerate or filter, but the counter never stably settles into state N or beyond.

The second technique is the synchronous/direct design method: derive each flip-flop's excitation equations directly from a state table covering only the N intended states (using standard sequential-circuit design tools such as excitation tables and K-maps, as covered for JK/D/T flip-flops in Module 8). This approach can be made 'self-correcting' — meaning that even if the counter somehow powers up in one of the 2^n - N unused states, the derived next-state logic guarantees it returns to a valid state within one or two clocks, without ever relying on an external reset — a guarantee the simple decode-and-clear method does not automatically provide.

Practical example and real-world application

Worked example: to build a Mod-6 counter (6 valid states, 0 through 5), compute n = ceil(log2(6)) = ceil(2.58...) = 3 flip-flops (2^3 = 8 states available, 2 unused). Using the reset/decode method: build a normal 3-bit binary counter and add a 2-input AND gate sensing Q2 AND Q1 (which is true exactly at state 110, decimal 6, the first state past the intended 0-5 range); that gate's output asynchronously clears all three flip-flops, so the counter transiently touches 110 for about one gate delay before snapping back to 000.

Mod-N counters chain together to build practical time-of-day circuits: a digital clock's 'seconds ones' digit is a Mod-10 counter (0-9), its 'seconds tens' digit is a Mod-6 counter (0-5, since seconds only go up to 59), and the ones digit's rollover (from 9 back to 0) is what clocks the tens digit forward by one — exactly the technique used inside real digital clock and calendar ICs to build a Mod-60 seconds counter, a Mod-60 minutes counter, and a Mod-24 (or Mod-12) hours counter out of smaller Mod-N stages.

Mod-N counter formula and reset-method notation

Always take the ceiling of log2(N) — truncating instead of rounding up under-provisions the counter (e.g. log2(10) = 3.32, truncated to 3 bits gives only 8 states, not enough for 10). When N is exactly a power of two, no unused states or reset logic exist at all — the counter is naturally Mod-N already.

Minimum flip-flops for a Mod-N counter:

  n = ceil(log2(N))

Examples:
  Mod-10  (decade)   n = ceil(log2(10))  = ceil(3.32) = 4 flip-flops  (16 states available, 10 used)
  Mod-6              n = ceil(log2(6))   = ceil(2.58) = 3 flip-flops  (8 states available, 6 used)
  Mod-16             n = ceil(log2(16))  = 4 flip-flops               (16 states available, 16 used -- natural binary, no reset needed)

Reset/decode method:
  binary counter (n bits) --> decode state N --> async CLEAR all flip-flops
  (counter transiently touches state N for ~1 gate delay, then clears to 0)

Code Examples

The counter behaves as an ordinary 3-bit binary up counter through states 0-5. The instant it would reach state 6 (110), the decode AND gate (sensing Q2 AND Q1) detects it and asynchronously clears all three flip-flops back to 0 — so state 6, and the remaining unused states 7 (111), never persist as stable counting states; only 0 through 5 are ever observed as settled values. Expected result: Stable count sequence observed: 0, 1, 2, 3, 4, 5, 0, 1, ... (6 valid states, Mod-6).

n = ceil(log2(6)) = 3 flip-flops; decode gate detects state 6 and asynchronously clears the counter back to 0.

n = ceil(log2(6)) = 3 flip-flops (2^3 = 8 states available)

Clock#   Q2 Q1 Q0   Decimal   Note
  0        0  0  0      0
  1        0  0  1      1
  2        0  1  0      2
  3        0  1  1      3
  4        1  0  0      4
  5        1  0  1      5
  6        1  1  0      6     <- decoder fires (Q2.Q1 = 1); async CLEAR forces state back to 0
         [transient, ~1 gate delay]
  6'       0  0  0      0     <- settled state after the clear

Mod-N counter via reset/decode

The decoder watches for the first invalid state (N) and immediately clears the counter, so it never stably settles past N-1.

CLK --> [n-bit binary counter] --Q(n-1..0)--> [decoder: state == N?] --> async CLEAR
              ^_________________________________________________________|
              (clear forces counter back to state 0 the instant state N is decoded)

Important Rules

n = ceil(log2(N)) is the minimum flip-flop count for a Mod-N counter — always round up, since a fractional log2(N) means the next integer bit count is required to reach at least N states.

The reset/decode design method causes a brief, transient (roughly one-gate-delay) pass through the first invalid state before clearing — this glitch must be accounted for in any logic observing the decode signal directly.

N need not be a power of two — Mod-N counters, especially Mod-10 decade counters, are essential for building human-readable decimal digit displays and real-world time/date counters (seconds, minutes, hours) out of binary flip-flops.

Decade counters in digital clocks and displays

Digital clocks, calendars, and any decimal numeric display are built almost entirely from chained Mod-N counters: a Mod-10 counter drives each 'ones' digit (seconds, minutes ones-digit), a Mod-6 counter drives each 'tens' digit for seconds and minutes (since a tens digit only needs to reach 5 before the whole two-digit field rolls over at 60), and the ones digit's own rollover-to-zero pulse is what advances the tens digit by one — building a full Mod-60 count purely from smaller Mod-N stages chained together.

Computing the flip-flop count for a Mod-N counter as log2(N) without rounding up (e.g., using 3 bits for N=10 because log2(10) is 'about 3').

Always take the ceiling: n = ceil(log2(N)). For N=10, log2(10) ~= 3.32, so 3 bits (only 8 states) is not enough — you need 4 bits (16 states) to have at least 10 available, even though 6 of those 16 states go unused.

Truncating instead of rounding up under-provisions the counter: an 3-bit register genuinely cannot represent 10 distinct values (its maximum is 8), so any Mod-N design must round the flip-flop count up to the next whole number whenever log2(N) is not already an integer.

[tricky-problem] A decade (Mod-10) counter is built from 4 flip-flops, which can represent 16 distinct binary combinations. Why does the counter only ever show 10 of them? A. Because the extra 4 flip-flop bits are physically disconnected B. Because the counter is deliberately designed (via a reset/decode circuit or a direct synchronous design) to never stably remain in states 10 through 15 — it detects or avoids them and returns to state 0 instead of counting into them C. Because binary counters can only ever use exactly powers-of-two minus one as their modulus D. Because 4 flip-flops can actually only represent 10 values, not 16

B. Because the counter is deliberately designed (via a reset/decode circuit or a direct synchronous design) to never stably remain in states 10 through 15 — it detects or avoids them and returns to state 0 instead of counting into them — This is exactly the spec's tricky point: 4 flip-flops genuinely offer 16 possible states, but a Mod-10 counter is intentionally designed (via decode-and-clear logic, or via directly-derived synchronous excitation equations) so that states 10 through 15 are never valid, stable counting states — the counter either transiently glitches through the first invalid state before self-clearing, or is designed from the start to never generate those states at all.

[interview] What is the minimum number of flip-flops needed to build a Mod-24 counter (for example, to drive a 24-hour clock display), and why must you round up rather than truncate? A. 4 flip-flops, because log2(24) rounds down to 4 B. 5 flip-flops, because log2(24) ~= 4.58, and only rounding UP to 5 gives 2^5 = 32 states, which is enough to cover all 24 required states (4 bits, giving only 16 states, would not be enough) C. 24 flip-flops, one per counted value D. 3 flip-flops, since any counter can be built with 3 bits regardless of N

B. 5 flip-flops, because log2(24) ~= 4.58, and only rounding UP to 5 gives 2^5 = 32 states, which is enough to cover all 24 required states (4 bits, giving only 16 states, would not be enough) — n = ceil(log2(24)) = ceil(4.58...) = 5. Four flip-flops would only provide 2^4 = 16 states, which is fewer than the 24 states required, so 4 bits is insufficient; you must round up to 5 bits (2^5 = 32 states) to have enough states available, leaving 8 of those 32 states unused by the Mod-24 design.

You need to build a Mod-12 counter (for example, to drive a 12-hour clock display, cycling 1 through 12 or 0 through 11). Compute the minimum number of flip-flops required, and describe (using the reset/decode method) which state your decoder must detect to trigger the reset.

n = ceil(log2(12)) = ceil(3.58...) = 4 flip-flops (2^4 = 16 states available, 12 used, 4 unused). If counting 0 through 11, the decoder should detect state 12 (binary 1100) — the first state past the intended range — and use that detection to asynchronously clear the counter back to 0, exactly mirroring the Mod-6 example, just with N=12 instead of N=6.

n = ceil(log2(12)); the decoder should fire on the first state past your intended range, not on the last valid state itself.