I have gone through various sources… But I am not quite sure what it is.I want an and gate and the logical equivalent is two inputs feeding to one gate and for Y=AB' the logical equivalent is feeding to one not gate and one and gate. But it is the same LUT for both AND and Y=AB'. I think we store the values as desired in the LUT. Someone elaborate on this
An LUT in FPGA
fpga
Related Solutions
Actually your first guess is not as afar off as some are claiming.
A CPU is built around something called an "Arithmetic Logic Unit" (ALU) and a simplistic implementation of that is to have the logic gates implementing all basic operations wired up to the inputs in parallel. All of the possible elementary computations are thus performed in parallel, with the output of the actually desired one selected by a multiplexor.
In an extremely simple (chalk-board-model) CPU, a few bits of the currently executing instruction opcode are wired to that multiplexor to tell it which logic function result to use. (The other, undesired results are simply wasted)
The actual technology used to implement the computations in the ALU varies - it could be "real" logic gates, or it could be LUT's if the CPU is implemented inside an LUT-based FPGA (one very good way to understand the essentials of stored-program computing is to design a simple processor and build it in a logic simulator and perhaps then an FPGA).
There are three ways todo this (forth listed for completeness) and it comes downto space-time tradeoffs:
Do you do the calculations ahead of time (storage space) or do you do the calculations on the fly (time tradeoff)
1) Look up table. Do the calculations ahead of time & store the information in a ROM/table. By realising you only have to store 1/4 of the waveform can decrease the amount you need to store. However... depending on the accuracy & the number of steps can lead to a very large table
2) Interpolated LUT. A tradeoff between a lookup table and full calculations. Take advance of the change between entries might be well within accepted errors. Sometimes only 3 points are required (NOTE: 3point example is for atan only)
3) CORDIC. (COordinate Rotation DIgital Computer). Basically a hunting algorithm which can be reduced to simple add's and shifts. The accuracy is pretty much governed by the number of computational steps
4) Full taylor expansion. If accuracy is paramount, speed is imporant but local storage isn't an option
My advice. Look into a CORDIC. There are plenty of example cordics in VHDL and an FPGA is perfect for a CORDIC. A project I am working on at the moment heavily uses cordic's (12bit, 14 cycles to settle)
Example cordic in python
#http://code.activestate.com/recipes/576792-polar-to-rectangular-conversions-using-cordic/
def to_polar(x, y):
'Rectangular to polar conversion using ints scaled by 100000. Angle in degrees.'
theta = 0
for i, adj in enumerate((4500000, 2656505, 1403624, 712502, 357633, 178991, 89517, 44761)):
sign = 1 if y < 0 else -1
x, y, theta = x - sign*(y >> i) , y + sign*(x >> i), theta - sign*adj
return theta, x * 60726 // 100000
def to_rect(r, theta):
'Polar to rectangular conversion using ints scaled by 100000. Angle in degrees.'
x, y = 60726 * r // 100000, 0
for i, adj in enumerate((4500000, 2656505, 1403624, 712502, 357633, 178991, 89517, 44761)):
sign = 1 if theta > 0 else -1
x, y, theta = x - sign*(y >> i) , y + sign*(x >> i), theta - sign*adj
return x, y
#if __name__ == '__main__':
# print(to_rect(471700, 5799460)) # r=4.71700 theta=57.99460
# print(to_polar(250000, 400000)) # x=2.50000 y=4.00000
Notes on CORDICS and FPGA's http://www.uio.no/studier/emner/matnat/ifi/INF5430/v12/undervisningsmateriale/dirk/Lecture_cordic.pdf
Best Answer
A LUT, which stands for LookUp Table, in general terms is basically a table that determines what the output is for any given input(s). In the context of combinational logic, it is the truth table. This truth table effectively defines how your combinatorial logic behaves.
In other words, whatever behavior you get by interconnecting any number of gates (like AND, NOR, etc.), without feedback paths (to ensure it is state-less), can be implemented by a LUT.
The way FPGAs typically implement combinatorial logic is with LUTs, and when the FPGA gets configured, it just fills in the table output values, which are called the "LUT-Mask", and is physically composed of SRAM bits. So the same physical LUT can implement Y=AB and Y=AB', but the LUT-Mask is different, since the truth table is different.
You can also create your own lookup tables. For example, you could build a table for a complex mathematical function, which would work much faster than actually calculating the value by following an algorithm. This table would be stored in RAM or ROM.
This brings us to viewing the LUTs simply as memory, where the inputs are the address, and the corresponding outputs are the data stored in the given address.
Here's a snapshot from FPGA Architecture by Altera: