05 Chapter 5 - Combinational Circuit Design (Merged)

Chapter 5: Combinational Circuit Design - Complete Study Notes

NotebookLM Ingestion Compilation

This merged document contains all 6 study notes for Chapter 5: Combinational Circuit Design from ECE 2103 Digital Electronics (Sharif Sir).

---

Related Concepts: 02 Code Converters & Data Routing Implementations | 03 Tree Networks (Cascading MUX, Decoders & DeMUX) | 04 Programmable Logic Devices (ROM & PLA)

5.01 Arithmetic Circuits, Multipliers & Comparators

Combinational Arithmetic Building Blocks

Combinational Arithmetic Circuits form the core of a CPU’s Arithmetic Logic Unit (ALU). Because combinational circuits have no memory elements, their outputs are functions solely of their present inputs.

graph TD
    subgraph 3 Half-Adder Functional Generator
        InA[Inputs A, B] --> HA1[Half-Adder 1: S1 = A ⊕ B, C1 = AB]
        HA1 & InC[Input C] --> HA2[Half-Adder 2: S2 = A ⊕ B ⊕ C = D, C2 = S1 • C = E]
        HA1 & InC --> HA3[Half-Adder 3: S3 = C1 ⊕ C = F, C3 = C1 • C = G]
    end

---

1. The Combinational Circuit Design Blueprint

To design any combinational circuit from scratch (especially when resolving 14-mark word problems), engineers follow a structured 5-step blueprint:

+-----------------------------------+
|  1. Analyze Word Problem & Rules   |
+-----------------------------------+
                  |
                  v
+-----------------------------------+
|  2. Draw Truth Table (I/O Mapping)|
+-----------------------------------+
                  |
                  v
+-----------------------------------+
|  3. Simplify Outputs via K-Maps   |
+-----------------------------------+
                  |
                  v
+-----------------------------------+
|  4. Write Minimized Equations      |
+-----------------------------------+
                  |
                  v
+-----------------------------------+
|  5. Draw Schematic Gate Diagram   |
+-----------------------------------+

Step 1: Variable Identification

Determine the number of input variables and output variables from the problem specification. Assign distinct letter symbols (e.g., inputs $A,B,C$, outputs $X,Y,Z$) to each.

Step 2: Truth Table Construction

List all $2^n$ possible binary combinations for the $n$ input variables. Determine the required output value (1 or 0) for each row based on the system rules. If certain input states are physically impossible or will never occur, mark those output states as Don’t Cares (X).

Step 3: K-map Optimization

Plot a separate K-map for each output variable. Place 1s, 0s, and Xs in their corresponding cells, and group them to obtain the simplest expressions.

Step 4: Logic Equation Extraction

Write down the minimized Sum-of-Products (SOP) or Product-of-Sums (POS) algebraic equations for each output.

Step 5: Schematic Drafting

Draw the physical logic gate circuit. Ensure inputs flow from left to right, gates are drawn cleanly, and all lines and connections are clearly labeled.

---

2. The 4-Function Half-Adder Cascading Puzzle

Major Exam Problem: Implement 4 Functions using 3 Half-Adders (2015, 2018, 2019 - 12 Marks)

Question: Implement the following four Boolean functions using exactly three Half-Adder circuits:

• $D=A\oplus B\oplus C$
• $E=A^{\prime }BC+A{B}^{\prime }C$
• $F=AB{C}^{\prime }+(A^{\prime }+B^{\prime })C$
• $G=ABC$

Solution Step-by-Step:

1. Half-Adder 1 (HA1): Inputs $A$ and $B$.

   • Sum Output: $S_1=A\oplus B$
   • Carry Output: $C_1=AB$

2. Half-Adder 2 (HA2): Inputs $S_1$ and $C$.

   • Sum Output: $S_2=S_1\oplus C=(A\oplus B)\oplus C=\mathbf{A}\oplus \mathbf{B}\oplus \mathbf{C}=\mathbf{D}$
   • Carry Output: $C_2=S_1\cdot C=(A\oplus B)\cdot C=(A^{\prime }B+A{B}^{\prime })C={\mathbf{A}}^{\prime }\mathbf{BC}+\mathbf{A}{\mathbf{B}}^{\prime }\mathbf{C}=\mathbf{E}$

3. Half-Adder 3 (HA3): Inputs $C_1$ and $C$.

   • Sum Output: $S_3=C_1\oplus C=(AB)\oplus C=AB\cdot C^{\prime }+(AB{)}^{\prime }\cdot C=\mathbf{AB}{\mathbf{C}}^{\prime }+({\mathbf{A}}^{\prime }+{\mathbf{B}}^{\prime })\mathbf{C}=\mathbf{F}$
   • Carry Output: $C_3=C_1\cdot C=(AB)\cdot C=\mathbf{ABC}=\mathbf{G}■$

---

2. Full-Adder to Full-Subtractor Conversion

The Single Inverter Trick (2020 - 10 Marks)

Question: Show that a Full-Adder can be converted to a Full-Subtractor with the addition of one inverter gate.

• Standard Full-Adder (FA): $Sum=X\oplus Y\oplus Z$, $C_{out}=XY+XZ+YZ$
• Standard Full-Subtractor (FS): $Diff=X\oplus Y\oplus Z$, $B_{out}=X^{\prime }Y+X^{\prime }Z+YZ$

Solution:

Connect an inverter to the Minuend input ($X$) before it enters the Full-Adder.

