chapter

Combinational Logic Circuits and Data Selectors Notes for GATE CS

Combinational Logic Circuits and Data Selectors notes for GATE CS: 31 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice

combinational logic circuits and data selectors notes

Chapter Roadmap: Combinational Logic Circuits and Data Selectors

Chapter Roadmap Combinational Logic Circuits and Data Selectors Your structured learning path to mastering digital building blocks. 1. Logic Gate Circuit Analysis and Hazards Master propagation delays, static and dynamic hazards, and timing analysis. 2. Decoders, Multiplexers and Address Selection Understand internal architecture, enable lines, and addressing logic. 3. Boolean Function Realization Using Multiplexers Implement arbitrary logic functions using minimal multiplexer hardware. 4. Cascaded Multiplexer and Decoder Circuits Analyze complex, multi-stage systems built from smaller modules. Weightage Hint: Expect ~8 questions. Mastery of MUX realization and hazard elimination is critical.

Logic Gate Circuit Analysis and Hazards

Topic Introduction Logic Gate Circuit Analysis and Hazards Bridging the gap between ideal Boolean algebra and real-world timing. What you will learn here The concept of propagation delay and how it affects circuit timing. The definition and causes of static and dynamic hazards in combinational logic. How to identify potential hazards using Karnaugh maps . The standard method for eliminating static hazards by adding redundant prime implicants . Step-by-step techniques for tracing signal transitions through delayed gates.

Propagation Delay in Logic Gates

Core Concept Propagation Delay in Logic Gates In theoretical Boolean algebra, logic gates respond instantaneously. In physical hardware, every gate introduces a time lag. Propagation Delay (t_{p d}) The time interval between a change in the input signal and the corresponding stable change in the output signal. Key Assumptions for Exam Analysis Gate Delay: Every logic gate has a specified propagation delay (t_{p d}). Wire Delay: Interconnecting wires are assumed to have zero delay . Instantaneous Transitions: Signal transitions (0 to 1, or 1 to 0) are treated as instantaneous at the boundaries of the delay period. When multiple gates are in series, their delays add up. The total delay of a path is the sum of the t_{p d} of all gates along that path.

28 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Assertion (A): When implementing the function f (x, y, z) = \sum m (0, 1, 3, 4, 5, 6) using a 4-to-1 multiplexer with y and z as select lines, the data input I_{2} is connected to the variable x . Reason (R): Minterm 2 (binary 010) is absent from the function, and minterm 6 (binary 110) is present, so the transition from 0 to 1 in the implementation table requires the MSB variable x . Which of the following is correct?

Question 2

Level 1: Warm-up

When identifying static-1 hazards in a Sum-of-Products circuit using a Karnaugh map, a hazard exists during a single-variable transition between two adjacent cells if:

Question 3

Level 1: Warm-up

Which of the following statements correctly identifies the condition for a Static-1 hazard on a Karnaugh map?

Question 4

Level 1: Warm-up

Consider the following statement: "When implementing a 3-variable Boolean function using a 4-to-1 multiplexer with the implementation table method, the data inputs can only be connected to logic 0 or logic 1." Is this statement true or false?

Question 5

Level 1: Warm-up

Which of the following statements correctly describes the possible values for data inputs when implementing an n -variable function using a 2^{n - 1} -to-1 multiplexer via the Implementation Table method?

Question 6

Level 1: Warm-up

A student claims that dynamic hazards can occur in 2-level logic circuits. According to the topic introduction, what is the minimum number of gate levels actually required for dynamic hazards to occur, contradicting this claim?

Question 7

Level 1: Warm-up

A combinational circuit exhibits momentary false outputs due to unequal propagation delays. Considering all possible hazard types (Static-1, Static-0, and Dynamic), what is the total number of distinct hazard categories?

Question 8

Level 1: Warm-up

