Combinational circuits: multiplexers, decoders, adders

Why it matters

Combinational blocks do the routing and arithmetic inside every digital controller: a multiplexer picks which sensor an ADC reads, a decoder enables one memory chip or one display digit, and adders sit inside every ALU and counter. Knowing how these blocks work, and how to build a logic function from them, lets you read datasheets of standard ICs and design glue logic for a mechatronic system without guesswork.

Key ideas

Combinational versus sequential. A combinational circuit's outputs depend only on its present inputs; it has no memory and no clock. (Sequential circuits, covered next, add flip-flops so the output also depends on past inputs.) The design procedure is: write the truth table, derive minimal SOP or POS expressions (Boolean algebra or K-map), then implement with gates or standard blocks. Real gates have a propagation delay, so outputs settle only after the longest path through the circuit.

Multiplexer (MUX, data selector). A 2ⁿ-to-1 MUX has 2ⁿ data inputs, n select lines and one output. The select code routes the input with the same number to the output; a 4-to-1 MUX gives Y = S₁′S₀′I₀ + S₁′S₀I₁ + S₁S₀′I₂ + S₁S₀I₃. Larger MUXes are built as trees (two 4-to-1 MUXes and a 2-to-1 MUX make an 8-to-1). Most MUX ICs also have an active-low enable.

MUX as a function generator. A 2ⁿ-to-1 MUX implements any function of n variables directly (put the variables on the select lines and tie each data input to 0 or 1 from the truth table). More efficiently, it implements any function of n + 1 variables: put n variables on the select lines and feed each data input with 0, 1, the remaining variable or its complement.

Demultiplexer. The reverse of a MUX: one input routed to one of 2ⁿ outputs chosen by n select lines. A decoder with an enable input acts as a demultiplexer when the enable is used as the data input.

Decoder. An n-to-2ⁿ line decoder activates exactly one output, the one whose number equals the binary input (each output is one minterm). Uses: memory and I/O address decoding, driving one-of-n loads, and building any function by OR-ing the required minterm outputs. A BCD-to-decimal (4-to-10) decoder leaves inputs 1010–1111 unused; a BCD-to-7-segment decoder drives a display.

Encoder. The reverse of a decoder: 2ⁿ inputs, n-bit output code of the active input. A plain encoder gives a wrong code if two inputs are active together, so a priority encoder outputs the code of the highest-priority active input and usually a "valid" flag.

Adders. A half adder adds two bits: S = A ⊕ B, C = A·B. A full adder adds A, B and a carry-in; it can be built from two half adders and an OR gate. An n-bit ripple-carry adder chains n full adders, each carry-out feeding the next carry-in. It is simple but slow: in the worst case the carry ripples through every stage. A carry look-ahead adder computes all carries in parallel from generate (G = A·B) and propagate (P = A ⊕ B) signals, trading gates for speed. Subtraction uses the same adder: A − B = A + B′ + 1, with each B bit passed through an XOR controlled by a mode line that is also the initial carry-in.

Comparators. A 1-bit comparator gives A > B = A·B′, A < B = A′·B and A = B = (A ⊕ B)′. Multi-bit magnitude comparators compare from the MSB down.

Formulas

Number of select lines n = log₂(N) (N data inputs, N a power of 2; otherwise round up)

Half adder: S = A ⊕ B, C = A · B

Full adder: S = A ⊕ B ⊕ Cᵢₙ, Cₒᵤₜ = A·B + B·Cᵢₙ + Cᵢₙ·A = A·B + Cᵢₙ·(A ⊕ B)

• A, B: operand bits; Cᵢₙ: carry from the previous stage; S: sum bit; Cₒᵤₜ: carry to the next stage.

Gᵢ = Aᵢ · Bᵢ, Pᵢ = Aᵢ ⊕ Bᵢ, Cᵢ₊₁ = Gᵢ + Pᵢ · Cᵢ (carry look-ahead)

Worst-case ripple-adder delay ≈ (n − 1)·t_c + t_s for the last sum bit, n·t_c for the final carry

• n: number of stages; t_c: carry-in to carry-out delay of one full adder (s); t_s: carry-in to sum delay (s). Assumes all operand bits arrive together.

