Combinational Circuits: Adders, Multiplexers and Decoders Explained
A combinational circuit is one whose outputs depend only on the present inputs. It has no memory and no clock. Adders, multiplexers, decoders, encoders and comparators all fall in this class, and together they make up the datapath of every processor. In this tutorial you will design a full adder from its truth table, see why ripple-carry adders are slow and how carry look-ahead fixes that, and learn two powerful tricks: implementing any Boolean function with a multiplexer, and implementing several functions at once with a decoder.
Half Adder and Full Adder
A half adder adds two bits and produces a sum and a carry: S = A XOR B and C = AB. It cannot accept a carry from a previous stage, so for multi-bit addition you need a full adder, which adds three bits: A, B and the incoming carry Cin.
Full adder truth table A B Cin | S Cout --------+------- 0 0 0 | 0 0 0 0 1 | 1 0 0 1 0 | 1 0 0 1 1 | 0 1 1 0 0 | 1 0 1 0 1 | 0 1 1 1 0 | 0 1 1 1 1 | 1 1 S = A XOR B XOR Cin = Σm(1, 2, 4, 7) Cout = AB + Cin(A XOR B) = Σm(3, 5, 6, 7)
Notice that the sum is 1 whenever an odd number of inputs are 1, which is exactly a three-input XOR. The carry is a majority function. A full adder is commonly built from two half adders and an OR gate: the first half adder produces A XOR B and AB, the second adds Cin, and the OR combines the two carries.
Ripple-carry adder and adder-subtractor
Chaining n full adders, with each Cout feeding the next Cin, gives an n-bit ripple-carry adder. The 74283 is a 4-bit binary adder in one IC. To make it subtract, pass each B bit through an XOR gate controlled by a mode line M, and connect M to the first carry input. When M = 0 the circuit computes A + B. When M = 1 every B bit is inverted and 1 is added, which forms the 2's complement, so the circuit computes A - B.
Example: 4-bit, M = 1, A = 0110 (6), B = 0010 (2) B XOR 1111 = 1101, Cin = 1 0110 + 1101 + 1 ------ 1 0100 -> discard carry -> 0100 = 4 correct
Why Ripple Carry Is Slow: Carry Look-Ahead
In a ripple adder the carry must pass through every stage before the most significant sum is valid, so the worst-case delay grows linearly with the number of bits. A 32-bit ripple adder can have 32 carry delays in its critical path. Carry look-ahead (CLA) computes all carries in parallel using two signals per bit: generate G = AB, meaning this bit produces a carry by itself, and propagate P = A XOR B, meaning it passes an incoming carry through.
C(i+1) = Gi + Pi.Ci C1 = G0 + P0.C0 C2 = G1 + P1.G0 + P1.P0.C0 C3 = G2 + P2.G1 + P2.P1.G0 + P2.P1.P0.C0 C4 = G3 + P3.G2 + P3.P2.G1 + P3.P2.P1.G0 + P3.P2.P1.P0.C0 Each carry is a two-level AND-OR expression of the inputs, so all carries settle after roughly the same fixed delay.
The cost is gate count and fan-in, which grow quickly with width, so practical designs use 4-bit look-ahead blocks combined hierarchically. The 74182 was a look-ahead carry generator IC used this way with 74181 ALUs. FPGAs take a different approach and include dedicated fast carry chains in their logic blocks.
Multiplexers and Function Implementation
A multiplexer (MUX) selects one of 2^n data inputs and routes it to a single output, controlled by n select lines. A 4:1 MUX has the expression Y = S1'S0'I0 + S1'S0 I1 + S1 S0' I2 + S1 S0 I3. Common ICs include the 74151 (8:1) and the 74153 (dual 4:1). Because a MUX contains every minterm of its select lines, it can implement any function.
Worked example: F(A, B, C) = Σm(1, 2, 6, 7) with a 4:1 MUX
Use A, B as select lines; express each data input in terms of C. A B | rows (C=0, C=1) | F values | Data input ----+-----------------+----------+----------- 0 0 | m0, m1 | 0, 1 | I0 = C 0 1 | m2, m3 | 1, 0 | I1 = C' 1 0 | m4, m5 | 0, 0 | I2 = 0 1 1 | m6, m7 | 1, 1 | I3 = 1 A 3-variable function with one 4:1 MUX and one inverter.
This method generalises: an n-variable function needs only a 2^(n-1):1 multiplexer, with the remaining variable or its complement, 0 or 1 on each data input. The reverse device, a demultiplexer, routes one input to one of many outputs and is essentially a decoder with an enable input.
Decoders and Encoders
An n-to-2^n decoder activates exactly one output for each input combination, so each output is one minterm. The 74138 is a 3-to-8 decoder with active-low outputs and three enable inputs (G1 active high, G2A and G2B active low). It is widely used for memory and I/O address decoding, where it selects one chip out of eight.
Since each output is a minterm, a decoder plus OR gates implements any set of functions of the same inputs. With active-low outputs, use NAND gates instead of OR gates. For the full adder: S = NAND(Y1, Y2, Y4, Y7) and Cout = NAND(Y3, Y5, Y6, Y7), using one 74138 and two 4-input NAND gates from a 7420.
An encoder does the opposite: it converts one active input line into a binary code. A plain encoder gives wrong outputs if two inputs are active together, so practical designs use a priority encoder such as the 74148 (8-to-3), which outputs the code of the highest-numbered active input. Keyboard scanning and interrupt controllers use this idea.
Common Mistakes
- Forgetting to enable the 74138: G1 must be high and both G2A and G2B low, otherwise all outputs stay high.
- Using OR gates on active-low decoder outputs. Use NAND to combine active-low minterms.
- Ignoring the carry-out when using an adder-subtractor for signed numbers. Use the overflow rule, not the carry, for signed results.
- Swapping the select line order when building a MUX implementation, which permutes the data inputs.
Summary
Full adders compute S = A XOR B XOR Cin and a majority carry, and a chain of them forms a ripple adder that becomes a subtractor with an XOR stage. Carry look-ahead trades extra gates for speed using generate and propagate terms. Multiplexers implement any function by putting the leftover variable on their data inputs, and decoders produce all minterms so several functions can share one chip. These blocks, combined with the flip-flops in the next lesson, form complete digital systems.