Assertion (A): To select one of 32 words in a register file, 5 address bits are required. Reason (R): The memory size is 32 bytes, and since each byte requires 1 address bit, 32 bytes require 5 bits. Which of the following is correct?

Question 9

Level 1: Warm-up

A signal can travel from input A to output Y through two paths. Path 1 has 3 gates each of delay 2 ns. Path 2 has 2 gates each of delay 4 ns. What is the maximum propagation delay from A to Y?

Question 10

Level 1: Warm-up

Consider the following two statements about a timing analysis circuit where input A transitions at t = 0 and feeds through a NOT gate (delay 2 ns) and an AND gate (delay 3 ns) to an OR gate (delay 2 ns): Assertion (A): The output Y experiences a static-1 hazard. Reason (R): The hazard occurs because the NOT gate path (2 ns) and AND gate path (3 ns) have unequal propagation delays. Which of the following is correct?

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Combinational Logic Circuits and Data Selectors Notes for GATE CS

Combinational Logic Circuits and Data Selectors notes for GATE CS: 31 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Combinational Logic Circuits and Data Selectors

Chapter Roadmap

Combinational Logic Circuits and Data Selectors

Your structured learning path to mastering digital building blocks.

1. Logic Gate Circuit Analysis and Hazards

Master propagation delays, static and dynamic hazards, and timing analysis.

2. Decoders, Multiplexers and Address Selection

Understand internal architecture, enable lines, and addressing logic.

3. Boolean Function Realization Using Multiplexers

Implement arbitrary logic functions using minimal multiplexer hardware.

4. Cascaded Multiplexer and Decoder Circuits

Analyze complex, multi-stage systems built from smaller modules.

Weightage Hint: Expect ~8 questions. Mastery of MUX realization and hazard elimination is critical.

Logic Gate Circuit Analysis and Hazards

Topic Introduction

Logic Gate Circuit Analysis and Hazards

Bridging the gap between ideal Boolean algebra and real-world timing.

What you will learn here

The concept of propagation delay and how it affects circuit timing.
The definition and causes of static and dynamic hazards in combinational logic.
How to identify potential hazards using Karnaugh maps.
The standard method for eliminating static hazards by adding redundant prime implicants.
Step-by-step techniques for tracing signal transitions through delayed gates.

Propagation Delay in Logic Gates

Core Concept

Propagation Delay in Logic Gates

In theoretical Boolean algebra, logic gates respond instantaneously. In physical hardware, every gate introduces a time lag.

Propagation Delay ( $t_{p d}$ )

The time interval between a change in the input signal and the corresponding stable change in the output signal.

Key Assumptions for Exam Analysis

Gate Delay: Every logic gate has a specified propagation delay ( $t_{p d}$ ).
Wire Delay: Interconnecting wires are assumed to have zero delay.
Instantaneous Transitions: Signal transitions (0 to 1, or 1 to 0) are treated as instantaneous at the boundaries of the delay period.

When multiple gates are in series, their delays add up. The total delay of a path is the sum of the $t_{p d}$ of all gates along that path.

Understanding Logic Hazards

Core Concept

Understanding Logic Hazards

A hazard is a momentary, unwanted glitch (false output) in a combinational circuit caused by unequal propagation delays along different signal paths.

1. Static-1 Hazard

Condition: Output should remain at 1 during a single input change.
Glitch: Momentarily drops to 0.
Common In: Sum-of-Products (SOP) circuits.

2. Static-0 Hazard

Condition: Output should remain at 0 during a single input change.
Glitch: Momentarily spikes to 1.
Common In: Product-of-Sums (POS) circuits.

3. Dynamic Hazard

Condition: Output changes from 0 to 1 (or vice versa).
Glitch: Changes multiple times (e.g., 0 $\to$ 1 $\to$ 0 $\to$ 1) before settling.
Common In: Multi-level logic circuits (3+ gate levels).

Combinational Logic Circuits and Data Selectors: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Digital Logic MCQ

