High yield ●●●

🔌 Combinational Circuits

Why it matters: Adders, multiplexers and decoders are asked almost every year: implement a function with a MUX or decoder, or count gates and delay.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 6 done.

Formulas

Full adder
S = A⊕B⊕Cin; Cout = AB + Cin(A⊕B)
Half adder
S = A⊕B; C = AB
Half / full subtractor
D = A⊕B (⊕Bin); Bout = A′B (+ (A⊕B)′Bin)
Look-ahead carries
Gᵢ = AᵢBᵢ; Pᵢ = Aᵢ⊕Bᵢ; Cᵢ₊₁ = Gᵢ + PᵢCᵢ
MUX
F = Σ mᵢ·Iᵢ; 2ⁿ:1 MUX has n selects and handles n + 1 variables with data inputs 0, 1, X, X′
MUXes in a tree
2ⁿ:1 from 2:1 MUXes: 2ⁿ − 1
ROM size
2^(address bits) × (data bits)
Decoder
n inputs → 2ⁿ outputs; function of n variables = OR of its minterm outputs

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Implement a function with a MUX or decoder
Find the data inputs of a 4:1 or 8:1 MUX, or the OR of decoder outputs.
★★★
What does this combinational circuit compute?
Trace the gates, build the truth table, recognise adder/subtractor/parity/comparator.
★★★
Delay or gate count of adders
Ripple versus look-ahead, number of gates, critical path through the carry chain.
★★★
Hazards, ROM/PLA size, encoder behaviour
Spot the glitch, size a ROM, read a priority encoder table.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

10 real questions from the official GATE CSE papers (2013 to 2024), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

10 questions · 0 correct of 0 attempted · marks 0 / 15

Year:
GATE 2024 CS1 · Q28MSQ1 mark
Consider the circuit shown below where the gates may have propagation delays. Assume that all signal transitions occur instantaneously and that wires have no delays. The circuit: input X goes directly to one input of an AND gate and also through an inverter (NOT gate) to the other input of the AND gate; the AND output is Y. Which of the following statements about the circuit is/are CORRECT?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q64NAT2 marks
Consider a digital logic circuit consisting of three 2-to-1 multiplexers M1, M2 and M3. X1 and X2 are inputs 0 and 1 of M1, X3 and X4 are inputs 0 and 1 of M2. A, B and C are the select lines of M1, M2 and M3 respectively; the outputs of M1 and M2 go to inputs 0 and 1 of M3, whose output is Y. For an instance of inputs X1 = 1, X2 = 1, X3 = 0 and X4 = 0, the number of combinations of A, B, C that give the output Y = 1 is ______.
GATE 2023 · Q44MCQ2 marks
A Boolean digital circuit is composed using two 4-input multiplexers (M1 and M2) and one 2-input multiplexer (M3). X₀ to X₇ are the inputs of the multiplexers M1 (X₀ to X₃) and M2 (X₄ to X₇) and could be connected to either 0 or 1. The select lines S₁S₀ of both M1 and M2 are A and C. The outputs of M1 and M2 go to inputs 0 and 1 of M3, whose select line is B. Which one of the following set of values of (X₀, X₁, X₂, X₃, X₄, X₅, X₆, X₇) will realise the Boolean function A′ + A′C′ + AB′C?
GATE 2022 · Q40MCQ2 marks
Consider a digital display system (DDS) that displays the contents of register X. A 16-bit code word (a mode bit M, a 10-bit S-address and a 5-bit R-address) is used to load a word in X, either from S or from R. S is a 1024-word memory segment and R is a 32-word register file. Based on the value of mode bit M, T selects an input word to load in X. P and Q interface with the corresponding bits in the code word to choose the addressed word. Which one of the following represents the functionality of P, Q, and T?
GATE 2021 Set 2 · Q5MCQ1 mark
Which one of the following circuits implements the Boolean function f(x, y, z) = m₀ + m₁ + m₃ + m₄ + m₅ + m₆, where mᵢ is the iᵗʰ minterm? Each option is a 4×1 multiplexer with select lines S₁ = y and S₀ = z and data inputs I₀ I₁ I₂ I₃ connected as follows.
GATE 2016 Set 2 · Q7NAT1 mark
Consider an eight-bit ripple-carry adder for computing the sum of A and B, where A and B are integers represented in 2′s complement form. If the decimal value of A is one, the decimal value of B that leads to the longest latency for the sum to stabilize is ______.
GATE 2016 Set 1 · Q30MCQ2 marks
Consider the two cascaded 2-to-1 multiplexers. The first MUX has data inputs 0 (input 0) and R (input 1), and select line P. The second MUX has data inputs R′ (input 0) and the output of the first MUX (input 1), and select line Q; its output is X. The minimal sum of products form of the output X is
GATE 2014 Set 3 · Q8MCQ1 mark
Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.
f(x, y, a, b) {
  if (x is 1) y = a;
  else y = b;
}
Which one of the following digital logic blocks is the most suitable for implementing this function?
GATE 2014 Set 1 · Q45MCQ2 marks
Consider the 4-to-1 multiplexer with two select lines S₁ and S₀. Data inputs are I₀ = 0, I₁ = 1, I₂ = R, I₃ = R′. The select lines are S₁ = P and S₀ = Q. The minimal sum-of-products form of the Boolean expression for the output F of the multiplexer is
GATE 2013 Code A · Q5MCQ1 mark
In the following truth table, V = 1 if and only if the input is valid. Inputs D₀ D₁ D₂ D₃, outputs X₀ X₁ V: 0000 → x x 0; 1000 → 0 0 1; x100 → 0 1 1; xx10 → 1 0 1; xxx1 → 1 1 1. What function does the truth table represent?

Common traps

You may wire any variables to the select lines, but the data inputs (0, 1, X, X′) depend on that choice, so recompute them if you change it.
A decoder's outputs are minterms: complemented-output decoders need NAND, not OR.
In a ripple adder the carry chain, not the sum, is the critical path.
A static hazard appears for a single input change between adjacent 1s; it is not a logic error, so the truth table still looks right.