Hi. Let's say, I have big table which is usually suitable to fit it in some ROM. But it's possible to construct some circuit containing only primitive gates that acts just as that ROM. Here is an example of converting tables from DES cipher into gates:
There are multiple way of doing this. In college 10 years ago, I wrote a C program to do this based on my engineering coarse at the time. Most synthesizers can do this to some extent. They will optimize it to fit in their target library. If the FPGA has a ram that it fits, The code may not be optimized becuase the fpga can just use the memory.
Found the algorithm used.
This is the method I wrote a C program for, but this is NOT my code. careful about implementing this code in your HP calculator. Your Instructor will not give you full credit on the exam if you do not show your work. Mine sure didn't. I think this is the one exam I failed in my engineering coarses. I had the final solution, I just skipped the boring part. Mind numbing to do by hand for a large table.
a C
ay not
Yes, but I still don't know, what will be better in my case: generated logic or just usual RAM blocks in FPGA. It's interesting to see your work too, but is there anything already incorporated into well-known EDA tools? Or, for example, Altera Quartus, do this in automated way so I can free my mind from this?
It isn't my work. Can't take the credit. I just happened to do something like it a long time ago.
Ah... this is a different question versus what you first posted.
The answer is both YES and NO. The comericially available tools do have optimizing routines to save chip area or to map to existing target resources. Will Quartus know that a giant table can be optimized to a small equation? Don't know haven't used that tool. But based on the tools I have used it is IFFY at best. The optimization may map it to a smaller equation but perhaps not the absolute minimum. Or it may map it to RAM and skip the the whole processes becuase the FPGA had the resource. It is YOUR job as the engineer to weight the value of using the built in ram versus optimizing to a logic function.
The optimizers available in the tools can do alot, but they also require alot of input from the user to tell it how to do it's job. Do you need speed? Do you need less gates? Do you need to keep the hierachy? Does your design need to make use of a large portion of the available RAM? if so mapping to gates may be a better option.
Yes, but I still don't know, what will be better in my case: generated logic or just usual RAM blocks in FPGA. It's interesting to see your work too, but is there anything already incorporated into well-known EDA tools? Or, for example, Altera Quartus, do this in automated way so I can free my mind from this?
Depends how big 'big' is, and what the average bit density, and randomness is. You can certainly fit FONT roms, like 7 segment and Sine or palette tables into Logic - but I'd call those small tables.
I've seen tools that map into Wide AND. OR (ie CPLD cells), but not ones that go a step further and use multiple layers of logic, with intermediate merge nodes.
RAM is likely to be faster, and more deterministic. Code it as both, and see what the tools report ?
-jg
For modern systems, especially FPGAs, it might be better to consider multiple smaller tables.
I have a data book from years ago with a sine lookup table ROM in it. They start with one ROM with limited resolution. Next they do linear interpolation on the first ROM with the help of one, two, or three more ROMs.
Also, in the past nanoprogramming has been used to avoid the problems of large microprogram ROMs. That is, a two level lookup table in place of one large one, as a more efficient storage system for microprogram ROMs.
In most cases it might be easier to do by hand, using knowledge about the table data. There are still some possibilities for automation, though.
-- glen
Hmm. Any modern Synthesis will do that. Try Xilinx XST for example. In VHDL define an array with data and use an integer to index that array. Depending on the synthesizer options either a BRAM or combinational logic will be created.
The results will not be very good for general data. You can easily proof that most tables can't be implemented with less than 2**N gates for N inputs.
However, many useful tables show structure that allows at least some optimizations.
Kolja Sulimma
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.