Assertion (A): When implementing the function $f (x, y, z) = \sum m (0, 1, 3, 4, 5, 6)$ using a 4-to-1 multiplexer with $y$ and $z$ as select lines, the data input $I_{2}$ is connected to the variable $x$ .

Reason (R): Minterm 2 (binary 010) is absent from the function, and minterm 6 (binary 110) is present, so the transition from 0 to 1 in the implementation table requires the MSB variable $x$ .

Which of the following is correct?

A.
Both A and R are true and R is the correct explanation of A
B.
Both A and R are true but R is NOT the correct explanation of A
C.
A is true but R is false
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Key idea: This is a construction problem testing the implementation table method with assertion-reason format.

Step 1: Verify Assertion (A):

Select lines: $S_{1} = y$ , $S_{0} = z$
For $I_{2}$ : $S_{1} S_{0} = 10$ (binary 2)
This corresponds to minterms where $y z = 10$ : minterm 2 (010) and minterm 6 (110)
Minterm 2 is absent (0), minterm 6 is present (1)
Implementation table: top=0, bottom=1 $\to$ input = MSB = $x$
Assertion A is True ✓

Step 2: Verify Reason (R):

Minterm 2 (010) is absent ✓
Minterm 6 (110) is present ✓
Transition 0→1 requires MSB variable $x$ ✓
Reason R is True ✓

Step 3: Check if R explains A:

Yes, the absence of minterm 2 and presence of minterm 6 directly leads to $I_{2} = x$

Answer: Both A and R are true, and R is the correct explanation of A (Option A)

Question 2 · Digital Logic MCQ

When identifying static-1 hazards in a Sum-of-Products circuit using a Karnaugh map, a hazard exists during a single-variable transition between two adjacent cells if:

A.
both cells contain 0 and are covered by the same prime implicant loop
B.
both cells contain 1 and are covered by the same prime implicant loop
C.
both cells contain 1 but are not covered by the same prime implicant loop
D.
both cells contain 0 but are not covered by the same prime implicant loop

Correct Answer:

Step-by-Step Solution

Key idea: Static-1 hazards occur when adjacent 1-cells are not covered by a common prime implicant.

Step 1: Recall the condition for static-1 hazards in SOP circuits:

Output should remain at 1 during transition
Both cells must contain 1

Step 2: Recall the hazard condition:

The two adjacent 1-cells must NOT be covered by the same prime implicant loop

Step 3: Combine conditions:

Both cells contain 1 AND are not in the same loop

Answer: Option C

Question 3 · Digital Logic MCQ

Which of the following statements correctly identifies the condition for a Static-1 hazard on a Karnaugh map?

A.
Two adjacent 0s not covered by the same prime implicant loop
B.
Any two 1s in the K-map that are not adjacent
C.
Two adjacent 1s not covered by the same prime implicant loop
D.
Two diagonally adjacent 1s not covered by the same loop

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question where you must identify the exact constraints for a Static-1 hazard.

Step 1: Recall that Static-1 hazards occur in SOP circuits when the output should stay at 1 but briefly drops to 0.

Step 2: On a K-map, this happens when two adjacent 1s are not covered by the same prime implicant loop.

Step 3: The constraints are:

Must be 1s (not 0s)
Must be adjacent (not diagonal or non-adjacent)
Must not be in the same loop

Step 4: Match with the options.

Answer: Option C

Question 4 · Digital Logic MCQ

Consider the following statement: "When implementing a 3-variable Boolean function using a 4-to-1 multiplexer with the implementation table method, the data inputs can only be connected to logic 0 or logic 1."

Is this statement true or false?

A.
True, because only constants are needed
B.
False, because the MSB variable or its complement may be required
C.
True, because external gates are not allowed
D.
False, because all variables must appear on data inputs

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the implementation table method constraints.

Step 1: Recall the implementation table method for $2^{n - 1}$ -to-1 MUX.

