Unit II — Combinational Circuits

UNIT II — Combinational Circuits

2.1 Introduction to Combinational Logic

What is Combinational Logic?

Think of a vending machine’s coin display: you insert coins (inputs) and the screen shows the total amount (output) based only on what you inserted right now. It doesn’t “remember” yesterday’s coins. That’s the essence of combinational logic.

A combinational circuit is one whose output depends only on the present inputs — no memory, no feedback, no stored state. Given the same inputs, you always get the same output.

Combinational vs Sequential — The Big Distinction

This is one of the most fundamental distinctions in digital design:

The 4-Step Design Process

Every combinational circuit follows the same design recipe:

1. Understand the problem → Translate the English/real-world description into a precise truth table. This is the hardest step — get this wrong and everything else fails.
2. Write the Boolean expression → From the truth table, write the SOP (sum of minterms for 1-outputs) or POS (product of maxterms for 0-outputs).
3. Simplify → Use K-Map or Boolean algebra to minimize the expression. Fewer terms = fewer gates = cheaper, faster circuit.
4. Draw the logic circuit → Convert the simplified expression directly into gates.

What’s Coming in Unit II

Everything in Unit II is a combinational circuit. Here’s the roadmap:

Each of these follows the same 4-step design process. Once you master the process, every new circuit is just a new truth table.

2.2 Code Converters

Why Do We Need Code Converters?

Different parts of a digital system use different binary codes for different reasons:

• Binary is what computers naturally use for arithmetic
• Gray code is used in rotary encoders and K-Maps because only 1 bit changes between adjacent values (preventing glitches)
• BCD is used in displays (each decimal digit stored separately)
• Excess-3 is used when you need self-complementing arithmetic

When these different subsystems need to talk to each other, you need code converters — circuits that translate one code to another.

Code converters translate one binary code to another.

Binary to Gray Code Converter

The Conversion Rule — Intuitive Understanding

Rule: $G_i = B_{i+1} \oplus B_i$ (XOR adjacent bits), $G_{MSB} = B_{MSB}$

In plain English:

• The MSB stays the same (Gray MSB = Binary MSB)
• Each other Gray bit = XOR of the corresponding binary bit with the bit to its left

Why XOR? XOR tells you “are these two bits different?” A Gray bit is 1 when the two adjacent binary bits differ, and 0 when they’re the same. That’s literally what XOR computes.

Truth Table (4-bit):

Expressions:

• $G_3 = B_3$
• $G_2 = B_3 \oplus B_2$
• $G_1 = B_2 \oplus B_1$
• $G_0 = B_1 \oplus B_0$

Circuit: 3 XOR gates in parallel.

Gray to Binary Code Converter

The Reverse Process — Why It’s Trickier

Going back from Gray to Binary is slightly more complex because each step depends on the previous result, not just the input.

Rule: $B_{MSB} = G_{MSB}$, then $B_i = B_{i+1} \oplus G_i$

In plain English:

• MSB stays the same (just like Binary→Gray)
• For all other bits: XOR the previous binary output with the current Gray input
• You must work left to right because each bit needs the result from the bit to its left

Expressions:

• $B_3 = G_3$
• $B_2 = B_3 \oplus G_2 = G_3 \oplus G_2$
• $B_1 = B_2 \oplus G_1$
• $B_0 = B_1 \oplus G_0$

Summary: Binary ↔ Gray Conversion at a Glance

2.3 Binary Comparators

What is a Comparator?

A comparator answers the most basic question in computing: “How do two numbers relate to each other?” Is A bigger? Is B bigger? Are they equal?

Real-world analogy: Think of comparing two people’s heights. You start by looking at the most significant feature first (overall height), and only look at finer details (centimeters) if the overall measurement is the same.

A comparator compares two binary numbers and produces three outputs:

• $A > B$ → 1 when A is larger
• $A = B$ → 1 when they’re equal
• $A < B$ → 1 when B is larger

Important: Exactly one of these three outputs is 1 at any time (they’re mutually exclusive).

1-Bit Comparator

The simplest comparator compares two single bits. Let’s think about it logically:

• When is A > B? Only when A=1 and B=0. That’s $A \cdot \overline{B}$ (AND gate with B inverted)
• When is A < B? Only when A=0 and B=1. That’s $\overline{A} \cdot B$
• When is A = B? When both are the same (both 0 or both 1). That’s exactly what XNOR does!

Expressions:

• $A > B = A\overline{B}$
• $A = B = \overline{A \oplus B} = A \odot B$ (XNOR)
• $A < B = \overline{A}B$

2-Bit Comparator

Now things get interesting. Comparing 2-bit numbers $A = A_1A_0$ with $B = B_1B_0$ uses the cascading principle — exactly how you compare numbers in real life:

Step 1: Compare the MSBs first ($A_1$ vs $B_1$)

• If $A_1 > B_1$ → A > B. Done! (Don’t even look at the other bits)
• If $A_1 < B_1$ → A < B. Done!
• If $A_1 = B_1$ → tie at MSB, move to next bit

Step 2: Only if MSBs are equal, compare $A_0$ vs $B_0$

• The MSB equality check uses XNOR: $(A_1 \odot B_1)$
• This “enable signal” gates the LSB comparison — the LSB result only matters when MSBs are equal

This gives us the expressions:

Read this as: “A equals B when MSBs are equal AND LSBs are equal.”

Read this as: “A is greater when MSB of A wins OR (MSBs tie AND LSB of A wins).”

Read this as: “A is less when MSB of B wins OR (MSBs tie AND LSB of B wins).”

2.4 Half & Full Adders

The Building Blocks of All Arithmetic

Every calculator, every CPU, every phone does arithmetic. And at the very bottom, all arithmetic is built from adders — tiny circuits that add single bits. These are the most fundamental arithmetic building blocks in digital design.

Half Adder

What does “half” mean?

A half adder adds 2 single-bit inputs (A and B) and produces a Sum and a Carry. It’s called “half” because it only handles half the job — it can’t accept a carry from a previous stage. It’s like adding the rightmost column of a multi-digit addition (where there’s no carry coming in).

Think about it: What happens when you add two single bits?

• $0 + 0 = 0$ → Sum=0, no carry
• $0 + 1 = 1$ → Sum=1, no carry
• $1 + 0 = 1$ → Sum=1, no carry
• $1 + 1 = 10$ → Sum=0, Carry=1 (just like 5+5=10 in decimal!)

Why these gates?

• Sum = XOR: XOR is 1 when inputs differ — that’s exactly when the sum is 1 (0+1=1, 1+0=1). When both inputs are the same, the sum is 0 (0+0=0, 1+1=10 → sum digit is 0).
• Carry = AND: A carry only happens when both inputs are 1. AND is the “both must be true” gate.

Circuit: Just 1 XOR gate + 1 AND gate — the simplest arithmetic circuit possible!

Full Adder

Why do we need the “full” version?

A half adder can only add 2 bits. But when adding multi-bit numbers (like adding two 8-bit numbers), each column after the first might have a carry coming in from the previous column. A full adder handles this by accepting 3 inputs: A, B, and Carry-in ($C_{in}$).

Think of it like decimal addition:

  1 ← carry from previous column
  47
+ 35
----
  82

When adding the tens column: 4 + 3 + 1(carry) = 8. That “adding three things” is what a full adder does.

Adds 3 single-bit inputs (A, B, and Carry-in $C_{in}$).

Understanding the formulas:

• Sum = Triple XOR: XOR with three inputs gives 1 when an odd number of inputs are 1. Think: 1+1+1=11 (sum=1), 0+1+1=10 (sum=0), 0+0+1=01 (sum=1). The “oddness” of the count is exactly what XOR computes.
• Carry-out = “at least two inputs are 1”: The carry is 1 when two or more of the three inputs are 1. The formula $AB + C_{in}(A \oplus B)$ says: “either A AND B are both 1 (guaranteed carry), OR the carry-in is 1 AND exactly one of A,B is 1 (which gives a second 1 to generate carry).”

