GATE EC · EE · IN

Combinational circuits

Arithmetic circuits, multiplexers, decoders, code converters

A combinational circuit has no memory: its outputs depend only on the inputs present now. Adders, subtractors, comparators, multiplexers, decoders, encoders, code converters and ROM/PLA logic are all built this way. The procedures below cover the common tasks: naming the function a MUX or decoder network implements, building a given function from these blocks, counting blocks or ROM bits, and finding the worst-case delay of an adder or gate network.

12 previous-year questions · 12 solved · 5 practice questions

Conventions, half and full adders, subtractors

Conventions used in these notes. Positive logic (1 = HIGH). The complement of $A$ is written with an overline, $\overline{A}$ . A multi-bit word is written MSB first, $A = A_{n - 1} \dots A_{1} A_{0}$ , where $A_{0}$ is the LSB. Signed numbers are in 2's complement unless stated otherwise. $\oplus$ is XOR, $⊙$ is XNOR, $+$ is OR, and writing variables side by side means AND. Gate delays are propagation delays $t_{p d}$ as defined in the last section.

A combinational circuit has no memory. Every output is a Boolean function of the present inputs only, so a truth table describes it completely. A sequential circuit is different: its outputs also depend on stored state. The basic arithmetic cells are the half adder, which adds two bits, and the full adder, which adds two bits and an incoming carry. The subtractor cells work the same way but produce a borrow instead of a carry.

HALF ADDER

S = A \oplus B, C = A B

Adds two 1-bit inputs and has no carry-in. A full adder with $C_{in} = 0$ reduces to this.

FULL ADDER

S = A \oplus B \oplus C_{in}, C_{o u t} = A B + B C_{in} + A C_{in} = A B + C_{in} (A \oplus B)

$S$ is 1 when an odd number of the three inputs are 1. $C_{o u t}$ is the 3-input majority function. Use the second form of $C_{o u t}$ when the adder is built from two half adders.

HALF SUBTRACTOR (COMPUTES A − B)

D = A \oplus B, B_{o} = \overline{A} B

A borrow occurs only when the minuend $A = 0$ and the subtrahend $B = 1$ .

FULL SUBTRACTOR (A MINUS B MINUS BORROW-IN)

D = A \oplus B \oplus B_{in}, B_{o u t} = \overline{A} B + \overline{A} B_{in} + B B_{in} = \overline{A} B + B_{in} \overline{(A \oplus B)}

Computes $A - B - B_{in}$ . The difference has the same expression as the full-adder sum. The borrow is the majority function of $\overline{A}$ , $B$ and $B_{in}$ . The complement goes on the minuend $A$ .

Full adder from half adders. Two half adders and one OR gate make a full adder. The first half adder gives $A \oplus B$ and $A B$ . The second adds $C_{in}$ to $A \oplus B$ and gives $S$ and $C_{in} (A \oplus B)$ . ORing the two carries gives $C_{o u t}$ .

Truth table: full adder (A plus B plus carry-in) and full subtractor (A minus B minus borrow-in)

A	B	$C_{in}$ or $B_{in}$	S	$C_{o u t}$	D	$B_{o u t}$
0	0	0	0	0	0	0
0	0	1	1	0	1	1
0	1	0	1	0	1	1
0	1	1	0	1	0	1
1	0	0	1	0	1	0
1	0	1	0	1	0	0
1	1	0	0	1	0	0
1	1	1	1	1	1	1

EXAM TIP

With an odd number of inputs, an XNOR chain equals the XOR of the same inputs, so $A ⊙ B ⊙ C = A \oplus B \oplus C$ and the full-adder sum can be written either way. With an even number of inputs the two differ by a complement. Minimum counts of 2-input NAND gates: 5 for a half adder, 9 for a full adder. The same counts hold for 2-input NOR gates.

EXAM TIP

Do not copy the carry expression into the borrow. The half-subtractor borrow is $\overline{A} B$ , not $A \overline{B}$ . The complement sits on the minuend, the number being subtracted from.

Multi-bit adders: ripple carry, carry look-ahead, add/subtract

An n-bit ripple-carry adder (RCA) is a chain of n full adders. The carry $C_{i + 1}$ out of stage $i$ is the carry-in of stage $i + 1$ , and $C_{0}$ is the external carry-in. If there is no external carry-in, stage 0 can be a half adder. The circuit is small but slow. In the worst case a carry generated in stage 0 has to ripple through every later stage, as in $1111 + 0001$ with $C_{0} = 0$ .

RIPPLE-CARRY ADDER DELAY

T_{R C A} = (n - 1) t_{c} + max (t_{c}, t_{s})

$t_{c}$ is a stage's delay from $C_{in}$ to $C_{o u t}$ , and $t_{s}$ is its delay from $C_{in}$ to $S$ . $C_{n}$ settles at $n t_{c}$ and $S_{n - 1}$ at $(n - 1) t_{c} + t_{s}$ . The formula assumes all $A_{i}$ , $B_{i}$ and $C_{0}$ are applied at $t = 0$ and each stage's $A_{i} \oplus B_{i}$ is ready before its carry arrives. If stage 0 is slower from $A, B$ than from $C_{in}$ , which is the case in a gate-level full adder, compute arrival times directly (see the worked example).

A carry look-ahead adder (CLA) removes the ripple. Stage $i$ generates a carry when $A_{i} = B_{i} = 1$ , whatever $C_{i}$ is. It propagates an incoming carry when exactly one of $A_{i}, B_{i}$ is 1. Expanding $C_{i + 1} = G_{i} + P_{i} C_{i}$ recursively gives every carry directly in terms of the $P$ s, the $G$ s and $C_{0}$ , so once the $P$ s and $G$ s are ready, all carries settle after the same two gate levels.

GENERATE, PROPAGATE, CARRY AND SUM

G_{i} = A_{i} B_{i}, P_{i} = A_{i} \oplus B_{i}, C_{i + 1} = G_{i} + P_{i} C_{i}, S_{i} = P_{i} \oplus C_{i}

