Combinational circuits: adders and multiplexers
Foundations of combinational circuits: half- and full-adders, ripple vs carry look-ahead adders, and multiplexers (2ⁿ:1) with implementations, equations, timing, and exam-style examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Combinational circuits like adders and multiplexers are the building blocks of arithmetic and data routing inside every digital system, from microcontrollers to SoCs. Understanding how to design, analyze, and time these circuits lets an engineer reason about correctness, speed, and area/power trade-offs in real hardware.
Key ideas
- Half adder (HA): A combinational circuit that adds two 1-bit inputs A and B and outputs a 1-bit sum S and a 1-bit carry C. Exact definition: “A half adder produces S = A ⊕ B and C = A · B.” Assumptions: A, B ∈ {0,1}. Derivation: From the 2-bit addition truth table: 00→S0C0, 01→S1C0, 10→S1C0, 11→S0C1. Recognize XOR pattern for S and AND for C.
- What to draw: Block titled “Half Adder” with inputs A, B; inside one XOR gate to S, one AND gate to C. Label outputs S and C.
- Full adder (FA): A combinational circuit that adds three 1-bit inputs A, B, and Cin (carry-in) and outputs a 1-bit sum S and carry-out Cout. Exact definition: “A full adder produces S = A ⊕ B ⊕ Cin and Cout = A·B + B·Cin + A·Cin.” Assumptions: A, B, Cin ∈ {0,1}.
- Derivation from truth table (standard 8-row): S is odd-parity over A, B, Cin, hence XOR of three. Carry is 1 when at least two inputs are 1, hence the three pairwise products ORed.
- Equivalent derivation using two HAs: First HA adds A and B → S1 = A ⊕ B, C1 = A·B. Second HA adds S1 and Cin → S = S1 ⊕ Cin, C2 = S1·Cin. Then Cout = C1 + C2 = A·B + (A ⊕ B)·Cin.
- What to draw: Two HA blocks in cascade: inputs A, B to first HA; its sum to second HA with Cin; OR gate combines the two carries to Cout; final sum from second HA.
- N-bit ripple-carry adder (RCA): A chain of N full adders where Cout of bit i is Cin of bit i+1. Exact statement: “In an N-bit ripple-carry adder, the worst-case carry propagation traverses N stages; the worst-case path delay is approximately N times the FA carry-propagation delay.” Assumptions: identical FA delay; inputs applied simultaneously.
- What to draw: N FA blocks in series with labeled A0..AN−1, B0..BN−1, Cin, and S0..SN−1, Cout, arrows showing carry chain.
- Propagate (P) and generate (G) signals: For bit i, define Pi = Ai ⊕ Bi (carry-propagate when one of Ai, Bi is 1) and Gi = Ai · Bi (carry-generate when both are 1). Exact relations: Si = Pi ⊕ Ci and Ci+1 = Gi + Pi·Ci. Assumption: standard FA structure.
- Carry look-ahead adder (CLA): A faster adder computing carries in parallel using P and G. For a 4-bit group (bits 0..3) with input C0, the carries are:
- 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 These come from repeated substitution of Ci+1 = Gi + Pi·Ci.
- Group propagate and generate: PG = P3·P2·P1·P0, GG = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0. Used to build multi-level CLAs.
- What to draw: A 4-bit CLA block feeding Si blocks, with a “carry look-ahead unit” computing C1..C4 from Ai, Bi, C0 using P/G logic.
- Multiplexer (MUX): A combinational circuit that selects one of 2^m data inputs and forwards it to a single output based on m select inputs. Exact definition: “An n:1 MUX has n data inputs D0..Dn−1, one output Y, and m select inputs S(m−1)..S0 such that n = 2^m; output Y equals Di where i is the binary value of S.”
- 2:1 MUX equation: Y = S′·D0 + S·D1. Here S′ is NOT S. Generalized: Y = Σ Di·Mi where Mi is the minterm of the select lines equal to i (to avoid confusion with the propagate signal Pi used in adders).
- What to draw: Triangle/box with inputs D0..Dn−1 on left, select lines below, single output on right. For 4:1, label S1, S0 and internal selection controlled by decoding logic.
- Realizing logic with a MUX: Any Boolean function of m variables can be implemented using a 2^m:1 MUX by connecting each input Di to 0, 1, or a don’t-care as per the truth table. Alternatively, for k-variable function implemented on a 2^m:1 MUX with m < k, use m variables as selects and express Di as a function of the remaining k−m variables.
- Demultiplexer (DEMUX): Complement of MUX (one input to one of many outputs). Mentioned for context only; this topic focuses on multiplexers.
- Cascading MUXes: Building larger MUXes from smaller ones, e.g., two 4:1 MUXes feeding a 2:1 MUX to make an 8:1. Select lines are shared/hierarchical. Timing: extra stage adds delay.
- Timing and delay: In combinational circuits, the worst-case propagation delay is the longest path from any input to any output through gates. For adders, the carry chain dominates for RCAs; for CLAs, parallel carry logic reduces this chain length but adds fan-in gates. Units: seconds (often ns).
Formulas
S = A ⊕ B — Half-adder sum; A, B are 1-bit inputs (unitless logic); ⊕ is XOR; applies to half adder.
C = A · B — Half-adder carry; · is AND; applies to half adder carry output.
S = A ⊕ B ⊕ Cin — Full-adder sum; Cin is carry-in; applies to 1-bit full adder.
Cout = A·B + B·Cin + A·Cin — Full-adder carry-out; + is OR; applies to 1-bit full adder.
Pi = Ai ⊕ Bi — Propagate for bit i; applies in carry-look-ahead derivations.
Gi = Ai · Bi — Generate for bit i; applies in carry-look-ahead derivations.
Si = Pi ⊕ Ci — Sum bit in terms of propagate and carry-in; applies to FA structure.
Ci+1 = Gi + Pi·Ci — Recursive carry equation; applies in FA and CLA analysis.
C1 = G0 + P0·C0 — CLA carry for bit 0 to 1; 1-bit index; logic unitless; applies to 4-bit CLA.
C2 = G1 + P1·G0 + P1·P0·C0 — CLA carry to bit 2; applies to 4-bit CLA.
C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0 — CLA carry to bit 3; applies to 4-bit CLA.
C4 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·C0 — Group carry-out of 4-bit CLA; applies to 4-bit block.
PG = P3·P2·P1·P0 — Group propagate for a 4-bit block; applies in hierarchical CLAs.
GG = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 — Group generate for a 4-bit block; applies in hierarchical CLAs.
Y = S′·D0 + S·D1 — 2:1 MUX output; S is select (unitless logic), Di are data inputs.
n = 2^m — Relation between number of data inputs n and number of select lines m for a MUX; unitless count.
tRCA ≈ N · tFA_carry — Worst-case delay of N-bit ripple-carry adder (carry-out path); tFA_carry is carry-propagation delay per FA (seconds); approximation assumes uniform stages.
tS_MSB ≈ (N − 1) · tFA_carry + tFA_sum — Worst-case arrival time of the most significant sum bit in an N-bit RCA; tFA_sum is the sum logic delay (seconds).
tMUX_k:1 ≈ tdecode + tmux — MUX delay equals decoder plus selection gate delays; seconds; qualitative when library-specific numbers are unknown.
Worked examples
- Theory + construction: Derive full adder from two half adders and obtain Cout expression Given: You have half adders: S = A ⊕ B, C = A·B. Steps:
- First half adder (HA1): Inputs A, B → S1 = A ⊕ B, C1 = A·B.
- Second half adder (HA2): Inputs S1, Cin → S = S1 ⊕ Cin = (A ⊕ B) ⊕ Cin.
- Carry outputs: From HA2, C2 = S1·Cin = (A ⊕ B)·Cin; from HA1, C1 = A·B.
- Overall Cout: OR the carries: Cout = C1 + C2 = A·B + (A ⊕ B)·Cin.
- Expand to standard sum-of-products: (A ⊕ B)·Cin = (A′·B + A·B′)·Cin = A′·B·Cin + A·B′·Cin. Also A·B term remains. Grouping by pairs gives A·Cin + B·Cin + A·B (since whenever two inputs are 1, carry is 1). Therefore Cout = A·B + A·Cin + B·Cin. Final: S = A ⊕ B ⊕ Cin, Cout = A·B + A·Cin + B·Cin. What to draw: Two half-adder blocks and one OR gate as described under Key ideas.
- Numerical + timing: 4-bit ripple-carry adder delay and addition Given: Add A = 1011₂ (11₁₀) and B = 0111₂ (7₁₀) with Cin = 0. Each full adder has carry-propagation delay tFA_carry = 2 ns, sum delay tFA_sum = 3 ns. Find sum, Cout, and worst-case output timing for S3 and Cout. Steps:
- Bitwise addition (LSB is bit 0):
- Bit 0: A0=1, B0=1, Cin0=0 → S0 = 1 ⊕ 1 ⊕ 0 = 0; C1 = 1·1 + 1·0 + 1·0 = 1.
- Bit 1: A1=1, B1=1, Cin1=C1=1 → S1 = 1 ⊕ 1 ⊕ 1 = 1; C2 = 1·1 + 1·1 + 1·1 = 1.
- Bit 2: A2=0, B2=1, Cin2=1 → S2 = 0 ⊕ 1 ⊕ 1 = 0; C3 = 0·1 + 1·1 + 0·1 = 1.
- Bit 3: A3=1, B3=0, Cin3=1 → S3 = 1 ⊕ 0 ⊕ 1 = 0; C4 = 1·0 + 0·1 + 1·1 = 1.
- Result: From steps S0=0, S1=1, S2=0, S3=0 → S3..S0 = 0010₂. Decimal: 11 + 7 = 18, which is 10010₂; our 4-bit sum 0010₂ with Cout = 1 gives 1·2⁴ + 2 = 18. Consistent.
- Timing (worst-case):
- Carry chain: C1 ready at 2 ns, C2 at 4 ns, C3 at 6 ns, C4 at 8 ns (ripple across 4 FAs).
- Sums: S0 depends only on local inputs: ready at 3 ns. S1 depends on Cin1 (C1); worst-case S1 at max(C1 time + sum stage) ≈ 2 ns + 3 ns = 5 ns. Similarly, S2 ≈ 4 ns + 3 ns = 7 ns; S3 ≈ 6 ns + 3 ns = 9 ns. Cout becomes valid at 8 ns. Final answers: Sum = 0010₂ with Cout = 1. Worst-case arrival times: S3 at 9 ns, Cout at 8 ns.
- Realization using a 4:1 MUX: Implement F(A, B, C) = Σm(1, 2, 6, 7) Goal: Use a 4:1 MUX with select lines S1 = A and S0 = B. Inputs D0..D3 will be functions of C. Steps:
- Form the truth table of F over A,B,C (A is MSB): minterms 1 (001), 2 (010), 6 (110), 7 (111) are 1; others 0.
- Group rows by select pair (A,B):
- (A,B) = 00 → rows C=0 (m0) and C=1 (m1). F = 0 at m0, 1 at m1 → function over C is F = C.
- (A,B) = 01 → rows C=0 (m2) and C=1 (m3). F = 1 at m2, 0 at m3 → function over C is F = C′.
- (A,B) = 10 → rows C=0 (m4) and C=1 (m5). F = 0 at m4, 0 at m5 → function over C is F = 0.
- (A,B) = 11 → rows C=0 (m6) and C=1 (m7). F = 1 at m6, 1 at m7 → function over C is F = 1.
- Therefore connect MUX inputs: D0 = C, D1 = C′, D2 = 0, D3 = 1; select S1=A, S0=B; output Y=F.
- Check with a sample input, e.g., A=0,B=1,C=0 → selects D1 = C′ = 1, matching m2 ∈ function; A=1,B=0,C=1 → selects D2=0, matching m5 not in function. What to draw: 4:1 MUX box; left side D0..D3 labeled as above; bottom select A=S1, B=S0; right side output F.
- CLA carry computation example (4-bit) Given: A = 1011₂, B = 0111₂, C0 = 0. Compute P, G, C1..C4, and S using CLA equations. Steps:
- Bitwise values (i from 0 LSB to 3 MSB): A = [1,1,0,1], B = [1,1,1,0]. So:
- i=0: A0=1, B0=1 → P0 = 1 ⊕ 1 = 0; G0 = 1·1 = 1.
- i=1: A1=1, B1=1 → P1 = 0; G1 = 1.
- i=2: A2=0, B2=1 → P2 = 1; G2 = 0.
- i=3: A3=1, B3=0 → P3 = 1; G3 = 0.
- Carries (C0=0):
- C1 = G0 + P0·C0 = 1 + 0·0 = 1.
- C2 = G1 + P1·G0 + P1·P0·C0 = 1 + 0·1 + 0·0·0 = 1.
- C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0 = 0 + 1·1 + 1·0·1 + 1·0·0·0 = 1.
- C4 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·C0 = 0 + 1·0 + 1·1·1 + 1·1·0·1 + 1·1·0·0·0 = 1.
- Sums: Si = Pi ⊕ Ci.
- S0 = P0 ⊕ C0 = 0 ⊕ 0 = 0.
- S1 = P1 ⊕ C1 = 0 ⊕ 1 = 1.
- S2 = P2 ⊕ C2 = 1 ⊕ 1 = 0.
- S3 = P3 ⊕ C3 = 1 ⊕ 1 = 0.
- Result: S = 0010₂ with C4 = 1, consistent with Example 2.
Common mistakes
- In MUX implementation, assigning select lines in wrong order (e.g., S1 as LSB). Always state which select bit is MSB and match Di accordingly.
- Overlooking don’t-care conditions when mapping a function to MUX inputs; leads to more complex Di than needed.
- Timing calculations: ignoring that each sum output depends on its local carry; S(i) arrival time is carry arrival time plus sum logic delay.
- Using decimal minterm indices with different variable order (ABC vs CBA). Fix variable order first and keep it consistent throughout.
- For CLA, writing C2 = G1 + P1·C1 (this is not look-ahead; expand fully to break the ripple dependency).
For your exam
- Derivations: step-by-step from FA truth table to Cout in sum-of-products; CLA carry expansion for C1..C4 by substitution; 2:1 MUX equation Y = S′·D0 + S·D1 from truth table.
- Numericals: timing of RCAs given gate delays; compute sum and carry for N-bit addition; compute arrival times of S(i) and Cout; given library delays, compare RCA vs CLA delay for N bits (show formula and substitution).
- Realizations: implement a given Boolean function using a 4:1 or 8:1 MUX by selecting variable(s) as select lines and deriving Di; draw neatly labeled diagrams.
- Diagrams: half adder with XOR/AND; full adder using two HAs and OR; N-bit RCA chain; 4-bit CLA block with look-ahead unit; 4:1 and 8:1 MUX with select lines and data inputs labeled; show signal names on each pin.
- Full-marks answers: start with clean definition, present truth table or K-map if relevant, derive equations clearly with Boolean steps, add a labeled diagram, then discuss timing/limitations (e.g., ripple delay) if asked.
Quick check
- Write the equations for sum and carry of a full adder in terms of A, B, Cin.
- For a 4:1 MUX with selects S1S0 = AB, what are D0..D3 to implement F(A,B,C) = Σm(0,2,3,6)?
- If each FA has 250 ps carry delay and 350 ps sum delay, what are worst-case arrival times of S7 and Cout in an 8-bit RCA with Cin ready at t=0? Answers: (1) S = A ⊕ B ⊕ Cin; Cout = A·B + A·Cin + B·Cin. (2) With AB as selects, group over C: AB=00→F=1 at m0 and 0 at m1 ⇒ D0 = C′; AB=01→m2=1, m3=1 ⇒ D1 = 1; AB=10→m4=0, m5=0 ⇒ D2 = 0; AB=11→m6=1, m7=0 ⇒ D3 = C′. (3) Carry arrives at C8 ≈ 8·250 ps = 2000 ps; S7 depends on C7 at 7·250 ps plus sum delay 350 ps ⇒ 1750 + 350 = 2100 ps; Cout at 2000 ps.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?