Digital Electronics

Every traffic light, every microwave timer, every dishwasher cycle is built from the same small idea. There is a tiny brain inside that knows which mode it is currently in, and which buttons or signals are allowed to push it into a different mode. Press start on a microwave and it goes from idle to cooking. Open the door and it pauses. Press start again and it resumes. That decision-maker has a name — a finite-state machine — and once you have seen one, you start recognising them everywhere.

This demo wraps a stopwatch — the same one from Lab 3. It has three modes it can be in: stopped (waiting for you), ticking (counting time up), and paused (frozen mid-count, remembering where it left off). The buttons it understands are start, pause, resume, reset, and a clock tick that fires every time the crystal oscillator pulses. That is the entire vocabulary of the machine — three states, five inputs, nothing else.

Load the Start then pause preset and step through it by hand. The stopwatch begins in stopped. The first input is start — it moves to ticking. The next input is a clock tick — it stays in ticking (time is passing). Another tick — still ticking. The final input is pause — it moves to paused. Four button presses, and the machine landed exactly where you expected. That is the whole loop: read an input, look up the next mode, repeat.

Here is the punchline that makes state machines worth their name. Press pause while the stopwatch is in stopped — nothing happens. Press resume while it is in ticking — nothing happens. The same button does different things depending on where the machine currently is. That is the difference between this and a calculator: the answer depends not only on what you just pressed, but on the history of everything you pressed before it, collapsed down into the current mode.

That lookup rule has a name. Write it as $\delta (s,i)=s^{\prime }$\delta(s, i) = s' — given current state s and input i, the function δ returns the next state s’. For the stopwatch,

and $\delta (\text{ticking},\text{pause})=\text{paused}$\delta(\text{ticking}, \text{pause}) = \text{paused}, and so on. Anything not in the table — like pressing pause from stopped — simply maps the state back to itself: $\delta (s,i)=s$\delta(s, i) = s. A real FSM is just this table plus an initial state.

The stopwatch is what is called a Moore machine: the only thing it shows to the outside world — the indicator light reading stopped, ticking, or paused — depends purely on which state it is in. The light only changes once the state has changed. The alternative, a Mealy machine, would let the output depend on the input as well, so a label could light the instant you press a button without waiting for the next clock edge. Moore behaviour is calmer and easier to time; Mealy is faster but jumpier.

Three states means the machine needs $\lceil {\log }_{2}3\rceil =2$\lceil \log_2 3 \rceil = 2 bits to remember where it is — say 00 for stopped, 01 for ticking, 10 for paused. The fourth pattern 11 is unused, which is a free defensive feature: if a glitch or a bad reset ever flips the register into 11, you can route that case straight to a fallback transition back to stopped. Two flip-flops, three legal states, and one paranoid spare.

Reset is the one input that ignores everything else. From stopped, from ticking, from paused — pressing reset always sends the machine back to stopped with the count cleared. Load the Reset from running preset to watch the stopwatch tick for a beat and then snap straight to idle. Most real digital systems wire a synchronous reset like this onto every register, so a single power-on pulse drops the entire chip into a known starting position before the first useful clock cycle.

Try it yourself.

So a finite-state machine is just three things: a current mode, a table of $\delta (s,i)\to s^{\prime }$\delta(s, i) \to s' arrows, and a rule for what to output once you land. The Stopwatch FSM animation demo further down the page paints those same transitions onto a circle-and-arrow diagram and lets you walk the clock yourself; the featured problem on the 1011 sequence detector builds on the same machinery to recognise patterns in a bitstream, and shows how a Mealy encoding can shave a flip-flop off the design. Same algorithm, different jobs.

You have just finished sketching a truth table for a 4-input Boolean function. Sixteen rows, ones and zeros scattered down the right column, and your job is to wire up the smallest circuit that gives the same answers. Reading the table straight off gives you one AND gate per “1” row plus one giant OR — sixteen gates for what feels like it ought to be three. There has to be a smaller circuit hiding in those ones, and the Karnaugh map is the trick for spotting it with your eyes instead of with algebra.

The aha is one piece of clever bookkeeping. Instead of listing the rows of the truth table in normal binary order — 00, 01, 10, 11 — a K-map lays them out in Gray-code order, so neighbouring cells always differ in exactly one input bit. Two ones sitting side by side therefore mean the function does not care what that bit was, so the pair collapses into a smaller term. Eyeballing rectangles of ones on the grid is, secretly, factoring Boolean algebra by hand.

Load the AND gate preset — two inputs, A and B, with a single 1 in the cell where both are high. There is nothing to merge, so the map gives back the literal term $F=A\cdot B$F = A \cdot B. Boring, but it is the base case: a lone 1 cannot pair with any neighbour, so its cube keeps every variable. Every K-map exercise starts with this one-cell-equals-one-product rule and then looks for ways to grow.

Switch to the Majority-of-3 preset. The function is 1 whenever at least two of A, B, C are high, which puts four ones on the 3-variable map. Pair them up: minterms $m_3$m_3 and $m_7$m_7 share the AB=11 edge so they merge into AB, $m_5$m_5 and $m_7$m_7 merge into AC, and $m_6$m_6 with $m_7$m_7 merges into BC. Three pairs, three terms, and the answer is $F=AB+AC+BC$F = AB + AC + BC — three 2-input ANDs into one OR instead of four 3-input ANDs. Same function, fewer literals.

Under the hood the demo is not actually drawing rectangles — it runs the Quine-McCluskey algorithm, the algorithmic cousin of the K-map. It generates every minterm, repeatedly tries to merge pairs that differ in exactly one bit (replacing the disagreeing bit with a dash), and keeps merging until nothing more will combine. The leftovers are the prime implicants — the largest rectangles you could have drawn on the map. A greedy second pass then picks the smallest set of those rectangles that still covers every 1.

Sometimes a circuit is guaranteed never to see certain input combinations — maybe upstream logic stops them from ever appearing, or those codes are reserved for something else. The demo marks those cells with an X, and you read it as “we never input this combination, so the chip is free to output whatever simplifies the answer”. The minimiser then treats each X as a wildcard: include it in a rectangle if it lets that rectangle grow, ignore it otherwise. Free optimisation, no behaviour change.

Load the 4-var with don’t-cares preset. The real minterms — $m_1,m_3,m_7,m_{11},m_{15}$m_1, m_3, m_7, m_{11}, m_{15} — are scattered across the 16-cell map, and on their own they would not pair up cleanly. The don’t-cares at $m_0,m_2,m_5$m_0, m_2, m_5 let the minimiser absorb extra cells so the rectangles grow. Watch the literal count drop in the readout: that number is roughly the cost of the circuit in transistors, and don’t-cares are the cheapest optimisation you will ever get.

Try it yourself.

So a K-map is just a Gray-coded grid that turns Boolean factoring into a spot-the-rectangle puzzle, with Quine-McCluskey doing the same job algorithmically once the map grows too big to eyeball. The Logic gate truth table builder demo above is the perfect sibling — start there to generate the truth table, then bring those minterms here to minimise. The featured problem “Karnaugh-map minimisation of a 4-variable Boolean function” walks that same pipeline by hand, and the next-state logic that drives the FSM Simulator is exactly the kind of multi-output expression this minimiser is built to shrink.