How does a LUT work, why is it used?
A lookup table (LUT) is a fast way to realize a complex function in digital logic.  The address is the function input, and the value at that address is the function output.  The advantage is that computing the function only takes a single memory lookup regardless of the complexity of the function, so is very fast.  The disadvantage is that it takes memory, especially if you need high resolution for the function input.

For example, the sine function is often implemented as a table lookup.  If 10 bit angles are good enough resolution, then the whole function can be implemented as a lookup table with 1024 entries.  (Actually, in the case of sine, only 1/4 cycle is stored then negated or indexed backwards depending on the actual quadrant, but that is a aside specific to sine).

The function input can also be a combination of different input variables with the result expressed as a single integer.  For example, a 4 x 4 bit multiply can be implemented as a lookup table of 256 values.  The 8-bit table address can be the two 4-bit input values concatenated.