1. Input to FA becomes $X^{\prime }$.
2. Carry Out becomes: $C_{out\_new}=X^{\prime }Y+X^{\prime }Z+YZ={\mathbf{B}}_{\mathbf{out}}$ (matches Full-Subtractor Borrow Out).
3. Note: The Sum output becomes $Su{m}_{new}=X^{\prime }\oplus Y\oplus Z=(X\oplus Y\oplus Z{)}^{\prime }=\mathbf{Dif}{\mathbf{f}}^{\prime }$ (complement of Difference). $■$

---

4. Carry Look-Ahead Mathematical Proof & Parallelism

In a standard Ripple Carry Adder, the propagation delay accumulates as carries ripple sequentially through each stage. A Carry Look-Ahead (CLA) Adder eliminates this sequential bottleneck by calculating all carry signals in parallel.

4.1 Derivation of the Carry Equation

Carry Equation Proof (2018 - 10 Marks)

Question: Prove that the output carry $C_{i+1}$ of any full-adder stage $i$ can be expressed in terms of generate ($G_i$) and propagate ($P_i$) functions as:

$C_{i+1}=G_i+P_i{C}_i$

1. Standard Full-Adder carry-out logic equation: $C_{i+1}=A_i{B}_i+A_i{C}_i+B_i{C}_i$
2. Factor out the carry-in $C_i$: $C_{i+1}=A_i{B}_i+C_i(A_i+B_i)$
3. Define Carry Generate ($G_i$): A carry is generated internally if both inputs are 1, regardless of carry-in: $G_i=A_i{B}_i$
4. Define Carry Propagate ($P_i$): An input carry is propagated to the output if either input is 1 (commonly implemented using XOR for sum generation): $P_i=A_i\oplus B_i$
5. Substituting $G_i$ and $P_i$ back into the carry equation: $$\mathbf{C_{i+1} = G_i + P_i C_i} \quad \blacksquare$

---

4.2 Parallel Carry Generation (Look-Ahead Formulas)

By expanding the recurrence relation, we express every carry signal solely in terms of the initial carry-in $C_0$ and the primary input variables ($A$ and $B$, which generate $G_i$ and $P_i$ instantly at the first gate level):

• $C_1$ (Stage 1 Carry): $C_1=G_0+P_0{C}_0$
• $C_2$ (Stage 2 Carry): $C_2=G_1+P_1{C}_1={\mathbf{G}}_1+{\mathbf{P}}_1{\mathbf{G}}_0+{\mathbf{P}}_1{\mathbf{P}}_0{\mathbf{C}}_0$
• $C_3$ (Stage 3 Carry): $C_3=G_2+P_2{C}_2={\mathbf{G}}_2+{\mathbf{P}}_2{\mathbf{G}}_1+{\mathbf{P}}_2{\mathbf{P}}_1{\mathbf{G}}_0+{\mathbf{P}}_2{\mathbf{P}}_1{\mathbf{P}}_0{\mathbf{C}}_0$
• $C_4$ (Stage 4 Carry): $C_4=G_3+P_3{C}_3={\mathbf{G}}_3+{\mathbf{P}}_3{\mathbf{G}}_2+{\mathbf{P}}_3{\mathbf{P}}_2{\mathbf{G}}_1+{\mathbf{P}}_3{\mathbf{P}}_2{\mathbf{P}}_1{\mathbf{G}}_0+{\mathbf{P}}_3{\mathbf{P}}_2{\mathbf{P}}_1{\mathbf{P}}_0{\mathbf{C}}_0$

Propagation Delay Analysis

Since all $G_i$ and $P_i$ terms are computed simultaneously at the first gate level, all carry signals ($C_1$ to $C_4$) are generated in parallel with a flat delay of only two gate levels (one level of ANDs, one level of ORs). This eliminates the $O(n)$ ripple carry delay, keeping the addition speed independent of the word size.

---

5. 2-Bit Binary Multiplier Circuit Design

Major PYQ Problem: $A_1{A}_0\times B_1{B}_0$ (2022 - 10 Marks)

Inputs: $A_1{A}_0$ and $B_1{B}_0$. Outputs: $P_3{P}_2{P}_1{P}_0$.

graph TD
    subgraph Multiplier Architecture
        P0[P0 = A0 • B0]
        AND1[A1 • B0] & AND2[A0 • B1] --> HA1[Half-Adder 1: Sum = P1, Carry = C1]
        AND3[A1 • B1] & HA1 --> HA2[Half-Adder 2: Sum = P2, Carry = P3]
    end

• Hardware Required: 4 AND gates and 2 Half-Adders.

---

6. Magnitude Comparator Design & Mathematics

A magnitude comparator is a combinational circuit that compares two multi-bit binary numbers ($A$ and $B$) to determine their relative magnitude ($A=B$, $A>B$, or $A<B$).

6.1 Bit Equivalence Coefficient ($x_i$)

To compare two numbers, we first define an equivalence coefficient $x_i$ for each individual bit position $i$ using the XNOR gate:

$x_i=A_i\odot B_i=A_i{B}_i+A_i^{\prime }{B}_i^{\prime }$

• $x_i=1$ if bit $A_i$ is equal to bit $B_i$.
• $x_i=0$ if bit $A_i$ is not equal to bit $B_i$.

6.2 Equality Condition ($A=B$)

For the entire 4-bit numbers $A$ and $B$ to be equal, every single bit position must be equal simultaneously:

$(\mathbf{A}=\mathbf{B})={\mathbf{x}}_3\cdot {\mathbf{x}}_2\cdot {\mathbf{x}}_1\cdot {\mathbf{x}}_0$

Hardware Implementation: Four 2-input XNOR gates feeding into a single 4-input AND gate.

---

6.3 Inequality Conditions ($A>B$ and $A<B$)

To determine if $A$ is greater than or less than $B$, we compare bits starting from the Most Significant Bit (MSB, position 3) down to the Least Significant Bit (LSB, position 0).

