Handling large arrays in VHDL

If you just want random numbers, then use a Linear Feedback Shift Register (LFSR), see this doc and source:

http://www.ovro.caltech.edu/~dwh/correlator/pdf/lfsr_tutorial.pdf

http://www.ovro.caltech.edu/~dwh/correlator/pdf/lfsr_tutorial_src.zip

Cheers,

Dave

--- 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.

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

--- 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

--- 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.

--- 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

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.