Step 2: For a 3-variable function with a 4-to-1 MUX, 2 variables are select lines, and 1 variable (MSB) determines data inputs.

Step 3: Data inputs can be: 0, 1, MSB variable, or complement of MSB variable.

Step 4: The statement says "only 0 or 1", which is false because variables can appear.

Answer: False, because the MSB variable or its complement may be required (Option B)

Question 5 · Digital Logic MCQ

Which of the following statements correctly describes the possible values for data inputs when implementing an $n$ -variable function using a $2^{n - 1}$ -to-1 multiplexer via the Implementation Table method?

A.
Any arbitrary boolean variable
B.
Only logic 0 or logic 1
C.
Logic 0, logic 1, the MSB variable, or its complement
D.
The LSB variable or its complement, but never a constant

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the constraints of the Implementation Table method.

Step 1: Recall the Implementation Table method for a $2^{n - 1}$ -to-1 MUX.

Step 2: The table compares the function values for MSB = 0 and MSB = 1.

Step 3: The possible outcomes for each column are:

(0, 0) $\to$ Logic 0
(1, 1) $\to$ Logic 1
(0, 1) $\to$ MSB variable
(1, 0) $\to$ Complement of MSB variable

Step 4: Match this with the options.

Answer: Logic 0, logic 1, the MSB variable, or its complement (Option C)

Question 6 · Digital Logic MCQ

A student claims that dynamic hazards can occur in 2-level logic circuits. According to the topic introduction, what is the minimum number of gate levels actually required for dynamic hazards to occur, contradicting this claim?

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: Dynamic hazards require multi-level circuits with at least 3 gate levels.

Step 1: Recall the definition from the topic introduction:

"Dynamic hazard: Common in multi-level logic circuits (3+ gate levels)"

Step 2: The student's claim: dynamic hazards in 2-level circuits

Step 3: The contradiction: dynamic hazards require at least 3 levels

Step 4: Minimum number of levels = 3

Answer: 3 (Option C)

Question 7 · Digital Logic MCQ

A combinational circuit exhibits momentary false outputs due to unequal propagation delays. Considering all possible hazard types (Static-1, Static-0, and Dynamic), what is the total number of distinct hazard categories?

A.
1
B.
2
C.
4
D.
3

Correct Answer:

Step-by-Step Solution

Key idea: This is a casework question asking you to count the distinct types of hazards.

Step 1: List all hazard types mentioned in the concept:

Static-1 hazard
Static-0 hazard
Dynamic hazard

Step 2: Count the total number of distinct categories.

Total = 3

Step 3: Match with the given options.

Answer: 3 (Option D)

Question 8 · Digital Logic MCQ

Assertion (A): To select one of 32 words in a register file, 5 address bits are required.

Reason (R): The memory size is 32 bytes, and since each byte requires 1 address bit, 32 bytes require 5 bits.

Which of the following is correct?

A.
Both A and R are true and R is the correct explanation of A
B.
A is true but R is false
C.
Both A and R are true but R is NOT the correct explanation of A
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing the distinction between words and bytes in memory interfacing.

Step 1: Evaluate Assertion (A): To select 1 of 32 words, we need $n$ bits where $2^{n} = 32$ . Thus, $n = 5$ . Assertion A is True.

Step 2: Evaluate Reason (R): R states the size is 32 bytes and each byte requires 1 bit. This is a unit mismatch. Address bits select words (or bytes, depending on addressing), but the calculation "32 bytes require 5 bits because each byte requires 1 bit" is logically false. The correct reasoning is $2^{5} = 32$ unique addresses.

Step 3: Conclusion: A is true, but R is false.

Answer: Option B

Question 9 · Digital Logic MCQ

A signal can travel from input A to output Y through two paths. Path 1 has 3 gates each of delay 2 ns. Path 2 has 2 gates each of delay 4 ns. What is the maximum propagation delay from A to Y?