1. The $A>B$ Logic Equation

$A>B$ if the MSB of $A$ is $1$ and $B$ is $0$. If they are equal, we check the next bit down, and so on:

$(\mathbf{A}>\mathbf{B})={\mathbf{A}}_3{\mathbf{B}}_3^{\prime }+{\mathbf{x}}_3{\mathbf{A}}_2{\mathbf{B}}_2^{\prime }+{\mathbf{x}}_3{\mathbf{x}}_2{\mathbf{A}}_1{\mathbf{B}}_1^{\prime }+{\mathbf{x}}_3{\mathbf{x}}_2{\mathbf{x}}_1{\mathbf{A}}_0{\mathbf{B}}_0^{\prime }$

2. The $A<B$ Logic Equation

Similarly, $A<B$ if the MSB of $A$ is $0$ and $B$ is $1$. If they are equal, we check the next bit down:

$(\mathbf{A}<\mathbf{B})={\mathbf{A}}_3^{\prime }{\mathbf{B}}_3+{\mathbf{x}}_3{\mathbf{A}}_2^{\prime }{\mathbf{B}}_2+{\mathbf{x}}_3{\mathbf{x}}_2{\mathbf{A}}_1^{\prime }{\mathbf{B}}_1+{\mathbf{x}}_3{\mathbf{x}}_2{\mathbf{x}}_1{\mathbf{A}}_0^{\prime }{\mathbf{B}}_0$

Hardware Implementation: Utilizes the existing XNOR equivalence outputs $x_i$ along with AND gates and a final multi-input OR gate to evaluate the conditions.

---

7. BCD Adder Design & Operation

Syllabus Context: Hardware Block Design

Design and operation of BCD adders is a standard 10-mark design question in ECE 2103 examinations.

A BCD Adder is a digital circuit that adds two BCD digits in parallel and produces a BCD sum digit.

The Correction Logic

The sum of two BCD digits ($A,B\le 9$) plus a carry-in ($C_{in}\le 1$) can range from $0$ to $19$.

• Standard 4-bit binary addition handles sums up to 15 without a carry-out.

• To convert a binary sum ($S_3{S}_2{S}_1{S}_0$ with carry $K$) into a valid BCD digit (where values $>9$ must generate a decimal carry and be offset by $+6$), we define a correction detection logic function $F$.

• Detection Rule: An overflow (sum $>9$) occurs if:

  1. $K=1$ (the binary sum is $\ge 16$).
  2. $S_3\cdot S_2=1$ (the binary sum is $12,13,14,$ or $15$).
  3. $S_3\cdot S_1=1$ (the binary sum is $10$ or $11$).

  $\mathbf{F}=\mathbf{K}+{\mathbf{S}}_3{\mathbf{S}}_2+{\mathbf{S}}_3{\mathbf{S}}_1$

• If $F=1$, we add binary $6_{10}=0110_2$ to the sum. The output carry for the next decimal stage is $F$.

Hardware Block Diagram:

graph TD
    subgraph BCD Adder Architecture
        InA[BCD Input A] & InB[BCD Input B] --> Adder1[4-Bit Binary Adder 1]
        Cin[Carry In] --> Adder1
        Adder1 --> BinSum[Binary Sum: S3 S2 S1 S0]
        Adder1 --> CarryK[Carry K]
        
        BinSum & CarryK --> Detect[Detection Logic: F = K + S3•S2 + S3•S1]
        
        Detect -->|F| CorrectionBit[Correction Value: 0 F F 0]
        
        BinSum & CorrectionBit --> Adder2[4-Bit Binary Adder 2]
        Adder2 --> BCDOut[Final BCD Sum Output]
        Detect --> CarryOut[Final BCD Carry Out Cout = F]
    end

---

Past Year Questions (PYQs)

• [PYQ 2015, 2018, 2019]: Implement 4 functions using 3 Half-Adders. (12 Marks)
• [PYQ 2018]: Carry Look-Ahead proof $C_{i+1}=G_i+P_i{C}_i$. (10 Marks)
• [PYQ 2020]: FA to FS conversion using 1 inverter. (10 Marks)
• [PYQ 2022]: 2-bit binary multiplier circuit design. (10 Marks)
• [PYQ 2023, 2024, 2025]: 4-bit magnitude equality comparator ($A=B$). (14 Marks)
• [Syllabus / PYQ]: Explain BCD Adder operation and draw its circuit diagram. (10 Marks)

---

Related Concepts: 01 Arithmetic Circuits, Multipliers & Comparators | 03 Tree Networks (Cascading MUX, Decoders & DeMUX) | 04 Programmable Logic Devices (ROM & PLA)

5.02 Code Converters & Data Routing Implementations

MSI Component Architecture

Medium Scale Integration (MSI) components—such as Decoders, Multiplexers (MUX), and Demultiplexers (DeMUX)—drastically reduce hardware gate counts and wiring complexity by replacing custom SSI gate networks.

---

1. Core Data Routing Definitions

• Decoder: Converts binary information from $n$ input lines to a maximum of $2^n$ unique output lines {generates all minterms internally}.
• Multiplexer (MUX): Selects binary data from one of $2^n$ input lines and routes it to a single output controlled by $n$ select lines {Data Selector}.
• Demultiplexer (DeMUX): Takes data from a single input line and routes it to one of $2^n$ output lines controlled by $n$ select lines {Data Distributor}.

---

2. Master Code Converter: 2,4,2,1 to 8,4,-2,-1

Major PYQ Problem (2017, 2019, 2020, 2023, 2024, 2025 - 14 Marks)

Question: Design a combinational circuit to convert a decimal digit from 2,4,2,1 code to 8,4,-2,-1 code.

