4.4 Combinational Circuits: Adders, Decoders, Multiplexers & ALU

Theory: Combinational Circuits: Adders, Decoders, Multiplexers & ALU

So far we have treated Boolean functions on paper. Now we build them. A combinational circuit is a network of gates whose outputs depend only on the current inputs: apply new inputs and, after a tiny gate delay, the outputs settle to the new values. There is no memory. Combinational circuits are the “doing” part of a CPU: adders, comparators, decoders, multiplexers and the ALU (Null & Lobur, Ch. 3).

From Boolean Function to Gate Circuit

Every Boolean expression maps directly onto gates:

Expression part	Gate
each complemented variable $x'$	a NOT gate (inverter) on $x$
each product term	an AND gate with one input per literal
the sum of the terms	an OR gate with one input per term

Procedure (two-level AND-OR circuit from a sum of products):

1. Draw an inverter for each variable that appears complemented.
2. Draw one AND gate per product term (a single-literal term needs no AND).
3. Feed all product outputs into one OR gate; its output is $F$.

Because every gate costs area, power and delay, we simplify first (identities or a K-map) and then draw the circuit.

Mini-example (lecture)

$F(x, y, z) = x + y'z$: one inverter makes $y'$; one AND gate computes $y'z$; one OR gate combines $x$ with $y'z$. Three gates in total.

Half Adder

The simplest arithmetic circuit adds two bits $x$ and $y$. The result can be $0$, $1$ or $2 = 10_2$, so it needs two outputs: Sum and Carry.

$x$	$y$	Carry	Sum
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Reading the columns: Sum is 1 when the inputs differ → XOR; Carry is 1 only when both are 1 → AND.

$$\text{Sum} = x \oplus y, \qquad \text{Carry} = xy$$

So a half adder is just one XOR gate and one AND gate sharing the same two inputs.

Mini-example

$1 + 1$: Sum $= 1 \oplus 1 = 0$, Carry $= 1 \cdot 1 = 1$, i.e. $10_2 = 2$ ✓.

Full Adder

To add multi-bit numbers, every column except the rightmost must also add the carry coming in from the column to its right. A full adder adds three bits: $x$, $y$ and Carry In ($z$, or $C_{in}$).

$x$	$y$	$C_{in}$	Carry Out	Sum
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

As derived in 4.2:

$$\text{Sum} = x \oplus y \oplus C_{in}, \qquad C_{out} = xy + C_{in}(x \oplus y)$$

Construction (the lecture’s circuit) = two half adders plus an OR gate:

• Half adder 1 on $x, y$: produces $p = x \oplus y$ and $g = xy$.
• Half adder 2 on $p$ and $C_{in}$: produces Sum $= p \oplus C_{in}$ and $c_2 = p \cdot C_{in}$.
• OR gate: $C_{out} = g + c_2$.

Intuition for the carry: a carry goes out if $x$ and $y$ are both 1 (generate, $xy$), or if exactly one of them is 1 and a carry comes in (propagate, $C_{in}(x \oplus y)$).

Ripple-Carry Adder

Chain $n$ full adders, one per bit column, connecting each Carry Out to the next column’s Carry In. The rightmost column has no incoming carry, so its $C_{in} = 0$ (or a half adder is used there). The carry “ripples” from right to left, hence ripple-carry adder.

The ripple-carry adder is simple but slow for wide words: bit $n-1$ cannot produce its final sum until the carry has passed through all $n - 1$ adders before it. Faster designs (carry-lookahead, carry-select) compute carries in parallel.

Decoder

A decoder takes an $n$-bit binary number on its inputs and activates exactly one of its $2^n$ output lines: the one whose index equals the input value.

$$n \text{ inputs} \;\longrightarrow\; 2^n \text{ outputs}$$

Main use: memory address decoding. The binary address placed on the address lines of a memory bus goes into a decoder, and the single active output selects (enables) one memory location or one memory chip. Address decoders with $n$ inputs can select any of $2^n$ locations.

Inside a 2-to-4 decoder: two inverters make $x'$ and $y'$, and four AND gates each produce one minterm:

$x$	$y$	$x'y'$ (out 0)	$x'y$ (out 1)	$xy'$ (out 2)	$xy$ (out 3)
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