2.5 Half & Full Subtractors

Subtraction: The Mirror of Addition

Just as adders handle addition, subtractors handle subtraction. The structure is almost identical to adders, but instead of a “carry,” we have a “borrow.”

Key insight: In practice, most digital systems don’t use dedicated subtractors. They use adders + 2’s complement instead (subtracting B is the same as adding −B). But understanding subtractors is essential for exams and for understanding the underlying logic.

Half Subtractor

What does it do?

Subtracts B from A (two 1-bit inputs), producing a Difference and a Borrow. No borrow-in (that’s why it’s “half”).

Think about each case:

• $0 - 0 = 0$ → Difference=0, no borrow
• $0 - 1 = ?$ → Can’t subtract! Need to borrow from the next column → Difference=1, Borrow=1 (borrowed 1 from the next higher bit, so we actually computed $10 - 1 = 1$)
• $1 - 0 = 1$ → Difference=1, no borrow
• $1 - 1 = 0$ → Difference=0, no borrow

Why these formulas?

• Difference = XOR: Same as Sum in a half adder! The difference bit behaves identically to the sum bit.
• Borrow = $\overline{A} \cdot B$: A borrow happens when A=0 and B=1 (we’re trying to subtract a larger digit from a smaller one). Compare with the carry formula $C = A \cdot B$ — the only difference is that A is inverted!

Full Subtractor

Why do we need it?

Same reason we need a full adder: when subtracting multi-bit numbers, each column (except the first) might have a borrow coming in from the previous column. A full subtractor handles three inputs: A, B, and Borrow-in ($B_{in}$).

Think of decimal subtraction with borrowing:

     0          (borrow happened here)
   4 12
-  3  5
------
   0  7

When subtracting the tens column: 4 - 3 - 0(borrow) = 1… but wait, we had a borrow from the units column, so it’s actually 4 - 3 - 1 = 0. That “three-way subtraction” is what a full subtractor computes.

Three inputs: A, B, and Borrow-in ($B_{in}$).

Understanding $B_{out}$: A borrow-out occurs when:

• $\overline{A}B$: A=0 and B=1 (can’t subtract without borrowing), OR
• $B_{in}(\overline{A \oplus B})$: There’s an incoming borrow AND A=B (the incoming borrow “tips the scale” — we can’t absorb it)

2.6 Serial & Parallel Adders, BCD Adder

Now that we have the full adder as a building block, the question is: how do we add multi-bit numbers? There are two fundamental approaches, representing the classic engineering trade-off between speed and cost.

Ripple Carry (Parallel) Adder

The Idea: Line Up Full Adders Side by Side

Think of how you add two numbers by hand: you line up the columns, start from the rightmost digit, and carry to the left. A ripple carry adder does exactly this — it chains $n$ full adders in parallel, one for each bit.

Chain $n$ full adders in parallel. The carry output of each stage feeds into the carry input of the next stage.

   A₃ B₃    A₂ B₂    A₁ B₁    A₀ B₀
    │  │      │  │      │  │      │  │
   ┌▼──▼┐   ┌▼──▼┐   ┌▼──▼┐   ┌▼──▼┐
C₄←│ FA │←C₃│ FA │←C₂│ FA │←C₁│ FA │←C₀=0
   └──┬─┘   └──┬─┘   └──┬─┘   └──┬─┘
      S₃       S₂       S₁       S₀

Disadvantage: The Ripple Problem

Propagation delay — the carry must ripple through all stages from right to left before the final answer is ready. Total delay = $n \times t_{FA}$ where $t_{FA}$ is the delay of one full adder.

Why this matters: For a 32-bit adder, the carry might need to ripple through all 32 stages. FA₃₁ can’t produce its correct sum until it receives the carry from FA₃₀, which needs the carry from FA₂₉, and so on. The entire chain must settle before the answer is valid.

Solution (not in syllabus but good to know): Carry Lookahead Adders (CLA) compute all carries simultaneously using extra logic, reducing delay from $O(n)$ to $O(\log n)$. This is what real CPUs use.