Complete Conversion Truth Table:

Decimal	Inputs (2,4,2,1) $ABCD$	Outputs (8,4,-2,-1) $WXYZ$	Weight Check
0	0 0 0 0	0 0 0 0	$0=0$
1	0 0 0 1	0 1 1 1	$4-2-1=1$
2	0 0 1 0	0 1 1 0	$4-2-0=2$
3	0 0 1 1	0 1 0 1	$4-0-1=3$
4	0 1 0 0	0 1 0 0	$4-0-0=4$
5	1 0 1 1	1 0 1 1	$8-2-1=5$
6	1 1 0 0	1 0 1 0	$8-2-0=6$
7	1 1 0 1	1 0 0 1	$8-0-1=7$
8	1 1 1 0	1 0 0 0	$8-0-0=8$
9	1 1 1 1	1 1 1 1	$8+4-2-1=9$

• Don’t Care Conditions: Unused 2,4,2,1 binary combinations $0101\dots 1010⟹d=\Sigma d(5,6,7,8,9,10)$.

---

3. Shannon’s Expansion Theorem & MUX Logic Design

Shannon’s Expansion Theorem is the mathematical foundation behind multiplexer-based logic design. It states that any Boolean function can be decomposed into smaller sub-functions by expanding it about one or more select variables.

3.1 Theorem Statement

For any $n$-variable Boolean function $F(x_n,\dots ,x_1)$, it can be expanded about an individual variable $x_i$ as:

$\mathbf{F}={\mathbf{x}}_{\mathbf{i}}^{\prime }\cdot \mathbf{F}({\mathbf{x}}_{\mathbf{n}},\dots ,0,\dots ,{\mathbf{x}}_1)+{\mathbf{x}}_{\mathbf{i}}\cdot \mathbf{F}({\mathbf{x}}_{\mathbf{n}},\dots ,1,\dots ,{\mathbf{x}}_1)$

Using cofactor notation, we write: $F=x_i^{\prime }\cdot F_{x_i=0}+x_i\cdot F_{x_i=1}$

Where:

• $F_{x_i=0}$ is the cofactor of $F$ evaluated with variable $x_i=0$.
• $F_{x_i=1}$ is the cofactor of $F$ evaluated with variable $x_i=1$.

3.2 Direct Hardware Mapping to Multiplexers

A multiplexer is physically a hardware implementation of Shannon’s expansion equation:

• The Select Lines ($S$) act as the expansion variables ($x_i$).
• The Data Inputs ($I$) of the MUX are hardwired to the resulting cofactors.

The Select Line Rule

Since each select line represents one expansion variable, an $n$-variable Boolean function can always be implemented using a Multiplexer with:

• $n-1$ select lines (where the remaining $1$ variable feeds the data inputs as $0,1,V,\text{or }{V}^{\prime }$).
• $n$ select lines (where the data inputs are tied to static constants 0 or 1).

---

4. Implementing Full-Adder using 4x1 Multiplexers

Major PYQ Problem: Full-Adder via MUX (2021 - 10 Marks)

Question: Implement a Full-Adder circuit using two 4x1 Multiplexers.

Solution: A Full-Adder has three inputs: $X,Y$ (which we choose as our select lines $S_1=X,S_0=Y$) and $Z$ (the carry-in, which will feed the data inputs).

1. Sum Function ($S=\Sigma m(1,2,4,7)$): Apply Shannon’s expansion about variables $X,Y$: $S=X^{\prime }{Y}^{\prime }\cdot I_0+X^{\prime }Y\cdot I_1+X{Y}^{\prime }\cdot I_2+XY\cdot I_3$
   • For $XY=00$: $S=Z⟹I_0=Z$ (covers minterm 1)
   • For $XY=01$: $S=Z^{\prime }⟹I_1=Z^{\prime }$ (covers minterm 2)
   • For $XY=10$: $S=Z^{\prime }⟹I_2=Z^{\prime }$ (covers minterm 4)
   • For $XY=11$: $S=Z⟹I_3=Z$ (covers minterm 7)
2. Carry Function ($C_{out}=\Sigma m(3,5,6,7)$): Apply Shannon’s expansion about variables $X,Y$: $C_{out}=X^{\prime }{Y}^{\prime }\cdot I_0+X^{\prime }Y\cdot I_1+X{Y}^{\prime }\cdot I_2+XY\cdot I_3$
   • For $XY=00$: $C_{out}=0⟹I_0=0$
   • For $XY=01$: $C_{out}=Z⟹I_1=Z$ (covers minterm 3)
   • For $XY=10$: $C_{out}=Z⟹I_2=Z$ (covers minterm 5)
   • For $XY=11$: $C_{out}=1⟹I_3=1$ (covers minterms 6, 7)

graph TD
    subgraph 4x1 MUX Full-Adder Implementation
        S1[Select S1 = X] & S0[Select S0 = Y] --> MUX_Sum[MUX 1: Sum S]
        S1 & S0 --> MUX_Carry[MUX 2: Carry Out C]
        
        Z[Input Z] -->|I0=Z, I1=Z', I2=Z', I3=Z| MUX_Sum
        Z -->|I0=0, I1=Z, I2=Z, I3=1| MUX_Carry
    end

---

5. Implementing Full-Adder using 3-to-8 Decoder

Major PYQ Problem (2019 - 7 Marks)

Inputs: $x,y,z$ connected to 3-to-8 decoder select lines.

• Sum Output ($S$): Connect decoder output pins 1, 2, 4, 7 to a 4-input OR gate $⟹S=\Sigma m(1,2,4,7)$.
• Carry Output ($C_{out}$): Connect decoder output pins 3, 5, 6, 7 to a second 4-input OR gate $⟹C_{out}=\Sigma m(3,5,6,7)$. $■$