A − B = A + B′ + 1 (2's complement subtraction)

Worked examples

Example 1 (standard: 4-bit ripple adder). Add A = 1011 and B = 0110 in a 4-bit ripple-carry adder with C₀ = 0. Each full adder has t_c = 10 ns and t_s = 15 ns. Find the sum, the carry-out and the worst-case time for the result to settle.

1. Bit 0: 1 + 0 + 0 → S₀ = 1, C₁ = 0.
2. Bit 1: 1 + 1 + 0 → S₁ = 0, C₂ = 1.
3. Bit 2: 0 + 1 + 1 → S₂ = 0, C₃ = 1.
4. Bit 3: 1 + 0 + 1 → S₃ = 0, C₄ = 1.
5. Result: C₄S₃S₂S₁S₀ = 1 0001 = 17 (check: 11 + 6 = 17).
6. Worst-case delay of the last sum bit = (n − 1)·t_c + t_s = 3 × 10 + 15 = 45 ns; final carry = n·t_c = 4 × 10 = 40 ns.

Sum = 0001 with Cₒᵤₜ = 1 (that is, 17); worst-case settling time 45 ns.

Example 2 (GATE level: function from a MUX). Implement F(A, B, C) = Σm(1, 2, 4, 7) with a single 4-to-1 MUX, using A and B on the select lines (S₁ = A, S₀ = B).

1. Split the truth table into pairs of rows with the same A, B, and express F in terms of C.
2. AB = 00: m0 → 0, m1 → 1, so F = C; I₀ = C.
3. AB = 01: m2 → 1, m3 → 0, so F = C′; I₁ = C′.
4. AB = 10: m4 → 1, m5 → 0, so F = C′; I₂ = C′.
5. AB = 11: m6 → 0, m7 → 1, so F = C; I₃ = C.
6. Note that Σm(1, 2, 4, 7) is exactly the full-adder sum A ⊕ B ⊕ C, which confirms the pattern C, C′, C′, C.

I₀ = C, I₁ = C′, I₂ = C′, I₃ = C; the MUX realises F = A ⊕ B ⊕ C.

Example 3 (decoder realisation). A full adder is to be built from a 3-to-8 decoder with active-high outputs and OR gates, inputs A, B, Cᵢₙ. From the truth table, S = Σm(1, 2, 4, 7) and Cₒᵤₜ = Σm(3, 5, 6, 7).

S = OR of decoder outputs Y1, Y2, Y4, Y7; Cₒᵤₜ = OR of Y3, Y5, Y6, Y7: one decoder and two 4-input OR gates.

Common mistakes

• Swapping S₁ and S₀ (MSB and LSB of the select code), which routes the wrong input.
• Assuming an N-to-1 MUX needs N select lines; it needs log₂N.
• Forgetting active-low outputs or enables on real decoder ICs (outputs are often Y′, so NAND, not OR, combines them).
• Writing the full-adder carry as A ⊕ B ⊕ Cᵢₙ or the sum as A + B + Cᵢₙ.
• Taking the ripple-adder delay as one full-adder delay; the carry chain sets the speed.
• Using a plain encoder where two inputs can be active at once; a priority encoder is needed.

For GATE ME

Typical questions: identify the function realised by a MUX or decoder circuit, implement a three-variable function with a 4-to-1 MUX, count select lines or MUXes needed for a larger MUX, trace a full-adder or half-adder circuit, and compute worst-case delay of a ripple adder. Practise reading a MUX circuit back to its truth table, and the C/C′/0/1 method for assigning MUX inputs.

Quick check

1. How many select lines does a 32-to-1 MUX need?
2. How many 2-to-1 MUXes are needed to build a 4-to-1 MUX?
3. A half adder has A = 1, B = 1. What are S and C?
4. A 3-to-8 decoder has input 110. Which output is active?
5. In a full adder, A = 1, B = 0, Cᵢₙ = 1. What are S and Cₒᵤₜ?

Answers: 1. 5. 2. 3. 3. S = 0, C = 1. 4. Y6. 5. S = 0, Cₒᵤₜ = 1.