Chapter 4: Combinational Logic Circuits

Source files used: ELEC205 Week 3 slides (slides 40-46), Week 5 slides (slides 16-44), Week 6 slides; textbook Chapter 4 as support. No worked examples are included.

1. Big Picture

Chapter 4 is the standard “plays” built from gates: adders, decoders, encoders, multiplexers.

Chapters 2 and 3 asked: how do we build and minimize one function? Chapter 4 asks: what are the reusable building blocks, and how do we design any function with them?

$$\boxed{\text{Analyze or design a combinational circuit using XOR, adders, decoders, encoders and MUXes.}}$$

New ideas in this chapter:

• XOR/XNOR as odd/even functions and parity,
• half adder, full adder, ripple-carry adder,
• 2’s complement adder/subtractor and overflow detection,
• decoders (and implementing functions with them),
• encoders and priority encoders,
• multiplexers (and implementing functions with them), demultiplexers.

Erzin groups the blocks by job: decoding, encoding, selecting.

---

2. Core Ideas

2.1 Analysis vs Design

Analysis: given a circuit, find what it does.

• exhaustive (truth table),
• algebraic (expressions),
• simulation / test bench (HDL description, test vectors, compare with a known-good model).

Design: given a specification, build the circuit. Either write the equations directly from “logic”, or brute-force it: truth table → canonical sum → minimize (Chapter 3).

---

2.2 XOR: The Odd Function

$X\oplus Y$ is 1 when the inputs differ. A multi-input XOR is 1 when an odd number of inputs are 1 (sum modulo 2). XNOR is the even function.

The K-map of a 3- or 4-input XOR is a checkerboard: no two 1’s are adjacent, so it cannot be simplified as SOP. That is why XOR gets its own gate.

---

2.3 Parity

Multi-input XOR computes parity. A chain of 2-input XORs works but has a long delay line. A parity tree (balanced XOR tree) gives the same result with less delay.

---

2.4 Building Wide Adders

A 32-bit adder is a 64-input, 33-output combinational system. Its truth table is impossible to write, so it is built from 1-bit cells: a half adder (or a full adder with $C_{in}=0$) at bit 0 and full adders above, with each carry feeding the next stage. Two 32-bit adders cascade into a 64-bit adder by connecting $C_{out}$ of the low half to $C_{in}$ of the high half.

---

2.5 Subtraction with an Adder

In 2’s complement, $A-B=A+(-B)=A+B'+1$. Invert every bit of $B$ and set the LSB carry-in to 1. No separate subtractor is needed.

---

2.6 Decoders

A decoder maps an $n$-bit code to $2^n$ output lines. With enable on, exactly one output is 1: output $k$ is minterm $m_k$ of the inputs. With enable off, all outputs are 0.

Applications: selecting memory banks or I/O devices, instruction decoding, memory row selection, seven-segment (4-to-7) decoding.

---

2.7 Encoders and Priority

An encoder is the reverse of a decoder: $2^n$ inputs to an $n$-bit code. A plain encoder assumes exactly one input is active. If two inputs are active, or none, it gives a wrong or ambiguous code.

A priority encoder fixes this: the highest-priority active input wins, lower inputs become don’t-cares, and a valid output $V$ says whether any input is active.

---

2.8 Multiplexers

A MUX selects one of many inputs and sends it to a single output. With $n$ select bits it has $2^n$ data inputs ($2^n$-to-1 MUX). A demultiplexer (DMUX) is the inverse: one input routed to one of $2^n$ outputs. A 1-to-4 DMUX is the same circuit as a 2-to-4 decoder with enable, with the enable used as the data input.

---

3. Main Governing Equations and Formulas

3.1 XOR Identities

$$X\oplus Y=XY'+X'Y$$ $$X\oplus0=X\qquad X\oplus1=X'\qquad X\oplus X=0$$ $$X\oplus Y=Y\oplus X\qquad (X\oplus Y)\oplus Z=X\oplus(Y\oplus Z)=X\oplus Y\oplus Z$$

$X\oplus1=X'$ is why an XOR works as a controlled inverter (used in the adder/subtractor).

---

3.2 XOR with Four NAND Gates