---

6. BCD to Seven-Segment Decoder Design [PYQ 2018]

A BCD to Seven-Segment decoder takes a 4-bit binary coded decimal input ($A,B,C,D$, where $A$ is MSB) and converts it to active-high control outputs ($a,b,c,d,e,f,g$) to drive a standard 7-segment LED display to render decimal numbers 0 through 9.

6.1 Display Segment Layout

       a
     +---+
   f |   | b
     +---+  <- g
   e |   | c
     +---+
       d

6.2 Truth Table (Active-High Display)

States $10\dots 15$ (binary 1010 to 1111) are invalid BCD inputs and are treated as Don’t Care ($X$) states.

Decimal	Inputs ($ABCD$)	Segments ($abcdefg$)
0	0 0 0 0	1 1 1 1 1 1 0
1	0 0 0 1	0 1 1 0 0 0 0
2	0 0 1 0	1 1 0 1 1 0 1
3	0 0 1 1	1 1 1 1 0 0 1
4	0 1 0 0	0 1 1 0 0 1 1
5	0 1 0 1	1 0 1 1 0 1 1
6	0 1 1 0	1 0 1 1 1 1 1
7	0 1 1 1	1 1 1 0 0 0 0
8	1 0 0 0	1 1 1 1 1 1 1
9	1 0 0 1	1 1 1 1 0 1 1

6.3 Minimized Logic Equations (using K-Maps)

• Segment a: $a=A+C+BD+B^{\prime }{D}^{\prime }$
• Segment b: $b=B^{\prime }+C^{\prime }{D}^{\prime }+CD$
• Segment c: $c=B+C^{\prime }+D$
• Segment d: $d=A+B^{\prime }{D}^{\prime }+C{D}^{\prime }+B^{\prime }C+B{C}^{\prime }D$
• Segment e: $e=B^{\prime }{D}^{\prime }+C{D}^{\prime }$
• Segment f: $f=A+C^{\prime }{D}^{\prime }+B{C}^{\prime }+B{D}^{\prime }$
• Segment g: $g=A+B^{\prime }C+B{C}^{\prime }+C{D}^{\prime }$

---

7. Basic 1-to-4 Demultiplexer (DeMUX) Design [PYQ 2023]

A Demultiplexer (DeMUX) is a logic circuit that takes a single input line $D$ and routes it to one of $2^n$ outputs, based on the select variables.

7.1 Truth Table

• Inputs: Data $D$, Selects $S_1,S_0$ (where $S_1$ is MSB).
• Outputs: $Y_3,Y_2,Y_1,Y_0$.

Selects ($S_1{S}_0$)	Outputs ($Y_3{Y}_2{Y}_1{Y}_0$)
0 0	0 0 0 D
0 1	0 0 D 0
1 0	0 D 0 0
1 1	D 0 0 0

7.2 Logic Equations & Schematic Implementation

${\mathbf{Y}}_0={\mathbf{S}}_1^{\prime }{\mathbf{S}}_0^{\prime }\mathbf{D}$ ${\mathbf{Y}}_1={\mathbf{S}}_1^{\prime }{\mathbf{S}}_0\mathbf{D}$ ${\mathbf{Y}}_2={\mathbf{S}}_1{\mathbf{S}}_0^{\prime }\mathbf{D}$ ${\mathbf{Y}}_3={\mathbf{S}}_1{\mathbf{S}}_0\mathbf{D}$

The hardware is implemented using four 3-input AND gates:

• The select lines $S_1,S_0$ are connected to the gate inputs through inverters to generate the addressing minterms.
• The data line $D$ is fed to one input of all four AND gates in parallel.

---

8. Past Year Questions (PYQs) [PYQ 2017, 2018, 2019, 2020, 2021, 2023, 2024, 2025]

• [PYQ 2018, 2019]: Define Decoder, MUX, DeMUX. (06 Marks)
• [PYQ 2017, 2019, 2020, 2023, 2024, 2025]: 2,4,2,1 to 8,4,-2,-1 code converter. (14 Marks)
• [PYQ 2021]: Implement Full-Adder using two 4x1 MUXes. (10 Marks)
• [PYQ 2019]: Implement Full-Adder using 3-to-8 decoder and two OR gates. (07 Marks)
• [PYQ 2018]: Design BCD to 7-segment decoder. (12 Marks)
• [PYQ 2023]: Implement 1-to-16 DeMUX tree or basic DeMUX operation. (08 Marks)

---

Related Concepts: 01 Arithmetic Circuits, Multipliers & Comparators | 02 Code Converters & Data Routing Implementations | 04 Programmable Logic Devices (ROM & PLA)

5.03 Tree Networks (Cascading MUX, Decoders & DeMUX)

Concept Overview: MSI Tree Networks

When required system line counts exceed single IC capacity, smaller Medium Scale Integration (MSI) components are cascaded into Tree Networks.

• Multiplexers: Level-1 outputs feed into Level-2 data inputs.
• Decoders & Demultiplexers: Master decoder uses MSBs to drive the Enable ($E$) pins of Slave decoders sharing LSB select lines.

graph TD
    subgraph 16-to-1 MUX Tree Architecture
        LSB[LSB Selects S1 S0] --> M1[4x1 MUX 1: D0-D3] & M2[4x1 MUX 2: D4-D7] & M3[4x1 MUX 3: D8-D11] & M4[4x1 MUX 4: D12-D15]
        M1 & M2 & M3 & M4 --> OutLevel1[4 Intermediate Outputs]
        OutLevel1 --> MUX_Final[Level 2: 4x1 MUX Driven by MSBs S3 S2]
        MUX_Final --> FinalOut[16-to-1 Output Y]
    end