Serial Adder

The Cheap Alternative

What if you can’t afford $n$ full adders? Use just one and process bits one pair at a time!

Uses a single full adder + a flip-flop (memory element) for the carry. Bits are fed one pair at a time (LSB first). The flip-flop stores the carry for the next clock cycle.

How it works:

1. Clock cycle 1: Feed $A_0, B_0$, $C_{in}=0$ → get $S_0$, store carry in flip-flop
2. Clock cycle 2: Feed $A_1, B_1$, $C_{in}$ from flip-flop → get $S_1$, store new carry
3. … repeat for all n bits
4. After $n$ clock cycles, you have the complete sum

BCD Adder

The Problem: Binary Adders Don’t Speak BCD

This is one of the most interesting circuits in the course. Here’s the issue:

A 4-bit binary adder can produce results from 0 to 30 (if adding two 4-bit numbers + carry). But BCD only allows 0–9 for each digit. So when the sum exceeds 9, we get an invalid BCD result that needs correction.

Adds two BCD digits (0–9). Since BCD is valid only for 0–9 and a 4-bit binary adder can produce 0–19 (max: 9+9+1=19), a correction is needed.

The “Add 6” Correction — Why 6?

When is correction needed? If the 4-bit sum > 9 (i.e., 1010–1111) or if carry out = 1, add 6 (0110) to the result.

But WHY add 6? Here’s the intuition:

• BCD uses only 10 out of 16 possible 4-bit codes (0000–1001)
• There are 6 unused codes (1010–1111)
• When the sum falls into this invalid range, adding 6 skips over those 6 invalid codes and jumps to the next valid BCD digit
• Example: Binary 1100 (12) is invalid BCD. Add 6: $1100 + 0110 = 10010$ = “0001 0010” = BCD 12. The “1” ripples up to become the tens digit!

Understanding the condition: The sum > 9 when:

• Carry out = 1 (sum ≥ 16), OR
• $S_3 \cdot S_2 = 1$ (binary 11XX, i.e., sum ≥ 12), OR
• $S_3 \cdot S_1 = 1$ (binary 1X1X, i.e., sum is 10 or 11)

BCD Adder Circuit — Block Diagram:

A₃A₂A₁A₀  B₃B₂B₁B₀
    │           │
    └─────┬─────┘
    ┌─────▼─────┐
    │ 4-bit     │
    │ Binary    │←── C_in
    │ Adder #1  │
    └─────┬─────┘
     C₄  S₃S₂S₁S₀
      │    │
      ├────▼───┐
      │ Detect │ ← Is sum > 9?
      │ >9 ?   │ ← C₄ OR (S₃·S₂) OR (S₃·S₁)
      └───┬────┘
     Correction = 0 or 0110
          │
    ┌─────▼─────┐
    │ 4-bit     │
    │ Binary    │ ← Adds 0000 or 0110
    │ Adder #2  │
    └─────┬─────┘
   BCD Carry  BCD Sum

The circuit uses two 4-bit adders: the first does the raw addition, and the second adds the correction (0110) only when needed. The correction logic between them is just a few AND/OR gates.

2.7 Multiplexers (MUX)

What is a Multiplexer? — The Data Selector

Real-world analogy: Think of a TV channel selector. Your TV antenna receives 100 channels simultaneously, but you can only watch one at a time. The channel selector (remote control) picks which channel’s data reaches your screen. That’s exactly what a MUX does!

A multiplexer is a combinational circuit that selects one of $2^n$ inputs and forwards it to a single output, using $n$ select lines to choose which input wins.

Key relationship: $n$ select lines → $2^n$ possible inputs → 1 output

• 1 select line → 2:1 MUX
• 2 select lines → 4:1 MUX
• 3 select lines → 8:1 MUX
• $n$ select lines → $2^n$:1 MUX

2:1 MUX — The Simplest Case

The most basic MUX: one select line (S) chooses between two inputs ($I_0$ and $I_1$).

Read the formula: “When S=0, the output equals $I_0$. When S=1, the output equals $I_1$.”