$$F=\big[((XY)'\cdot X)'\cdot((XY)'\cdot Y)'\big]'=XY'+X'Y$$

One shared NAND makes $(XY)'$, two NANDs combine it with $X$ and $Y$, one output NAND.

---

3.3 Half Adder

$$S=A\oplus B,\qquad C=AB$$

Adds two bits with no carry-in. One XOR and one AND.

---

3.4 Full Adder

$$S=A\oplus B\oplus C_{in}$$ $$C_o=AB+C_{in}(A\oplus B)$$

Built from two half adders plus an OR gate: the first HA makes $A\oplus B$ and $AB$, the second adds $C_{in}$, the OR combines the two carries.

---

3.5 Ripple-Carry Adder

$$S_i=A_i\oplus B_i\oplus C_i,\qquad C_{i+1}=A_iB_i+C_i(A_i\oplus B_i)$$

Bit 0 is on the right; the carry ripples right to left. $n$ full adders make an $n$-bit adder, and the final carry is $C_n$.

---

3.6 Adder/Subtractor

Each $B_i$ passes through an XOR with a control line $S$; $S$ also drives $C_0$:

$$B_i^{*}=B_i\oplus S,\qquad C_0=S$$ $$S=0:\ A+B\qquad\qquad S=1:\ A+B'+1=A-B$$

Use for any “add or subtract with one circuit” question (slide Fig. 3-31).

---

3.7 Overflow Detection

For an $n$-bit 2’s complement adder/subtractor:

$$V=C_n\oplus C_{n-1}$$

where $C_n$ is the carry out of the MSB and $C_{n-1}$ is the carry into the MSB. $V=1$ means overflow.

Slide examples (4 bits, range $[-8,7]$): $+5+7$ has carries $0111$, so $C_4\oplus C_3=1$: overflow. $-4-6$ has carries $1000$: overflow. $+5+2$ and $-4-3$ have equal last two carries: no overflow.

$C$ (the carry out itself) is the overflow indicator for unsigned numbers; $V$ is the one for signed numbers.

---

3.8 Decoder Outputs

For a 2-to-4 decoder with enable $EN$:

$$D_0=I_1'I_0'\,EN,\quad D_1=I_1'I_0\,EN,\quad D_2=I_1I_0'\,EN,\quad D_3=I_1I_0\,EN$$

In general:

$$D_k=m_k\cdot EN$$

---

3.9 Decoder Expansion

3-to-8 from two 2-to-4 decoders with enable:

$$EN_{\text{low}}=A_2',\qquad EN_{\text{high}}=A_2$$

$A_1A_0$ go to both decoders. The upper decoder produces $D_0$-$D_3$ ($A_2=0$), the lower produces $D_4$-$D_7$ ($A_2=1$). With an overall enable, AND it into both enables.

---

3.10 Function from Decoder + OR

$$F=\sum m(k_1,k_2,\dots)=D_{k_1}+D_{k_2}+\dots$$

An $n$-to-$2^n$ decoder generates every minterm, so any $n$-variable function (or several functions at once) needs only one OR gate per output. Use when a question says “decoder and external OR gates”.

---

3.11 Binary Encoder (8-to-3)

$$A_0=D_1+D_3+D_5+D_7$$ $$A_1=D_2+D_3+D_6+D_7$$ $$A_2=D_4+D_5+D_6+D_7$$

Each output bit ORs the inputs whose index has that bit set. Valid only if exactly one input is 1.

---

3.12 4-to-2 Priority Encoder

Priority $D_3>D_2>D_1>D_0$:

$$A_1=D_3+D_2$$ $$A_0=D_3+D_2'D_1$$ $$V=D_0+D_1+D_2+D_3$$

When $V=0$ (no input active), $A_1A_0$ are don’t-cares. Derived from K-maps of Table 3-6 using the don’t-cares.

---

3.13 8-to-3 Priority Encoder from Two 4-to-2s

Let encoder A take $D_0$-$D_3$ (outputs $A_1,A_0,V_A$) and encoder B take $D_4$-$D_7$ (outputs $B_1,B_0,V_B$). The upper group has priority:

$$C_2=V_B$$ $$C_1=V_B'A_1+V_BB_1,\qquad C_0=V_B'A_0+V_BB_0$$ $$V_C=V_A+V_B$$

$V_B$ acts as the select of two 2-to-1 MUXes.

---

3.14 4-to-1 MUX

$$Y=S_1'S_0'D_0+S_1'S_0D_1+S_1S_0'D_2+S_1S_0D_3$$

Each term is a select minterm ANDed with its data input. In general, a $2^n$-to-1 MUX outputs $Y=\sum_k m_k(S)\,D_k$. A quadruple 2-to-1 MUX is four 2-to-1 MUXes sharing one select line (selects a 4-bit word).

---

3.15 Function from a MUX

An $n$-variable function fits a $2^{n-1}$-to-1 MUX. Put the first $n-1$ variables on the selects; each data input becomes one of

$$D_k\in\{0,\ 1,\ Z,\ Z'\}$$

where $Z$ is the last variable. This is the Shannon expansion applied to the select variables.

Slide example: $F(X,Y,Z)=\sum m(1,2,6,7)$ with $S_1=X$, $S_0=Y$ gives $D_0=Z$, $D_1=Z'$, $D_2=0$, $D_3=1$.

Slide example: $F(A,B,C,D)=\sum m(1,3,4,11,12,13,14,15)$ on an 8-to-1 MUX with $S_2S_1S_0=ABC$ gives $D_0=D$, $D_1=D$, $D_2=D'$, $D_3=0$, $D_4=0$, $D_5=D$, $D_6=1$, $D_7=1$.

---

4. Problem-Solving Workflow

4.1 Implementing $F$ with a $2^{n-1}$-to-1 MUX

1. Write the truth table with the select variables as the leading (most significant) columns.
2. Split the rows into pairs that share the same select values.
3. In each pair, compare $F$ with the last variable:
   • $F=0,0$ → $D_k=0$,
   • $F=1,1$ → $D_k=1$,
   • $F$ equals the last variable → $D_k=Z$,
   • $F$ is its complement → $D_k=Z'$.
4. Connect, making sure $S_0$ is the least significant select variable.

4.2 Implementing $F$ with a Decoder

1. Express each output as $\sum m(\dots)$ (expand terms to minterms if given as an expression).
2. Use an $n$-to-$2^n$ decoder on the $n$ inputs.
3. OR the decoder outputs listed in each function.
4. If a function has many minterms, OR the outputs of $F'$ and invert (NOR), which needs fewer inputs (textbook tip).

4.3 Designing a Priority Encoder

1. Write the condensed truth table (inputs below the highest active one are X).
2. Plot each output on a K-map, filling X rows as don’t-cares.
3. Minimize each output; add $V$ as the OR of all inputs.

4.4 Adder/Subtractor Questions

1. Choose the control: $S=0$ add, $S=1$ subtract.
2. XOR each $B_i$ with $S$; set $C_0=S$.
3. Ripple through the full adders.
4. Check overflow with $V=C_n\oplus C_{n-1}$.

---

5. Decision Rules / Decision Trees

5.1 Which Building Block?

Need exactly one of $2^n$ lines active from an $n$-bit code? → decoder

Need the index of the active line as a code? → encoder (priority encoder if several can be active)

Need to route one of many inputs to one output? → multiplexer

Need many functions of the same $n$ inputs? → one decoder + one OR per function

Need one function of $n$ inputs with a single block? → $2^{n-1}$-to-1 MUX

5.2 Overflow or Carry?

Operands are unsigned? → look at $C$ (carry out)

Operands are 2’s complement? → look at $V=C_n\oplus C_{n-1}$

5.3 Priority Encoder Output

Highest active input is $D_i$? → output is $i$ in binary, lower inputs ignored, $V=1$

No input active? → $V=0$, outputs are don’t-care

---

6. Important Tables / Correlations Needed

6.1 Adder Truth Tables

$A$	$B$	$C_{in}$	$C_o$	$S$
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

The half adder is the first four rows with $C_{in}=0$ (rows $A,B=00,01,10,11$ give $C,S=00,01,01,10$).

6.2 2-to-4 Decoder with Enable

$EN$	$I_1$	$I_0$	$Y_3$	$Y_2$	$Y_1$	$Y_0$
0	X	X	0	0	0	0
1	0	0	0	0	0	1
1	0	1	0	0	1	0
1	1	0	0	1	0	0
1	1	1	1	0	0	0

6.3 4-to-2 Priority Encoder (Table 3-6)

$D_3$	$D_2$	$D_1$	$D_0$	$A_1$	$A_0$	$V$
0	0	0	0	X	X	0
0	0	0	1	0	0	1
0	0	1	X	0	1	1
0	1	X	X	1	0	1
1	X	X	X	1	1	1

6.4 Block Size Summary

Block	Inputs	Outputs	Control
$n$-to-$2^n$ decoder	$n$ (+ enable)	$2^n$	enable
$2^n$-to-$n$ encoder	$2^n$	$n$ (+ $V$ if priority)	none
$2^n$-to-1 MUX	$2^n$ data	1	$n$ select
1-to-$2^n$ DMUX	1 data	$2^n$	$n$ select

Slide quiz facts: a decoder with $2N$ inputs has at most $2^{2N}$ outputs; a priority encoder favoring higher indices with $I_3I_2I_1I_0=0110$ outputs $Y_1Y_0=10$.

---

7. Key Takeaways

• XOR is the odd function, XNOR the even function; their K-maps are checkerboards and cannot be simplified.
• Half adder: $S=A\oplus B$, $C=AB$. Full adder: $S=A\oplus B\oplus C_{in}$, $C_o=AB+C_{in}(A\oplus B)$.
• Subtraction: invert $B$, set $C_0=1$; one XOR per bit makes an adder/subtractor.
• Signed overflow: $V=C_n\oplus C_{n-1}$; unsigned overflow: carry out $C$.
• Decoder output $k$ is minterm $m_k$; decoder + OR gates implement any function.
• Expanding decoders: the extra MSB drives the enables ($A_2'$ and $A_2$).
• Priority encoder (4-to-2): $A_1=D_3+D_2$, $A_0=D_3+D_2'D_1$, $V=$ OR of all inputs.
• 4-to-1 MUX: $Y=\sum m_k(S_1S_0)D_k$.
• $n$-variable function on a $2^{n-1}$-to-1 MUX: data inputs are $0$, $1$, $Z$ or $Z'$.
• Trap: check which variable goes to $S_0$ (LSB select); swapping selects scrambles the data inputs.