Electrical – How to implement a three-input LUT if I have a lot of two-input LUTs

A 3-input LUT is an 8-bit memory, and that memory can contain one of 2⁸ = 256 different values. Each value represents one possible Boolean function of the three input variables.

A 2-input LUT can contain one of 2⁴ = 16 different functions.

When you cascade two 2-input LUTs, you are effectively creating a temporary variable T that is a function of two of the inputs (16 choices) and then the final output is a function of T and the third input (16 more choices), for a total of 32 choices. Since you get to pick which of the three input variables is connected to the second LUT, you can actually create up to 32 × 3 = 96 different functions this way.

However, this leaves 256 - 96 = 160 functions that cannot be created. These additional functions require a true 3-input LUT, or two 2-input LUTs plus a mux.

It's easy to construct such a function — a function that requires two different 2-input LUTs. For example, suppose you want A AND B when C is high, but A OR B when C is low:

$$Y = ABC + (A+B)\overline{C} = ABC + A\overline{C}+B\overline{C}$$

There's no way to decompose this into two functions of two variables each. If you look at the 3-D Karnaugh map of this function, you'll gain some insight as to why.

If all you have is 2-input LUTs, you'll need to use three of them to create a 2:1 mux, and then two more to hold your 8 function bits, for a total of five 2-input LUTs to emulate a general-purpose 3-input LUT.

If you are given

$$Y = f(A, B, C)$$

The five 2-input LUTS are

$$S = f(A, B, 0)$$ $$T = f(A, B, 1)$$ $$U = S \cdot \overline{C}$$ $$V = T \cdot C$$ $$Y = U + V$$

Here's the same thing in the form of a diagram:

^{simulate this circuit – Schematic created using CircuitLab}