Project ForgeDigital Logic
Combinational & Sequential Circuits
GATE 2007
Hard
Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed?
- A2ⁿ line to 1 line
- B2^(n+1) line to 1 line
- 2^(n-1) line to 1 line
- D2^(n-2) line to 1 line
Explanation
The standard Shannon-expansion-based multiplexer implementation uses n-1 of the variables to select among 2^(n-1) data inputs, feeding each data input with either 0, 1, the last variable, or its complement (via the single available inverter) as needed — requiring only a 2^(n-1)-line-to-1-line multiplexer.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.