--- title: "32:1 MUX tree from 4:1; implement ฮฃ(0,1,3,8,9,13)" subject: "Digital Logic" chapter: 4 key: "semester_3/digital_logic:mux-32to1-tree-function" source: https://www.bctengineer.com/q/semester_3/digital_logic/mux-32to1-tree-function site: BCT Engineering --- # 32:1 MUX tree from 4:1; implement ฮฃ(0,1,3,8,9,13) Digital Logic ยท Chapter 4: Data Processing Circuits - Asked in: 2074 Chaitra, 4+2 marks - Video: [Implement the given function using 4:1 multiplexer. ๐‘ญ(๐‘จ,๐‘ฉ,๐‘ช)=โˆ‘(๐Ÿ,๐Ÿ‘,๐Ÿ“,๐Ÿ”)](https://www.youtube.com/watch?v=M_cnctZqk-s) โ€” Engg-Course-Made-Easy - 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 - Whole chapter: https://www.bctengineer.com/md/semester_3/digital_logic/chapter-4 ## Question Design the 32:1 Multiplexer using 4:1 multiplexers tree concept and implement the function F = ฮฃ(0,1,3,8,9,13) using suitable Multiplexer. ## Short answer 32:1 MUX tree: eight 4:1 MUXes with S1S0, two with S3S2, one final with S4 on S0 (S1=0), total 11. F = ฮฃ(0,1,3,8,9,13) implemented by 8:1 MUX with A,B,C as selects: I0=I4=1, I1=I6=D, others 0. ## Answer #### 32:1 MUX using a 4:1 multiplexer tree A 32:1 MUX has 32 data inputs and 5 select lines $S_4S_3S_2S_1S_0$ ($2^5 = 32$). With 4:1 MUXes (2 selects each) the tree has three levels: | Level | 4:1 MUXes | Select lines | Function | |---|---|---|---| | 1 | 8 (M1โ€“M8) | $S_1S_0$ | Each picks 1 of 4 inputs | | 2 | 2 (M9, M10) | $S_3S_2$ | Each picks 1 of 4 level-1 outputs | | 3 | 1 (M11) | $S_4$ (on its $S_0$; its $S_1 = 0$) | Picks M9 or M10 | ```text I0-I3 ->[M1 ]--+ I4-I7 ->[M2 ]--+->[M9 ]--+ I8-I11 ->[M3 ]--+ S3S2 | I12-I15 ->[M4 ]--+ | S4 on S0, +--->[M11]---> Y I16-I19 ->[M5 ]--+ | S1 = 0 I20-I23 ->[M6 ]--+->[M10]--+ I24-I27 ->[M7 ]--+ S3S2 I28-I31 ->[M8 ]--+ (M1-M8 use S1S0) ``` Total: 11 MUXes of 4:1 (the last one uses only two inputs; a 2:1 MUX could replace it). Example: $S_4..S_0 = 10110$ โ†’ M6 passes $I_{22}$, M10 ($S_3S_2 = 01$) passes M6, M11 ($S_4 = 1$) passes M10, so $Y = I_{22}$. #### Implementing $F = \Sigma m(0,1,3,8,9,13)$ The largest minterm is 13, so F is a 4-variable function $F(A,B,C,D)$. A suitable MUX is an **8:1 MUX** with $A, B, C$ as selects and $D$ on the data side. | | $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$ | 0 | ```text +--------+ 1 ------->| I0 | D ------->| I1 | 0 ------->| I2,I3 | 1 ------->| I4 8:1 |----> F 0 ------->| I5 | D ------->| I6 | 0 ------->| I7 | +--------+ A B C (S2 S1 S0) ``` **Check:** $ABCD = 1101$ (13): select 110 โ†’ $I_6 = D = 1$, so $F = 1$. $ABCD = 1100$ (12): $I_6 = 0$, so $F = 0$. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How many 4:1 MUXes are needed for a 32:1 MUX tree? A. 8 B. 9 C. 11 D. 16 Answer: C. 8 at level 1, 2 at level 2 and 1 at level 3 give 11. (Key point: MUX count of the tree) 2. Which select lines drive level 1 and level 2 of the 4:1 tree? A. S4S3 then S2S1 B. S1S0 then S3S2 C. S3S2 then S1S0 D. S2S1 then S4S3 Answer: B. Level 1 uses S1S0, level 2 uses S3S2, and the last MUX uses S4. (Key point: Select line per level) 3. F = ฮฃm(0,1,3,8,9,13) is a function of how many variables? A. 3 B. 5 C. 6 D. 4 Answer: D. The largest minterm 13 needs 4 bits, so F is a function of A, B, C, D. (Key point: Variables in the function) 4. In the implementation table, what is I1 (ABC = 001, minterms 2 and 3)? A. D' B. D C. 1 D. 0 Answer: B. Minterm 3 (D = 1) is in F and minterm 2 is not, so I1 = D. (Key point: Data inputs for the 8:1 MUX) ## Related in Digital Logic - [32:1 MUX tree; implement ฮฃm(0,1,3,8,9,13,15)](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-32to1-tree-function-15) โ€” 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 - [32:1 MUX from 16:1 and 2:1 MUXes](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-32to1-from-16to1) โ€” 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 - [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 ## Related in other subjects - [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ร—