Combinational Circuits

A circuit is combinational when its output depends only on its present inputs, with no memory of what came before. That single restriction means every combinational circuit is exactly a truth table, and the named blocks — adders, decoders, multiplexers — are simply truth tables that turned out to be worth building once and reusing everywhere.

So the productive way to reason about a block is to ask what its table says, not to trace its internal gates. A 4-to-1 multiplexer selects one of four inputs; whether it is built from AND-OR logic or transmission gates changes nothing about how it behaves in a larger circuit.

The second organising fact is that two costs matter and they trade against each other: gate count and propagation delay. The ripple-carry adder and the carry-lookahead adder compute the same function; one is small and slow, the other large and fast. Almost every design question in this chapter is a point on that trade-off.

The third is that delay is not merely a performance concern. Unequal path delays inside a circuit produce hazards — momentary wrong outputs — and the fix is to add logic that is functionally redundant but temporally necessary.

1. Adders

The half adder adds two bits and produces a sum and a carry.

$S=A\oplus BC=A\cdot B$

It cannot accept a carry from a lower position, which is why it is only ever used in the least significant stage, and often not even there.

The full adder accepts three inputs — two operand bits and a carry in.

$S=A\oplus B\oplus C_{in}{C}_{out}=AB+C_{in}(A\oplus B)$

The sum is the parity of the three inputs and the carry is the majority of them, which is the fastest way to remember both and to verify an answer.

A full adder can be built from two half adders plus one OR gate, which is a standard question: the first half adder combines $A$ and $B$, the second combines that partial sum with $C_{in}$, and the OR merges the two carries.

A subtractor is not a separate circuit. Two's complement arithmetic turns $A-B$ into $A+\overline{B}+1$, so an adder with XOR gates on the $B$ inputs and the carry-in tied to the same control line performs both operations: control 0 gives addition and control 1 gives subtraction.

That works because $B\oplus 0=B$ and $B\oplus 1=\overline{B}$, making the XOR a controlled inverter.

2. Carry Propagation

Chaining $n$ full adders gives a ripple-carry adder, in which each stage waits for the carry from the stage below.

The delay is proportional to $n$, since the carry must ripple through every stage. With each full adder contributing two gate delays on the carry path, an $n$-bit ripple-carry adder settles after about $2n$ gate delays.

The carry-lookahead adder removes the dependence by computing all carries directly from the inputs. Each bit position produces two signals:

$G_i=A_i{B}_i{P}_i=A_i\oplus B_i$

Generate means this position produces a carry regardless of what arrives; propagate means it passes along whatever arrives.

The carry recurrence unrolls into a flat expression:

$C_{i+1}=G_i+P_i{C}_i$

Expanding it gives $C_{i+1}$ purely in terms of the $G$ and $P$ signals and $C_0$, with no chaining. Every carry is then available after two gate delays — one for the AND terms and one for the OR.

The cost is fan-in. The expression for a high-order carry has many terms, and gate fan-in is bounded in real hardware, so lookahead is applied in blocks of four and the blocks are themselves chained or looked ahead over. That is why practical adders are hierarchical rather than flat.

The carry-select adder takes a different route: compute each block twice, once assuming a carry-in of 0 and once assuming 1, then select the right answer when the actual carry arrives. It buys speed with area rather than with fan-in.

3. Comparators and Parity

A magnitude comparator produces three outputs: greater than, equal to, and less than.

Equality is the exclusive-NOR of every bit pair, ANDed together, since two numbers are equal exactly when they agree in every position.

For magnitude, the comparison proceeds from the most significant bit downward: the first position where the numbers differ decides the result, and all lower positions are irrelevant. That is why a comparator's high-order logic dominates its delay.

A parity generator is a chain of XOR gates producing 1 when the number of 1s is odd. Even parity appends a bit making the total number of 1s even; odd parity makes it odd.

The checker is the same circuit applied to the transmitted word including its parity bit, and a non-zero result signals an error. A single parity bit detects any odd number of bit errors and no even number, which is why it detects single errors and misses double ones.

4. Decoders and Encoders

An $n$-to-$2^n$ decoder asserts exactly one of its $2^n$ outputs, selected by the $n$ input lines.

Each output of a decoder is a minterm, which is why a decoder plus an OR gate implements any function directly: OR together the outputs corresponding to the function's minterms.

An enable input allows decoders to be cascaded. A 3-to-8 decoder can be built from two 2-to-4 decoders with the third input driving the enables, and larger structures follow the same pattern.

An encoder does the reverse, producing the binary index of an asserted input. A plain encoder misbehaves when two inputs are asserted at once, because it effectively ORs the two codes and produces a third, meaningless value.

A priority encoder fixes this by defining a precedence, outputting the index of the highest-priority asserted input and typically supplying a valid bit to distinguish "no input asserted" from "input zero asserted".

That valid output matters: without it, an all-zero output is ambiguous between the two cases, which is exactly the distinction interrupt-controller questions turn on.