A decoder therefore generates all minterms of its inputs, which means any function can be built from a decoder plus one OR gate (Worked Example 6).

Mini-example (lecture)

In the 2-to-4 decoder, if $x = 0$ and $y = 1$, only the AND gate computing $x'y$ has both inputs at 1, so the $x'y$ output (output 1) is enabled.

Multiplexer (MUX)

A multiplexer does roughly the opposite of a decoder: it has many data input lines and one output, and the value on its control (select) lines chooses which input is passed to the output. Think of it as a digitally controlled rotary switch.

With $s$ select lines you can name $2^s$ inputs, so to select among $n$ inputs you need

$$s = \log_2 n \text{ control lines}$$

(From $n = 2^s$: $\log n = s \log 2$, so $s = \log n / \log 2 = \log_2 n$.)

Inside a 4-to-1 mux (inputs $I_0..I_3$, selects $S_1 S_0$): two inverters, four 3-input AND gates and one 4-input OR gate:

$$\text{Output} = S_1'S_0'I_0 + S_1'S_0I_1 + S_1S_0'I_2 + S_1S_0I_3$$

For any select value, exactly one AND gate has both of its select inputs at 1, so it passes its data input; the other three output 0, and the OR gate forwards the chosen bit.

$S_1$	$S_0$	Output
0	0	$I_0$
0	1	$I_1$
1	0	$I_2$
1	1	$I_3$

Mini-example (lecture)

If $S_0 = 1$ and $S_1 = 0$, the select value is $S_1S_0 = 01 = 1$, so input $I_1$ is transferred to the output.

A Simple 2-Bit ALU

The Arithmetic Logic Unit performs the CPU’s arithmetic and logic operations. The lecture’s ALU takes two 2-bit operands $A = A_1A_0$ and $B = B_1B_0$, two function-select (control) lines $f_1 f_0$, and produces a 2-bit result $C = C_1C_0$ plus an overflow (carry-out) signal.

$f_1 f_0$	Operation	Result $C$
00	ADD	arithmetic sum $A$ plus $B$ (2 bits + overflow)
01	OR	$C_i = A_i + B_i$ for each bit
10	NOT	$C_i = A_i'$ (each bit of $A$ complemented)
11	AND	$C_i = A_i B_i$ for each bit

How it is built (it combines everything on this page):

1. A 2-to-4 decoder on $f_1 f_0$ turns the operation code into four enable lines, exactly one active.
2. For each bit position, an AND gate, a NOT gate (on the $A$ bit) and an OR gate compute all the logic results in parallel.
3. The adder part: a half adder for bit 0 (no carry in) and a full adder for bit 1, with the carry from bit 0 feeding bit 1; the carry out of bit 1 is the overflow output.
4. Each result is ANDed with its decoder enable line, and an OR gate per bit merges them, so only the selected operation’s result reaches $C_1$ and $C_0$. (This AND-OR selection is a multiplexer in disguise.)

---

Worked Examples

Exercise 1

Draw (as a gate list) the AND-OR circuit for $F(x, y, z) = x'yz + xy'z + xyz$, then simplify $F$ and draw the simpler circuit. Compare the gate counts.

Show solution ↓Hide solution ↑

Solution

Original circuit:

• Inverters: $x'$, $y'$ → 2 NOT gates.
• AND gates (3-input): $a_1 = x'yz$, $a_2 = xy'z$, $a_3 = xyz$ → 3 AND gates.
• OR gate (3-input): $F = a_1 + a_2 + a_3$ → 1 OR gate.

Total 6 gates.

Simplify (K-map: 1s at m3, m5, m7):

$x \backslash yz$	00	01	11	10
0	0	0	1	0
1	0	1	1	0

• Group A: m3, m7 (column 11) → $yz$.
• Group B: m5, m7 (bottom row, columns 01 and 11) → $xz$.

$F = yz + xz = z(x + y)$ (Distributive).

Simplified circuit: one OR gate $x + y$, one AND gate $z(x + y)$ → 2 gates, no inverters.

Check: $z(x+y)$ is 1 when $z = 1$ and at least one of $x, y$ is 1: rows 011, 101, 111 = m3, m5, m7 ✓. Going from 6 gates to 2 is why we simplify before building.

Exercise 2

