how to implement look-up table in RTL?

EDAboard.com Forum Index -> ASIC Design Methodologies & Tools (Digital) -> how to implement look-up table in RTL?

Author

Message

xldu

Joined: 03 Apr 2005
Posts: 15

12 Nov 2005 4:48 lookup table with dff

If a table have variable length value, how to look up the table in RTL fast ?
what about using CAM?
can anyone introduce some methods to implementing looking up table in RTL level?
thanks!

xldu

Joined: 03 Apr 2005
Posts: 15

15 Nov 2005 3:08 Re: how to implement look-up table in RTL?

on one answer me?
when decoding bitstream, i should look up a decoding-table. the table is large and has
varible length content, so i don't know how to implement it in RTL. the table can be saved in ram but how to save it? someone say dividing the table into several segments is good, but how to dividing it?
anyone can help me?

archillios

Joined: 29 Jun 2005
Posts: 97
Helped: 4

15 Nov 2005 4:26 how to implement look-up table in RTL?

hi,
1.
some vendor provide CAM core ,and you can get CAM simulation lib ,then use it in your RTL.
2.
if not ,use verilog reg array to build a lookup table,using the max length as the array width .
this way may lead to large die area consumed if the look-up table is big.

3.
if your target is FPGA,then using CAM or LUT or something in FPGA.

xldu

Joined: 03 Apr 2005
Posts: 15

15 Nov 2005 10:13 Re: how to implement look-up table in RTL?

thank you!
our target is ASIC, and the size can't be too big.
so the regsiter array is not good.
we want to save the table in the RAM, but the critical problem is how to look up the content?
for example:
when received one bitstream, i should compare the bitstream and the table in the RAM, output the result of looking-up. otherwise, the bitstream is not fixed-length.
do you have any advices for it?

Google
AdSense
Google Adsense

15 Nov 2005 10:13 Ads

vlsi_whiz

Joined: 12 Nov 2005
Posts: 171
Helped: 24

15 Nov 2005 11:06 Re: how to implement look-up table in RTL?

You've mentioned that you need a dynamic look-up table whose contents/size can be modified and thatn you are targetting ASIC. There's a contradiction here... First, hardware structure or size cannot be modified/changed dynamically.

What you can do, is to design a ROM of fixed size by first deciding on an upper memory limit and the number of data that are going to be stored in the ROM table. Then hardcode the ROM with the values of the table. This way you have created a lookup table. The only drawback here is that you cannot modify the contents of the ROM later. This is the method followed in storing the instructions in processors.

If you implemet this table in RAM, you will loose all the data when the chip looses power and to overcome this you will have to use a external ROM to load the data back in.

funster

Joined: 30 Jun 2005
Posts: 234
Helped: 12

20 Nov 2005 6:20 Re: how to implement look-up table in RTL?

for lookup table, if you use DFF to construct it,

you can use CASE struct directly. if you

use ram, you should prepare a file to programmble

ram.

best regards

xldu wrote:

If a table have variable length value, how to look up the table in RTL fast ?
what about using CAM?
can anyone introduce some methods to implementing looking up table in RTL level?
thanks!

AlexWan

Joined: 26 Dec 2003
Posts: 305
Helped: 6

21 Nov 2005 2:23 how to implement look-up table in RTL?

ami

Joined: 28 Apr 2005
Posts: 62
Helped: 4
Location: VN

22 Nov 2005 3:55 Re: how to implement look-up table in RTL?

hi,
I think how to design a look-up table depends much on the requirements of your design.
1. if your input value for look-up varies in its bit-length, try to define the min & max length
----> the min length will be the depth of your unit table.
----> The max leng will define how many unit tables that you need
2.ex: you need to look up this [a2a1a0][b4b3b2b1b0] for a data of 16 bits
----> divide the look up table in to ([a2a1a0]max)=8 unit table
-----> ([b4b3b2b1b0])max = 32 ----> unit table size = 32x16
so you can look-up in parallel on 8 unit-table --> decode --> your desire lookup value

Hope this help.

avimit

Joined: 16 Nov 2005
Posts: 417
Helped: 69
Location: Fleet, UK

28 Nov 2005 23:35 Re: how to implement look-up table in RTL?

you may use a case statement i.e combinational logic

Example:

cosout_p : PROCESS(index_in)
BEGIN
CASE index_in IS
WHEN "000000" => cosout <= "11111111111111111111111";
WHEN "000001" => cosout <= "11111111101100010000111";
WHEN "000010" => cosout <= "11111110110001000110110";
WHEN "000011" => cosout <= "11111101001110101010101";
WHEN "000100" => cosout <= "11111011000101001011111";
WHEN "000101" => cosout <= "11111000010100111111011";
WHEN "000110" => cosout <= "11110100111110100000101";
WHEN "000111" => cosout <= "11110001000010010000100";
WHEN "001000" => cosout <= "11101100100000110101111";
WHEN "001001" => cosout <= "11100111011010111101011";
WHEN "001010" => cosout <= "11100001110001011001011";
WHEN "001011" => cosout <= "11011011100101000001101";
WHEN "001100" => cosout <= "11010100110110110011000";
WHEN "001101" => cosout <= "11001101100111110000001";
WHEN "001110" => cosout <= "11000101111001000000001";
WHEN "001111" => cosout <= "10111101101011101111100";
WHEN "010000" => cosout <= "10110101000001001111001";
WHEN "010001" => cosout <= "10101011111010110100100";
WHEN "010010" => cosout <= "10100010011001111001100";
WHEN "010011" => cosout <= "10011000011111111011111";
WHEN "010100" => cosout <= "10001110001110011101100";
WHEN "010101" => cosout <= "10000011100111000011110";
WHEN "010110" => cosout <= "01111000101011010111010";
WHEN "010111" => cosout <= "01101101011101000100000";
WHEN "011000" => cosout <= "01100001111101111000101";
WHEN "011001" => cosout <= "01010110001111100110100";
WHEN "011010" => cosout <= "01001010010100000001100";
WHEN "011011" => cosout <= "00111110001100111111001";
WHEN "011100" => cosout <= "00110001111100010111000";
WHEN "011101" => cosout <= "00100101100100000010000";
WHEN "011110" => cosout <= "00011001000101111010011";
WHEN "011111" => cosout <= "00001100100011111011001";
WHEN "100000" => cosout <= "00000000000000000000000";
WHEN OTHERS => cosout <= (others => '0');
END CASE;
END PROCESS cosout_p;

xldu

Joined: 03 Apr 2005
Posts: 15

29 Nov 2005 10:04 Re: how to implement look-up table in RTL?

thanks all!

using CAM will result in large size, sequential looking-up a table will result in a waste of time. i must balance the size and time. does anyone more advise?

to ami,
your solution for table structure is good for me, can you explain more? because
how to look-up the table is critical!

to avimit,
using case structure (DFF) will result in huge size, as the table is very large!

avimit

Joined: 16 Nov 2005
Posts: 417
Helped: 69
Location: Fleet, UK

29 Nov 2005 12:10 how to implement look-up table in RTL?

hello xldu,
tell me what exactly you want to implement, and then I may be able to give you a better edvice.
In some applications, only a few values are stored in a lookup table at regular intervals, while the others may be calculated using the stored values and linear interpolation.
Kr,
Aviral Mittal

ami

Joined: 28 Apr 2005
Posts: 62
Helped: 4
Location: VN

07 Dec 2005 11:19 Re: how to implement look-up table in RTL?

Hi,
this is the heart code of my CAM (search unit table),

Code:

reg [W-1:0] cam_reg [D-1:0];
reg [D-1:0] match;
integer i;
always @ (posedge clock or negedge reset)
if (!reset)
begin
match <= {D{1'b0}};
end
else
begin
for (i=0;i<D;i=i+1) match[i] <= (search_data == cam_reg[i]);
end

----> then, simply decode the "match" register ----> search result

this code works well with D=8 (256 locations), W=32 @155MHz

* Hope this help
Regards

Added after 33 minutes:

xldu wrote:

to avimit,
using case structure (DFF) will result in huge size, as the table is very large!

yes, building the CAM with DFF cost much area, but you must accept that if the time for search result is important.
The CAM I give you above (4 unit of 256x32) cost 112422 area (a DFF with drive strength =1 cost 30 area).

Regards

Added after 11 minutes:

Another experience in this: if you use RAM for search, you must use many design tricks. Then, it will make your design more complex and hard to change afterward.
Using logic cell in such design like this cost area but it worth its weight in gold. If you use RAMs, there will many small RAMs in your design----> cost area in total too and you will face the difficult in P&R later.
It's my experience and I have paid for it Smile

Regards[/b]

jackson_peng

Joined: 11 Apr 2005
Posts: 141
Helped: 13
Location: Shanghai, China

08 Dec 2005 4:15 how to implement look-up table in RTL?

the verilog HDL can't just discribe the CAM structure perporly, use the comercial CAM model to bulid your Lookup table

ami

Joined: 28 Apr 2005
Posts: 62
Helped: 4
Location: VN

08 Dec 2005 5:23 Re: how to implement look-up table in RTL?

jackson_peng wrote:

the verilog HDL can't just discribe the CAM structure perporly, use the comercial CAM model to bulid your Lookup table

Yes,
But we can use HDL to build something which functions like the comercial CAM, OK?
(self-bulding one will not be optimization like comercial CAM, but it still function well in many case)