Inverse Transform Sampling method on FPGA
Started by 6 years ago●3 replies●latest reply 6 years ago●125 viewsA user is seeking guidance on implementing the Inverse Transform Sampling method for generating random numbers on an FPGA based on a specific cumulative distribution function (CDF).
The discussion highlights the transition from theoretical probability to hardware implementation, focusing on handling mathematical functions and data types.
A practical recommendation was provided to use Look-Up Tables (LUTs) and shift registers to optimize runtime performance and simplify complex calculations like natural logarithms.
- Precomputing the CDF into a Look-Up Table (LUT) avoids complex runtime mathematical computations.
- Linear Feedback Shift Registers (LFSR) can be used to generate the initial uniform random values.
- The generated uniform values serve as addresses for the LUT to retrieve the inverse samples.
- Converting ratios from shift registers allows for efficient mapping of random numbers to the 0-1 range.
Hi,
I am working on pseudo random number generation topic. To be precise, Inverse Transform Sampling method , i.e., a method for generating sample numbers at random from any probability distribution given its cumulative distribution function.
The problem that the inverse transform sampling method solves is as follows:
- Let X be a random variable whose distribution can be described by the cumulative distributive function Fx.
- I want to generate values of X which are distributed according to this distribution.
The exact reference of what I would like to implement on FPGA is : https://en.wikipedia.org/wiki/Inverse_transform_sa...
Questions:
- What would be the mathematical challenges? I mean challenges in context of natural log and then data types like integer, fixed and floating points.
- What should be the right approach? I mean the starting point.
I am looking for some example codes (if any) and helping literature that would help me to understand the granularity of implementation on FPGA.
Looking forward to suggestions. Thanks a lot !
Hi,
Here are my initial thoughts
1) You can precompute your chosen CDF and insert it in a look up table. This will reduce a lot of run time computations.
2) You then generate runtime initial random numbers say from shift registers with feedback taps and assume they are in the range 0-1 e.g a 16 bit shift register will generate numbers between 1 and 2^16 then you can assume the ratio as the generated number relative to 2^16
3) use the generated numbers to address the look up table. The content will be your inverse sample.
thanks :-)
Kaz it was a helpful reply... I have posted another question on the forum. Can you also please help me in that question. Here is the link: https://www.fpgarelated.com/thread/10860/
