Forum Discussion
Altera_Forum
Honored Contributor
Honored ContributorHandling 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_ForumIf 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- Altera_Forum--- 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
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--- 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--- 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--- 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
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.
