Exercises — Ring and Johnson counters

A ring counter circulates one hot bit through $n$ positions, so it has $N_{\text{ring}}=n$ states. A Johnson counter fills then empties, taking $n+n$ steps, so $N_{\text{John}}=2n$ states. With $n=6$: $N_{\text{ring}}=6,N_{\text{John}}=2\times 6=12.$

The single difference is the inverter. Feeding back the straight output $Q_0$ copies the last bit → Circuit A is the ring counter. Feeding back the complement $\overline{Q_0}$ twists the ring → Circuit B is the Johnson counter.

(Note on convention: the parent note wired feedback from $Q_3$ because it drew the register in the opposite orientation. On this page bits slide toward $Q_0$, so the "last" cell the bit reaches is $Q_0$, and feedback is taken from $Q_0$. The two descriptions are the same circuit, just mirrored on paper.)

Apply the fixed shift rule from the notation box: each cell copies the cell to its left, and $Q_3$ takes the fed-back bit $Q_0$. So the whole pattern slides one place toward $Q_0$ (the right), and the bit that leaves the $Q_0$ end re-enters at the $Q_3$ end.

After 4 clocks the 1 has visited all 4 cells and returned home — confirming $N=4$.

The figure below stacks these five rows top-to-bottom, one red cell per row marking where the single 1 sits.

Apply the same shift rule, but now the incoming bit is $\overline{Q_0}$ (the complement of the rightmost cell):

Fill (4 steps) then empty (4 steps) = 8 states. Here "fill" means 1s enter at the $Q_3$ end and build up leftward; "empty" means 0s enter at the $Q_3$ end and push the 1s out toward $Q_0$.

At $1111$ the rightmost bit is $Q_0=1$, so the shifted-in bit is $\overline{Q_0}=0$. One shift slides everything toward $Q_0$ and pushes a single 0 into the $Q_3$ end: $1111\to 0111.$ Not $0000$. The all-zero state appears only after all four 1s have been shifted out one at a time (clock 8). In figure s02 this is the transition from row "4 1111" to row "5 0111": exactly one red 0 has appeared at the left, nothing more.

Key idea: in a Johnson counter the register is always "1s on one side, 0s on the other". So there is exactly one place where the pattern switches value — call it the boundary. The boundary sits between a different pair of adjacent cells in every single state, which is why one adjacent-pair test pins down one state.

Why the boundary is unique to each state — systematic argument. Using this page's sequence (fill states $0000,1000,1100,1110,1111$ and empty states $0111,0011,0001$), look at state $0011$. Its cells are $Q_3{Q}_2{Q}_1{Q}_0=0011$: reading right-to-left the switch from 1 to 0 happens between $Q_1=1$ and $Q_2=0$.

Walk the states and record which adjacent pair $(Q_{i+1}=0,Q_i=1)$ holds (a "0 sitting just left of a 1"):

Each of these states has its 0-left-of-1 switch at a different index, so the pairs are distinct. The remaining valid states $1000,1100,1110,1111$ have their 1s on the left, so none of them has a 0 immediately left of a 1 — in particular none satisfies $Q_2=0$ and $Q_1=1$. Therefore no valid state except $0011$ has $Q_2=0$ and $Q_1=1$ simultaneously.

That gives the one-gate decode: $\text{decode}(0011)=Q_1\cdot \overline{Q_2}.$ A single 2-input AND with one input inverted — cheap and glitch-free. To decode any other state, just AND the two cells straddling its boundary (the 0-side inverted).

Step 1 — how many of the $2n$ states have $Q_i=1$? Look down any single column of figure s02. Take $Q_0$ (rightmost column): scanning clocks 0→7 its values are $0,0,0,0,1,1,1,1$ — high for exactly 4 of the 8 states. Take $Q_3$ (leftmost column): $0,1,1,1,1,0,0,0$ — again high for exactly 4 of the 8. This is no accident: in a Johnson counter every cell spends the "fill" half of the cycle transitioning to 1 and staying 1, then the "empty" half transitioning to 0 and staying 0, so each output is high for exactly $n$ of the $2n$ states and low for the other $n$.

Step 2 — that means one full high-then-low period per whole cycle. Because each $Q_i$ makes a single continuous block of 1s followed by a single continuous block of 0s per cycle, it completes exactly one up-and-down (one period) every time the counter runs through all $2n$ states. The whole cycle is $2n$ clock ticks long, so: $f_Q=\frac{f_{\text{clk}}}{2n}=\frac{8\text{ MHz}}{2\times 4}=\frac{8}{8}\text{ MHz}=1\text{ MHz}.$ So a Johnson counter divides the clock by $2n$. (A ring counter would divide by $n=4$, giving $2$ MHz.) This is the Frequency Division use-case.

With $n=8$, $2^n=256$. $\text{ring: }\frac{n}{2^n}=\frac{8}{256}=0.03125=3.125\%.$ $\text{Johnson: }\frac{2n}{2^n}=\frac{16}{256}=0.0625=6.25\%.$ Johnson uses $16/8=2$ times as many of the available states, so it is twice as efficient. Both are still hugely wasteful versus a binary counter (100%) — the trade is silicon-for-simplicity and glitch-freedom.