How the circuit enforces this: The $\overline{S}$ term “enables” $I_0$ when S=0 (AND gate passes $I_0$). The $S$ term “enables” $I_1$ when S=1. The OR gate combines them. Only one AND gate is active at a time, so only one input reaches the output.

4:1 MUX — The Workhorse

Select lines: $S_1, S_0$. Inputs: $I_0, I_1, I_2, I_3$. The two select lines form a 2-bit binary number that picks which input to pass through.

Pattern: Each term is a minterm of the select lines ANDed with the corresponding input. The select lines act like an “address” that identifies which input to route to the output.

Implementing Boolean Functions with MUX

This is one of the most important exam topics. The key insight is:

An n-variable function can be implemented with a $2^{n-1}$:1 MUX (one size smaller than you’d expect) or a $2^n$:1 MUX directly.

Method: Using a $2^{n-1}$:1 MUX for an $n$-variable function

1. Choose n-1 variables as select lines (usually the first variables: A, B, …)
2. The remaining variable (usually the last one: C, D, …) appears at the data inputs
3. For each combination of select lines, figure out what F equals in terms of the remaining variable
4. The data input will be one of: 0, 1, X, or $\overline{X}$ (where X is the remaining variable)

Why this works: The select lines of the MUX partition the truth table into groups. Each group has only 2 rows (for the remaining variable = 0 and = 1). The behavior of F within each group matches one of the four options (always 0, always 1, equals X, or equals $\overline{X}$).

2.8 Demultiplexers (DEMUX)

What is a DEMUX? — The Reverse of MUX

Real-world analogy: A MUX is like choosing which of 8 microphones to listen to. A DEMUX is like a speaker system where you have one audio source and you route it to one of 8 rooms. You’re sending one input to one of many outputs.

A demultiplexer takes one input (data line D) and routes it to one of $2^n$ outputs based on $n$ select lines. All other outputs stay at 0.

MUX vs DEMUX — Mirror Images:

1:4 DEMUX

One data input D, two select lines ($S_1, S_0$), four outputs ($Y_0$–$Y_3$).

The select lines form a 2-bit “address” telling the DEMUX which output to activate:

\(Y_0 = D \cdot \overline{S_1} \cdot \overline{S_0}\) \(Y_1 = D \cdot \overline{S_1} \cdot S_0\) \(Y_2 = D \cdot S_1 \cdot \overline{S_0}\) \(Y_3 = D \cdot S_1 \cdot S_0\)

Pattern: Each output = Data input AND one minterm of the select lines. Only the output whose “address” matches the select line combination gets the data; all others receive 0.

How to read the formula: $Y_2 = D \cdot S_1 \cdot \overline{S_0}$ means “output Y₂ receives the data D only when S₁=1 and S₀=0 (i.e., select = 10 = 2).”

2.9 Encoders

What is an Encoder? — The Reverse of a Decoder

Real-world analogy: Imagine a calculator keypad with 10 buttons (0–9). When you press button “7”, the calculator internally needs to store $0111$ (the binary code for 7). The circuit that converts “button 7 is pressed” into the binary code $0111$ is an encoder.

An encoder converts $2^n$ input lines to $n$ output lines. At any time, one input is active (HIGH), and the encoder outputs the binary code corresponding to which input is active. It’s the reverse of a decoder.

Key relationships:

• Decoder: binary code → activate one line (code to one-hot)
• Encoder: one active line → binary code (one-hot to code)

4:2 Encoder (Simple)

4 inputs ($I_0$–$I_3$), 2 outputs ($Y_1, Y_0$). The encoder outputs the 2-bit binary number of whichever input is HIGH.

Critical Assumption: Only ONE input is active at a time. If multiple inputs are active simultaneously, the output is undefined (garbage). This is the fundamental limitation of a simple encoder.

How to derive these: Look at which inputs make each output 1:

• $Y_1$ is 1 for inputs $I_2$ (code 10) and $I_3$ (code 11) — both have $Y_1 = 1$
• $Y_0$ is 1 for inputs $I_1$ (code 01) and $I_3$ (code 11) — both have $Y_0 = 1$