Trace the full adder (two XORs, two ANDs, one OR, as in the lecture circuit) for the inputs $x = 1$, $y = 1$, $C_{in} = 1$, and then for $x = 1$, $y = 0$, $C_{in} = 1$. Give every internal signal.

Show solution ↓Hide solution ↑

Solution

Internal signals: $p = x \oplus y$ (XOR 1), $g = xy$ (AND 1), Sum $= p \oplus C_{in}$ (XOR 2), $c_2 = p\,C_{in}$ (AND 2), $C_{out} = g + c_2$ (OR).

Signal	$x=1, y=1, C_{in}=1$	$x=1, y=0, C_{in}=1$
$p = x \oplus y$	$1 \oplus 1 = 0$	$1 \oplus 0 = 1$
$g = xy$	$1$	$0$
Sum $= p \oplus C_{in}$	$0 \oplus 1 = 1$	$1 \oplus 1 = 0$
$c_2 = p \cdot C_{in}$	$0$	$1$
$C_{out} = g + c_2$	$1 + 0 = 1$	$0 + 1 = 1$
result $C_{out}\,\text{Sum}$	$11_2 = 3$	$10_2 = 2$

Check against arithmetic: $1 + 1 + 1 = 3 = 11_2$ ✓ and $1 + 0 + 1 = 2 = 10_2$ ✓.

Note how the carry is produced differently: in the first case it is generated ($g = 1$, both bits 1); in the second it is propagated (one bit is 1 and the carry in passes through).

Exercise 3

A 4-bit ripple-carry adder computes $A + B$ with $A = 1011_2$ and $B = 0110_2$. Trace each full adder from bit 0 to bit 3, giving its inputs, Sum and Carry Out. What is the result, and does it fit in 4 bits?

Show solution ↓Hide solution ↑

Solution

Bit 0 has $C_{in} = 0$; each later stage takes the previous stage’s carry out.

Stage	$A_i$	$B_i$	$C_{in}$	$A_i + B_i + C_{in}$	Sum $S_i$	$C_{out}$
bit 0	1	0	0	1	1	0
bit 1	1	1	0	2	0	1
bit 2	0	1	1	2	0	1
bit 3	1	0	1	2	0	1

Reading the sums from bit 3 down: $S_3S_2S_1S_0 = 0001$, with final carry $C_4 = 1$. The full result is $1\,0001_2 = 17$.

Check: $1011_2 = 11$, $0110_2 = 6$, $11 + 6 = 17 = 10001_2$ ✓.

As an unsigned 4-bit number the answer does not fit (max 15): the carry out $C_4 = 1$ signals this. Notice the carry rippling: stage 1 had to wait for stage 0’s carry (0), stage 2 for stage 1’s (1), and stage 3 for stage 2’s (1).

Exercise 4

(a) How many inputs does a decoder with 16 outputs have? How many outputs does a decoder with 10 inputs have?

(b) A 32-word memory is built from 8 chips of 4 words each, and addresses are 5 bits $A_4A_3A_2A_1A_0$. A decoder chooses the chip. Which bits go to the decoder, what size is it, and which chip and which word inside it does address $10110_2$ select?

Show solution ↓Hide solution ↑

Solution

(a) $n$ inputs give $2^n$ outputs.

• $2^n = 16 \Rightarrow n = \log_2 16 = 4$ inputs (a 4-to-16 decoder).
• 10 inputs → $2^{10} = 1024$ outputs (a 10-to-1024 decoder, enough to select any of 1024 memory locations).

(b) 8 chips need $\log_2 8 = 3$ bits to pick a chip, and 4 words per chip need $\log_2 4 = 2$ bits to pick a word. Use the high bits for the chip:

• $A_4A_3A_2$ → a 3-to-8 decoder; each of its 8 outputs enables one chip.
• $A_1A_0$ → go to all chips and select the word within the enabled chip.

Address $10110_2$: $A_4A_3A_2 = 101_2 = 5$ → decoder output 5 is active → chip 5 is enabled. $A_1A_0 = 10_2 = 2$ → word 2 of chip 5.

Check: chip 5 holds addresses $5 \times 4 = 20$ to $23$; word 2 is address $22 = 10110_2$ ✓.

Exercise 5

A 4-to-1 multiplexer has data inputs $I_3I_2I_1I_0 = 1001$.

