Determine the size of PROM required for implementing the 16-to-1 multiplexer.

A PROM (or any lookup-table memory) implements a Boolean function by storing one output value for every possible combination of its input variables — it does not compute, it only recalls a stored value. So the address space must include every signal that can change the output: PROM size = 2n × m, where n is the number of input (address) lines and m is the number of output lines.

1. Identify what the output actually depends on: in a 16-to-1 MUX, the output Y equals whichever of the 16 data lines (D0–D15) is currently selected — so Y depends on the values on all 16 data lines, not only on which one is chosen.

2. Count the select lines needed to choose among 16 data lines: 24 = 16, so 4 select lines (S0–S3) are required.

3. Total input (address) lines n = data lines + select lines = 16 + 4 = 20.

4. Number of outputs m = 1 (the single MUX output line).

5. PROM size = 2n × m = 220 × 1 = 1,048,576 × 1, commonly written as 1M × 1.

Cross-check: if only the 4 select lines were counted (24 × 1 = 16 × 1), the PROM would only be able to reproduce a MUX whose 16 data inputs are fixed constants — a decoder-style ROM, not a true multiplexer with independently variable data inputs. Because the data lines here are variable inputs (not hard-wired constants), all 20 signals must be part of the address, confirming the size 220 × 1 = 1M × 1.

Required PROM size = 1M × 1.