So each output is just an OR of the inputs that have a 1 in that bit position.

8:3 Priority Encoder — The Practical Version

Why priority?

When multiple inputs can be active simultaneously, a priority encoder has a built-in hierarchy — it outputs the code for the highest-priority (usually highest-numbered) active input, ignoring all lower-priority ones.

Real-world analogy: In a hospital emergency room, if patients with severity levels 2, 5, and 7 all arrive at once, the system reports level 7 (highest priority) first.

$V$ (valid bit) = 1 when at least one input is active. This solves the “no input vs $I_0$” ambiguity:

• If V=0: no inputs are active (output code is meaningless)
• If V=1: at least one input is active (output code is valid)

The X entries in the table mean “don’t care” — when a higher-priority input is active, it doesn’t matter what the lower-priority inputs are doing.

IC: 74148 (8:3 priority encoder) — a commonly used chip.

2.10 Decoders

What is a Decoder? — Binary Code to One-Hot

Real-world analogy: Think of an elevator floor selector. You press button “3” (a binary code input), and the elevator activates floor 3’s relay (one specific output out of many). The button panel is the encoder (you→code), and the floor relay system is the decoder (code→action).

A decoder converts $n$ input lines to $2^n$ output lines. For each input combination (binary code), exactly one output is activated (set to 1), and all others remain 0. This “one-hot” output is why decoders are so useful — each output corresponds to exactly one minterm!

Key insight: Each decoder output is a minterm of the input variables. This makes decoders incredibly powerful for implementing Boolean functions.

2:4 Decoder — The Basic Case

2 inputs ($A_1, A_0$), 4 outputs ($Y_0$–$Y_3$). The input forms a 2-bit binary number that selects which output to activate.

Notice: Each output is literally a minterm!

• $Y_0 = m_0 = \overline{A_1}\overline{A_0}$ (active when input = 00)
• $Y_1 = m_1 = \overline{A_1}A_0$ (active when input = 01)
• $Y_2 = m_2 = A_1\overline{A_0}$ (active when input = 10)
• $Y_3 = m_3 = A_1A_0$ (active when input = 11)

Circuit: Each output just needs one AND gate (with appropriate inversions). A 2:4 decoder is just 4 AND gates + 2 NOT gates.

3:8 Decoder (IC 74138)

3 inputs ($A_2, A_1, A_0$) → 8 outputs ($Y_0$–$Y_7$). Each output corresponds to a minterm of the 3 input variables.

Why 3:8? 3 input bits → $2^3 = 8$ possible combinations → 8 outputs. The decoder “decodes” a 3-bit binary number into which of the 8 outputs to activate.

Implementing Boolean Functions with Decoders

This is the most powerful application of decoders and a major exam topic.

Since each decoder output = one minterm, implementing any function is trivial — just OR together the outputs corresponding to the minterms you need.

Why This is Brilliant

• You don’t need to simplify the Boolean expression — no K-Maps needed!
• The decoder provides ALL minterms; you just pick the ones you want
• Multiple functions can share the same decoder — you only need different OR gates
• It’s a completely systematic, no-thinking-required method

Building Larger Decoders from Smaller Ones

4:16 decoder from two 3:8 decoders: Use the 4th input ($A_3$) as an enable signal:

• When $A_3 = 0$ → enable the first 3:8 decoder (produces outputs $Y_0$–$Y_7$), disable the second
• When $A_3 = 1$ → enable the second 3:8 decoder (produces outputs $Y_8$–$Y_{15}$), disable the first

The lower 3 inputs ($A_2, A_1, A_0$) go to both decoders simultaneously. The enable line ensures only one decoder is active, giving you 16 mutually exclusive outputs.

General rule: To build a $n$-to-$2^n$ decoder, use two $(n-1)$-to-$2^{n-1}$ decoders + 1 NOT gate (for the enable). This is the same hierarchical construction idea as building larger MUXes.

Unit II — Practice Questions & PYQs

Back to Digital Logic & Design