Skills Built:K-Map MinimizationAdder Circuit DesignMultiplexer ImplementationHazard Detection

1. Intuition First: Logic Without Memory

A combinational logic circuit has no memory and no feedback. Its outputs at any instantaneous moment are purely a direct function of its current inputs:

$\mathbf{Y}(t) = f(\mathbf{X}(t))$

If the inputs remain steady, the outputs remain fixed. If the inputs change, the outputs respond after a tiny physical delay known as propagation delay ( $t_{pd}$ ).

The Lookup Table vs. The Spatial Map

A truth table is essentially a raw sequential lookup table listing all $2^n$ input combinations. However, truth tables make algebraic adjacencies difficult to spot.

A Karnaugh Map (K-map) reorganizes the truth table into an $n$ -dimensional hypercube flattened into a 2D grid. The key innovation is Gray code ordering ( $00 \to 01 \to 11 \to 10$ ) along each axis:

Every geometrically adjacent cell differs by exactly one literal (Hamming distance $= 1$ ).
When two adjacent cells both equal $1$ , their Boolean expression $A B + A B' = A(B + B') = A$ allows the varying variable to be completely eliminated.
Grouping $2^k$ adjacent ones eliminates $k$ Boolean variables from that product term.

Addition on Silicon: The Ripple Bottleneck

When you add multi-digit numbers by hand on paper, you start at the least significant digit, write down the sum, and forward the carry to the next column.

A hardware Ripple-Carry Adder (RCA) mimics this exact process:

Each bit stage is a Full Adder (FA) that cannot calculate its final sum or carry until the carry output ( $C_{\text{out}}$ ) from the preceding lower-order stage arrives.
In an $n$ -bit ripple adder, the carry must ripple through all $n$ stages in the worst case. For a 32-bit or 64-bit word, this creates an intolerable latency bottleneck.
Carry Look-Ahead Adders (CLA) break this serial chain by pre-computing all carries in parallel using two auxiliary functions: Generate ( $G_i$ ) and Propagate ( $P_i$ ).

Multiplexers & Decoders

A Multiplexer (MUX) acts as a hardware digital rotary switch. With $n$ select lines, it routes one of $2^n$ data inputs to a single output line. Because of this structure, an $n$ -select MUX can act as a universal function generator for any Boolean function of $n+1$ variables.
A Decoder performs the dual operation: given $n$ binary input lines, it activates exactly one of $2^n$ output lines, with each output corresponding directly to a unique minterm.

2. Formula & Unit Quick-Reference Strip

Formula & Unit Quick-Reference Strip

Half AdderDimensionless (Bits)

S = A ⊕ B, C = A · B

Adds two 1-bit inputs; generates sum and carry-out with no carry-in.

Full Adder SumDimensionless (Bit)

S = A ⊕ B ⊕ C_in

Parity sum of three 1-bit inputs (A, B, and Carry-in).

Full Adder CarryDimensionless (Bit)

C_out = A·B + C_in·(A ⊕ B)

Majority function: true when at least two of the three inputs are 1.

Generate & PropagateDimensionless (Bits)

G_i = A_i·B_i, P_i = A_i ⊕ B_i

G produces an unconditional carry; P propagates an incoming carry.

Look-Ahead CarryDimensionless (Bit)

C_{i+1} = G_i + P_i·C_i

Recursive carry formulation evaluated in two gate levels of delay.

Multiplexer (MUX)2^n Data : n Select

Y = \sum_{k=0}^{2^n - 1} I_k · m_k(S)

Steers 1 of 2^n inputs to output using n control select address lines.

Decodern Inputs : 2^n Outputs

Y_k = m_k(A_{n-1}, ..., A_0)

Decodes n binary inputs into 2^n unique active minterm lines.

K-Map GroupingVariables Eliminated

Group\ Size = 2^k \implies k\ \text{Vars Removed}

A rectangular block of 2^k ones eliminates k Boolean literals.

3. Mathematical Derivation: Full Adder Carry-Out Formulation

4. Typical Bench Values & Laboratory Tolerances

When prototyping combinational logic circuits on solderless breadboards or measuring timing characteristics with an oscilloscope or logic analyzer, standard 74xx TTL and 74HC CMOS logic families operate within these nominal ranges:

Typical Laboratory Hardware Ranges

Parameter / Part	Typical Value	Lab Range	Practical Notes
Propagation Delay (t_pd)	9ns to 15ns (74LS) / 3ns (74ACT)	1.5ns - 35ns	Delay per logic gate level under 15pF capacitive load
Supply Rail (V_CC)	5.0 V DC (TTL/HC) or 3.3 V (LVC)	4.75V - 5.25V (TTL)	Bypass with 100nF decoupling capacitor at every IC V_CC pin
Noise Margin High (NM_H)	0.7 V (TTL) / 1.4 V (CMOS)	0.4V - 2.0V	NM_H = V_OH(min) - V_IH(min); prevents false logic flips
Noise Margin Low (NM_L)	0.4 V (TTL) / 0.9 V (CMOS)	0.3V - 1.2V	NM_L = V_IL(max) - V_OL(max); immunity against ground bounce
Fan-out Capability	10 LS-TTL unit loads (20 for HC)	10 - 50 gates	Maximum number of gate inputs driven without signal degradation
Static Power Dissipation	2 mW/gate (LS-TTL), 10 µW (CMOS)	1µW - 25mW	CMOS consumes near-zero static power; power scales linearly with frequency

