PAST-PAPER PRACTICE Choose a paper All papers 2025 T2 End-term (AN) 2025 T2 End-term (FN) 2026 T2 End-term 2025 T2 Quiz 2 2026 T2 Quiz 2 2025 T3 End-term 2025 T2 Quiz 1 2025 T3 End-term (AN) 2025 T3 End-term (FN) 2025 T3 Quiz 1 2026 T2 Quiz 1
20 of 20 questions shown
Start here Week 4 (decoders, encoders, multiplexers)
gives sure marks in every paper: true/false facts, delay, “read this MUX
circuit”, “read this decoder circuit”, “minimum number of MUXes” and
priority encoders. This page teaches each method from zero, then solves
every Week 4 question from the 11 past papers , each
with the paper it came from. Two answer keys were wrong. Those are
marked.
How to read this page: each grey “Asked in” box is a
real past-paper question. Below it, How to solve shows
every step.
These sentences come back again and again. Learn the answers.
Question: “In a decoder, at any point, exactly one
of the outputs is 1 and all the rest are 0s.”
Show solution a decoder turns each input pattern
into exactly one active output line. For 2 inputs = 10,
only D 2 = 1 D_{2} = 1 D 2 = 1
Question: “A multiplexer selects one of several
input signals and forwards it to a single output line.”
Show solution this is the definition of a MUX. Many
inputs, one output, and the select lines choose which input gets
through.
Question: “A decoder performs the inverse operation
of a multiplexer.”
Show solution a MUX takes many lines → one line. A
decoder with an enable input works as a demultiplexer :
one line → many lines, the reverse. Strictly, a decoder is the inverse
of an encoder , but the exam’s answer is
True .
Find the longest chain of gates from any input to
the output.
Add the delays of the gates in that chain. Gates
side by side don’t add up; only gates one after another do.
Block
Longest chain
2 : 1 MUX ( Y = S ‾ ⋅ I 0 + S ⋅ I 1 ) 2 : 1 \operatorname{MUX} \left(Y = \overline{S} \cdot I_{0} + S \cdot I_{1}\right) 2 : 1 MUX ( Y = S ⋅ I 0 + S ⋅ I 1 ) NOT → AND → OR
n : 2 n n : 2^{n} n : 2 n NOT → AND
3:8 decoder from 2-input ANDs
NOT → AND → AND (a 3-input AND needs two 2-input ANDs in a row)
Question: NOT has a delay of 1 ns, and 2-input
AND/OR have 2 ns. Maximum delay of a 2 × 1 MUX a 2 \times 1 \operatorname{MUX} a 2 × 1 MUX
Show solution
Chain: S → NOT → AND → OR → Y
A d d : 1 + 2 + 2 = A d d : 1 + 2 + 2 = A dd : 1 + 2 + 2 = 5 ns ✔ Question: NOT and 2-input AND/OR all have a delay of
1 ns. Maximum delay of a 2 × 1 MUX a 2 \times 1 \operatorname{MUX} a 2 × 1 MUX
Show solution same chain NOT → AND → OR = 1 + 1 + 1 = \operatorname{NOT} \to \operatorname{AND} \to \operatorname{OR} = 1 + 1 + 1 = NOT → AND → OR = 1 + 1 + 1 = 3 ns ✔
Question: NOT and 2-input AND/OR all have 1 ns
delay. Maximum delay of a 3 × 8 a 3 \times 8 a 3 × 8
Show solution
Each output is a 3-input AND, like A ‾ ⋅ B ⋅ C ‾ \overline{A} \cdot B \cdot \overline{C} A ⋅ B ⋅ C AND ( AND ( A ‾ , B ) , C ‾ ) → \operatorname{AND} \left(\operatorname{AND} \left(\overline{A} , B\right) , \overline{C}\right) \to AND ( AND ( A , B ) , C ) → 2 ANDs in a row .
Before that, the input goes through a NOT.
Chain: NOT → AND → AND = 1 + 1 + 1 = \operatorname{NOT} \to \operatorname{AND} \to \operatorname{AND} = 1 + 1 + 1 = NOT → AND → AND = 1 + 1 + 1 = 3 ns ✔
Question: A 4 × 16 A 4 \times 1 6 A 4 × 16
Show solution each output is one 4-input AND. Chain:
NOT → AND = 1 + 2 = \operatorname{NOT} \to \operatorname{AND} = 1 + 2 = NOT → AND = 1 + 2 = 3 ns ✔
Make a table with one row for each select
pattern .
In each row, write which signal reaches the output.
Look for the pattern, then test every option with
numbers.
Level 1: 2 : 1 MUX , S = A , I 0 = 0 , I 1 = B 2 : 1 \operatorname{MUX} , S = A , I_{0} = 0 , I_{1} = B 2 : 1 MUX , S = A , I 0 = 0 , I 1 = B A = 0 → 0 A = 0 \to 0 A = 0 → 0 A = 1 → B A = 1 \to B A = 1 → B F = F = F = AB .
Enlarge diagram ↗ Open full size diagram ↗ Fill one row per select pattern. Here
the output only follows Z, so F = X ⊕ Z F = X \oplus Z F = X ⊕ Z Question: 4 × 1 MUX : I 0 = X , I 1 = X ‾ , I 2 = X , I 3 = X ‾ 4 \times 1 \operatorname{MUX} : I_{0} = X , I_{1} = \overline{X} , I_{2} = X , I_{3} = \overline{X} 4 × 1 MUX : I 0 = X , I 1 = X , I 2 = X , I 3 = X S 1 = Y , S 0 = Z S_{1} = Y , S_{0} = Z S 1 = Y , S 0 = Z X ( Z ‾ + Y Z ) + X ‾ ⋅ Y ⋅ Z / X ( Z ‾ + Y Z ) + X ‾ ⋅ Y ‾ ⋅ Z / X ( Z + Y Z ) + X ‾ ⋅ Y ‾ ⋅ Z / X ( Z ‾ + Y Z ) + X ⋅ Y ‾ ⋅ Z X \left(\overline{Z} + Y Z\right) + \overline{X} \cdot Y \cdot Z / X \left(\overline{Z} + Y Z\right) + \overline{X} \cdot \overline{Y} \cdot Z / X \left(Z + Y Z\right) + \overline{X} \cdot \overline{Y} \cdot Z / X \left(\overline{Z} + Y Z\right) + X \cdot \overline{Y} \cdot Z X ( Z + Y Z ) + X ⋅ Y ⋅ Z / X ( Z + Y Z ) + X ⋅ Y ⋅ Z / X ( Z + Y Z ) + X ⋅ Y ⋅ Z / X ( Z + Y Z ) + X ⋅ Y ⋅ Z
Show solution
Table:
Y ( S 1 ) Y \left(S_{1}\right) Y ( S 1 ) Z ( S 0 ) Z \left(S_{0}\right) Z ( S 0 ) Input chosen
F
0
0
I 0 I_{0} I 0 X
0
1
I 1 I_{1} I 1 X ‾ \overline{X} X
1
0
I 2 I_{2} I 2 X
1
1
I 3 I_{3} I 3 X ‾ \overline{X} X
Z = 0 → F = X Z = 0 \to F = X Z = 0 → F = X Z = 1 → F = X ‾ Z = 1 \to F = \overline{X} Z = 1 → F = X F = X ⊕ Z F = X \oplus Z F = X ⊕ Z Test the keyed option at X = 1 , Y = 1 , Z = 1 : X ( Z ‾ + Y Z ) + X ‾ Y ‾ Z = 1 ⋅ ( 0 + 1 ) + 0 = X = 1 , Y = 1 , Z = 1 : X \left(\overline{Z} + Y Z\right) + \overline{X} \overline{Y} Z = 1 \cdot \left(0 + 1\right) + 0 = X = 1 , Y = 1 , Z = 1 : X ( Z + Y Z ) + X Y Z = 1 ⋅ ( 0 + 1 ) + 0 = 1 . The circuit gives I 3 = X ‾ = I_{3} = \overline{X} = I 3 = X = 0 ✗
No option equals X ⊕ Z → X \oplus Z \to X ⊕ Z → None of these . (We checked
all 8 rows by computer.)
Question: The same MUX circuit ( I 0 = X , I 1 = X ‾ , I 2 = X , I 3 = X ‾ , S 1 = Y , S 0 = Z ) \left(I_{0} = X , I_{1} = \overline{X} , I_{2} = X , I_{3} = \overline{X} , S_{1} = Y , S_{0} = Z\right) ( I 0 = X , I 1 = X , I 2 = X , I 3 = X , S 1 = Y , S 0 = Z ) X ⊕ Y / X ⊙ Y / X + Y / X Y X \oplus Y / X \odot Y / X + Y / X Y X ⊕ Y / X ⊙ Y / X + Y / X Y
Show solution
Same table as above → F = X ⊕ Z F = X \oplus Z F = X ⊕ Z
The key says X ⊕ Y X \oplus Y X ⊕ Y X = 0 , Y = 1 , Z = 0 : X ⊕ Y = 1 X = 0 , Y = 1 , Z = 0 : X \oplus Y = 1 X = 0 , Y = 1 , Z = 0 : X ⊕ Y = 1 I 2 = X = I_{2} = X = I 2 = X = 0 ✗
F depends on Z ( S 0 ) \left(S_{0}\right) ( S 0 ) X ⊕ Z → X \oplus Z \to X ⊕ Z → None of these .
Every decoder output Dₖ is minterm k. If Dₖ goes into the OR, then
k is in Σ m \Sigma m Σ m .
Follow each wire carefully. A wire can bend and join another
line.
Simplify, then answer what is asked.
Question: A 3:8 decoder (A, B, C) has D 2 , D 3 , D 5 , D 6 D_{2} , D_{3} , D_{5} , D_{6} D 2 , D 3 , D 5 , D 6
Show solution
Y = Σ m ( 2 , 3 , 5 , 6 ) = 010 , 011 , 101 , 110 Y = \Sigma m \left(2 , 3 , 5 , 6\right) = 0 1 0 , 0 1 1 , 1 0 1 , 1 1 0 Y = Σ m ( 2 , 3 , 5 , 6 ) = 010 , 011 , 101 , 110 Split on A:
A = 0 A = 0 A = 0 Y = B Y = B Y = B A = 1 A = 1 A = 1 Y = B ⊕ C Y = B \oplus C Y = B ⊕ C
So Y = A ‾ ⋅ B + A ⋅ ( B ⊕ C ) = Y = \overline{A} \cdot B + A \cdot \left(B \oplus C\right) = Y = A ⋅ B + A ⋅ ( B ⊕ C ) = B ⊕ A C B \oplus A C B ⊕ A C
Build with MUXes (NOT costs a MUX):
M1 = MUX ( S = A , I 0 = 0 , I 1 = C ) = \operatorname{MUX} \left(S = A , I_{0} = 0 , I_{1} = C\right) = MUX ( S = A , I 0 = 0 , I 1 = C ) = AC
M2 = MUX \operatorname{MUX} MUX NOT(AC)
Y = MUX Y = \operatorname{MUX} Y = MUX I 1 = I_{1} = I 1 = B ⊕ A C B \oplus A C B ⊕ A C
Total 3 ✔ (a computer search confirmed 2 is
impossible)
Question: The same decoder circuit. Using 2-input
XOR gates plus NAND gates, minimum number of NAND
gates?
Show solution
Y = B ⊕ A C Y = B \oplus A C Y = B ⊕ A C The XOR is free (XOR gates are given). We only need
AC from NANDs.
AND from NAND = \operatorname{NAND} = NAND = 2 : G1 = NAND(A, C), G2 = NAND(G1,
G1) = AC ✔
Question: The same decoder circuit. Using only
4:1 MUXes, minimum number?
Show solution
Put A, B on the select lines ( S 1 = A , S 0 = B ) \left(S_{1} = A , S_{0} = B\right) ( S 1 = A , S 0 = B )
A B
Rows
Y
Input
00
0, 1
0, 0
I 0 = I_{0} = I 0 = 0
01
2, 3
1, 1
I 1 = I_{1} = I 1 = 1
10
4, 5
0, 1
I 2 = I_{2} = I 2 = C
11
6, 7
1, 0
I 3 = I_{3} = I 3 = C ‾ \overline{C} C
One 4:1 MUX does it → 1 ✔
Note: this assumes C ‾ \overline{C} C C ‾ \overline{C} C Rules the papers use: the variables and 0, 1 are
free. A NOT costs one MUX : A ‾ = MUX ( S = A , I 0 = 1 , I 1 = 0 ) \overline{A} = \operatorname{MUX} \left(S = A , I_{0} = 1 , I_{1} = 0\right) A = MUX ( S = A , I 0 = 1 , I 1 = 0 )
Splitting on one variable: F = A ‾ F = \overline{A} F = A A = 0 , I 1 = F A = 0 , I_{1} = F A = 0 , I 1 = F A = 1 A = 1 A = 1
Function
2:1 MUXes
How
A ⋅ B A \cdot B A ⋅ B 1
MUX ( S = A , I 0 = 0 , I 1 = B ) \operatorname{MUX} \left(S = A , I_{0} = 0 , I_{1} = B\right) MUX ( S = A , I 0 = 0 , I 1 = B )
A + B A + B A + B 1
MUX ( S = A , I 0 = B , I 1 = 1 ) \operatorname{MUX} \left(S = A , I_{0} = B , I_{1} = 1\right) MUX ( S = A , I 0 = B , I 1 = 1 )
A ‾ \overline{A} A 1
MUX ( S = A , I 0 = 1 , I 1 = 0 ) \operatorname{MUX} \left(S = A , I_{0} = 1 , I_{1} = 0\right) MUX ( S = A , I 0 = 1 , I 1 = 0 )
A ⊕ B A \oplus B A ⊕ B 2
B ‾ \overline{B} B MUX ( S = A , I 0 = B , I 1 = B ‾ ) \operatorname{MUX} \left(S = A , I_{0} = B , I_{1} = \overline{B}\right) MUX ( S = A , I 0 = B , I 1 = B )
A ⊙ B A \odot B A ⊙ B 2
B ‾ \overline{B} B MUX ( S = A , I 0 = B ‾ , I 1 = B ) \operatorname{MUX} \left(S = A , I_{0} = \overline{B} , I_{1} = B\right) MUX ( S = A , I 0 = B , I 1 = B )
Question: Minimum 2:1 MUXes for A ⊙ B ( XNOR ) A \odot B \left(\operatorname{XNOR}\right) A ⊙ B ( XNOR )
Show solution
Split on A : A = 0 → F = B ‾ A : A = 0 \to F = \overline{B} A : A = 0 → F = B A = 1 → F = B A = 1 \to F = B A = 1 → F = B
We need B ‾ → \overline{B} \to B → MUX ( S = B , I 0 = 1 , I 1 = 0 ) \operatorname{MUX} \left(S = B , I_{0} = 1 , I_{1} = 0\right) MUX ( S = B , I 0 = 1 , I 1 = 0 )
F = MUX F = \operatorname{MUX} F = MUX 2 ✔ Question: Minimum 2:1 MUXes for A ⊕ B ( XOR ) A \oplus B \left(\operatorname{XOR}\right) A ⊕ B ( XOR )
Show solution split on A : A = 0 → B , A = 1 → B ‾ A : A = 0 \to B , A = 1 \to \overline{B} A : A = 0 → B , A = 1 → B B ‾ ( 1 MUX ) + \overline{B} \left(1 \operatorname{MUX}\right) + B ( 1 MUX ) + MUX ( 1 ) = \operatorname{MUX} \left(1\right) = MUX ( 1 ) = 2 .
Question: Minimum 2:1 MUXes for F ( X , Y ) = Π ( 0 , 3 ) F \left(X , Y\right) = \Pi \left(0 , 3\right) F ( X , Y ) = Π ( 0 , 3 )
Show solution
F = 0 F = 0 F = 0 3 ( 11 ) → F = 1 3 \left(1 1\right) \to F = 1 3 ( 11 ) → F = 1 F = X ⊕ Y F = X \oplus Y F = X ⊕ Y XOR = \operatorname{XOR} = XOR = 2 MUXes ✔ Question: Minimum 2:1 MUXes for F ( X , Y , Z ) = Π ( 0 , 4 ) F \left(X , Y , Z\right) = \Pi \left(0 , 4\right) F ( X , Y , Z ) = Π ( 0 , 4 )
Show solution
F = 0 F = 0 F = 0 100 → F = 0 1 0 0 \to F = 0 100 → F = 0 Y = 0 Y = 0 Y = 0 Z = 0 → Z = 0 \to Z = 0 → F = Y + Z F = Y + Z F = Y + Z OR = \operatorname{OR} = OR = 1 MUX : MUX ( S = Y , I 0 = Z , I 1 = 1 ) \operatorname{MUX} : \operatorname{MUX} \left(S = Y , I_{0} = Z , I_{1} = 1\right) MUX : MUX ( S = Y , I 0 = Z , I 1 = 1 ) Question: Minimum 2:1 MUXes for F = Σ ( 0 , 2 , 8 , 10 ) F = \Sigma \left(0 , 2 , 8 , 1 0\right) F = Σ ( 0 , 2 , 8 , 10 )
Show solution
F = B ‾ ⋅ D ‾ F = \overline{B} \cdot \overline{D} F = B ⋅ D D = 0 D = 0 D = 0 Split on B : B = 0 → D ‾ B : B = 0 \to \overline{D} B : B = 0 → D B = 1 → 0 B = 1 \to 0 B = 1 → 0
Make D ‾ ( 1 MUX ) \overline{D} \left(1 \operatorname{MUX}\right) D ( 1 MUX ) MUX ( S = B , I 0 = D ‾ , I 1 = 0 ) ( 1 MUX ) → \operatorname{MUX} \left(S = B , I_{0} = \overline{D} , I_{1} = 0\right) \left(1 \operatorname{MUX}\right) \to MUX ( S = B , I 0 = D , I 1 = 0 ) ( 1 MUX ) → 2 ✔
Question: Minimum 2:1 MUXes for F = Σ ( 0 , 1 , 2 , 3 , 4 , 5 , 7 ) F = \Sigma \left(0 , 1 , 2 , 3 , 4 , 5 , 7\right) F = Σ ( 0 , 1 , 2 , 3 , 4 , 5 , 7 )
Show solution
F = 0 F = 0 F = 0 6 ( 110 ) → F = A ‾ + B ‾ + C 6 \left(1 1 0\right) \to F = \overline{A} + \overline{B} + C 6 ( 110 ) → F = A + B + C Split on A : A = 0 → A : A = 0 \to A : A = 0 → 1 . A = 1 → B ‾ + C A = 1 \to \overline{B} + C A = 1 → B + C
B ‾ + C \overline{B} + C B + C B : B = 0 → 1 , B = 1 → C → MUX ( S = B , I 0 = 1 , I 1 = C ) B : B = 0 \to 1 , B = 1 \to C \to \operatorname{MUX} \left(S = B , I_{0} = 1 , I_{1} = C\right) B : B = 0 → 1 , B = 1 → C → MUX ( S = B , I 0 = 1 , I 1 = C ) no NOT needed .F = MUX F = \operatorname{MUX} F = MUX 2
✔ Question: Minimum 2:1 MUXes for F ( X , Y , Z ) = ( 4 , 5 , 6 , 7 ) F \left(X , Y , Z\right) = \left(4 , 5 , 6 , 7\right) F ( X , Y , Z ) = ( 4 , 5 , 6 , 7 )
Show solution
The paper forgot to write Σ or Π.
I f Σ : F = 1 I f \Sigma : F = 1 I f Σ : F = 1 F = X F = X F = X 0 MUXes (just a wire).I f Π : F = 0 I f \Pi : F = 0 I f Π : F = 0 F = X ‾ F = \overline{X} F = X 1 MUX.Neither gives 2. The question is faulty. If it comes again, read the
symbol carefully.
Find the highest-numbered input that is 1 . It
wins.
Write its number in binary. Done.
Optional check: put the values into the given equations.
Question: A 4-to-2 priority encoder: L 3 L_{3} L 3 L 0 L_{0} L 0 Y 1 = L 3 + L 2 Y_{1} = L_{3} + L_{2} Y 1 = L 3 + L 2 Y 0 = L 3 + L 2 ‾ L 1 Y_{0} = L_{3} + \overline{L_{2}} L_{1} Y 0 = L 3 + L 2 L 1 ( L 3 , L 2 , L 1 , L 0 ) = ( 0 , 1 , 1 , 1 ) \left(L_{3} , L_{2} , L_{1} , L_{0}\right) = \left(0 , 1 , 1 , 1\right) ( L 3 , L 2 , L 1 , L 0 ) = ( 0 , 1 , 1 , 1 )
Show solution
The highest input that is 1 is L 2 L_{2} L 2 10
Check: Y 1 = 0 + 1 = Y_{1} = 0 + 1 = Y 1 = 0 + 1 = 1 ; Y 0 = 0 + ( L 2 ‾ = 0 ) ⋅ 1 = Y_{0} = 0 + \left(\overline{L_{2}} = 0\right) \cdot 1 = Y 0 = 0 + ( L 2 = 0 ) ⋅ 1 = 0 → 10 ✔
NOT = 2 \operatorname{NOT} = 2 NOT = 2 AND = OR = 3 \operatorname{AND} = \operatorname{OR} = 3 AND = OR = 3
2 + 3 + 3 = 8 ns.
4:1 MUX with I 0 = 0 , I 1 = 1 , I 2 = 1 , I 3 = 0 I_{0} = 0 , I_{1} = 1 , I_{2} = 1 , I_{3} = 0 I 0 = 0 , I 1 = 1 , I 2 = 1 , I 3 = 0 S 1 = A , S 0 = B S_{1} = A , S_{0} = B S 1 = A , S 0 = B
Rows 00 → 0 , 01 → 1 , 10 → 1 , 11 → 0 → F = A ⊕ B 0 0 \to 0 , 0 1 \to 1 , 1 0 \to 1 , 1 1 \to 0 \to F = A \oplus B 00 → 0 , 01 → 1 , 10 → 1 , 11 → 0 → F = A ⊕ B
A 3:8 decoder with D 1 , D 2 , D 4 , D 7 D_{1} , D_{2} , D_{4} , D_{7} D 1 , D 2 , D 4 , D 7
Σ m ( 1 , 2 , 4 , 7 ) = A ⊕ B ⊕ C \Sigma m \left(1 , 2 , 4 , 7\right) = A \oplus B \oplus C Σ m ( 1 , 2 , 4 , 7 ) = A ⊕ B ⊕ C
Minimum 2:1 MUXes for F = A ⋅ B ‾ F = A \cdot \overline{B} F = A ⋅ B
1 : MUX ( S = B , I 0 = A , I 1 = 0 ) 1 : \operatorname{MUX} \left(S = B , I_{0} = A , I_{1} = 0\right) 1 : MUX ( S = B , I 0 = A , I 1 = 0 )
Priority encoder input ( L 3 , L 2 , L 1 , L 0 ) = ( 1 , 0 , 0 , 1 ) \left(L_{3} , L_{2} , L_{1} , L_{0}\right) = \left(1 , 0 , 0 , 1\right) ( L 3 , L 2 , L 1 , L 0 ) = ( 1 , 0 , 0 , 1 )
L 3 L_{3} L 3 In one line: Learn the true/false facts, add delays
along the longest chain, read MUX/decoder circuits row by row, split on
one variable to count MUXes (NOT costs one), and for a priority encoder
just find the highest 1. Exam words: decoder, encoder,
priority encoder, multiplexer, select line, propagation delay, Σ m \Sigma m Σ m
