LUT sizes
An
ninput function needs 2
^{n} rows in its truth table. The LUT that performs the function will have 2
^{n} (corrected by DP 2/11/2000) configuration bits.
The number of functions an ninput LUT can perform is 2^{# config bits}, because each different bit combination represents a different set of outputs.
5LUT from 4LUTs
One homework question asks for a 5input LUT made of 4LUTs. Here is a
wrong answer:
This takes 5 inputs, has one output, and is made completely from programmable 4LUTs. But it is not a complete 5LUT; it cannot perform any function of 5 inputs.
To see this, consider a function that has the beginning of a truth table like this:

A

B

C

D

E

OUT

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

0

1

1

1

0

0

1

0

0

1

0

0

1

0

1

0







Think about the first LUT’s output signal.
It is a function of A, B, C, and D only, which means that it has the same value for truth table rows 1 and 2. Suppose it’s a 0 for those inputs.
Next, consider rows 2 and 3. The first LUT’s output has to be constant for these rows, too, because they also share ABCD values. The intermediate output also has to be the opposite for these rows, because the output behavior is different. If the intermediate output was the same for ABCD=0000 and ABCD=0001, the output could not possibly be different for inputs 00000 and 00010. Suppose the intermediate output is a 1 for those inputs.
Notice that the output is not dependent on E for any of the first 4 rows. So whether the first LUT outputs a 0 or 1, the second LUT must not change when E changes. And we know that the first LUT will output both those values for rows 14, because it needs to output two different values for the first two row pairs to be any different.
But now one of rows 5 and 6 is impossible! The first LUT output is necessarily the same for those rows, because ABCD don’t change. It looks like the output will have to change with E. This would be a contradiction in the second LUT, because we already confirmed that its output does not change with E.
Another way to prove that this approach doesn’t work is to count configuration bits. We know that a real 5LUT needs 32 configuration bits. My circuit here has 16
bits in the first LUT, but only uses 4 bits of the second LUT. The second LUT may have 32 configuration bits, but since
C and D are tied to ground, any truth table row with nonzero C or D is never going to be used, so its output bit will never matter. There are only 4 rows in the 4LUT truth table with CD=00, so there are only 4 useful configuration bits. My design has 20 configuration bits that affect its output. That means it can perform 2
^{20} different functions, which isn’t enough. A real 5LUT can perform 2
^{32} different functions (each of 32 input combinations can make one of 2 outputs).