5. Worked Problems & Engineering Solutions

Example 1: 4-Bit Ripple-Carry Addition & Latency Analysis

Step-by-Step Worked Problem

Add binary numbers A = 0110_2 (6_10) and B = 0111_2 (7_10) using a 4-bit ripple-carry adder with initial carry-in C_0 = 0. If each full adder stage has a carry propagation delay of t_carry = 10 ns, determine the sum bits, final carry, and worst-case propagation delay. Contrast with a 32-bit architecture.

Step 1: Bit 0 Addition (Least Significant Bit)

Inputs: A_0 = 0, B_0 = 1, C_0 = 0. Sum: S_0 = A_0 ⊕ B_0 ⊕ C_0 = 0 ⊕ 1 ⊕ 0 = 1. Carry: C_1 = (A_0 · B_0) + C_0(A_0 ⊕ B_0) = 0 + 0(1) = 0. Output settles at t = 10 ns.

Step 2: Bit 1 Addition

Inputs: A_1 = 1, B_1 = 1, C_1 = 0. Sum: S_1 = 1 ⊕ 1 ⊕ 0 = 0. Carry: C_2 = (1 · 1) + 0(1 ⊕ 1) = 1 + 0 = 1. Output settles at t = 20 ns.

Step 3: Bit 2 Addition

Inputs: A_2 = 1, B_2 = 1, C_2 = 1. Sum: S_2 = 1 ⊕ 1 ⊕ 1 = 1. Carry: C_3 = (1 · 1) + 1(1 ⊕ 1) = 1 + 1(0) = 1. Output settles at t = 30 ns.

Step 4: Bit 3 Addition (Most Significant Bit)

Inputs: A_3 = 0, B_3 = 0, C_3 = 1. Sum: S_3 = 0 ⊕ 0 ⊕ 1 = 1. Carry: C_4 = (0 · 0) + 1(0 ⊕ 0) = 0 + 0 = 0. Output settles at t = 40 ns.

Step 5: Latency Comparison for 32-bit Words

Result: Sum = S_3 S_2 S_1 S_0 = 1101_2 = 13_10, Carry C_4 = 0. Verified: 6 + 7 = 13. For 4 bits, worst-case delay is 4 * 10 ns = 40 ns. For a 32-bit ripple adder, worst-case latency scales linearly to 32 * 10 ns = 320 ns (restricting clock frequency to < 3.125 MHz). Carry Look-Ahead reduces this delay to just 3–4 gate delays (~12 ns).

Example 2: K-Map Minimization with Wrap-Around & Adjacency

Step-by-Step Worked Problem

Minimize the 4-variable Boolean function F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10) into its minimal Sum-of-Products (SOP) form. Identify all prime implicants, check for corner wrap-around groups, and compute the literal savings.

Step 1: Populate the 4-Variable K-Map Grid

Row variables: AB (00, 01, 11, 10); Column variables: CD (00, 01, 11, 10). Cells with 1: m_0(0000), m_1(0001), m_2(0010), m_5(0101), m_8(1000), m_9(1001), m_10(1010).

Step 2: Group 1 (Four Corners Wrap-Around)

Cells m_0(0000), m_2(0010), m_8(1000), and m_10(1010) form a valid quad group of size 4 by simultaneous vertical and horizontal edge wrap-around. Variables A and C vary (0 and 1). Variables B=0 and D=0 remain constant. Term = B' D'.

Step 3: Group 2 (Top and Bottom Rows, Left Columns)

Cells m_0(0000), m_1(0001), m_8(1000), and m_9(1001) form a quad group of size 4 across the top (AB=00) and bottom (AB=10) rows in columns CD=00 and CD=01. Variables A and D change; B=0 and C=0 remain constant. Term = B' C'.

Step 4: Group 3 (Covering Isolated Minterm m_5)

Minterm m_5(0101) must be grouped. Its only adjacent neighbor with a 1 is m_1(0001). Forming a pair of size 2 with (m_1, m_5): Here A changes (0 to 1), while B=0, C=0, D=1 are fixed for m_1, but across the group: A varies, B changes from 0 to 1? Check: m_1=0001 (A=0,B=0), m_5=0101 (A=0,B=1). Thus A=0 is constant, B changes (0 and 1), C=0 is constant, D=1 is constant. Term = A' C' D.

Step 5: Minimal SOP Expression & Literal Count

All minterms are covered: F = B' D' + B' C' + A' C' D. The unminimized canonical sum of 7 minterms had 7 * 4 = 28 literals. The minimized expression has only (2 + 2 + 3) = 7 literals, achieving a 75% hardware reduction.

