I wonder how the LUT (look-up-table) works in digital design. Why do you use it? Could you give me an example of how to implement it, for example a circuit sketch or something? I Would be glad if you had pictures too.
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.
Perhaps the best way to understand a LUT is to consider how one would enumerate all the combinatorial circuits which take two inputs and produce one output. If one assumes that the inputs are hard-wired to other things so that e.g. "A and not B" is different from "B and not A", and functions which ignore one or both of the inputs may be useful [e.g. something will be wired to input B, but one may not care about what it's outputting], there are sixteen such circuits:
0000 Always output zero 0001 Output (not A) and (not B) 0010 Output A and (not B) 0011 Output (not B) 0100 Output (not A) and B 0101 Output (not A) 0110 Output A xor B 0111 Output A or (not B) 1000 Output (A and B) 1001 Output not (A xor B) 1010 Output A 1011 Output A or (not B) 1100 Output B 1101 Output (not A) or B 1110 Output A or B 1111 Always output 1
Each of the above circuits may be described by the four digit binary value to its left: the first digit says what should be output when both inputs are high. The second says what should be output if B is high and A is low. The third says what to do if A is high and B is low. The fourth says what to do when both inputs are low.
Rather than trying to invent some complicated scheme for allowing a device programmer to switch among various kinds of gates, FPGA manufacturers often have as their dominant logic type a circuit similar to the above (though often using eight bits to describe a three-input function, or sixteen bits to describe a four-input function). The circuit is referred to as a LUT because the N input bits are used to "look up" one of the 2^N "mode select" bits.
An important thing to note when using LUTs as compared with some other types of logic circuitry is that even if one has a logic device like the above configured to output "A", it will really compute "(A and B) or (A and not B)". As a consequence, if a device has e.g. a minimum propagation time of 2ns and a maximum propagation time of 5ns, then even if the A input remains constant, the behavior of the output will become unspecified 2ns after the B input changes and remain unspecified until 5ns after the B input is stable. If the B output is feeding a flip flop which is clocked by the same source as its inputs, this glitch will be inconsequential. If the B input is driving asynchronous sequential logic, however, such glitches may cause unexpected and undesirable behavior.
The look up table is often implemented with RAM or ROM cells in an array. The logic inputs are the address lines to to the array. The array data outputs become the logic outputs of the LUT. One determines the logic performed by the LUT based upon where in the array that 1's and 0's are written. The content bits for each output column of the array can be determined using standard logic synthesis techniques for the various combinations of the input bits. Note that actual logic minimization is not normally needed for a LUT because there are bits in the output columns of the array for every combination of the input bits.
You can get more good information concerning LUTs and their usages by referring to the various FPGA Logic Family Data Sheets from the likes of Altera and Xilinx. Their FPGAs make heavy use of LUTs for random logic generation. Typically FPGA LUTs are small RAM arrays that get loaded from a non-volatile configuration memory at time of power up.
One example that springs to mind is the sinewave look-up table. If you have a DAC and want to output a sinewave you can store several values that represent a sinewave in the first 90º of its waveform. These values can be stored in contiguous memory say from value 0 to value 90.
To produce the first 90º of the sinewave you incrementally read the values from 0 to 90 then for 91 to 180 you work backwards down the table then for the next 2 quadrants you start again but negate the values. This takes you to the start again.
DDS chips from Analog devices use this technique and if the definition of the sinewave is broad enough you can skip values to produce higher frequencies.