Implementing Look up table in FPGA

Hi,
How to implement look up table in fpga and what is its purpose in fpga?

I will assume you are confusing concepts.

An FPGA can implement any logic, and the way it does it is by programming its internal look up tables. A simple google search of 'FPGA LUT diagram' will show you how it works. In general, you write code without the need to directly use the lookup tables. Software will do that for you -- translate your code into a bitstream that populates the LUTs.

I guess the question isn't asking about LUT as logic element in FPGAs but how to implement a ROM table e.g. for a sine generator. The term LUT is unfortunately equivocal.

I don't know, the question is so poorly phrased that I assume the OP is as naive as my students and got his concepts wrong.

FvM said:

I guess the question isn't asking about LUT as logic element in FPGAs but how to implement a ROM table e.g. for a sine generator. The term LUT is unfortunately equivocal.

Click to expand...

Exactly, you got right. Could you please explain little bit lets say for sine generator?
As far I know If I take rom as look up table, I need to initilaize with .coe file but I don't know how to generate corresponding .coe file? Can I also use Block RAM for this purpose?

I hope you know that Xilinx and Altrea both have documentation and that documentation tells you how to implement a ROM in their devices.
Altera: http://www.altera.com/en_US/pdfs/literature/ug/ug_ram_rom.pdf
Xilinx: http://www.xilinx.com/support/documentation/ip_documentation/blk_mem_gen/v8_3/pg058-blk-mem-gen.pdf
**broken link removed**

MIF format: http://quartushelp.altera.com/15.0/mergedProjects/reference/glossary/def_mif.htm
COE format: http://www.xilinx.com/support/documentation/sw_manuals/xilinx11/cgn_r_coe_file_syntax.htm

I would think going to the documentation is much more efficient use of your time than posting questions (that are easy to find in the documentation) on edaboard and waiting for answers and then having to explain your vague question until you have a question that can be answered.

Hi ads-ee,
this is not what I am asking

https://www.xilinx.com/support/documentation/sw_manuals/xilinx11/cgn_r_coe_file_syntax.htm

but how I know What will be the value of sine generator(certain functionality we want to implement) to put into
memory_initialization_vector= ?

DO I need some other tools to generate these values for certain functionality lets say sine generator in this case before assigning to
memory_initialization_vector=
?

Lock-up tables above a certain size will be always implemented in block RAM (ROM is just another name for initialized block RAM in terms of FPGA design).

Usual options are
- generating the initialization file (e.g. *.coe) in a spread sheet calculator or math tool.
- describing the look up table completely in VHDL or Verilog, including the calculation of sine values at synthesis time

You need to follow specific design templates to get the behavioral table description implemented in block RAM.

A classic LUT example is bitcounting. It's not the best example, but it is an interview question.

In the example question, a 16 bit value is provided and the goal is to count the number of 1's.

Two LUT-based designs are immediately obvious. The first uses 8bit address to 4 bit output LUTs and then sums the outputs. 4*256b LUT + 4*256b + 4 bit adder. The second uses a 16bit address and 5 bit output for 5*64k bits of LUT. This is an interview question you can ask.

The 8b luts map 0000_0000 to 0, 0000_0001 and 0000_0010 to 1, 0000_0011 to 2, etc... 1111_1111 gets mapped to 8.

This is actually a terrible interview question as non-LUT based approaches are likely to be faster in HW or SW. That said, if someone knows or questions the LUT based approach it is a bonus.

If you actually care about sine waves, look up the Xilinx DDS coregen guide. That explains how you should actually do things.

Hi FvM,
Thank you.

FvM said:

- generating the initialization file (e.g. *.coe) in a spread sheet calculator or math tool.

Click to expand...

This you mean like using MATLAB or MS EXCEL?

FvM said:

You need to follow specific design templates to get the behavioral table description implemented in block RAM.

Click to expand...

one thing is still not clear to me.
Let's say I have generated a .coe file for sine using matlab/excel that have 32 points i.e. "memory_initialization_vector=" contains 32 different values.
This look up table can not be used for sine having more than 32 points?

FvM said:

- describing the look up table completely in VHDL or Verilog, including the calculation of sine values at synthesis time

Click to expand...

This I didn't understand.

Let's say I have generated a .coe file for sine using matlab/excel that have 32 points i.e. "memory_initialization_vector=" contains 32 different values.
This look up table can not be used for sine having more than 32 points?

Click to expand...

You can generate finer resolution by linear interpolation. Or implement the table with required number of points. Having 1024 to 4096 points is no problem with mid range FPGA. Or use the sine tables provided by FPGA vendor DDS cores. They are using different "hybrid" methods with optimized memory or logic utilization.

This I didn't understand.

Click to expand...

Many previous posts are discussing sine table calculation in HDL, see e.g.
https://www.edaboard.com/showthread.php?t=200160&p=841972&viewfull=1#post841972

Hi FvM,
Thank you for the concept.

This method works for 1D Lookup Table.

For 1D look up table:
let's say contents of .coe file for a block memory of depth=16, and width=8 is:
memory_initialization_radix=16;
memory_initialization_vector=
ff,
ab,
f0,
11,
11,
00,
01,
aa,
bb,
cc,
dd,
ef,
ee,
ff,
00,
ff;

to read/access data all I need is to provide corresponding address of block RAM.

Now just for curiosity:
how the format of .coe file looks like for 2D look up table?
and how to access it in FPGA?

Similarly for 3-D and so on?

any other format is converted into a linear, 1d address. Either unpacked or packed

packed:
r1c1 r2c1 r3c3 r2c1 r2c2 r2c3 r3c1 r3c2 r3c3

unpacked:
r1c1 r2c1 r3c3 0 r2c1 r2c2 r2c3 0 r3c1 r3c2 r3c3 0 0 0 0 0

For FPGAs, where the resources already exist, an unpacked representation allows you to compute the address using 2 bit row as 2 msb, and 2bit column as 2 lsb. When the grid is large enough to use several resources, packing can be used. In this case the address needs to be computed as 3*row + col in HW before being provided to the RAM.

The same for higher dimensions. For a 3x4x5 space, a packed version would have addr = 4*5*x + 5*y + z, assuming x is 0:2, y is 0:3, z is 0:4.

Please remember that in case you want to have sinusoidal values and don't have enough logic resources for the whole look up table, an alternate is to use CORDIC. It is a very neat algorithm.