---

1. 16-to-1 MUX using 4-to-1 MUXes

Major PYQ Problem (2016, 2017 - 8 Marks)

Question: Design a 16-to-1 Multiplexer using 4-to-1 Multiplexers.

Wiring Architecture:

• Level 1 (4 MUXes): Receives inputs $D_0\dots D_{15}$. LSB select lines $S_1,S_0$ are connected in parallel to all four MUXes.
• Level 2 (1 MUX): Receives the 4 intermediate outputs from Level 1. MSB select lines $S_3,S_2$ select which block output reaches final $Y$.
• Total Chips: $4+1=5\text{ MUXes}$.

---

2. Decoder Expansion Tree Networks

graph TD
    subgraph Master-Slave Decoder Expansion
        MSB[MSB Inputs A B] --> Master[Master 2x4 Decoder]
        Master -->|O0| E1[Enable Slave 1: Out 0-7]
        Master -->|O1| E2[Enable Slave 2: Out 8-15]
        Master -->|O2| E3[Enable Slave 3: Out 16-23]
        Master -->|O3| E4[Enable Slave 4: Out 24-31]
        
        LSB[LSB Inputs C D E] -->|Parallel Selects| E1 & E2 & E3 & E4
    end

A. 4-to-16 Decoder using Five 2-to-4 Decoders

• Master Decoder (1 Chip): Driven by MSBs $A,B$. Outputs $O_0\dots O_3$ drive Enable pins of Slaves.
• Slave Decoders (4 Chips): Driven by LSBs $C,D$ in parallel. Generates outputs $D_0\dots D_{15}$.

B. 5-to-32 Decoder using Four 3x8 and One 2x4 Decoders

• Master Decoder (2x4 Decoder): Driven by MSBs $A,B$. Outputs $O_0\dots O_3$ drive Enable pins of 3x8 Slaves.
• Slave Decoders (Four 3x8 Decoders): Driven by LSBs $C,D,E$ in parallel. Generates 32 outputs ($0\dots 31$).

---

3. 1x16 Demultiplexer using 2-to-4 Decoders

Major PYQ Problem (2023 - 7 Marks)

Question: Implement a 1x16 Demultiplexer using 2-to-4 decoders.

• Architecture: Wire five 2-to-4 decoders. Connect global Data Input ($D_{in}$) to the Enable pin of the Master decoder. MSBs $S_3,S_2$ drive Master select pins. LSBs $S_1,S_0$ drive Slave select pins in parallel.

---

Past Year Questions (PYQs)

• [PYQ 2016, 2017]: 16-to-1 MUX using 4-to-1 MUXes. (08 Marks)
• [PYQ 2021]: 4-to-16 decoder using five 2-to-4 decoders. (10 Marks)
• [PYQ 2024, 2025]: 5-to-32 decoder using four 3x8 and one 2x4 decoder. (10 Marks)
• [PYQ 2023]: 1x16 Demux using 2-to-4 decoders. (07 Marks)

---

Related Concepts: 01 Arithmetic Circuits, Multipliers & Comparators | 02 Code Converters & Data Routing Implementations | 05 Application-Specific Word Problems

5.04 Programmable Logic Devices (ROM & PLA)

PLD Classifications

Programmable Logic Devices (PLDs) replace custom SSI logic networks with dense arrays of AND and OR gates connected via programmable fuses.

• ROM: Fixed AND array (decoder) + Programmable OR array.
• PAL: Programmable AND array + Fixed OR array.
• PLA: Programmable AND array + Programmable OR array {maximum term-sharing flexibility}.

graph LR
    subgraph PLA Architecture
        Inputs[Inputs A B C] --> Buffers[Input Buffers / Inverters]
        Buffers --> ProgAND[Programmable AND Array: k Product Terms]
        ProgAND --> ProgOR[Programmable OR Array: m Outputs]
        ProgOR --> ProgInv[Programmable Output Inverters XOR/Fuses]
        ProgInv --> FinalOutputs[Outputs F1 F2]
    end

---

1. ROM Design: 3-Bit Input Square Generator

Major PYQ Problem (2015, 2017, 2020, 2021, 2025 - 8 Marks)

Question: Design a combinational circuit using a ROM that accepts a 3-bit number and generates an output equal to its square.

Solution & Optimization:

• Inputs: 3 bits ($A_2{A}_1{A}_0$, Max $7_{10}=111_2$).
• Outputs: Max $7^2=49_{10}=110001_2⟹6$ bits ($B_5{B}_4{B}_3{B}_2{B}_1{B}_0$).

Truth Table:

Decimal	Inputs ($A_2{A}_1{A}_0$)	Outputs ($B_5{B}_4{B}_3{B}_2{B}_1{B}_0$)
$0\to 0$	0 0 0	0 0 0 0 0 0
$1\to 1$	0 0 1	0 0 0 0 0 1
$2\to 4$	0 1 0	0 0 0 1 0 0
$3\to 9$	0 1 1	0 0 1 0 0 1
$4\to 16$	1 0 0	0 1 0 0 0 0
$5\to 25$	1 0 1	0 1 1 0 0 1
$6\to 36$	1 1 0	1 0 0 1 0 0
$7\to 49$	1 1 1	1 1 0 0 0 1

Circuit Hardware Optimization:

• Notice $B_0=A_0$ directly {no ROM needed}.
• Notice $B_1=0$ permanently {hardwired to Ground}.
• ROM Size Required: $2^3\times 4=8\times 4\text{ ROM}$ to generate $B_5,B_4,B_3,B_2$. $■$

---

