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,

 

[Allan Herriman]

On Fri, 14 Feb 2014 07:40:15 -0800, fl wrote:

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

 

[fl]

On Saturday, February 15, 2014 6:24:02 PM UTC-5, Allan Herriman wrote:

On Fri, 14 Feb 2014 07:40:15 -0800, fl wrote:



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.

 

[Allan Herriman]

On Sun, 16 Feb 2014 04:18:27 -0800, fl wrote:

On Saturday, February 15, 2014 6:24:02 PM UTC-5, Allan Herriman wrote:
On Fri, 14 Feb 2014 07:40:15 -0800, fl wrote:



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.

I meant that instead of using a table to hold the value of log2(x+1)
function over the range [0,1), you could instead use the function log2(x
+1)-(x+1), then add the input (x+1) after the table lookup using a
regular adder.

BTW, the '1' comes from the most significant bit of the mantissa that is
always 1 (that we discarded). In floating point parlance it is called a
"hidden bit" or "implicit bit".


Compare the functions log2(x) with log2(x)-x with x in the range [1,2)
and you will see that log2(x) has outputs in the range of [0,1) whereas
log2(x)-x has outputs in the range [0, 0.087]. This means you need three
bits less table width for a given accuracy, or (more likely) 3 bits more
accuracy for a given width of lookup table, for the cost of one adder.

If your table already takes only 1 block ram and meets your accuracy
goal, this isn't an improvement.

Regards,
Allan