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 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). $■$

---

3. Carry Look-Ahead Mathematical Proof

Major Exam Proof: $C_{i+1}=G_i+P_i{C}_i$ (2018 - 10 Marks)

Question: Show that the output carry in a full-adder circuit can be expressed as $C_{i+1}=G_i+P_i{C}_i$.

Proof Steps:

1. Standard Full-Adder Carry Out: $C_{i+1}=A_i{B}_i+A_i{C}_i+B_i{C}_i=A_i{B}_i+C_i(A_i+B_i)$
2. Define Carry Generate ($G_i$): $G_i=A_i{B}_i$
3. Define Carry Propagate ($P_i$): $P_i=A_i\oplus B_i$
4. Substituting $G_i$ and $P_i$ yields: ${\mathbf{C}}_{\mathbf{i}+1}={\mathbf{G}}_{\mathbf{i}}+{\mathbf{P}}_{\mathbf{i}}{\mathbf{C}}_{\mathbf{i}}■$

---

4. 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.

---

5. 4-Bit Magnitude Equality Comparator

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

Question: Design a circuit that compares two 4-bit numbers ($A,B$) and outputs $x=1$ if $A=B$, and $x=0$ if $A\ne B$.

Solution:

1. Bitwise Equality via XNOR: $x_i=A_i\odot B_i=A_i{B}_i+A_i^{\prime }{B}_i^{\prime }$
2. Total Equality ($A=B$): $\mathbf{x}={\mathbf{x}}_3\cdot {\mathbf{x}}_2\cdot {\mathbf{x}}_1\cdot {\mathbf{x}}_0=({\mathbf{A}}_3\odot {\mathbf{B}}_3)({\mathbf{A}}_2\odot {\mathbf{B}}_2)({\mathbf{A}}_1\odot {\mathbf{B}}_1)({\mathbf{A}}_0\odot {\mathbf{B}}_0)$
3. Circuit: Four 2-input XNOR gates feeding into one 4-input AND gate. $■$

---

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)

---

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. Implementing Full-Adder using 4x1 Multiplexers

Major PYQ Problem (2021 - 10 Marks)

Inputs: $X,Y,Z$. Use two 4x1 MUXes (select lines $S_1=X,S_0=Y$).

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

---

4. 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)$. $■$

---

Past Year Questions (PYQs)

• [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]: Full-Adder using two 4x1 MUXes. (10 Marks)
• [PYQ 2019]: Full-Adder using 3-to-8 decoder and two OR gates. (07 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. $■$

---

Past Year Questions (PYQs)

• [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)

---