Question 6 of 6: Fundamentals: gates, circuit classes, state machines and counters

Question 6 (12 marks) — Fundamentals: gates, circuit classes, state machines and counters

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

This question is descriptive, and the marks reward precision about definitions rather than calculation. Each part is answered in turn.

(a) The three basic gates, and single-gate universality [3 pts]

The three basic logic gates are AND, OR and NOT. They are basic in the precise sense that they implement the three operations of Boolean algebra — conjunction, disjunction and complementation — and every switching function can be written in sum-of-products or product-of-sums form using only those three.

It is possible to realise any combinational function with a single gate type, provided that type is NAND or NOR. Such a gate is called functionally complete or universal. The proof is constructive: it suffices to build the three basic gates out of the candidate. Using NAND, and writing $\uparrow$ for the NAND operation,

The NOR construction is the exact dual, obtained by exchanging AND with OR throughout. Since AND, OR and NOT can each be built from NAND alone, and every function can be built from AND, OR and NOT, every function can be built from NAND alone — and likewise from NOR alone. This is not merely a curiosity: it is why logic families are manufactured predominantly as NAND and NOR parts, and it is exactly the property Question 1(d) exploited when that function was realised in four NOR gates.

Note that AND, OR and XOR are not universal on their own, because none of them can produce a complement: with all inputs held at 1 each of those gates outputs 1, so no combination can ever generate the constant-0 or the inverting behaviour that complementation requires.

(b) Combinational versus sequential circuits [3 pts]

The main difference is memory. In a combinational circuit the outputs at any instant are a function of the present inputs alone, so the circuit has no history and its behaviour is fully described by a truth table:

A sequential circuit adds a set of state variables $S$ held in latches or flip-flops and fed back into the input logic. The same input pattern applied at two different times can therefore produce two different outputs, depending on what has happened before. Structurally, the tell-tale sign is a feedback path from an output back to the input logic, usually broken by a storage element; a combinational circuit's signal flow is strictly from inputs to outputs with no loops. Consequentially, combinational circuits are specified by truth tables and characterised by propagation delay, whereas sequential circuits are specified by state tables and diagrams and are additionally constrained by setup and hold times.

(c) Finite state machines, and counters as a special case [3 pts]

A finite state machine is a sequential circuit that can occupy only a finite number of distinct states, together with a next-state function that maps the present state and input to the next state, and an output function. Formally it is the tuple $(S, X, Z, g, f)$ with a finite state set $S$, input alphabet $X$, output alphabet $Z$, next-state function $S^{+} = g(X,S)$ and output function $Z = f(S)$ for a Moore machine or $Z = f(X,S)$ for a Mealy machine — exactly the structure analysed in Question 3.

A counter is a special case of a finite state machine. An $n$-bit counter has $2^{n}$ possible states held in its flip-flops, and its next-state function is the fixed rule “advance to the next value in the count sequence”. It qualifies as an FSM in every respect; what makes it a special case is that its state graph is a single closed ring traversed in a fixed order, and that its output is normally just the state variables themselves, taken straight off the flip-flop outputs with no output decoding. It is therefore a Moore machine whose output function is the identity. A general FSM is less constrained: its state graph may branch on the input, as the Question 3 machine does when $I$ selects between two different three-state rings.

(d) Synchronous versus asynchronous counters [3 pts]

In a synchronous counter every flip-flop is driven by the same clock signal, and the count sequence is produced by combinational logic on the J/K or D inputs, as in Question 2. All the outputs therefore change together, within one clock-to-output delay of the common edge.

In an asynchronous or ripple counter, only the first flip-flop receives the external clock; each subsequent stage is clocked by the output of the stage before it. The transition therefore ripples along the chain, and the worst-case settling time accumulates:

The practical consequences are that a ripple counter is simpler — it needs no steering logic at all — but is slower for a given width and, more seriously, passes through transient false counts while the ripple propagates, so its outputs must not be decoded combinationally without gating. A synchronous counter avoids both problems at the cost of the extra gates.

How to identify which is which: look at the clock inputs on the schematic. If every flip-flop clock pin is connected to the same common CLK net, the counter is synchronous; if a flip-flop's clock pin is driven by the $Q$ or $\overline{Q}$ output of a neighbouring stage, it is asynchronous. A secondary tell is the presence of steering logic: a synchronous counter has AND gates feeding the J/K inputs, whereas in a ripple counter those inputs are usually tied permanently to 1.