A.
6 ns
B.
8 ns
C.
10 ns
D.
14 ns

Correct Answer:

Step-by-Step Solution

Key idea: Calculate the total delay for each path, then identify the maximum.

Step 1: Calculate delay for Path 1:

Path 1 delay = 3 gates × 2 ns/gate = 6 ns

Step 2: Calculate delay for Path 2:

Path 2 delay = 2 gates × 4 ns/gate = 8 ns

Step 3: Identify the maximum delay:

Max(6 ns, 8 ns) = 8 ns

Answer: 8 ns (Option B)

Question 10 · Digital Logic MCQ

Consider the following two statements about a timing analysis circuit where input A transitions at t = 0 and feeds through a NOT gate (delay 2 ns) and an AND gate (delay 3 ns) to an OR gate (delay 2 ns):

Assertion (A): The output Y experiences a static-1 hazard.

Reason (R): The hazard occurs because the NOT gate path (2 ns) and AND gate path (3 ns) have unequal propagation delays.

Which of the following is correct?

A.
Both A and R are true and R is the correct explanation of A
B.
Both A and R are true but R is NOT the correct explanation of A
C.
A is true but R is false
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Key idea: Analyze the timing to verify both the assertion and the reason.

Step 1: Trace the signal paths:

Path 1 (NOT): A changes at t=0, NOT output changes at t=2 ns
Path 2 (AND): A changes at t=0, AND output changes at t=3 ns

Step 2: Analyze OR gate output Y:

At t=0: Assume initial state Y=1
At t=2 ns: NOT output changes (1→0), AND output still 0, so Y=0
At t=3 ns: AND output changes (0→1), so Y=1
Y transitions: 1 → 0 → 1 (glitch)

Step 3: Verify Assertion (A):

Y should stay at 1 but glitches to 0 → Static-1 hazard ✓

Step 4: Verify Reason (R):

Unequal delays (2 ns vs 3 ns) cause the timing mismatch ✓
This unequal delay is why the glitch occurs ✓

Step 5: Check if R explains A:

Yes, the unequal delays directly cause the hazard

Answer: Both A and R are true, and R correctly explains A (Option A)

combinational logic circuits and data selectors notes

Chapter Roadmap: Combinational Logic Circuits and Data Selectors

Combinational Logic Circuits and Data Selectors

1. Logic Gate Circuit Analysis and Hazards

2. Decoders, Multiplexers and Address Selection

3. Boolean Function Realization Using Multiplexers

4. Cascaded Multiplexer and Decoder Circuits

Logic Gate Circuit Analysis and Hazards

Logic Gate Circuit Analysis and Hazards

What you will learn here

Propagation Delay in Logic Gates

Propagation Delay in Logic Gates

Propagation Delay (tpd​)

Key Assumptions for Exam Analysis

Try a question

Login to view the complete notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Combinational Logic Circuits and Data Selectors Notes for GATE CS

Chapter Roadmap: Combinational Logic Circuits and Data Selectors

Combinational Logic Circuits and Data Selectors

1. Logic Gate Circuit Analysis and Hazards

2. Decoders, Multiplexers and Address Selection

3. Boolean Function Realization Using Multiplexers

4. Cascaded Multiplexer and Decoder Circuits

Logic Gate Circuit Analysis and Hazards

Logic Gate Circuit Analysis and Hazards

What you will learn here

Propagation Delay in Logic Gates

Propagation Delay in Logic Gates

Propagation Delay (tpd​)

Key Assumptions for Exam Analysis

Understanding Logic Hazards

Understanding Logic Hazards

1. Static-1 Hazard

2. Static-0 Hazard

3. Dynamic Hazard

Combinational Logic Circuits and Data Selectors: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More notes in this unit

Propagation Delay ( $t_{p d}$ )

Propagation Delay ( $t_{p d}$ )