4-to-1 Multiplexer from 2-to-1 Mux Primitives
Multiplexers are the universal routing primitive in digital design. Every FPGA lookup table, every bus arbitration unit, and every ALU output stage relies on muxes to select among multiple data sources. In real ASIC design, a 4-to-1 mux is frequently implemented hierarchically from 2-to-1 mux cells because the 2-to-1 cell has been carefully optimized at the transistor level. Understanding this hierarchy is expected knowledge for any digital design interview.
Your task is to build a 4-to-1 multiplexer using exactly three 2-to-1 MUX components and no other logic gates. The 4-to-1 mux has four data inputs (I0, I1, I2, I3), two select bits (S1 as MSB and S0 as LSB), and one output Y. The selection encoding is:
S1=0, S0=0 → Y = I0 S1=0, S0=1 → Y = I1 S1=1, S0=0 → Y = I2 S1=1, S0=1 → Y = I3
Worked examples: with I0=1, I1=0, I2=1, I3=0 and S1=0, S0=1 the output is I1=0. With the same data inputs and S1=1, S0=0 the output is I2=1. The circuit uses S0 to select within each pair (I0 vs I1 in the lower stage, I2 vs I3 in the upper stage) and S1 to select between the two stage results.
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | I0 | input | 1 | Data input 0, selected when S1=0 and S0=0 | | I1 | input | 1 | Data input 1, selected when S1=0 and S0=1 | | I2 | input | 1 | Data input 2, selected when S1=1 and S0=0 | | I3 | input | 1 | Data input 3, selected when S1=1 and S0=1 | | S0 | input | 1 | Select LSB | | S1 | input | 1 | Select MSB | | Y | output | 1 | The selected data input |
Constraints
- Only 2-to-1 MUX components are allowed. No AND, OR, NOT, or any gate.
- Exactly 3 MUX components must be used — this is both the minimum and maximum for a correct tree structure.
- S0 controls the first stage (lower pair vs upper pair within each group). S1 controls the second stage (final selection between the two first-stage outputs).
- The circuit is purely combinational — no clock or state.
Topics
Solve this problem
Place the gates, wire them up and watch the signals settle. Every submission runs on the same simulation engine that grades it.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.