How to implement an irragular table?

Discussion in 'VHDL' started by fl, Feb 14, 2014.

  1. fl

    fl Guest

    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, Feb 14, 2014
    #1
    1. Advertising

  2. fl

    fl Guest

    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, Feb 16, 2014
    #2
    1. Advertising

  3. fl

    fl Guest

    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.
    fl, Feb 16, 2014
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David Williams
    Replies:
    2
    Views:
    1,107
    Jacob Yang [MSFT]
    Aug 12, 2003
  2. Rio
    Replies:
    4
    Views:
    1,172
  3. monkeydragon
    Replies:
    5
    Views:
    252
    monkeydragon
    Dec 15, 2005
  4. ravi

    How to implement a Hash Table in C

    ravi, Aug 11, 2007, in forum: C Programming
    Replies:
    164
    Views:
    3,302
    CBFalconer
    Sep 7, 2007
  5. Thomas Ekegren

    Building a custom control that implement table server control

    Thomas Ekegren, Jul 19, 2003, in forum: ASP .Net Building Controls
    Replies:
    2
    Views:
    232
    Victor Garcia Aprea [MVP]
    Jul 20, 2003
Loading...

Share This Page