Forum Discussion

Altera_Forum's avatar
Altera_Forum
Icon for Honored Contributor rankHonored Contributor
13 years ago

Handling large arrays in VHDL

I have a constant array of integers (2^8 words deep) declared in VHDL. Each entry is a random number in the range 0-65535. There is a nonlinear mapping between the random numbers and the index of the array. For instance if the array is

0: 1

1: 4

2: 19

3: 54

...

and my random number generator generates the value 24, the output is 2. If the number is 10, the output is 1 and so on.

For now I have a for loop that goes through the whole array to determine the index for which the Random_Number >= Array(I).

I was wondering whether there is an alternative to this implementation since I want to reduce the amount of combinational logic used by the design.

I have thought about a ROM but this is not a ROM in the traditional sense since the random number is not an "address" into the array.

Alternatively, I could declare an array that is 2^16 words deep and can be indexed using the random number. This would essentially synthesize a ROM block in Quartus. But in case I have multiple such arrays, I'm going to run out of internal memory very quickly.

Any thoughts/insights on this will be appreciated. Thanks!

7 Replies

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    --- Quote Start ---

    If you just want random numbers

    --- Quote End ---

    Actually my implementation of RNG is based on LFSR. Generating the numbers is not a problem at all. Once I generate a number, I want to figure out which "bin" between 1-256 does this number correspond to using the constant array. The mapping happens to be non-linear.

    For now I do it using a for loop, which requires the synthesis tool to implement large number of muxes and demuxes.

    I was curious to know whether there is a less resource-hungry implementation.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    I think what you need is CAM (content addressed memory).

    Haven't used it myself but it outputs the address(s) if given data content.

    Make a search for CAM RAM
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    --- Quote Start ---

    Once I generate a number, I want to figure out which "bin" between 1-256 does this number correspond to using the constant array. The mapping happens to be non-linear.

    --- Quote End ---

    Perhaps you can be a little clearer on what is non-linear. You say there are only 256 possible RAM locations, but comment there are 16-bit data coming in.

    Can this non-linearity be described by an equation, eg., the simplest case would be truncation of the 8 LSBs. FPGAs can be used to implement spline fits. If a low-order polynomial can be used to describe your mapping, perhaps it can be implemented as an efficient input-to-RAM address mapping.

    Cheers,

    Dave
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    --- Quote Start ---

    Perhaps you can be a little clearer on what is non-linear.

    --- Quote End ---

    The attached jpeg file hopefully makes it clearer. The x-axis represents the random numbers and the y-axis is the "bins" (1-256).

    In a mathematical sense, there is a many-to-one relationship: many random numbers map to the same bin. The values stored in the array are the lower and upper limits for a particular bin. In the example in my first post, any random number generated between 19 & 54 corresponds to Bin 2.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    --- Quote Start ---

    The attached jpeg file hopefully makes it clearer. The x-axis represents the random numbers and the y-axis is the "bins" (1-256).

    In a mathematical sense, there is a many-to-one relationship: many random numbers map to the same bin. The values stored in the array are the lower and upper limits for a particular bin. In the example in my first post, any random number generated between 19 & 54 corresponds to Bin 2.

    --- Quote End ---

    The plot is a nice smooth function, so you should be able to represent it using a polynomial. If you are lucky, it might be as simple as X^N. If it is that simple, then given Y = X^N, taking the log of both sides gives

    log(Y) = N*log(X)

    So if you plot log(Y) versus log(X), you'll have a straight line with slope N. Try it and see. (Actually, it might be Y = X^N/256, since X is 16-bit, but y is 8-bit).

    Your FPGA processing logic would then consist of;

    1) Logic to calculate Y_full = X^N

    2) Logic to quantize Y_full to 8-bits to give the output Y

    3) Use Y as the 256-entry table address

    Cheers,

    Dave
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    Regarding the original problem, how to scan the content of a 256x16 table.

    A result in one clock cycle can be only achieved by the two solutions mentioned in your post. Alternatively you can implement a binary search tree, that finds the result in 8 steps (8 clock cycles) in a 256x16 ROM table. The method is very similar to the operation of a succesive approximation ADC.

    Hybrid methods using multiple small tables and 2 or 3 clock cycles should be possible as well.