5. Multiplexers

A $2^n$-to-1 multiplexer routes one of $2^n$ data inputs to the output, chosen by $n$ select lines. A demultiplexer does the reverse, routing one input to one of several outputs.

A multiplexer with $n$ select lines implements any function of $n$ variables directly: connect the variables to the select lines and wire each data input to the constant 0 or 1 that the truth table requires.

The more useful result is the one that halves the size. A multiplexer with $n$ select lines can implement any function of $n+1$ variables. Connect $n$ variables to the select lines, and connect each data input to one of $0$, $1$, the remaining variable, or its complement.

The reason is that fixing the $n$ select variables leaves a function of one remaining variable, and a one-variable function can only be one of those four things.

For an example on three variables using a 4-to-1 multiplexer: put $A$ and $B$ on the selects, then for each of the four combinations examine the two rows of the truth table that share it and read off whether the output equals 0, 1, $C$ or $\overline{C}$.

A demultiplexer with its data input tied to 1 behaves exactly like a decoder, which is why the two are often the same physical part.

6. Programmable Logic

Programmable devices implement sum-of-products expressions with an AND plane feeding an OR plane, and they differ in which planes are programmable.

A PROM generates every minterm, so it wastes hardware on a sparse function but requires no minimisation at all. Its AND plane is a full decoder, so an $n$-input PROM has $2^n$ product lines whether they are needed or not.

A PLA is the most flexible and the most expensive, since both planes are programmable and product terms can be shared between several outputs. Sharing is the point: a term appearing in three output functions is implemented once.

A PAL sacrifices OR-plane flexibility for speed and cost. Each output has a fixed number of product terms available to it, so a function needing more terms than the part provides simply does not fit, and no sharing across outputs is possible.

The examinable consequence is a sizing question: given a set of functions, count the distinct product terms to size a PLA, and check the per-output term count to see whether a PAL suffices.

7. Hazards

A hazard is a momentary incorrect output caused by unequal delays along different paths, even though the circuit is logically correct.

A static-1 hazard occurs when an output that should remain at 1 momentarily dips to 0 during an input change. A static-0 hazard is the mirror case. A dynamic hazard is an output that changes more than once when it should change only once.

The cause is always the same shape. Two adjacent K-map groups cover the two input states involved, but no single group covers both, so during the transition one term switches off slightly before the other switches on.

The fix is to add a redundant product term covering the boundary between the two groups. That term is logically unnecessary — the function is unchanged — but it holds the output steady during the transition.

This is precisely the consensus term from Boolean algebra, and it is why consensus terms are deliberately reintroduced in hazard-free design after minimisation removed them.

Hazards matter only in circuits where the momentary glitch is observed. In a synchronous design where outputs are sampled only at a clock edge, a glitch that settles before the edge is harmless, which is one of the main arguments for synchronous design.

8. Worked Examples

Example 1. How many gate delays does an 8-bit ripple-carry adder take to settle, and how does a carry-lookahead adder compare?

In a ripple-carry adder each full adder produces its carry-out two gate levels after its carry-in arrives: one level for the AND terms and one for the OR.

With 8 stages, the final carry emerges after $2\times 8=16$ gate delays, and the most significant sum bit needs one more XOR level, so about 17 in total.

A carry-lookahead adder computes all $G_i$ and $P_i$ in one gate delay, since each is a single AND or XOR of the inputs.

Every carry is then a two-level sum-of-products in those signals, adding two more delays, so all carries are available after about 3 gate delays regardless of width. The sum bits need one further XOR.

The comparison is 17 delays against roughly 4, and the difference grows linearly with width — which is exactly why lookahead exists.

The price is fan-in: the expression for $C_8$ contains nine product terms, one with nine literals, which no real gate provides. This forces the hierarchical block structure used in practice.

Example 2. Implement $F(A,B,C)=\sum m(0,2,3,5)$ using a 4-to-1 multiplexer.

A 4-to-1 multiplexer has two select lines, so it can implement a 3-variable function using the $n+1$ rule.

Put $A$ and $B$ on the select lines, leaving $C$ as the residue variable.

Now examine each select combination against the truth table.

$AB=00$ covers minterms 0 and 1. Minterm 0 is in the list and 1 is not, so the output is 1 when $C=0$ and 0 when $C=1$. That is $\overline{C}$.

$AB=01$ covers minterms 2 and 3. Both are in the list, so the output is 1 regardless of $C$. That is the constant 1.

$AB=10$ covers minterms 4 and 5. Only 5 is in the list, and 5 has $C=1$, so the output equals $C$.

$AB=11$ covers minterms 6 and 7. Neither is in the list, so the output is the constant 0.

Wire the four data inputs to $\overline{C}$, 1, $C$ and 0 respectively.

Note that the select lines must be connected in the right order: $A$ to the more significant select and $B$ to the less significant, matching how the minterm indices were formed.

Example 3. A combinational circuit implements $F=AB+\overline{A}C$. Identify the hazard and remove it.

Consider the input transition where $B=C=1$ and $A$ changes from 1 to 0.

Before the change, $A=1$ makes the term $AB$ equal to 1, so $F=1$. After the change, $A=0$ makes $\overline{A}C$ equal to 1, so $F=1$ again. The output should hold steady at 1.

But the two terms depend on $A$ through different paths. The term $\overline{A}C$ waits for the inverter on $A$, while $AB$ responds to $A$ directly. So $AB$ falls before $\overline{A}C$ rises, and the output dips to 0 for the duration of the inverter delay.

That is a static-1 hazard.

The fix is to add the consensus term $BC$, giving $F=AB+\overline{A}C+BC$.

The added term does not change the function — consensus terms are always redundant — but during the transition $B=C=1$ holds $BC$ at 1 throughout, so the output never falls.

On the K-map, the two original groups are adjacent but not overlapping, and $BC$ is precisely the group that bridges the boundary between them.

Example 4. How many 2-to-4 decoders with enable are needed to build a 4-to-16 decoder?

A 4-to-16 decoder has 16 outputs, and each 2-to-4 decoder supplies 4, so at least 4 decoders are needed for the outputs.

Those four must be selected between, one at a time, which requires a decoder driving their enable inputs. The two high-order address bits select which group of four is active, so a fifth 2-to-4 decoder drives the four enables.

The two low-order bits go to the data inputs of all four output decoders in parallel.

The total is 5 decoders.

The general pattern is worth extracting: building a larger decoder from smaller ones needs one extra decoder as the enable driver at each level, which is the same recursive structure that appears in memory address decoding.

Example 5. A set of four Boolean functions of five variables shares 12 distinct product terms among them, with the largest single function needing 5 terms. Would a PAL with 4 product terms per output suffice, and what does a PLA require?

The PAL question is decided per output, not in total. Its OR plane is fixed, so each output has a fixed allocation of product terms and nothing can be borrowed from another output.

The largest function needs 5 terms and the part supplies 4, so it does not fit. The function would have to be split across two outputs and recombined externally, or a larger PAL chosen.

The PLA question is decided in total, because its programmable OR plane lets any product term feed any output. Twelve distinct terms are needed, so a PLA with at least 12 product lines and at least 5 inputs and 4 outputs suffices.

The comparison is the whole point of the device family: a PLA sizes on distinct terms across all outputs, a PAL sizes on the worst single output, and a PROM ignores both and simply provides all 32 minterms of a 5-variable input.

Example 6. Show that a full adder can be built from two half adders and one OR gate, and verify the carry expression.

The first half adder takes $A$ and $B$, producing $S_1=A\oplus B$ and $C_1=AB$.

The second half adder takes $S_1$ and $C_{in}$, producing $S_2=S_1\oplus C_{in}=A\oplus B\oplus C_{in}$, which is the required sum, and $C_2=S_1{C}_{in}=(A\oplus B)C_{in}$.

The final carry is $C_{out}=C_1+C_2=AB+(A\oplus B)C_{in}$, produced by one OR gate.

Verify this equals the majority function. When exactly two of the three inputs are 1, the sum should be 0 and the carry 1.

Take $A=1$, $B=1$, $C_{in}=0$: $AB=1$ so $C_{out}=1$, and $A\oplus B\oplus C_{in}=0$. Correct.

Take $A=1$, $B=0$, $C_{in}=1$: $AB=0$ but $A\oplus B=1$ so $C_2=1$ and $C_{out}=1$, with sum $=0$. Correct.

The structure also explains the two-gate-delay carry path that sets the ripple-carry adder's timing: the carry passes through one AND and one OR at each stage.

Summary

A combinational circuit is a truth table, so reason about a block from what it does rather than from how it is built.

The half adder gives sum as XOR and carry as AND; the full adder gives sum as the parity and carry as the majority of its three inputs.

A subtractor is an adder with XOR controlled inverters on one operand and the same control tied to the carry-in.

Ripple carry costs about $2n$ gate delays. Carry lookahead computes generate and propagate signals and produces every carry in constant depth, at the price of fan-in, which is why practical adders are hierarchical.

Equality is the XNOR of every bit pair ANDed together; magnitude comparison is decided by the highest differing bit.

Each decoder output is a minterm, so a decoder plus an OR gate implements any function. Enable inputs allow cascading, and a larger decoder needs one extra decoder to drive the enables.

A plain encoder breaks on simultaneous inputs; a priority encoder resolves them and needs a valid bit to distinguish no input from input zero.

A multiplexer with $n$ select lines implements any function of $n+1$ variables, with each data input tied to 0, 1, the residue variable, or its complement.

PROM has a fixed AND plane, PAL a fixed OR plane, and PLA neither. A PLA sizes on distinct terms overall; a PAL sizes on the worst single output.

Hazards come from unequal path delays; the cure is the redundant consensus term bridging two adjacent K-map groups, and in a synchronous design a glitch that settles before the clock edge is harmless.