Defining $P_{i} = A_{i} + B_{i}$ gives the same carries, but then $S_{i} \neq = P_{i} \oplus C_{i}$ whenever $A_{i} = B_{i} = 1$ . The XOR definition lets the sum reuse $P_{i}$ .

LOOK-AHEAD CARRIES (4-BIT)

C_{1} C_{2} C_{3} C_{4} = G_{0} + P_{0} C_{0} = G_{1} + P_{1} G_{0} + P_{1} P_{0} C_{0} = G_{2} + P_{2} G_{1} + P_{2} P_{1} G_{0} + P_{2} P_{1} P_{0} C_{0} = G_{3} + P_{3} G_{2} + P_{3} P_{2} G_{1} + P_{3} P_{2} P_{1} G_{0} + P_{3} P_{2} P_{1} P_{0} C_{0}

Each carry is a two-level SOP of $P$ , $G$ and $C_{0}$ . $C_{i}$ has $i + 1$ product terms, and the largest has $i + 1$ literals.

CLA DELAY

t_{carry} = 3 gate delays, t_{sum} = 4 gate delays

Measured from the operand inputs: 1 level for $P_{i}, G_{i}$ , 2 levels (AND then OR) for every carry, and 1 XOR for every sum. This assumes every gate, XOR included, has unit delay and unlimited fan-in. The depth does not grow with $n$ , but $C_{n}$ needs $(n + 1)$ -input gates, so wide adders are built from 4-bit CLA blocks.

GROUP GENERATE AND PROPAGATE (4-BIT BLOCK)

G_{3 : 0} = G_{3} + P_{3} G_{2} + P_{3} P_{2} G_{1} + P_{3} P_{2} P_{1} G_{0}, P_{3 : 0} = P_{3} P_{2} P_{1} P_{0}, C_{4} = G_{3 : 0} + P_{3 : 0} C_{0}

$G_{3 : 0} = 1$ when the block produces a carry by itself, and $P_{3 : 0} = 1$ when it passes its carry-in straight through. A second-level look-ahead unit combines the group $G$ and $P$ of four blocks with the same equations as the first level, giving $C_{4}$ , $C_{8}$ , $C_{12}$ and $C_{16}$ without ripple.

CLA CARRY-LOGIC GATE COUNT (N BITS)

N_{A N D} = \frac{n ( n + 1 )}{2}, N_{O R} = n

Counts the gates that form $C_{1} \dots C_{n}$ from $P$ , $G$ and $C_{0}$ . $C_{i}$ needs $i$ AND gates, because its $G_{i - 1}$ term needs none, plus one $(i + 1)$ -input OR gate. The count leaves out the n AND gates for $G$ and the n XOR gates for $P$ . For $n = 4$ : 10 AND and 4 OR.

Adder–subtractor. In 2's complement, $A - B = A + \overline{B} + 1$ (modulo $2^{n}$ ). One n-bit adder and n XOR gates can do both operations. A mode line $M$ is XORed with every $B_{i}$ , which passes $B$ unchanged when $M = 0$ and inverts it when $M = 1$ . $M$ also drives $C_{0}$ , which supplies the $+ 1$ . Below, $Y_{i} = B_{i} \oplus M$ is the operand bit that actually enters the adder.

ADDER–SUBTRACTOR

Y_{i} = B_{i} \oplus M, C_{0} = M : M = 0 \Rightarrow A + B, M = 1 \Rightarrow A + \overline{B} + 1 = A - B

Signed or unsigned operands use the same hardware. Only the reading of the flags differs.

