Adders, Multiplexers and Decoders for GATE: Combinational Circuits with Solved Examples

Combinational circuits for GATE: half and full adders, ripple carry delay, carry lookahead, building functions with a MUX or decoder, traps and practice questions.

In the K-map post we learnt to shrink a Boolean expression down to its smallest form. Now we put that skill to work. A combinational circuit is one whose output depends only on its present inputs, with no memory of the past. Adders, multiplexers and decoders are the three families GATE asks about most, and each one is just a small, well-chosen Boolean function.

Questions on these come up every year in GATE EC, and often in EE and CS too. Most are about delay, gate counts, or building one function out of a MUX or a decoder. Let's go through each block and the shortcuts that go with it.

The half adder

Adding two single bits $A$ and $B$ gives a sum bit and a carry bit:

$A$ $B$ Sum $S$ Carry $C$ ------------ 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1

Read the columns straight off the table:

One XOR gate and one AND gate. It's called a half adder because it can't accept a carry coming in from a previous stage.

The full adder

A full adder adds three bits: $A$, $B$ and a carry-in $C{in}$. Its outputs are

The carry-out is simply a majority function: it's 1 whenever at least two of the three inputs are 1. Put the eight rows on a K-map and you'll find exactly those three groups.

The neat way to build one is from two half adders and an OR gate:

Here the carry comes out as $C{out} = AB + C{in}(A \oplus B)$. That looks different from the majority form, but it's the same function. GATE likes to offer both, so be ready to recognise either one.

Adding n bits: ripple carry and its delay

To add two 4-bit numbers, chain four full adders. Each stage's carry-out feeds the next stage's carry-in:

This is a ripple carry adder. It's simple, but the last stage can't finish until the carry has rippled through every stage before it. If each full adder takes $tc$ to produce its carry and $ts$ to produce its sum, then

This formula is behind a large share of the adder questions in GATE.

Carry lookahead: making the carry fast

The fix is to work out every carry directly from the inputs, without waiting. For each bit, define

A stage generates a carry on its own when both inputs are 1. It passes an incoming carry along when exactly one input is 1. So

Expand this and every carry becomes a two-level AND-OR expression of the $G$s, $P$s and $C0$. For example,

With enough gate inputs, every carry is ready after the same small, fixed delay, however wide the adder. The price is more gates, and gates with many inputs. Here's the difference, counting gate delays:

The ripple adder's delay grows with $n$, while the lookahead adder's stays flat. In practice, very wide adders use lookahead in blocks of four bits, which keeps gate sizes sensible.

Subtraction with the same adder

Subtraction in 2's complement is addition in disguise:

So you feed $B$ through XOR gates controlled by a mode line $M$ and connect $M$ to the carry-in as well. With $M = 0$ the XOR gates pass $B$ unchanged and the circuit adds. With $M = 1$ they invert $B$, the carry-in adds the 1, and the circuit subtracts. One adder does both jobs.

The multiplexer

A multiplexer (MUX) is a data selector. A $2^n : 1$ MUX has $2^n$ data inputs, $n$ select lines and one output. The select lines pick which input reaches the output. For a 2:1 MUX,

and for a 4:1 MUX with selects $S1 S0$,

Any function from a MUX

This is the GATE favourite. A $2^{n-1} : 1$ MUX can build any function of $n$ variables. Put $n - 1$ variables on the select lines, and feed each data input with 0, 1, the last variable, or its complement.

Take $F(A, B, C) = \sum m(1, 2, 6, 7)$ with a 4:1 MUX, $A$ and $B$ on the selects. Look at the rows in pairs:

$A\,B$ rows $F$ on those rows data input ------------ 0 0 0, 1 0, 1 $I0 = C$ 0 1 2, 3 1, 0 $I1 = \bar{C}$ 1 0 4, 5 0, 0 $I2 = 0$ 1 1 6, 7 1, 1 $I3 = 1$

Four inputs, and the whole function is built. No K-map needed.

Building bigger MUXes

To build an $N:1$ MUX from 2:1 MUXes, you need $N - 1$ of them, arranged as a tree. From 4:1 MUXes, a 16:1 needs four in the first level and one more to choose between them, so five in all.

Decoders and encoders

A decoder with $n$ inputs has $2^n$ outputs, and exactly one output is high at a time, the one whose number matches the input. In other words, each output is one minterm. That makes a decoder another way to build any function: take a 3-to-8 decoder and OR together the outputs for the function's minterms. For our $F = \sum m(1, 2, 6, 7)$, that's a 4-input OR gate on outputs 1, 2, 6 and 7.

A decoder with an enable input doubles as a demultiplexer: the enable becomes the data line, and the inputs choose which output it goes to. Bigger decoders are built from smaller ones with enables. A 4-to-16 decoder needs four 2-to-4 decoders for the outputs and one more to drive their enables, five in all.

An encoder does the reverse, turning one active input line into its binary number. A priority encoder handles several active inputs by reporting the highest-priority one, which is why it's used for interrupt requests.

Common traps in GATE questions

These are the mistakes I see most often.

Counting the ripple delay one stage off. The carry-out needs $n\,tc$, but the last sum needs only $(n - 1)\,tc + ts$. Treating a half adder as a full adder. It has no carry-in, so it can't be the first stage of a subtractor or a chained stage. Wrong MUX input order. The select lines, read as a binary number, pick the input: $S1 S0 = 10$ selects $I2$, not $I1$. Check which variable is the most significant select. MUX tree counts. An $N:1$ MUX needs $N - 1$ 2:1 MUXes, not $N/2$ or $\log2 N$. Forgetting that decoder outputs can be active-low. If the outputs are active-low, combine them with a NAND gate, not an OR gate. Missing the enable level. Many decoder chips enable on a 0. Read the bubble on the diagram. Assuming lookahead is free. It's faster, but it needs more gates, and gates with many inputs.

Practice questions

Give yourself about two minutes each.

What are the outputs of a full adder when $A = 1$, $B = 1$ and $C{in} = 1$? A 4-bit ripple carry adder uses full adders with a carry delay of 10 ns and a sum delay of 15 ns. When is the final sum bit ready? How many 2:1 MUXes are needed to build a 32:1 MUX? Build $F = A \oplus B$ from a single 2:1 MUX with $A$ on the select line. How many 2-to-4 decoders with enable are needed to build a 4-to-16 decoder? A 4:1 MUX has $S1 = A$, $S0 = B$ and inputs $I0 = 1$, $I1 = C$, $I2 = 0$, $I3 = \bar{C}$. Write $F(A, B, C)$ as a sum of minterms.

Answers

$S = 1$ and $C{out} = 1$, since $1 + 1 + 1 = 112$. $(4 - 1) \times 10 + 15 = 45$ ns. $32 - 1 = 31$. $I0 = B$ and $I1 = \bar{B}$. When $A = 0$ the output is $B$, and when $A = 1$ it's $\bar{B}$. Five: four for the sixteen outputs and one to enable them. $AB = 00$ gives rows 0 and 1, $AB = 01$ with $C = 1$ gives row 3, and $AB = 11$ with $C = 0$ gives row 6. So $F = \sum m(0, 1, 3, 6)$.

If question 6 slowed you down, redo the pairing table from the MUX section in reverse: each data input tells you which of its two rows are 1. Next time we'll leave combinational logic and meet circuits with memory: latches and flip-flops. Tell me in the comments which question took you longest.