Combinational circuits: adders, multiplexers, decoders

Why it matters

Adders, multiplexers and decoders are the building blocks inside every processor, data-acquisition system and FPGA. An instrument that scans eight sensors uses a multiplexer to pick the channel, a decoder to select the memory chip that stores the reading, and an adder to average or offset-correct it. Knowing these blocks lets you implement any logic function with a single standard IC instead of a page of gates.

Key ideas

Combinational circuits. The outputs depend only on the present inputs: no memory, no clock. They are specified by a truth table and designed by writing and minimising output expressions. Their only time behaviour is propagation delay and possible glitches (hazards).

Half adder. Adds two bits A and B: Sum S = A ⊕ B, Carry C = A·B. One XOR and one AND gate. It has no carry input, so it can only serve the least significant bit.

Full adder. Adds A, B and an incoming carry Cᵢₙ: S = A ⊕ B ⊕ Cᵢₙ (odd-parity function: 1 when an odd number of inputs are 1), Cₒᵤₜ = AB + BCᵢₙ + ACᵢₙ (majority function). It can be built from two half adders and an OR gate: Cₒᵤₜ = AB + Cᵢₙ(A ⊕ B).

Ripple-carry adder. n full adders chained, each carry feeding the next. Simple, but the carry may have to ripple through all n stages, so the worst-case delay grows linearly with n.

Carry-lookahead adder (CLA). Define for each bit a generate Gᵢ = AᵢBᵢ (this stage makes a carry on its own) and a propagate Pᵢ = Aᵢ ⊕ Bᵢ (this stage passes an incoming carry on). Then Cᵢ₊₁ = Gᵢ + PᵢCᵢ, which can be expanded so that every carry is a two-level AND-OR function of the inputs and C₀. Delay becomes nearly independent of n at the cost of more gates and high fan-in; large adders use 4-bit CLA blocks with a second lookahead level.

Adder-subtractor. Feed B through XOR gates controlled by a mode line M and set C₀ = M. With M = 0 the circuit adds; with M = 1 it computes A + B' + 1 = A − B in 2's complement. Signed overflow V = Cₙ ⊕ Cₙ₋₁.

BCD adder. Add two BCD digits in binary; if the sum is greater than 9 or produces a carry, add 0110 to correct it and send a decimal carry to the next digit.

Multiplexer (MUX, data selector). 2ⁿ data inputs, n select lines, one output. A 4:1 MUX gives Y = S₁'S₀'I₀ + S₁'S₀I₁ + S₁S₀'I₂ + S₁S₀I₃. Uses: channel selection in data acquisition, parallel-to-serial conversion, and implementing logic: a 2ⁿ:1 MUX implements any function of n + 1 variables by putting n variables on the selects and feeding each data input with 0, 1, the last variable or its complement. Larger MUXes are built as trees of smaller ones.

Demultiplexer. One input routed to one of 2ⁿ outputs chosen by the select lines. A decoder with an enable input is a demultiplexer, with the enable acting as the data input.

Decoder. n inputs, up to 2ⁿ outputs; exactly one output is active for each input code, so each output is a minterm. Any function can be implemented by ORing the decoder outputs for its minterms (or NANDing active-low outputs). Uses: memory chip-select and address decoding, driving seven-segment displays (BCD-to-7-segment decoder). Larger decoders are built from smaller ones using the enable inputs.

Formulas

S = A ⊕ B ⊕ Cᵢₙ and Cₒᵤₜ = A·B + B·Cᵢₙ + A·Cᵢₙ

• Full adder; all signals are single bits.

Gᵢ = Aᵢ·Bᵢ, Pᵢ = Aᵢ ⊕ Bᵢ, Cᵢ₊₁ = Gᵢ + Pᵢ·Cᵢ, Sᵢ = Pᵢ ⊕ Cᵢ

• Carry-lookahead relations.

C₄ = G₃ + P₃G₂ + P₃P₂G₁ + P₃P₂P₁G₀ + P₃P₂P₁P₀C₀

t_ripple(worst) = (n − 1)·t_carry + max(t_sum, t_carry)

• n: number of bits; t_carry, t_sum: carry and sum delays of one full adder (s).

Select lines of a MUX = log₂(number of data inputs)

Number of 2:1 MUXes for a 2ⁿ:1 MUX = 2ⁿ − 1

V = Cₙ ⊕ Cₙ₋₁ (2's complement overflow)

Worked examples

Example 1 (standard). Add A = 1101 and B = 1011 with a 4-bit ripple-carry adder (C₀ = 0).

1. Bit 0: 1 + 1 + 0 → S₀ = 0, C₁ = 1.
2. Bit 1: 0 + 1 + 1 → S₁ = 0, C₂ = 1.
3. Bit 2: 1 + 0 + 1 → S₂ = 0, C₃ = 1.
4. Bit 3: 1 + 1 + 1 → S₃ = 1, C₄ = 1.
5. Result C₄S₃S₂S₁S₀ = 11000. Check: 13 + 11 = 24 = 11000₂.

Answer: Sum = 1000 with carry-out 1, i.e. 11000₂ = 24

Example 2 (GATE level). Implement F(A, B, C) = Σm(1, 2, 6, 7) with a 4:1 MUX, using A and B as the select lines (A = MSB).

1. For AB = 00 the rows are m0 (C = 0) and m1 (C = 1); F = 0, 1 → I₀ = C.
2. For AB = 01: m2, m3 → F = 1, 0 → I₁ = C'.
3. For AB = 10: m4, m5 → F = 0, 0 → I₂ = 0.
4. For AB = 11: m6, m7 → F = 1, 1 → I₃ = 1.
5. Check one row: A = 0, B = 1, C = 0 (m2) selects I₁ = C' = 1, and m2 is in the list.

Answer: I₀ = C, I₁ = C', I₂ = 0, I₃ = 1

Example 3 (delay). An 8-bit ripple-carry adder uses full adders with t_carry = 10 ns and t_sum = 15 ns. Find the worst-case addition time.

1. t = (n − 1)·t_carry + max(t_sum, t_carry).
2. = 7 × 10 ns + 15 ns = 85 ns.

Answer: 85 ns (so the adder supports at most about 11.7 million additions per second)

Common mistakes

• Writing the full-adder carry as A ⊕ B ⊕ ... or forgetting the BCᵢₙ and ACᵢₙ terms.
• Treating the carry OR as arithmetic: 1 + 1 + 1 in Boolean OR is 1, not 3.
• Mixing up select-line order (which select is the MSB) when implementing functions with a MUX.
• Counting a ripple adder's delay as n × t_sum; it is the carry chain that sets the delay.
• Forgetting C₀ = 1 when using the adder as a 2's complement subtractor.
• Building a 3-to-8 decoder from 2-to-4 decoders without using the enable inputs for the third variable.

For GATE IN

Common questions: identify the function realised by a given MUX or decoder circuit, implement a function with a MUX of given size, count MUXes or decoders needed to build a larger one, evaluate ripple-carry or carry-lookahead delay, and find outputs of an adder-subtractor for given inputs. Practise reading MUX circuits row by row from the select lines and writing the minterm list.

Quick check

1. Sum and carry of a full adder for A = 1, B = 1, Cᵢₙ = 1?
2. How many select lines does a 16:1 MUX need?
3. How many 2:1 MUXes make an 8:1 MUX?
4. What is the generate signal of a bit with A = 1, B = 0?
5. How many outputs does a 3-to-8 decoder activate at a time?

Answers: 1. S = 1, C = 1 2. 4 3. 7 4. 0 (it propagates instead) 5. One