--- title: "32:1 MUX tree; implement Σm(0,1,3,8,9,13,15)" subject: "Digital Logic" chapter: 4 key: "semester_3/digital_logic:mux-32to1-tree-function-15" source: https://www.bctengineer.com/q/semester_3/digital_logic/mux-32to1-tree-function-15 site: BCT Engineering --- # 32:1 MUX tree; implement Σm(0,1,3,8,9,13,15) Digital Logic · Chapter 4: Data Processing Circuits - Asked in: 2072 Chaitra, 4+3 marks - Video: [Implementation of Boolean Function using Multiplexers](https://www.youtube.com/watch?v=vOFeSu6Zr94) — Neso Academy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/digital_logic/mux-32to1-tree-function-15 - Whole chapter: https://www.bctengineer.com/md/semester_3/digital_logic/chapter-4 ## Question How do you design 32:1 Mux by using multiplexer tree? Implement logic function Y = Σm(0,1,3,8,9,13,15) by using suitable multiplexer. ## Short answer A 32:1 MUX tree uses four 8:1 MUXes on first level with S2-S0, and a 4:1 MUX with S4-S3 to select among them. For Y=Σm(0,1,3,8,9,13,15) with variables A,B,C,D, use an 8:1 MUX with A,B,C selects, data inputs: I0=1, I1=D, I2=0, I3=0, I4=1, I5=0, I6=D, I7=D. ## Answer #### 32:1 MUX by multiplexer tree A 32:1 MUX needs 5 select lines $S_4$–$S_0$. A common tree uses **four 8:1 MUXes and one 4:1 MUX**: - **Level 1:** four 8:1 MUXes with selects $S_2S_1S_0$: M1 takes $I_0$–$I_7$, M2 $I_8$–$I_{15}$, M3 $I_{16}$–$I_{23}$, M4 $I_{24}$–$I_{31}$. - **Level 2:** one 4:1 MUX (M5) with selects $S_4S_3$ selects one of M1–M4. ```text S2 S1 S0 I0-I7 -->[M1 8:1]--+ I8-I15 -->[M2 8:1]--+-->[M5 4:1]---> Y I16-I23 -->[M3 8:1]--+ S4 S3 I24-I31 -->[M4 8:1]--+ ``` | $S_4S_3$ | Selected MUX | Inputs reached | |---|---|---| | 00 | M1 | $I_0$–$I_7$ | | 01 | M2 | $I_8$–$I_{15}$ | | 10 | M3 | $I_{16}$–$I_{23}$ | | 11 | M4 | $I_{24}$–$I_{31}$ | Example: $S = 10101$ → M3 picks its input 5 ($I_{21}$) and M5 ($S_4S_3 = 10$) passes it, so $Y = I_{21}$. (With only 4:1 MUXes the tree would need 8 + 2 + 1 = 11 MUXes.) #### Implementing $Y = \Sigma m(0,1,3,8,9,13,15)$ The largest minterm is 15, so $Y = Y(A,B,C,D)$. A suitable MUX is an **8:1 MUX** with $A, B, C$ on the selects and $D$ on the data inputs. | | $I_0$ | $I_1$ | $I_2$ | $I_3$ | $I_4$ | $I_5$ | $I_6$ | $I_7$ | |---|---|---|---|---|---|---|---|---| | $D'$ | **0** | 2 | 4 | 6 | **8** | 10 | 12 | 14 | | $D$ | **1** | **3** | 5 | 7 | **9** | 11 | **13** | **15** | | Input | 1 | $D$ | 0 | 0 | 1 | 0 | $D$ | $D$ | ```text +--------+ 1 ------->| I0 | D ------->| I1 | 0 ------->| I2 | 0 ------->| I3 8:1 |----> Y 1 ------->| I4 MUX | 0 ------->| I5 | D ------->| I6 | D ------->| I7 | +--------+ A B C ``` **Check:** $ABCD = 1111$ (15): select 111 → $I_7 = D = 1$, $Y = 1$. $ABCD = 0010$ (2): select 001 → $I_1 = D = 0$, $Y = 0$. All 16 rows match. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which tree builds a 32:1 MUX in the answer, and which selects drive the last MUX? A. Four 8:1 MUXes at level 1 and one 4:1 MUX driven by S4S3 B. Two 16:1 MUXes driven by S4S3 C. Eight 4:1 MUXes driven by S2S1S0 D. Four 8:1 MUXes and one 4:1 MUX driven by S1S0 Answer: A. The lower selects S2S1S0 go to the four 8:1 MUXes; the higher selects S4S3 choose among their outputs in the 4:1 MUX. (Key point: Tree structure) 2. For S4S3S2S1S0 = 10101 in the tree, which input appears at Y? A. I5 B. I21 C. I10 D. I26 Answer: B. S4S3 = 10 picks M3 (I16-I23), and S2S1S0 = 101 picks its input 5, which is I21. (Key point: Worked example) 3. For Y = Σm(0,1,3,8,9,13,15) on an 8:1 MUX with A,B,C as selects, what goes to I1 (minterms 2 and 3)? A. D' B. 0 C. D D. 1 Answer: C. Of minterms 2 (D=0) and 3 (D=1), only 3 is in the list, so the output is 1 only when D=1, giving I1 = D. (Key point: Function implementation) 4. How many MUXes would a 32:1 tree need if only 4:1 MUXes were used? A. 8 B. 10 C. 16 D. 11 Answer: D. 8 + 2 + 1 = 11 MUXes: eight at level 1, two at level 2 and one at level 3. (Key point: MUX count) ## Related in Digital Logic - [32:1 MUX tree from 4:1; implement Σ(0,1,3,8,9,13)](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-32to1-tree-function) — Digital Logic, chapter 4 - [Σ(0,2,3,6,7,8,12,13,15) using 8×1 MUX](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-8x1-function-0236) — Digital Logic, chapter 4 - [Multiplexer tree; 16:1 MUX from 4:1](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-16to1-from-4to1) — Digital Logic, chapter 4 - [K-map ΠM(0,2,4,6,7,8,10,13,15) and 8:1 MUX](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Akmap-pom-8to1-mux) — Digital Logic, chapter 3 - [8:1 MUX operation; 32:1 MUX from 8:1](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-8to1-32to1-tree) — Digital Logic, chapter 4 - [Σm(0,1,3,4,8,9,15)+d using 8:1 MUX](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-8to1-function-dont-care) — Digital Logic, chapter 4 ## Related in other subjects - [AVL tree for 52, 65, 72, 15, 11, 32, 20](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-52-65-72) — Data Structure and Algorithm, chapter 6 - [Multiplexer and 4:1 MUX](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Amultiplexer-4-1) — Basic Electronics Engineering, chapter 6, asked 2×