MUX as Function Generator

FPGA lookup tables are nothing more than multiplexers used as function generators. Any Boolean function can be implemented using only a multiplexer and a few fixed logic levels, with no additional gates — a fact exploited by every modern programmable device.

Core Concept

A MUX as function generator exploits the output equation Y = Σ mi(selects) · Ii. If the Boolean variables are placed on the select inputs and the function's truth table output values are loaded onto the data inputs, the MUX computes the function exactly. No additional logic gates are needed.

An n:1 MUX with n data inputs and log₂(n) select lines can directly implement any Boolean function of log₂(n) variables. A 4:1 MUX implements any 2-variable function; an 8:1 MUX implements any 3-variable function; a 16:1 MUX implements any 4-variable function. This is the operating principle of FPGA LUT (look-up table) blocks.

To implement a function with one more variable than the MUX select count, place log₂(n) variables on the selects and express the remaining variable's contribution as 0, 1, D, or D' on each data input. The 74151 is the standard IC for 3-variable function generation. It runs at 5 V with 20 ns delay. The 74HC151 CMOS version suits lower-power designs.

Boolean Expression

For an 8:1 MUX: Y = Σ(i=0 to 7) mi(A,B,C) · Ii. To implement f(A,B,C), set Ii = f(A=a2, B=a1, C=a0) where a2a1a0 is the binary representation of i. For a 4-variable function f(A,B,C,D) on an 8:1 MUX, connect A, B, C to S2, S1, S0 and determine for each of the 8 select combinations what f equals as a function of D — if f = 0 for both D=0 and D=1, set Ii = 0; if f = 1 for both, set Ii = 1; if f = D set Ii = D; if f = D' set Ii = D'.

Given:
  Implement f(A,B,C,D) = Σm(1,3,5,7,9,11,13,15)
  using a single 8:1 MUX (74151)
  Connect A,B,C to S2,S1,S0

Formula / Rule:
  For each select combo (A,B,C), examine f for D=0 and D=1.
  Ii = 0 if f=0,0; Ii = 1 if f=1,1; Ii=D if f=0,1; Ii=D' if f=1,0

Step by step:
  ABC=000: f(0,0,0,0)=m0=0, f(0,0,0,1)=m1=1  → 0,1 → I0=D
  ABC=001: f(0,0,1,0)=m2=0, f(0,0,1,1)=m3=1  → 0,1 → I1=D
  ABC=010: f(0,1,0,0)=m4=0, f(0,1,0,1)=m5=1  → 0,1 → I2=D
  ABC=011: f(0,1,1,0)=m6=0, f(0,1,1,1)=m7=1  → 0,1 → I3=D
  ABC=100: f(1,0,0,0)=m8=0, f(1,0,0,1)=m9=1  → 0,1 → I4=D
  ABC=101: f(1,0,1,0)=m10=0,f(1,0,1,1)=m11=1 → 0,1 → I5=D
  ABC=110: f(1,1,0,0)=m12=0,f(1,1,0,1)=m13=1 → 0,1 → I6=D
  ABC=111: f(1,1,1,0)=m14=0,f(1,1,1,1)=m15=1 → 0,1 → I7=D

Final Answer:
  Connect all data inputs I0–I7 to D.
  f(A,B,C,D) = D regardless of A,B,C (function is simply D)
  (This makes sense: minterms 1,3,5…15 are all odd → D=1 in every case)

Exam Tip: GATE frequently gives a 4-variable function and asks you to implement it with an 8:1 MUX. The trick is to choose which variable goes on the data inputs (typically the last variable, D) and which three go on the selects. Then for each of the 8 combinations of the select variables, check the two rows of the truth table (D=0 and D=1). If the two output values are 0,0 → data = 0; 1,1 → data = 1; 0,1 → data = D; 1,0 → data = D'. A single external inverter for D' is the only extra component that may be needed.

Key Properties

• An n:1 MUX directly implements any Boolean function of log₂(n) variables.
• For one extra variable: load 0, 1, D, or D' on each data input — only one possible inverter needed externally.
• 74151: 8:1 MUX, 5 V TTL, 20 ns delay — directly implements any 3-variable function.
• 74HC151: CMOS, 2–6 V, extends use to battery-operated function generators.
• FPGA LUTs are 4:1 or 6:1 MUXes programmed with truth table data in SRAM cells.
• A 2:1 MUX implements XOR: connect A to S, apply B to I0 and B' to I1, Y = A XOR B.
• Larger functions (more than log₂(n)+1 variables) require cascading MUXes or a larger MUX.

Quick Revision

• Load truth table output values onto MUX data inputs.
• Place Boolean variables on select lines.
• 8:1 MUX → any 3-variable function with no extra gates.
• 4-variable function on 8:1 MUX: three variables on selects, fourth on data inputs as 0, 1, D, or D'.
• Data input expression rule: 0,0→0; 1,1→1; 0,1→D; 1,0→D'.
• At most one inverter (for D') needed as external component.
• FPGA LUTs exploit this principle using SRAM-loaded MUX trees.
• Exam trap: accidentally swapping the assignment — setting Ii = 1 when f is 0 for D=0 and 1 for D=1 should give Ii = D, not Ii = 1; Ii = 1 would incorrectly output 1 even when D = 0.