(a) Using the internal equation, find the output when $S_1 = 0$, $S_0 = 1$.

(b) Give the output for all four select values.

(c) How many select lines does an 8-input mux need? A 32-input mux?

Show solution ↓Hide solution ↑

Solution

$I_3 = 1$, $I_2 = 0$, $I_1 = 0$, $I_0 = 1$.

(a) $\text{Output} = S_1'S_0'I_0 + S_1'S_0I_1 + S_1S_0'I_2 + S_1S_0I_3$ with $S_1 = 0$, $S_0 = 1$ (so $S_1' = 1$, $S_0' = 0$):

AND gate	Select factors	Data	Gate output
$S_1'S_0'I_0$	$1 \cdot 0$	1	0
$S_1'S_0I_1$	$1 \cdot 1$	0	0 (this is the selected gate)
$S_1S_0'I_2$	$0 \cdot 0$	0	0
$S_1S_0I_3$	$0 \cdot 1$	1	0

Output $= 0 + 0 + 0 + 0 = 0$, which is $I_1$ ✓.

(b)

$S_1S_0$	selected input	Output
00	$I_0$	1
01	$I_1$	0
10	$I_2$	0
11	$I_3$	1

(c) Select lines $= \log_2(\text{inputs})$: $\log_2 8 = 3$; $\log_2 32 = 5$.

Exercise 6

Implement a full adder using a 3-to-8 decoder and OR gates.

Show solution ↓Hide solution ↑

Solution

Feed $x, y, C_{in}$ into the decoder (as a 3-bit number, $x$ the most significant bit). Output $D_k$ is active exactly when the input equals $k$, i.e. $D_k$ is minterm $m_k$.

From the full adder table (4.2): Sum $= \Sigma m(1, 2, 4, 7)$ and $C_{out} = \Sigma m(3, 5, 6, 7)$. So:

$$\text{Sum} = D_1 + D_2 + D_4 + D_7, \qquad C_{out} = D_3 + D_5 + D_6 + D_7$$

Hardware: one 3-to-8 decoder and two 4-input OR gates ($D_0$ is unused).

Check with $x y C_{in} = 110$ (= 6): only $D_6$ is 1. Sum $= 0$ (6 is not in its list), $C_{out} = 1$ (6 is in its list) → $10_2 = 2 = 1 + 1 + 0$ ✓.

Exercise 7

For the lecture’s 2-bit ALU ($f_1f_0$: 00 ADD, 01 OR, 10 NOT, 11 AND), give the output $C_1C_0$ (and the overflow/carry-out) for:

(a) $A = 01$, $B = 10$ under each of the four operations.

(b) $A = 11$, $B = 01$ with $f_1f_0 = 00$.

Show solution ↓Hide solution ↑

Solution

(a) $A_1A_0 = 01$, $B_1B_0 = 10$. The decoder activates exactly one enable line; the others force their results to 0 before the per-bit OR.

$f_1f_0$	Active operation	bit 1	bit 0	$C_1C_0$	overflow
11	AND	$0 \cdot 1 = 0$	$1 \cdot 0 = 0$	00	0
01	OR	$0 + 1 = 1$	$1 + 0 = 1$	11	0
10	NOT $A$	$0' = 1$	$1' = 0$	10	0
00	ADD	see below		11	0

ADD: bit 0 half adder: $A_0 + B_0 = 1 + 0$ → sum 1, carry 0. Bit 1 full adder: $A_1 + B_1 + c = 0 + 1 + 0$ → sum 1, carry out 0. Result $11_2 = 3 = 1 + 2$ ✓.

(b) $A = 11$, $B = 01$, ADD:

• Bit 0 (half adder): $1 + 1$ → $C_0 = 1 \oplus 1 = 0$, carry $= 1 \cdot 1 = 1$.
• Bit 1 (full adder): $1 + 0 + 1$ → $C_1 = 1 \oplus 0 \oplus 1 = 0$, carry out $= 1\cdot0 + 1\cdot(1 \oplus 0) = 1$.

$C_1C_0 = 00$ with overflow = 1. The true sum $3 + 1 = 4 = 100_2$ needs 3 bits; the 2-bit result has wrapped around and the overflow line warns the CPU.