2. PLA Design: Shared Product Terms

Major PYQ Problem (2015, 2023, 2024, 2025 - 11 Marks)

Question: Implement $F_1(A,B,C)=\sum m(3,5,6,7)$ and $F_2(A,B,C)=\sum m(0,2,4,7)$ with a PLA having 3 inputs, 4 product terms, and 2 outputs.

Solution:

Simplify $F_1,F_1^{\prime }$ and $F_2,F_2^{\prime }$:

• $F_1^{\prime }=B^{\prime }{C}^{\prime }+A^{\prime }{C}^{\prime }+A^{\prime }{B}^{\prime }$
• $F_2=B^{\prime }{C}^{\prime }+A^{\prime }{C}^{\prime }+ABC$

Selecting $F_1^{\prime }$ (Complement form) and $F_2$ (True form) shares product terms $B^{\prime }{C}^{\prime }$ and $A^{\prime }{C}^{\prime }$! The 4 distinct AND terms are: $B^{\prime }{C}^{\prime },A^{\prime }{C}^{\prime },A^{\prime }{B}^{\prime },ABC$.

PLA Program Table:

Product Term	Inputs ($A,B,C$)	Outputs ($F_1,F_2$)
1. $B^{\prime }{C}^{\prime }$	- 0 0	1 1
2. $A^{\prime }{C}^{\prime }$	0 - 0	1 1
3. $A^{\prime }{B}^{\prime }$	0 0 -	1 -
4. $ABC$	1 1 1	- 1
Output Mode:		C T

---

Past Year Questions (PYQs)

• [PYQ 2017, 2024, 2025]: Distinguish between ROM and PLA. (06 Marks)
• [PYQ 2017, 2018]: Internal block diagram of PLA. (05 Marks)
• [PYQ 2015, 2017, 2020, 2021, 2025]: 3-bit square generator $8\times 4$ ROM design. (08 Marks)
• [PYQ 2015, 2023, 2024, 2025]: PLA design with shared product terms. (11 Marks)

---

Related Concepts: 01 Arithmetic Circuits, Multipliers & Comparators | 02 Code Converters & Data Routing Implementations | 04 Programmable Logic Devices (ROM & PLA)

5.05 Application-Specific Word Problems

Real-World Logic Synthesis

Application-specific word problems test your ability to convert a real-world scenario into formal Boolean expressions: defining input/output variables $\to$ constructing the truth table $\to$ simplifying via K-map $\to$ drawing the hardware circuit.

---

1. The Restaurant Voting Tie-Breaker Logic

Major PYQ Problem (2016 - 11 Marks)

Scenario: Mom ($A$), Dad ($B$), Joe ($C$), Sue ($D$) vote: Vegetables ($1$) vs. Chicken ($0$). Rules:

1. Majority vote wins.
2. If Mom and Dad agree, they win regardless of the kids.
3. Any other tie votes result in Chicken ($0$).

Solution:

• Minterms where $Y=1$: $Y=\Sigma m(7,11,12,13,14,15)$
• K-map simplification:
  • Quad $(12,13,14,15)\to AB$ (Mom & Dad agree)
  • Pair $(7,15)\to BCD$
  • Pair $(11,15)\to ACD$ $\mathbf{Y}=\mathbf{AB}+\mathbf{ACD}+\mathbf{BCD}=\mathbf{AB}+\mathbf{CD}(\mathbf{A}+\mathbf{B})■$

---

2. The Spaceship Battery Monitor

Major PYQ Problem (2017 - 13 Marks)

Scenario: A 4-bit A/D converter ($A,B,C,D$) monitors a 0-15V battery. Generate HIGH output if voltage $>6\text{V}$.

Solution:

• Minterms for $>6\text{V}$: $Y=\Sigma m(7,8,9,10,11,12,13,14,15)$
• K-map simplification: Octet $(8\dots 15)\to A$, Pair $(7,15)\to BCD$. $\mathbf{Y}=\mathbf{A}+\mathbf{BCD}■$

---

3. Gas-Fired Boiler Alarm System

Major PYQ Problem (2021 - 10 Marks)

Scenario: Flame ($F$), Chimney Temp ($C$), Water Temp ($W$), Pressure ($P$). Alarm triggers if flame ignited AND chimney temp OR water temp OR pressure is high.

$\text{Alarm}=\mathbf{F}\cdot (\mathbf{C}+\mathbf{W}+\mathbf{P})■$

---

4. 4-Bit Divisibility Indicator (Divisible by 2 and 3)

Major PYQ Problem (2022 - 8 Marks)

Scenario: 4-bit input ($A,B,C,D$). Output $Z_1=1$ if divisible by 2; $Z_2=1$ if divisible by 3.

Solution:

• Divisible by 2 ($Z_1$): LSB must be $0⟹{\mathbf{Z}}_1={\mathbf{D}}^{\prime }$
• Divisible by 3 ($Z_2$): Numbers $0,3,6,9,12,15⟹Z_2=\sum m(0,3,6,9,12,15)$ ${\mathbf{Z}}_2=(\mathbf{A}\odot \mathbf{B})(\mathbf{C}\odot \mathbf{D})+{\mathbf{A}}^{\prime }\mathbf{BC}{\mathbf{D}}^{\prime }+\mathbf{A}{\mathbf{B}}^{\prime }{\mathbf{C}}^{\prime }\mathbf{D}■$

---

Past Year Questions (PYQs)

• [PYQ 2016]: Restaurant voting logic. (11 Marks)
• [PYQ 2017]: Spaceship battery monitor logic. (13 Marks)
• [PYQ 2021]: Boiler alarm logic. (10 Marks)
• [PYQ 2022]: Binary divisibility indicator for 2 and 3. (08 Marks)

