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

Question

I have gone through various sources... But I am not quite sure what it is.

For example, I have three input variables: A, B and C. Now I have to use two 2-input LUTs such that their input lines are connected to variables A and B. Then connect their outputs to a 2x1 multiplexer whose select line is the input variable C.

But in this problem, I'm not allowed to use the MUX, only two 2-input LUTs. How can it be?

The configuration of LUTs would depend upon the particular Boolean function that you wish to realise. Can you cite an example, please?

• Justin: Try giving A and B as inputs to LUT1, then send the output of LUT1 and C to the inputs of LUT2. You may need to change whether A, B, or C is the one in the second stage depending on the function. I'm not sure if all boolean functions can be made in this way, or just some of them.

Answer 1

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:

schematic

^{simulate this circuit – Schematic created using CircuitLab}

• L.Kh.Hovhannisyan: I find your terminology of LUT different than what I've learned; a LUT is a Look Up Table, so a 3 input table would have 3 address lines and thus 8 values. In addition the LUT words can be any size from 1 to n, so a 3 input LUT table could represent an 8 values of 32 bits for example. So I don't understand your derivation of how a 2 input function could contain one of 24 = 16 different functions? Are the variables A,B,C,S,T single bit variables or multibit variables?
• Dave Tweed: In the context of FPGAs, a LUT is strictly 1 bit wide, and generates a single Boolean function.
• L.Kh.Hovhannisyan: Can you send me, please, a circuit of scheme ?
• Dave Tweed: Seriously, you need to do at least some of the work on this yourself. If I hold your hand the whole way, you won't actually retain any of this.
• L.Kh.Hovhannisyan: Thank you very much )

Answer 2

There's always paper and pencil...

enter image description here

• Dave Tweed: This is correct.