Related Concepts: 5.02 Code Converters & Data Routing Implementations | 5.03 Tree Networks (Cascading MUX, Decoders & DeMUX) | 5.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

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 Index for this note

Question (as asked)	Years	Marks	Solved in
Design a 4-to-1 line multiplexer using NAND gates	2018	10	§1
A combinational circuit is defined by $F_1=x^{\prime }{y}^{\prime }+xy{z}^{\prime }$, $F_2=x^{\prime }+y$, $F_3=xy+x^{\prime }{y}^{\prime }$. Design the circuit with a decoder and external gates	2016, 2017 (12), 2020 (10)	10–12	§3, and 5.02 Code Converters & Data Routing Implementations §5.1

Pattern to notice: the decoder-with-three-functions question has appeared three times with identical functions. The trap is that $F_1$, $F_2$ and $F_3$ arrive unsimplified — and you must not simplify them. A decoder supplies raw minterms, so the correct move is to expand each expression outwards into its full minterm list, then OR the corresponding pins. Simplifying first actively destroys the structure the question wants.

For circuit-analysis questions (“here is Fig. 2(b)/2(c) — find $F$”), see 4.07 Logic Analysis, Switching Circuits & Positive-Negative Logic §3, where the six-paper run of those questions is indexed.