Example 3: Universal Function Synthesis with a 4:1 Multiplexer

Step-by-Step Worked Problem

Implement the 3-variable function F(A, B, C) = Σm(1, 2, 4, 7) using a single 4:1 Multiplexer (with select lines S_1, S_0) and no external logic gates other than inverters. Choose A and B as select lines.

Step 1: Partition Minterms by Select Lines

Let select lines be S_1 = A (MSB) and S_0 = B. The four multiplexer data inputs I_0, I_1, I_2, I_3 correspond to AB = 00, 01, 10, 11.

Step 2: Evaluate Input Lines against Residual Variable C

For AB = 00 (I_0): minterms are m_0(C=0) and m_1(C=1). Here F=0 for m_0 and F=1 for m_1. Therefore, when AB=00, F = C → Connect I_0 = C. For AB = 01 (I_1): minterms are m_2(C=0) and m_3(C=1). Here F=1 for m_2 and F=0 for m_3. Therefore, when AB=01, F = C' → Connect I_1 = C'. For AB = 10 (I_2): minterms are m_4(C=0) and m_5(C=1). Here F=1 for m_4 and F=0 for m_5. Therefore, when AB=10, F = C' → Connect I_2 = C'. For AB = 11 (I_3): minterms are m_6(C=0) and m_7(C=1). Here F=0 for m_6 and F=1 for m_7. Therefore, when AB=11, F = C → Connect I_3 = C.

Step 3: Synthesize and Identify Circuit Identity

Multiplexer wiring: I_0 = C, I_1 = C', I_2 = C', I_3 = C, with Select inputs S_1 = A, S_0 = B. Notice that F(A, B, C) = Σm(1, 2, 4, 7) is the canonical definition of a 3-input odd parity checker: F = A ⊕ B ⊕ C.

6. Common Exam Traps & Pitfalls

Common Exam Traps & Where Marks Are Lost

Avoid these classic calculation errors frequently spotted on semester examination answer scripts:

Gray Code Axis Ordering: In a K-map, never label row or column headers in standard binary order (00, 01, 10, 11). You MUST use Gray code sequence: 00, 01, 11, 10. Labeling 10 before 11 destroys Hamming distance adjacency and yields invalid groupings.
Illegal Group Sizes: K-map groupings must strictly be powers of two (sizes 1, 2, 4, 8, 16). Never group 3, 5, or 6 cells! Doing so violates Boolean algebraic laws.
Overlooking Toroidal Wrap-Around: The extreme left and right columns are adjacent, as are the top and bottom rows. Forgetting the four-corner group (m0, m2, m8, m10 in a 4-variable map) leaves unminimized redundant terms.
Don't-Care Overuse: Treat 'Don't-Care' (X or d) conditions strategically. Include an X in a group ONLY if it expands a group of 1s into a larger power of two (e.g., turning a pair into a quad). Never create a group containing only don't-cares.
Reversing MUX Select Lines: Connecting S1 to the least significant bit (LSB) and S0 to the most significant bit (MSB) transposes the entire internal minterm decoder, swapping I1 with I2 and destroying the circuit logic.
Static Hazards & Consensus Terms: Minimizing solely for lowest gate count leaves adjacent prime implicants that do not overlap. When an input variable transitions between those groups, unequal gate delays can produce an erroneous 0-glitch (static-1 hazard). Adding the redundant consensus term eliminates the glitch.

7. Interactive Logic Gate Simulation & 'Try Breaking It'

Experiment with gate behaviors, propagate logic levels, and observe propagation delay dynamics in the interactive simulator below:

Interactive Engineering Simulator

logic-gates

Simulator will mount when scrolled into view (conserving CPU & memory)

Try Breaking It: Predict Before You Test

Chain four full adders, set A=1111 and B=0001, and predict how many stages must wait for a carry before the output settles.

8. Parametrised Practice Problem

Practice calculating ripple-carry propagation limits and look-ahead speedups with randomized parameters:

Parametrised Practice Problem

Thévenin Equivalent of a Loaded Voltage Divider

A 36 V DC voltage source powers a divider with R1 = 20 Ω and R2 = 80 Ω. Calculate the open-circuit Thévenin voltage V_th (in Volts) appearing across terminals of R2.

Progressive Hints:

9. Unit Mastery Quiz

5-Question Mastery Check

Unit Quiz: Combinational Logic Design

Q1.A Full Adder has inputs A = 1, B = 0, and Cin = 1. What are the resulting Sum and Carry-out outputs?

Q2.How many select lines are required for an 8:1 Multiplexer?

Q3.In a Karnaugh Map, by how many variable states do two geometrically adjacent cells differ?

Q4.A rectangular group of 8 ones in a 4-variable K-map simplifies to a product term containing how many literals?

Q5.In a Carry Look-Ahead adder, what is the recursive Boolean expression for carry C_{i+1} in terms of generate G_i, propagate P_i, and carry C_i?

0 of 5 answered