Electrical Engineering › Section U · Sequential logic › Topic U.4

Finite state machines and asynchronous and synchronous counters

Traffic lights, vending machines and processor control units all step through a fixed set of states in response to a clock and their inputs. Counters are the simplest such machines, and the way their flip-flops are clocked decides how fast and how cleanly they count.

Finite state machines

A finite state machine (FSM) is a sequential circuit with a limited number of states. It has three parts: flip-flops that store the present state, combinational next-state logic that decides the following state from the present state and the inputs, and output logic. With n flip-flops it can have up to \(2^n\) states. In a Moore machine the outputs depend only on the present state, so they change only when the state does. In a Mealy machine the outputs depend on the present state and the present inputs, so an input change can alter an output straight away, often letting the machine do the same job with fewer states.

Worked example: a traffic-light controller

A light cycles green, yellow, red, each for a time set by a separate timer. 1. Three states need at least 2 flip-flops, since \(2^2 = 4 \ge 3\). 2. Encode them as \(Q_1Q_0\): green 00, yellow 01, red 10. The fourth code, 11, is unused. 3. Next-state rule: when the timer signals that time is up, green goes to yellow, yellow to red and red back to green; otherwise the state holds. 4. As a Moore machine, each lamp depends only on the state: green lamp \(= \overline{Q_1}\,\overline{Q_0}\), yellow \(= \overline{Q_1}Q_0\), red \(= Q_1\overline{Q_0}\). 5. Check: in each used state exactly one lamp is lit. A pedestrian button that lit a "wait" sign the instant it was pressed would make the machine Mealy.

Counters as state machines

A counter is an FSM whose states follow a fixed sequence, usually binary numbers, with the clock as its only input. Its modulus is the number of states in its sequence: n flip-flops give a full-modulus counter of \(2^n\) states, and a counter that stops short, such as a decade counter with 10 states, is called truncated. Counters fall into two families. In an asynchronous counter the flip-flops are not all clocked together: each is clocked by the output of the one before. In a synchronous counter every flip-flop receives the same clock.

Asynchronous (ripple) counters

Take three J-K flip-flops with \(J = K = 1\), so each toggles at its active clock edge, and make them falling-edge triggered. The external clock drives the first, whose output \(Q_0\) clocks the second, whose \(Q_1\) clocks the third. \(Q_0\) toggles on every clock pulse. \(Q_1\) toggles each time \(Q_0\) falls from 1 to 0, which is every second pulse, and \(Q_2\) every fourth. Read as \(Q_2Q_1Q_0\), the outputs count 000, 001, 010 up to 111 and then return to 000: a modulus-8 counter. Each stage also divides the frequency by 2, so \(Q_2\) runs at one-eighth of the clock frequency.

Worked example: watching the ripple

A 3-bit ripple counter goes from 011 to 100, with each flip-flop taking 10 ns to respond to its clock. 1. The clock edge toggles \(Q_0\) from 1 to 0, 10 ns later: the outputs read 010. 2. That falling \(Q_0\) clocks the second flip-flop, and 10 ns after that \(Q_1\) falls: 000. 3. The falling \(Q_1\) clocks the third, and at 30 ns \(Q_2\) rises: 100. 4. So the counter passes briefly through 010 and 000 before settling, and the full change takes \(3 \times 10 = 30\) ns. A decoder watching for 000 or 010 would produce a false pulse. The longest ripple, n stage delays, must also be shorter than the clock period.

Asynchronous decade counters

To count 0 to 9 and then restart, a 4-bit ripple counter needs its count cut short at 10. The first unwanted state, 1010, is the first count with both \(Q_3\) and \(Q_1\) HIGH, so a 2-input NAND gate on \(Q_3\) and \(Q_1\) drives the active-LOW clear inputs of all four flip-flops. As soon as 1010 appears, the NAND output goes LOW and the counter is forced to 0000. The state 1010 exists for only a few nanoseconds, but it is a real glitch. The same method truncates a ripple counter to any modulus: decode the first state that should not appear and use it to clear the counter.

Synchronous counters

In a synchronous counter all the flip-flops share the clock, and gates decide which ones toggle. In binary counting a bit changes exactly when all the bits below it are 1. So for a 4-bit up counter, using J-K flip-flops with J and K tied together: stage 0 always toggles; stage 1 toggles when \(Q_0 = 1\); stage 2 when \(Q_0Q_1 = 1\); stage 3 when \(Q_0Q_1Q_2 = 1\). All outputs that change do so together, one flip-flop delay after the edge, so there are no ripple states and the speed does not depend on the number of bits. The 74HC163 is a 4-bit synchronous binary counter.

Worked example: a synchronous decade counter

Modify the 4-bit synchronous counter to count 0 to 9. 1. After 1001 the next state must be 0000. 2. Stage 0 still toggles at every edge. 3. Stage 1 must not toggle at 1001, so its condition becomes \(Q_0\overline{Q_3}\). 4. Stage 2 keeps \(Q_0Q_1\). 5. Stage 3 must toggle at 0111, going up to 1000, and again at 1001, going back to 0: its condition is \(Q_0Q_1Q_2 + Q_0Q_3\). 6. Check by simulating every state: 0, 1, 2 up to 9, then 0. The six unused codes, 10 to 15, all lead back into the 0 to 9 sequence within two clocks, so the counter cannot get stuck if it powers up in one of them.

Up/down counters

An up/down counter can count in either direction, chosen by a control input. Counting up, a bit toggles when every lower bit is 1; counting down, it toggles when every lower bit is 0. So in a 3-bit down counter, stage 1 toggles when \(\overline{Q_0} = 1\) and stage 2 when \(\overline{Q_0}\,\overline{Q_1} = 1\): from 5 it counts 4, 3, 2, 1, 0, then wraps to 7. The direction input selects between the two sets of toggle conditions with AND-OR gates. The 74HC190 is a synchronous up/down decade counter with parallel load, and its down count runs 9, 8 down to 0, then 9.

Common mistakes to avoid

First, confusing Moore and Mealy: a Moore output depends on the state alone. Second, thinking a ripple counter's outputs change together; each waits for the stage before, so transient wrong states appear. Third, giving the modulus as the highest count: a 0 to 9 counter has modulus 10, not 9. Fourth, decoding the wrong state to truncate a ripple counter; use the first state that must not appear. Fifth, ignoring unused states in a truncated synchronous counter; check that each one leads back into the main sequence.

Key takeaways

An FSM has state flip-flops, next-state logic and output logic; Moore outputs depend on the state, Mealy outputs on the state and inputs. A counter is an FSM with a fixed sequence, and its modulus is its number of states. Ripple counters clock each stage from the one before, so delays add up and transient states cause glitches; a decade version clears itself at 1010. Synchronous counters clock every stage together, and a stage toggles when all lower bits are 1 when counting up, or all 0 when counting down.

Flashcards

Flashcard

Finite state machine

State flip-flops, next-state logic and output logic

n flip-flops give up to 2ⁿ states.

Test your understanding

Question 1 of 5

A state machine's output changes the instant an input changes, without waiting for a clock edge. What kind of machine is it?

Question 2 of 5

A 4-bit ripple counter uses flip-flops with a 12 ns delay each. What is the worst-case time for the outputs to settle after a clock edge?

Question 3 of 5

A ripple counter is to be truncated to modulus 12 by clearing it when the unwanted state appears. Which state should the gate detect?

Question 4 of 5

In a 4-bit synchronous up counter built from J-K flip-flops with J and K tied together, when does stage 3 toggle?

Question 5 of 5

A 3-bit synchronous down counter is at 010. What are its next three states?

← Previous topicNext topic →