How to implement an irragular table?

[fl]

Hi,

I want to implement a table, which has nonlinear input. For example, its input has 7 segmentations:

Segmentation........... Mapping ratio
1-511.................. 1 : 1
512-1023............... 1 : 2
1024-2047.............. 1 : 4
2048-4095.............. 1 : 8
4096-8191.............. 1 : 16
8192-16383............. 1 : 32
16384-32767............ 1 : 64

Thus, the first row has 511 entries while all others have 256 entries. There are values (26 bits in wordlength) corresponding to these entries.

I am new to VHDL. It looks like a lookup table, but the nonlinear entries make me feel difficult. Could you help me on this problem?


Thanks,

 

[fl]

Thanks Allan. Your post really gives me some fresh view on my question. I may start in your idea later.

After I sort through my question, I think that I care about resource cost for a Xilinx Spartan 6 now. The input has 15 bits for 0...32767 while there are total 2048 distinct value corresponding to these entries. A straight forward look up table works, which looks like a 15-bit input, 26-bit output table.

My question now is whether there is a structure less than the above design,because there are only 2048 (11-bit, not 15-bit) output distinct values.

Thanks,

 

[fl]

Hi,

I want to implement a table, which has nonlinear input. For example, its

input has 7 segmentations:

Segmentation........... Mapping ratio 1-511.................. 1 : 1

512-1023............... 1 : 2 1024-2047.............. 1 : 4

2048-4095.............. 1 : 8 4096-8191.............. 1 : 16

8192-16383............. 1 : 32 16384-32767............ 1 : 64

Thus, the first row has 511 entries while all others have 256 entries.

There are values (26 bits in wordlength) corresponding to these entries.

I am new to VHDL. It looks like a lookup table, but the nonlinear

entries make me feel difficult. Could you help me on this problem?


Thanks,

This reminds of the time I implemented a very fast integer log2 function

that could return one (pipelined) result every clock.

I have no idea whether this is relevant to your problem though, but you

might get something out of the following description.



The first thing I did was to check for a value of zero at the input.

Zero was a special case (as log(0) isn't a regular number) and won't be

considered further here.



Next I counted the number of leading zeros in the input word, using some

simple logic expressed in a few lines of VHDL. This number corresponded

to the "segment" in your post. I will call this number the "exponent".



Next I used a barrel shifter (a few lines of VHDL) to shift the input

word to the left by the number of leading zeros calculated in the

previous stage. At the output of the shifter (which I will call the

"mantissa"), the leftmost bit will be '1', of course (as we shifted by

the number of leading zeros and we are ignoring the special case of all

zeros input).



Next I took several of the most significant bits of the mantissa (but not

the most significant bit which is always 1 and carries no information)

and used them as an input to a lookup table implemented in a single FPGA

block ram.



The contents of the lookup table were precalculated (in a spreadsheet) to

be log2 over a range of [1, 2), giving results over [0, 1). Log2 is

fairly smooth in this range (it's close to a straight line), so I didn't

need to use a particularly wide or deep table to get my desired accuracy.

For more accuracy I could have coded this table as the deviation from a

straight line then added the input to the output, but I did not need to

do that.



The final result was the exponent concatenated with the output of the

lookup table.



I hope that helps, or at least does not confuse.



Regards,

Allan

I have found a solution for my problem. It is about using stages to get the value out.
Your method is really stimulating to me. Just one thing I need you more information.

"For more accuracy I could have coded this table as the deviation from a
straight line then added the input to the output, but I did not need to
do that."

Could you give me a little more detail on above? Thanks again.