Introduction

Lookup tables or LUT-s are key component of modern computer hardware.

4-input LUT

Five 4:1 muxes can be combined to form 16:1 mux.

16:1 mux used in 4-input LUT-s

Those 16 inputs are predefined by FPGA bitstream and in such component is called 4-input LUT-s or 4-LUT for short. The 4 selector inputs essentially address the value.

There are 65536 possible variations for 16-bit cell programming which define the boolean function represented by the 4-LUT. The shorthand notation for the 4-LUT programming is within range:

\begin{equation*} f_{0000} ... f_{ffff} \end{equation*}

FPGA cell

FPGA cell consists of a lookup table, flip-flop and a bypass mux.

FPGA cell internals

To be precise full adder is also part of the design:

Detailed FPGA cell internals

Here the carry chain is explicitly seen.

Boolean function using lookup table #1

Consider following boolean expression:

\begin{equation*} f(x) = x_1 \overline{x_2} + \overline{x_1} x_2 + x_3 \overline{x_4} \end{equation*}

The corresponding truth table:

x(3)	x(2)	x(1)	x(0)	f(x)
0	0	0	0	0	a
0	0	0	1	0
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1	f
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1	f
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0	4
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0

This boolean expression can be referred to as:

\begin{equation*} f_{4ffa}(x) \end{equation*}

Boolean function using lookup table #2

Consider following boolean expression:

\begin{equation*} f(x) = x_0 \oplus x_1 \oplus x_2 \oplus x_3 \end{equation*}

The corresponding truth table:

x(3)	x(2)	x(1)	x(0)	f(x)
0	0	0	0	0	6
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1	9
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	1	9
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0	6
1	1	0	1	1
1	1	1	0	1
1	1	1	1	0

4-LUT function can be referred to as:

\begin{equation*} f_{6996}(x) \end{equation*}