---

Related Concepts: 02 Code Converters & Data Routing Implementations | 03 Tree Networks (Cascading MUX, Decoders & DeMUX) | 04 Programmable Logic Devices (ROM & PLA)

5.06 Combinational Hardware Edge Cases & Logic Synthesis

Hardware Restrictions & Synthesis

Advanced exam questions test your ability to synthesize functions into restricted hardware architectures {such as designing a MUX using ONLY NAND gates or expanding unsimplified equations for a Decoder}.

---

1. Design a 4-to-1 MUX using ONLY NAND Gates

Major PYQ Problem (2018 - 10 Marks)

Question: Design a 4-to-1 line multiplexer using NAND gates.

Solution:

1. MUX SOP Equation: $Y=S_1^{\prime }{S}_0^{\prime }{I}_0+S_1^{\prime }{S}_0{I}_1+S_1{S}_0^{\prime }{I}_2+S_1{S}_0{I}_3$
2. NAND-NAND Transformation: $Y=\overline{\overline{S_1^{\prime }{S}_0^{\prime }{I}_0}\cdot \overline{S_1^{\prime }{S}_0{I}_1}\cdot \overline{S_1{S}_0^{\prime }{I}_2}\cdot \overline{S_1{S}_0{I}_3}}$
3. Circuit Construction:
   • Two 2-input NAND gates (inputs tied) to produce $S_1^{\prime }$ and $S_0^{\prime }$.
   • Four 3-input NAND gates in Level 1.
   • One 4-input NAND gate in Level 2. $■$

---

2. Multi-Equation Decoder Implementation

Major PYQ Problem (2016, 2017, 2019, 2020 - 12 Marks)

Question: Design a circuit using a 3-to-8 decoder and external OR gates for:

• $F_1=x^{\prime }{y}^{\prime }+xy{z}^{\prime }$
• $F_2=x^{\prime }+y$
• $F_3=xy+x^{\prime }{y}^{\prime }$

Canonical Minterm Expansion Solution:

1. Expand $F_1$: $x^{\prime }{y}^{\prime }(z+z^{\prime })+xy{z}^{\prime }=x^{\prime }{y}^{\prime }z+x^{\prime }{y}^{\prime }{z}^{\prime }+xy{z}^{\prime }⟹{\mathbf{F}}_1=\sum \mathbf{m}(0,1,6)$

2. Expand $F_2$: $x^{\prime }(y+y^{\prime })(z+z^{\prime })+y(x+x^{\prime })(z+z^{\prime })⟹{\mathbf{F}}_2=\sum \mathbf{m}(0,1,2,3,6,7)$

3. Expand $F_3$: $xy(z+z^{\prime })+x^{\prime }{y}^{\prime }(z+z^{\prime })⟹{\mathbf{F}}_3=\sum \mathbf{m}(0,1,6,7)$

Circuit Implementation:

• Connect inputs $x,y,z$ to a 3-to-8 decoder.
• $F_1$: Wire decoder pins 0, 1, 6 into a 3-input OR gate.
• $F_2$: Wire decoder pins 0, 1, 2, 3, 6, 7 into a 6-input OR gate (or pins 4, 5 into a 2-input NOR gate).
• $F_3$: Wire decoder pins 0, 1, 6, 7 into a 4-input OR gate. $■$

---

3. Combinational Circuit Analysis Blueprint [PYQ 2016, 2018, 2020]

Combinational circuit analysis is the reverse-engineering process of determining the logical function of an existing gate-level schematic.

3.1 The 4-Step Analysis Algorithm

1. Label Intermediate Outputs: Assign distinct algebraic variables (e.g., $T_1,T_2,T_3$) to all intermediate gate output lines that are not connected directly to the primary inputs.
2. Write Intermediate Boolean Equations: Starting from the input side and moving towards the output, write the Boolean expression for each intermediate labeled node.
3. Formulate Output Equations: Derive the final Boolean equations for the primary circuit outputs in terms of the primary inputs.
4. Construct the Truth Table:
   • List all $2^n$ binary input combinations.
   • Evaluate the intermediate and final equations for each input state to fill in the outputs.
   • Analyze the truth table or algebraically simplify the output equations to identify the circuit’s overall function (e.g., Adder, Comparator, Decoder).

Worked Example: Logic Circuit Analysis

Question: Analyze the logic circuit with inputs $A,B,C$ and outputs $F_1,F_2$.

• $T_1=A\cdot B$ (Output of AND gate 1)
• $T_2=A+C$ (Output of OR gate 2)
• $F_1=T_1\oplus C$
• $F_2=T_2\cdot B^{\prime }$

Truth Table Construction:

A B C	T1 (AB)	T2 (A+C)	F1 (T1 ⊕ C)	F2 (T2 • B’)
0 0 0	0	0	0	0
0 0 1	0	1	1	1
0 1 0	0	0	0	0
0 1 1	0	1	1	0
1 0 0	0	1	0	1
1 0 1	0	1	1	1
1 1 0	1	1	1	0
1 1 1	1	1	0	0

Simplified Output Equations:

• $F_1=(AB)\oplus C$
• $F_2=(A+C)B^{\prime }$

---

4. Past Year Questions (PYQs) [PYQ 2016, 2017, 2018, 2019, 2020]

• [PYQ 2018]: 4-to-1 MUX using ONLY NAND gates. (10 Marks)
• [PYQ 2016, 2017, 2019, 2020]: Multi-equation decoder implementation with unsimplified expressions. (12 Marks)
• [PYQ 2016, 2018, 2022]: Analyze a given logic circuit with gates to extract its Boolean function and truth table. (10 Marks)

---