SIGNED OVERFLOW (2'S COMPLEMENT)

V = C_{n} \oplus C_{n - 1} = \overline{A_{n - 1}} \overline{Y_{n - 1}} S_{n - 1} + A_{n - 1} Y_{n - 1} \overline{S_{n - 1}}

$Y = B \oplus M$ is the operand actually entering the adder, not $B$ itself. Overflow is possible only when both addends have the same sign, and it occurs when the sign of the sum differs from theirs.

NUMBER RANGES (N BITS)

signed: - 2^{n - 1} \leq x \leq 2^{n - 1} - 1, unsigned: 0 \leq x \leq 2^{n} - 1

The sum of two n-bit unsigned numbers can need $n + 1$ bits, because it can reach $2^{n + 1} - 2$ .

UNSIGNED SUBTRACTION FLAG

C_{n} = 1 ⟺ A \geq B

Applies when $A - B$ is computed as $A + \overline{B} + 1$ on unsigned operands. $C_{n} = 0$ means a borrow, and the n-bit result is then the 2's complement of $B - A$ .

BCD ADDER CORRECTION

K = C_{4} + Z_{3} Z_{2} + Z_{3} Z_{1}; K = 1 \Rightarrow add 0110, decimal carry = K

$Z_{3} Z_{2} Z_{1} Z_{0}$ and $C_{4}$ come from a 4-bit binary adder adding two BCD digits and a carry-in. $K$ detects binary sums of 10 to 19. The maximum sum is $9 + 9 + 1 = 19$ . A second 4-bit adder adds $0 K K 0$ to $Z_{3} Z_{2} Z_{1} Z_{0}$ ; its own carry-out is ignored, and the decimal carry is $K$ .

ARRAY MULTIPLIER (UNSIGNED N-BIT × M-BIT)

product width = n + m, nm AND gates, (m - 1) n-bit adders

The AND gates form the partial products $A_{i} B_{j}$ , and the adders sum the shifted partial-product rows. A 2-bit × 2-bit multiplier needs 4 AND gates and one 2-bit adder, which reduces to 2 half adders because nothing enters its carry-in.

WORKED EXAMPLE · RIPPLE CARRY VS CARRY LOOK-AHEAD DELAY

A 4-bit adder is built from XOR gates (4 ns), AND gates (3 ns) and OR gates (3 ns). The AND and OR delays are the same at any fan-in. Every stage forms $P_{i} = A_{i} \oplus B_{i}$ and $G_{i} = A_{i} B_{i}$ , and $S_{i} = P_{i} \oplus C_{i}$ . All operand bits and $C_{0}$ arrive at $t = 0$ . Find the worst-case delay of (a) a ripple-carry adder with $C_{i + 1} = G_{i} + P_{i} C_{i}$ , and (b) a carry look-ahead adder that forms every carry as a two-level SOP of $P$ , $G$ and $C_{0}$ .

Solution

In every stage $G_{i}$ is ready at 3 ns and $P_{i}$ at 4 ns.
(a) Stage 0: $P_{0} C_{0}$ is ready at $4 + 3 = 7$ ns, so $C_{1} = G_{0} + P_{0} C_{0}$ is ready at $7 + 3 = 10$ ns.
(a) In stage $i \geq 1$ , $P_{i}$ and $G_{i}$ are already stable when $C_{i}$ arrives, so each carry adds one AND and one OR: $C_{i + 1} = C_{i} + 6$ ns. That gives $C_{2} = 16$ , $C_{3} = 22$ , $C_{4} = 28$ ns.
(a) Sums: $S_{0} = P_{0} \oplus C_{0}$ at 8 ns, $S_{1}$ at 14, $S_{2}$ at 20, $S_{3}$ at $22 + 4 = 26$ ns. Worst case $= max (26, 28) = 28$ ns, set by $C_{4}$ .
(b) Every AND term in the look-ahead expressions contains at least one $P$ , so the AND outputs settle at $4 + 3 = 7$ ns and the ORs at 10 ns. All of $C_{1}$ to $C_{4}$ are ready at 10 ns.
(b) Each sum $S_{i} = P_{i} \oplus C_{i}$ is ready at $10 + 4 = 14$ ns, and so is the whole adder.
For comparison, a 16-bit ripple adder with these gates settles at $6 \cdot 16 + 4 = 100$ ns. A single-level 16-bit CLA would still take 14 ns but needs 17-input gates.

Answer: (a) Ripple carry: 28 ns, set by $C_{4}$ ( $S_{3}$ is ready at 26 ns). (b) Carry look-ahead: 14 ns, set by the sums (the carries are ready at 10 ns).

EXAM TIP

Overflow and carry mean different things. For unsigned addition the carry-out $C_{n}$ is the overflow. For signed 2's-complement addition, use $V = C_{n} \oplus C_{n - 1}$ and ignore $C_{n}$ . Adding two numbers of opposite sign can never overflow.

EXAM TIP

When a question gives gate delays, draw each stage and write an arrival time at every node. Stage 0 often has a different delay from the others, because its carry path starts at $A_{0}, B_{0}$ through an XOR. The later stages all add the same $C_{in} \to C_{o u t}$ delay.

Comparators, parity generators and code converters

A magnitude comparator decides whether $A > B$ , $A = B$ or $A < B$ for unsigned words. It scans from the MSB down: the most significant bit position in which the two words differ decides the result.

1-BIT COMPARATOR

(A > B) = A \overline{B}, (A < B) = \overline{A} B, (A = B) = \overline{A \oplus B}

Exactly one of the three outputs is 1 for any input.

4-BIT MAGNITUDE COMPARATOR

x_{i} (A > B) (A < B) = \overline{A_{i} \oplus B_{i}}, (A = B) = x_{3} x_{2} x_{1} x_{0} = A_{3} \overline{B_{3}} + x_{3} A_{2} \overline{B_{2}} + x_{3} x_{2} A_{1} \overline{B_{1}} + x_{3} x_{2} x_{1} A_{0} \overline{B_{0}} = \overline{A_{3}} B_{3} + x_{3} \overline{A_{2}} B_{2} + x_{3} x_{2} \overline{A_{1}} B_{1} + x_{3} x_{2} x_{1} \overline{A_{0}} B_{0}

Unsigned operands, with $A_{3}$ and $B_{3}$ as the MSBs. $x_{i} = 1$ when bit $i$ of the two words is equal.

A parity generator appends one bit so that the transmitted word has an even number of 1s (even parity) or an odd number (odd parity). The checker at the receiver XORs all the received bits, parity bit included.

PARITY GENERATOR

P_{E} = D_{n - 1} \oplus \dots \oplus D_{1} \oplus D_{0}, P_{O} = \overline{P_{E}}

$P_{E}$ makes the total count of 1s in data plus parity even. $P_{O}$ makes it odd.

PARITY CHECKER

E = P \oplus D_{n - 1} \oplus \dots \oplus D_{0}

In an even-parity system, $E = 1$ flags an error. In an odd-parity system, $E = 0$ flags one. The check detects any odd number of bit errors, misses any even number, and cannot locate the bit in error.

A code converter is a multi-output combinational circuit. Write the truth table from input code to output code, mark unused input combinations as don't-cares, and minimise each output bit. Binary↔Gray conversion needs only XOR gates. A BCD-to-7-segment decoder has 4 inputs, 7 outputs (segments a to g) and 6 don't-care inputs (1010 to 1111). On a common-cathode display a segment lights when driven with 1, so the outputs are active-high. On a common-anode display it lights when driven with 0, so every output is complemented.

BINARY TO GRAY

G_{n - 1} = B_{n - 1}, G_{i} = B_{i + 1} \oplus B_{i} (i = n - 2, \dots, 0)

This is the same as XORing the binary word with a copy of itself shifted right by one place. Needs n − 1 XOR gates, all working in parallel.

GRAY TO BINARY

B_{n - 1} = G_{n - 1}, B_{i} = B_{i + 1} \oplus G_{i} = G_{n - 1} \oplus G_{n - 2} \oplus \dots \oplus G_{i}

Each binary bit is the running XOR of the Gray bits from the MSB down. Built as a chain, the delay is up to n − 1 XOR delays.

BCD TO EXCESS-3

E_{3} E_{2} E_{1} E_{0} = B_{3} B_{2} B_{1} B_{0} + 0011

Applied to each BCD digit, valid for digits 0 to 9. Excess-3 is self-complementing: complementing every bit of a digit's Excess-3 code gives the Excess-3 code of its 9's complement.

BCD TO 7-SEGMENT, SEGMENT A

a = B_{3} + B_{1} + B_{2} B_{0} + \overline{B_{2}} \overline{B_{0}}

Input $B_{3} B_{2} B_{1} B_{0}$ is 8421 BCD with $B_{3}$ the MSB. Segments are active-high and 1010 to 1111 are don't-cares. Segment a is off only for digits 1 and 4. This assumes 6 is drawn with segment a.

Codes for the decimal digits. Segments: a top, b upper right, c lower right, d bottom, e lower left, f upper left, g middle. 6 is drawn with a, 9 with d, and 7 without f.

Decimal	8421 BCD	Excess-3	Gray (4-bit)	Segments on
0	0000	0011	0000	a b c d e f
1	0001	0100	0001	b c
2	0010	0101	0011	a b d e g
3	0011	0110	0010	a b c d g
4	0100	0111	0110	b c f g
5	0101	1000	0111	a c d f g
6	0110	1001	0101	a c d e f g
7	0111	1010	0100	a b c
8	1000	1011	1100	a b c d e f g
9	1001	1100	1101	a b c d f g

EXAM TIP

The two Gray conversions run in opposite directions. Binary to Gray XORs neighbouring binary bits. Gray to binary XORs each Gray bit with the binary bit just found above it, not with the next Gray bit. In the full n-bit reflected Gray code, consecutive codes differ in exactly one bit, and so do the last and first of all $2^{n}$ codes. A shortened list is not cyclic: in the table above, 9 (1101) and 0 (0000) differ in three bits.

Multiplexers and demultiplexers

A $2^{n} : 1$ multiplexer (data selector) has $2^{n}$ data inputs $I_{0} \dots I_{2^{n} - 1}$ , $n$ select lines $S_{n - 1} \dots S_{0}$ and one output. $S_{n - 1}$ is the MSB of the select code, and $I_{k}$ reaches the output when the select code equals $k$ . In AND–OR form it uses $2^{n}$ AND gates with $n + 1$ inputs each, one OR gate with $2^{n}$ inputs, and $n$ inverters for the complemented select lines. A demultiplexer works the other way: it routes one data input $D$ to one of $2^{n}$ outputs.

2:1 AND 4:1 MUX

Y_{2 : 1} = \overline{S} I_{0} + S I_{1}, Y_{4 : 1} = \overline{S_{1}} \overline{S_{0}} I_{0} + \overline{S_{1}} S_{0} I_{1} + S_{1} \overline{S_{0}} I_{2} + S_{1} S_{0} I_{3}

$S_{1}$ is the MSB of the select code.

GENERAL MUX WITH N SELECT LINES

Y = k = 0 \sum 2^{n} - 1 m_{k} I_{k}

$m_{k}$ is the k-th minterm of the select variables and $\sum$ means OR. An enable input E, where present, multiplies the whole expression.

DEMUX WITH N SELECT LINES

Y_{k} = m_{k} \cdot D, k = 0, 1, \dots, 2^{n} - 1

$m_{k}$ is the k-th minterm of the select lines. A 1: $2^{n}$ DEMUX is the same circuit as an n-to- $2^{n}$ decoder whose enable input carries the data.

MUX TREE

N_{MUX} = ⌈ \frac{N - 1}{k - 1} ⌉ (k:1 MUXes to build an N:1 MUX)

N and k are powers of 2. Each k:1 MUX cuts the number of candidate signals by at most k − 1. When N is a power of k the division is exact and the MUXes form a full tree: 16:1 from 4:1 needs 4 + 1 = 5, 8:1 from 2:1 needs 7, 64:1 from 4:1 needs 21. Otherwise the last MUX has unused inputs: 32:1 from 4:1 needs 8 + 2 + 1 = 11. The same count holds for a 1:N DEMUX built from 1:k DEMUXes.

Because the output is $\sum m_{k} I_{k}$ , a $2^{n} : 1$ MUX with only 0 and 1 on its data inputs implements any function of its $n$ select variables: the data inputs are simply the truth-table column. If the data inputs can also take one more variable or its complement, the MUX implements any function of $n + 1$ variables. So an n-variable function needs only a $2^{n - 1} : 1$ MUX.

Implementing an n-variable function on a MUX with n − 1 select lines

Put $n - 1$ of the variables on the select lines, keeping their order: the most significant of them goes on the highest select line. Call the remaining variable $X$ .
For each select code $k$ , find the two minterms of $F$ that share it. They differ only in $X$ . If $X$ is the LSB they are $m_{2 k}$ ( $X = 0$ ) and $m_{2 k + 1}$ ( $X = 1$ ). If $X$ is the MSB they are $m_{k}$ ( $X = 0$ ) and $m_{k + 2^{n - 1}}$ ( $X = 1$ ).
Set $I_{k} = 0$ if neither minterm is in $F$ , $1$ if both are, $X$ if only the one with $X = 1$ is, and $\overline{X}$ if only the one with $X = 0$ is.
For any other choice of $X$ , or as a check, use an implementation table: two rows ( $X = 0$ and $X = 1$ ), one column per data input, and every minterm written in the cell for its own $X$ value and select code. Mark the minterms of $F$ and read each column by the rule above.
Set don't-care minterms to 0 or 1, whichever makes a data input a constant.

WORKED EXAMPLE · A 4-VARIABLE FUNCTION ON AN 8:1 MUX

Implement $F (A, B, C, D) = \sum m (1, 3, 4, 11, 12, 13, 14, 15)$ with an 8:1 MUX. Use $S_{2} S_{1} S_{0} = A B C$ ( $A$ is the MSB) and put $D$ , $\overline{D}$ , 0 or 1 on the data inputs.

Solution

With $S_{2} S_{1} S_{0} = A B C$ , input $I_{k}$ is selected when $A B C = k$ . The two minterms sharing that code are $m_{2 k}$ ( $D = 0$ ) and $m_{2 k + 1}$ ( $D = 1$ ).
$k = 0$ : $m_{0} \in / F$ , $m_{1} \in F$ , so $I_{0} = D$ . $k = 1$ : $m_{2} \in / F$ , $m_{3} \in F$ , so $I_{1} = D$ .
$k = 2$ : $m_{4} \in F$ , $m_{5} \in / F$ , so $I_{2} = \overline{D}$ . $k = 3$ : $m_{6}, m_{7} \in / F$ , so $I_{3} = 0$ .
$k = 4$ : $m_{8}, m_{9} \in / F$ , so $I_{4} = 0$ . $k = 5$ : $m_{10} \in / F$ , $m_{11} \in F$ , so $I_{5} = D$ .
$k = 6$ : $m_{12}, m_{13} \in F$ , so $I_{6} = 1$ . $k = 7$ : $m_{14}, m_{15} \in F$ , so $I_{7} = 1$ .
Spot check: $A B C D = 0100$ ( $m_{4}$ ) selects $I_{2} = \overline{D} = 1$ , which is correct. $A B C D = 0101$ ( $m_{5}$ ) gives $\overline{D} = 0$ , also correct.

Answer: $I_{0} = D, I_{1} = D, I_{2} = \overline{D}, I_{3} = 0, I_{4} = 0, I_{5} = D, I_{6} = 1, I_{7} = 1$ . One inverter supplies $\overline{D}$ .

EXAM TIP

A 2:1 MUX is functionally complete when the constants 0 and 1 are available. NOT: $S = A$ , $I_{0} = 1$ , $I_{1} = 0$ gives $\overline{A}$ . AND: $S = A$ , $I_{0} = 0$ , $I_{1} = B$ gives $A B$ . OR: $S = A$ , $I_{0} = B$ , $I_{1} = 1$ gives $A + B$ . XOR needs a complemented input: $S = A$ , $I_{0} = B$ , $I_{1} = \overline{B}$ .

EXAM TIP

Check which variable drives which select line before you read off minterms. If the circuit puts the first-listed variable on $S_{0}$ instead of the highest select line, the index $k$ changes and the minterm list comes out wrong. For cascaded MUXes, write each MUX's output as an expression, then substitute it into the next.

Decoders and encoders

An n-to- $2^{n}$ decoder activates exactly one of its $2^{n}$ outputs: output $k$ is active when the input code equals $k$ . With active-high outputs, each output is a minterm of the inputs. A decoder plus OR gates therefore implements any set of functions of its inputs in sum-of-minterms form, with one decoder shared by all of them. An enable input $E$ gates every output. A decoder with an enable is the same circuit as a 1: $2^{n}$ demultiplexer, with $E$ as the data input and the code inputs as the select lines. Internally it uses $2^{n}$ AND gates with n inputs each ( $n + 1$ with an enable), plus n inverters.

DECODER OUTPUTS

Y_{k} = E \cdot m_{k} (active-high), \overline{Y_{k}} = \overline{E \cdot m_{k}} (active-low)

$m_{k}$ is the k-th minterm of the inputs. With $E = 1$ , an active-low output is the maxterm $M_{k} = \overline{m_{k}}$ .

FUNCTION FROM A DECODER

F = k \in F \sum Y_{k} (active-high outputs, OR gate) = \overline{k \in F \prod \overline{Y_{k}}} (active-low outputs, NAND gate) = k \in / F \prod \overline{Y_{k}} (active-low outputs of the 0-minterms, AND gate)

The decoder must be enabled. $\sum$ means OR, $\prod$ means AND, and $\overline{Y_{k}}$ is the active-low output line. A NOR gate on the active-high outputs of the 0-minterms also gives $F$ . Use the 0-minterm form when $F$ has more 1s than 0s, because the gate then needs fewer inputs.

DECODER TREE

N_{dec} = \frac{N - 1}{k - 1} (decoders with k outputs to build N outputs)

Valid when N is a power of k and each decoder has an enable input. Example: a 4:16 decoder from 2:4 decoders needs 4 + 1 = 5, with the first-level decoder driving the enables. A 3:8 decoder needs only two 2:4 decoders: the MSB drives one enable directly and the other through an inverter.

An encoder does the reverse job: it has $2^{n}$ inputs and $n$ outputs that give the index of the active input. A plain encoder assumes exactly one input is active. A priority encoder outputs the index of the highest-priority active input. It also has a valid output $V$ , because otherwise 'input 0 active' and 'no input active' both give code 0.

8:3 ENCODER (OCTAL TO BINARY)

Y_{2} = D_{4} + D_{5} + D_{6} + D_{7}, Y_{1} = D_{2} + D_{3} + D_{6} + D_{7}, Y_{0} = D_{1} + D_{3} + D_{5} + D_{7}

Valid only when exactly one input is 1. $D_{0}$ does not appear, so ' $D_{0}$ active' and 'no input active' both give 000.

4:2 PRIORITY ENCODER (D3 HIGHEST PRIORITY)

Y_{1} = D_{3} + D_{2}, Y_{0} = D_{3} + \overline{D_{2}} D_{1}, V = D_{3} + D_{2} + D_{1} + D_{0}

Active-high inputs and outputs. $V = 0$ means no input is active, and $Y_{1} Y_{0}$ should then be ignored.

EXAM TIP

A plain encoder with two active inputs outputs the bitwise OR of their codes. For example, $D_{3}$ and $D_{5}$ together give $011 + 101 = 111$ , which looks the same as $D_{7}$ alone. A priority encoder avoids this.

EXAM TIP

Before choosing the output gate, check whether the decoder outputs are active-low. Active-low outputs are maxterms, so ORing them does not give $F$ . A NAND of the 1-minterm lines does, and so does an AND of the 0-minterm lines.

ROM, PLA, PAL and the critical path

A ROM with $n$ address lines and $m$ data outputs is a combinational circuit. It is a fixed n-to- $2^{n}$ decoder (the AND array, which produces every minterm) followed by a programmable OR array. The ROM stores the truth table directly, so no minimisation is needed and it can hold any $m$ functions of $n$ variables.

ROM SIZE

ROM size = 2^{n} \times m bits

n is the number of input variables (address lines) and m the number of output functions (word length). All $2^{n}$ words count, even if some input combinations never occur.

A PLA has a programmable AND array, which forms k product terms from any inputs or their complements, and a programmable OR array, in which each output ORs any of the k terms. Outputs can share product terms, so minimise the outputs together to reduce the number of distinct terms. A PAL has a programmable AND array but a fixed OR array. Each output owns a fixed number of product terms and cannot share them.

PLA PROGRAMMABLE CONNECTIONS

N_{links} = 2 nk + k m

For n inputs, k product terms and m outputs. The AND array connects each term to any of the 2n true and complemented literals; the OR array connects each output to any term. Add m if each output has a programmable inverter.

ROM vs PLA vs PAL

Device	AND array	OR array	Product terms	Best when
ROM	Fixed (full decoder)	Programmable	All $2^{n}$ minterms, no minimisation	Dense truth tables, look-up tables, code converters
PLA	Programmable	Programmable	k chosen terms, shared among outputs	Many outputs that share product terms
PAL	Programmable	Fixed	Fixed number per output, not shared	Each output needs only a few terms

Propagation delay $t_{p d}$ of a gate is taken here as the worst-case time from an input change until the output settles, the larger of $t_{P L H}$ and $t_{P H L}$ . Some data sheets quote the average of the two, so use whichever definition the question gives. The critical path is the input-to-output path with the largest total delay. The circuit's outputs are valid only that long after the last input change.

ARRIVAL TIME AND CIRCUIT DELAY

t_{out} = i max (t_{in, i}) + t_{p d}, T = outputs max t_{out}

Apply this gate by gate from the inputs to the outputs. T is the delay along the longest path.

Finding the critical path

Give each primary input its arrival time: 0 unless stated. If complements are not available, add an inverter delay to each complemented input.
Work from the inputs towards the outputs. Each gate's output time is the latest of its input times plus that gate's $t_{p d}$ .
The largest time at any primary output is the circuit delay.
To find the critical path, trace back from that output, at each gate following the input that set the maximum.

Static hazards. Because paths have unequal delays, an output can glitch during an input change even when its final value equals its starting value. In a two-level AND–OR (SOP) circuit a static-1 hazard can occur when a single input change moves between two 1-cells of the K-map that no single product term covers. Adding the redundant consensus term that covers both cells removes it. Example: $F = A B + \overline{A} C$ can dip to 0 when $A$ changes while $B = C = 1$ ; adding $B C$ holds $F$ at 1 throughout.

EXAM TIP

ROM size counts every address, don't-cares included. A BCD-to-7-segment converter stored in ROM needs $2^{4} \times 7 = 112$ bits, even though only 10 addresses are used. In a PLA, a product term shared by two outputs counts only once.

EXAM TIP

Two-level AND–OR logic has a delay of 2 gate levels when complemented inputs are available, and 3 when inverters must be added. A NAND–NAND realisation has the same structure and depth as AND–OR.

PREVIOUS-YEAR QUESTIONS

12 questions from the EC, EE and IN papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE ECE 2026 · GATE ECE 2025 · GATE ECE 2024 · GATE ECE 2023 · GATE ECE 2022 · GATE ECE 2020 · GATE ECE 2018 · GATE EE 2024 · GATE IN 2025 · GATE IN 2022 · GATE IN 2020

GATE 2026 EC Q.48

GATE 2026 · ECQ.48 · 2 marks · MCQ

A Boolean function, $f (x, y, z)$ with $x$ as MSB and $z$ as LSB is realized by 4:1 multiplexer (MUX) with select lines, $S_{1}$ and $S_{0}$ ( $S_{1}$ is MSB, $S_{0}$ is LSB) and inputs, $I_{0}, I_{1}, I_{2}, I_{3}$ as shown in the Figure.

Which of the following options is the correct expression of $f (x, y, z)$ ?

GATE 2026 EC question 48: A 4:1 MUX block labelled '4:1 MUX' with data inputs I0, I1, I2, I3 on the left, select lines S1 and S0 at the bottom, and… — Figure from the GATE 2026 EC paper. It is part of the question.

(A)
$x z + y$
(B)
$x \overline{y} + z$
(C)
$x y + \overline{z}$
(D)
$\overline{x} y + \overline{z}$

Answer and solution

GATE 2026 EC Q.48: answer and solution

GATE 2025 EC Q.24

GATE 2025 · ECQ.24 · 1 mark · MCQ

A full adder and an XOR gate are used to design a digital circuit with inputs $X$ , $Y$ , and $Z$ , and output $F$ , as shown below. The input $Z$ is connected to the carry-in input of the full adder.

If the input $Z$ is set to logic '1', then the circuit functions as ________ with $X$ and $Y$ as inputs.

GATE 2025 EC question 24: Three inputs X, Y, Z enter from the top. — Figure from the GATE 2025 EC paper. It is part of the question.

(A)
an adder
(B)
a subtractor
(C)
a multiplier
(D)
a binary to Gray code converter

Answer and solution

GATE 2025 EC Q.24: answer and solution

GATE 2025 IN Q.17

GATE 2025 · INQ.17 · 1 mark · MCQ

The minimized expression of the Boolean function Y(P, Q, R) implemented by the multiplexer (MUX) circuit shown in the figure is

GATE 2025 IN question 17: Two multiplexers in cascade. — Figure from the GATE 2025 IN paper. It is part of the question.

(A)
$Y = R + (P \oplus Q)$
(B)
$Y = R (P \oplus Q)$
(C)
$Y = R + (\overline{P \oplus Q})$
(D)
$Y = R \oplus (P \oplus Q)$

Answer and solution

GATE 2025 IN Q.17: answer and solution

GATE 2024 EC Q.40

GATE 2024 · ECQ.40 · 2 marks · MCQ

A 4-bit priority encoder has inputs $D_{3}, D_{2}, D_{1},$ and $D_{0}$ in descending order of priority. The two-bit output $A B$ is generated as 00, 01, 10, and 11 corresponding to inputs $D_{3}, D_{2}, D_{1},$ and $D_{0}$ , respectively. The Boolean expression of the output bit $B$ is ______.

(A)
$\overline{D_{3}} \overline{D_{2}}$
(B)
$\overline{D_{3}} D_{2} + \overline{D_{3}} \overline{D_{1}}$
(C)
$D_{3} \overline{D_{2}} + \overline{D_{3}} D_{1}$
(D)
$\overline{D_{3}} \overline{D_{1}}$

Answer and solution

GATE 2024 EC Q.40: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 EC Q.40: answer and solution

GATE 2024 EC Q.41

GATE 2024 · ECQ.41 · 2 marks · MCQ

The propagation delay of the $2 \times 1$ MUX shown in the circuit is $10 ns$ . Consider the propagation delay of the inverter as $0 ns$ .

[Figure]

If S is set to 1 then the output Y is ________.

GATE 2024 EC question 41: A 2 X 1 MUX block with data inputs labelled 0 (upper) and 1 (lower), select input S at the bottom, and output Y on the… — Figure from the GATE 2024 EC paper. It is part of the question.

(A)
a square wave of frequency 100 MHz
(B)
a square wave of frequency 50 MHz
(C)
constant at 0
(D)
constant at 1

Answer and solution

GATE 2024 EC Q.41: answer and solution

GATE 2024 EE Q.26

GATE 2024 · EEQ.26 · 1 mark · MCQ

To obtain the Boolean function $F (X, Y) = X \overline{Y} + \overline{X}$ , the inputs $P QR S$ in the figure should be

GATE 2024 EE question 26: A 4:1 multiplexer drawn as a box labelled '4:1 Multiplexer'. — Figure from the GATE 2024 EE paper. It is part of the question.

(A)
1010
(B)
1110
(C)
0110
(D)
0001

Answer and solution

GATE 2024 EE Q.26: answer and solution

GATE 2023 EC Q.23

GATE 2023 · ECQ.23 · 1 mark · MCQ

In the circuit shown below, P and Q are the inputs. The logical function realized by the circuit shown below is

GATE 2023 EC question 23: A single 2 × 1 MUX block with output Y on the right. — Figure from the GATE 2023 EC paper. It is part of the question.

(A)
$Y = P Q$
(B)
$Y = P + Q$
(C)
$Y = \overline{P Q}$
(D)
$Y = \overline{P + Q}$

Answer and solution

GATE 2023 EC Q.23: answer and solution

GATE 2022 EC Q.19

GATE 2022 · ECQ.19 · 1 mark · MCQ

Consider the 2-bit multiplexer (MUX) shown in the figure. For OUTPUT to be the XOR of C and D, the values for $A_{0}$ , $A_{1}$ , $A_{2}$ , and $A_{3}$ are ________.

GATE 2022 EC question 19: A 4-to-1 multiplexer drawn as a box labelled with data inputs 0, 1, 2, 3 on its left side. — Figure from the GATE 2022 EC paper. It is part of the question.

(A)
$A_{0} = 0, A_{1} = 0, A_{2} = 1, A_{3} = 1$
(B)
$A_{0} = 1, A_{1} = 0, A_{2} = 1, A_{3} = 0$
(C)
$A_{0} = 0, A_{1} = 1, A_{2} = 1, A_{3} = 0$
(D)
$A_{0} = 1, A_{1} = 1, A_{2} = 0, A_{3} = 0$

Answer and solution

GATE 2022 EC Q.19: answer and solution

GATE 2022 IN Q.23

GATE 2022 · INQ.23 · 1 mark · MSQ

The output F of the digital circuit shown can be written in the form(s) ________

GATE 2022 IN question 23: Two 2×1 multiplexers connected in cascade. — Figure from the GATE 2022 IN paper. It is part of the question.

(A)
$\overline{A . B}$
(B)
$\overset{ˉ}{A} + \overset{ˉ}{B}$
(C)
$\overline{A + B}$
(D)
$\overset{ˉ}{A} . \overset{ˉ}{B}$

Answer and solution

GATE 2022 IN Q.23: answer and solution

GATE 2020 EC Q.10

GATE 2020 · ECQ.10 · 1 mark · MCQ

The figure below shows a multiplexer where $S_{1}$ and $S_{0}$ are the select lines, $I_{0}$ to $I_{3}$ are the input data lines, EN is the enable line, and $F (P, Q, R)$ is the output. $F$ is

GATE 2020 EC question 10: A 4-to-1 MUX block. — Figure from the GATE 2020 EC paper. It is part of the question.

(A)
$P Q + \overline{Q} R$ .
(B)
$P + Q \overline{R}$ .
(C)
$P \overline{Q} R + \overline{P} Q$ .
(D)
$\overline{Q} + P R$ .

Answer and solution

GATE 2020 EC Q.10: answer and solution

GATE 2020 IN Q.12

GATE 2020 · INQ.12 · 1 mark · MCQ

The Boolean operation performed by the following circuit at the output O is ____

GATE 2020 IN question 12: A 4:1 multiplexer ('4:1 Mux') with data inputs I_0, I_1, I_2, I_3 from top to bottom, output O on the right, and select… — Figure from the GATE 2020 IN paper. It is part of the question.

(A)
$O = S_{1} \oplus S_{0}$
(B)
$O = S_{1} \cdot \overline{S_{0}}$
(C)
$O = S_{1} + S_{0}$
(D)
$O = S_{0} \cdot \overline{S_{1}}$

Answer and solution

GATE 2020 IN Q.12: answer and solution

GATE 2018 EC Q.31

GATE 2018 · ECQ.31 · 2 marks · MCQ

A four-variable Boolean function is realized using $4 \times 1$ multiplexers as shown in the figure.

The minimized expression for $F (U, V, W, X)$ is

GATE 2018 EC question 31: Two 4x1 MUXes in cascade. — Figure from the GATE 2018 EC paper. It is part of the question.

(A)
$(U V + \overline{U} \overline{V}) \overline{W}$
(B)
$(U V + \overline{U} \overline{V}) (\overline{W} \overline{X} + \overline{W} X)$
(C)
$(U \overline{V} + \overline{U} V) \overline{W}$
(D)
$(U \overline{V} + \overline{U} V) (\overline{W} \overline{X} + \overline{W} X)$

Answer and solution

GATE 2018 EC Q.31: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · NAT

A ROM implements a combinational circuit that multiplies two 4-bit unsigned binary numbers and outputs the full product. The minimum ROM size, in bits, is ______.

Answer and solution

Answer: $2048$

The circuit has $4 + 4 = 8$ input bits, so the ROM needs 8 address lines and $2^{8} = 256$ words.
The largest product is $15 \times 15 = 225$ . Since $127 < 225 \leq 255$ , the product needs exactly 8 output bits.
ROM size $= 256 \times 8 = 2048$ bits.

PRACTICE 21 mark · MCQ

A 3-to-8 decoder has inputs $A_{2} A_{1} A_{0} = X Y Z$ ( $X$ is the MSB), is permanently enabled, and has active-low outputs $\overline{Y_{0}}, \dots, \overline{Y_{7}}$ . The outputs $\overline{Y_{1}}$ , $\overline{Y_{2}}$ , $\overline{Y_{4}}$ and $\overline{Y_{7}}$ drive a 4-input NAND gate. The NAND output $F$ is

(A)
$X \oplus Y \oplus Z$
(B)
$\overline{X \oplus Y \oplus Z}$
(C)
$X Y + Y Z + X Z$
(D)
$\overline{X} \overline{Y} \overline{Z} + X Y Z$

Answer and solution

Answer: (A)

Each active-low output is $\overline{Y_{k}} = \overline{m_{k}}$ .
By De Morgan, $F = \overline{\overline{m_{1}} \overline{m_{2}} \overline{m_{4}} \overline{m_{7}}} = m_{1} + m_{2} + m_{4} + m_{7}$ .
Minterms 001, 010, 100 and 111 are exactly the inputs with an odd number of 1s, so $F = X \oplus Y \oplus Z$ .

PRACTICE 32 marks · NAT

An 8-bit ripple-carry adder is built from full adders, each made of 2-input gates as $S_{i} = (A_{i} \oplus B_{i}) \oplus C_{i}$ and $C_{i + 1} = A_{i} B_{i} + (A_{i} \oplus B_{i}) C_{i}$ . Each stage computes $A_{i} \oplus B_{i}$ once and uses it for both outputs. Gate delays are XOR 3 ns, AND 2 ns, OR 2 ns. All operand bits and $C_{0}$ are applied at $t = 0$ . The minimum time, in ns, after which all eight sum bits and the final carry $C_{8}$ are guaranteed stable is ______.

Answer and solution

Answer: $35$

In every stage, $P_{i} = A_{i} \oplus B_{i}$ is ready at 3 ns and $A_{i} B_{i}$ at 2 ns.
Stage 0: $P_{0} C_{0}$ is ready at $3 + 2 = 5$ ns, so $C_{1}$ is ready at $5 + 2 = 7$ ns.
In stage $i \geq 1$ , $P_{i}$ is already stable when $C_{i}$ arrives, so $C_{i + 1} = C_{i} + 2 + 2$ . That gives $C_{i} = 4 i + 3$ ns: $C_{7} = 31$ ns and $C_{8} = 35$ ns.
The last sum, $S_{7} = P_{7} \oplus C_{7}$ , is ready at $31 + 3 = 34$ ns.
Worst case $= max (35, 34) = 35$ ns.

PRACTICE 42 marks · MSQ

A 4-bit adder–subtractor feeds $B_{i} \oplus M$ to a 4-bit ripple-carry adder and sets $C_{0} = M$ . $C_{4}$ is the carry out of the MSB stage and $C_{3}$ is the carry into it. With $A = 0110$ , $B = 1011$ and $M = 1$ , which of the following statements are correct?

(A)
The 4-bit output is $1011$ .
(B)
The signed-overflow flag $C_{4} \oplus C_{3}$ is 1.
(C)
The carry out $C_{4}$ is 1.
(D)
Reading $A$ and $B$ as unsigned numbers (6 and 11), $C_{4} = 0$ correctly signals that $A < B$ .

Answer and solution

Answer: (A), (B), (D)

With $M = 1$ the adder receives $A = 0110$ , $\overline{B} = 0100$ and $C_{0} = 1$ .
Bit 0: $0 + 0 + 1 = 1$ , carry 0. Bit 1: $1 + 0 + 0 = 1$ , carry 0. Bit 2: $1 + 1 + 0 = 0$ , carry $C_{3} = 1$ . Bit 3: $0 + 0 + 1 = 1$ , carry $C_{4} = 0$ .
The output is $1011$ , and $C_{4} \oplus C_{3} = 0 \oplus 1 = 1$ , so there is signed overflow. This is expected, because $6 - (- 5) = 11$ exceeds the 4-bit signed maximum of 7.
Unsigned: $C_{4} = 0$ means a borrow, i.e. $A < B$ , and indeed $6 < 11$ . So (A), (B) and (D) are correct, and (C) is false.

PRACTICE 52 marks · MCQ

A 4:1 multiplexer has select lines $S_{1} = A$ and $S_{0} = B$ ( $S_{1}$ is the MSB of the select code) and data inputs $I_{0} = C$ , $I_{1} = 1$ , $I_{2} = 0$ , $I_{3} = \overline{C}$ . With $A$ as the MSB of the minterm index, the output $F (A, B, C)$ is

(A)
$\sum m (1, 2, 3, 6)$
(B)
$\sum m (1, 2, 3, 7)$
(C)
$\sum m (0, 2, 3, 6)$
(D)
$\sum m (1, 4, 5, 6)$

Answer and solution

Answer: (A)

$F = \overline{A} \overline{B} C + \overline{A} B \cdot 1 + A \overline{B} \cdot 0 + A B \overline{C}$ .
$\overline{A} \overline{B} C = m_{1}$ , $\overline{A} B = m_{2} + m_{3}$ , and $A B \overline{C} = m_{6}$ .
So $F = \sum m (1, 2, 3, 6)$ . Option (D) is what you get with the select lines swapped, (B) comes from taking $I_{3} = C$ , and (C) from taking $I_{0} = \overline{C}$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE EC

arithmetic circuits, code converters, multiplexers, decoders

GATE EE

combinatorial … logic circuits, multiplexers, demultiplexers

GATE IN

Combinational logic circuits, multiplexer and demultiplexer … arithmetic circuits

Preparing in Kolkata? IAE Academy's course for GATE ECE, GATE EE or GATE IN.