Requirement "2-input decode + one-bit-per-clock" points to Johnson. Set $2n=10$: $2n=10\Rightarrow n=5.$ A 5-bit Johnson counter gives $10$ states, each decodable with a single 2-input gate. (A ring counter would need $n=10$ flip-flops to reach 10 states — twice the hardware — so Johnson wins here.)

Shift rule: new leftmost bit $Q_3\leftarrow \overline{Q_0}$, and every other cell copies its left neighbour.

• $0101$: $Q_0=1\Rightarrow$ shift in $\overline{Q_0}=0$ → $0010$.
• $0010$: $Q_0=0\Rightarrow$ shift in $1$ → $1001$.
• $1001$: $Q_0=1\Rightarrow$ shift in $0$ → $0100$.
• $0100$: $Q_0=0\Rightarrow$ shift in $1$ → $1010$; $1010\to 0101\to 0010\to \dots$

The trajectory wanders among unused patterns $\{0101,0010,1001,0100,1010\}$ and never reaches any valid state ($0000,1000,1100,1110,1111,0111,0011,0001$). This is a lock-out / dead loop — an unused-state cluster the counter can enter and cannot escape. Cured by making the counter self-starting.

Read the formula with the Boolean symbols from the notation box: $D_{\text{feedback}}$ is 1 only when $\overline{Q_0}$ is 1 AND ($Q_3$ OR $\overline{Q_1}$) is 1. The register updates as $Q_3\leftarrow D_{\text{feedback}}$, $Q_2\leftarrow Q_3$, $Q_1\leftarrow Q_2$, $Q_0\leftarrow Q_1$.

(a) Valid states are untouched. Compute $D_{\text{feedback}}$ for each valid state $Q_3{Q}_2{Q}_1{Q}_0$ and compare to the plain $\overline{Q_0}$:

Every valid state gives the same $D_{\text{feedback}}$ as plain $\overline{Q_0}$ → the normal cycle is preserved. ✓

(b) Full unused-state audit. The 8 unused states are $0010,0100,0101,0110,1001,1010,1011,1101$. For each, compute $D_{\text{feedback}}=\overline{Q_0}\cdot (Q_3+\overline{Q_1})$, then form the next state $(D_{\text{feedback}},Q_3,Q_2,Q_1)$ (leftmost is the new bit, the rest are the old $Q_3{Q}_2{Q}_1$ shifted right):

Trace each chain forward to see where it ends: $0110\to 0011(\text{valid})✓$ $1101\to 0110\to 0011(\text{valid})✓$ $0100\to 1010\to 1101\to 0110\to 0011(\text{valid})✓$ $1001\to 0100\to \cdots \to 0011(\text{valid})✓$ $0010\to 1001\to \cdots \to 0011(\text{valid})✓$ $0101\to 0010\to \cdots \to 0011(\text{valid})✓$ $1011\to 0101\to \cdots \to 0011(\text{valid})✓$ Every one of the eight unused states eventually funnels into the valid state $0011$ and rejoins the main cycle. So this feedback is self-starting: no matter which state the counter powers up in, it recovers into the legal count within a few clocks. (Contrast L4.2, where plain $\overline{Q_0}$ feedback left the counter trapped forever.)

(a) $16-8=8$ unused states. (b) The 8 valid states are $0000,1000,1100,1110,1111,0111,0011,0001$. Every other 4-bit pattern is unused: $0010,0100,0101,0110,1001,1010,1011,1101.$ Count: 8 patterns. ✓ Each of these is a candidate power-up state that a self-starting design must route back into the valid cycle.

Divide-by-7 needs 7 states. Johnson gives $2n$ (always even) — never 7. Ring gives $n$ (any integer) — so use a ring counter with $n=7$ flip-flops, preset with a single 1. $N=n=7,f_{\text{out}}=\frac{f_{\text{clk}}}{7}=\frac{14\text{ MHz}}{7}=2\text{ MHz}.$ A ring counter is the natural choice for odd division factors; Johnson only reaches even factors $2n$.

• Johnson: $2n=12\Rightarrow n=6$ flip-flops. One bit changes per clock ✓. Divide-by-12 with 6 FFs.
• Ring: $n=12$ flip-flops for 12 states. One bit changes per clock ✓ but twice the hardware.
• Binary (synchronous): $\lceil {\log }_{2}12\rceil =4$ flip-flops, but needs modulus logic and multiple bits flip per tick → decoding glitches.

Why the binary counter glitches — concrete example. Suppose a binary counter steps from $0111$ (decimal 7) to $1000$ (decimal 8). In an ideal world all four bits flip at the same instant. In reality each flip-flop has a slightly different propagation delay, so for a few nanoseconds the outputs may pass through intermediate patterns, e.g. $0111\to 0110\to \dots \to 1000,$ because the low bits fall before the high bit rises. A decoder watching for, say, pattern $0110$ (decimal 6) would see a brief false pulse — a decoding glitch — even though the count "6" is not really being visited. See figure s03 below.

This is exactly the hazard (Glitches and Decoding Hazards) that ring/Johnson counters avoid by design: only one bit ever moves, so no phantom pattern can appear. For divide-by-12 with glitch-free single-bit transitions, the 6-flip-flop Johnson counter is the sweet spot.