Date: 1 Dec 93 14:18:00 CST From: "VAXEC1::HANNA" Subject: Brief Description: Rnadom Number/Random Test Vector Generator Package To: "vhdlsynth" [This Document Serves as a Brief Description of the VHDL-Based Random Number Generator We put on the Reflector Earlier. We hope You find this document helpful, and the RNG package useful. The RNG Code was released for public use according to restrictions specified in the first paragraph of the code document. Please communicate questions, requests, and feedback to: W.A. (Bill) Hanna McDonnell Douglas Aerospace MC 500 4224 P.O. Box 426 St. Charles, MO 63302, USA. My e-mail address is: hanna%vaxec1.decnet@mdcgwy.mdc.com] Random Number Generator for VHDL Models (W.A. Hanna) Abstract: --------- This report describes a Random Number Generator (RNG) package written entirely in VHDL. This package can generate random numbers from a variety of distributions. Typical applications include stochastic simulations, performance modeling, and Monte Carlo worst-case analysis. Also, Random Test Vectors Generation based on random numbers generated is possible as indicated in the provided testbench, rnd_test . 1. Introduction: ---------------- Simulation models need to contain a large amount of information about the systems they represent. Unfortunately, much of this information cannot be specified exactly, either because the data is an estimate of an unknown parameter or because the value is simply not fixed. Examples of such of such vague information include message interarrival times on a network, noise on a signal, execution time of a yet-to-be written software task, values of inputs to test mathematical algorithms, etc. The most straight forward method of modeling this type of data is to use a random number generator. Unfortunately, VHDL has no such built-in capability, and even those languages and computer systems that do include random number generators usually only provide the traditional uniform distribution in the range (0,1) or (1,0). We started by calling the UNIX System V ernd48, UNIX Random Number Generator. Incremently, we encoded different functions/procedures in VHDL. This effort evolved to a full VHDL implementation which eliminates dependency on systems, and allows the user to choose a statistical distribution and generate random numbers from within VHDL by compiling and calling the VHDL Package provided, Package rnd2 (rnd2 for Version 2). We also included a testbench which generates random test vectors, type bit_vector. The specific limits chosen were to test a fiber optic link which has 18-bit wide data elements. The user can change the length and the type of data, as well. We presently are generating 100 vectors long streams of 18-bit random binary data ('0', '1'). Please communicate questions, requests, and feedback to: W.A. (Bill) Hanna, McDonnell Douglas Aerospace, MC 500 4224, P.O. Box 426, St. Charles, MO 63302, USA. My e-mail address is: hanna%vaxec1.decnet@mdcgwy.mdc.com 2. Operation: ------------- Library Name Is Utility2 Package Name Is rnd2 Library Utility2; Library Command Use Utility2.rnd2.all; Use Command for Package rnd [One can change Names/Directories(Path) to suit his system] Higher Math Functions: log (natural logarithm), floor (floor function), ceil (ceiling function), sqrt (square root function), "**" (exponentiation with real operand) [One can call native MATH LIBRARY for more accurate results, We used to call UNIX MATH LIBRARY: Use Utility.c_math.all] Main Random Number Generator: rnd48 (similar to UNIX SYSTEM V ernd48) Data Types: all start with "rnd_" rnd_distribution_t Is Random Distribution Type Enumeration: rnd_constant - Constant Value rnd_uniform_d - Discrete Unifrom Distribution rnd_poisson - Poisson Distribution rnd_binomial - Binomial Distribution rnd_geometric - Geometric Distribution rnd_empirical_d - Discrete Empirical (User Supplied) Distribution rnd_uniform_c - Continuous Unifrom Distribution rnd_normal - Normal (Continous) Distribution rnd_triangular - Triangualr (Continuous) Distribution rnd_exponential - Exponential (Continuous) Distribution rnd_hyperexponential - Hyperexponential (Continuous) Distribution rnd_gamma - Gamma (Continuous) Distribution rnd_erlang - Erlang (Continuous) Distribution rnd_empirical_c - Empirical (Continuous) Distribution rnd_seed_t Is Array of 4 Integers Seed, Indexed 3 downto 0 Each Is 12 Bit Integer (Total of 48 Bits) rnd_seed_vector_t Is Array of rnd_seed_t. It is Used as the base type of the predefined constant, rnd_seed rnd_empirical_t Is a record consisting of two real numbers, and represents a point on the cumulative distribution function (cdf) of the desired probability distribution. The fields are: x The value of the random variable at this commulative probability value. p The cummulative probability of the random value given x. rnd_empirical_vector_t An unconstrained One Dimensional Array of rnd_empirical_t Records. rnd_rec_t This Record Contains All the Information Needed to Execute the Random Number Generator Procedure, except for the Empirical Array. It also Contains the returned Random Value. The fields Are: rnd The Random value Returned distribution The desired Distribution, of type rnd_distribution_t seed Random Number Generator's Seed according to rnd_seed_t mean A Real Number Specifying Mean Value for Distributions Requiring it, Otherwise Ignored. std_dev A Real Number Specifying Standard Deviation for Distributions Requiring it, Otherwise Ignored. bound_l, bound_h Lower and Upper bound, respectively for Distributions Requiring it, Otherwise Ignored. trial An Integer Specifying the Number of Trials to be Performed, Presently Only Used by Binomial Distribution. p-success A Real Number Specifying probability of Success, between 0.0 and 1.0, Inclusive. Constants: rnd_seeds Constant Array of rnd-seed_vector_t (50 random seeds) Each element Is 100,000 Itterations Separated from the Previous One to Guarantee That The Random Streams Are Independent. Main Procedure: rnd_random (rnd_rec[,empirical_data]) procedure to generte random number according to rnd_rec, selected seed(s) rnd_rec (inout) accepts seed, and distribution type returns (new)seed, and rnd (new random number) empirical_data (in) [optional] When Needed, Is rnd_empirical_t (array of x,p) values, Used for Empirical Type Distributions Other Than the Ones Provided. rnd_read_record (rnd_rec) Read An External File Which Is Globally Defined, we could Not Pass A File Type Variable Parameter Because of Inconsistent Definition in VHDL-87 [Let me know if you have a way of compiling and executing rnd_read_record (f:in file, rnd_rec:inout rnd_rec_t) or variations thereof!!!!!!] 3. Statisitcal Charactristics: ------------------------------ One needs a variety of distributions, both discrete and continous, from which to choose, such as the normal, poisson, and exponential distributions. The package described here allows the user to choose from five discrete and eight continuous distributions. The distributions are derived from a 48-bit mixed linear congruential pseudo-random number generator that emulates the erand48 random number generator found in the UNIX System V Library. The distributions are all accessed through a single procedure call, with all parameters passed as fields of a single record, rnd_rec. This allows the parameters of a distribution, or even the distribution itself to be changed without having to change the source code. Such parameters can be passed into a model as generics, allowing different instances of an entity to have different distributions. The parameters may also be read from from a textfile, using a procedure supplied in the package, read_read_record. This last option is having difficulties because of the unclear rules of passing File Type Parameters in VHDL-87 Procedure Calls. One of the parameters in the rnd_rec is the seed of a randome number sequence. By passing the seed, the as a parameter, the user has complete control over the number of separate numbers streams generated; a requirement for all (pseudo)random number generators to achieve repeatability of model data/experiments. To make random number seed specification simpler, an array of fifty pre-generated seeds, spaced 100,000 iterations apart, is provided as constant, rnd_constant. The package is implemented completely in VHDL. A few math functions were originally implmented using UNIX MATH LIBRARY CALLS. These functions are now implemented in VHDL. One can switch back to UNIX Library calls, if he so chooses, by commenting the inline code for the function/procedure and reinistating the proper Library Calls. 4. Additional Information (Random Number Algorithms Provided): -------------------------------------------------------------- All algorithms provided have been adequately tested against the appropriate statistical distribution, however, we can not guarantee the accuracy and/or precision of the results from this publicly distributed package. 4.1 Linear Congruential Generator: All the distributions in this package are based on a single random number generator, which is uniformly distributed in the continuous range [0,1) {The notation [0,1) means including 0 but not including 1} The random number generator chosen is a mixed linear congruential generator which has the general form: Xn+1 = (a * Xn + c) mod m, n >= 0 where: X is usually referred to as the seed. in this implementation, m = 2**48 a = 0x0005DEECE66D c = 0x000000000B Note that each seed, Xi, is a 48-bit number. In order to implement the necessary 48-bit arithmetic in VHDL without causing integer overflows, the seed is stored as a four-element array of integers, with each element containing twelve bits of the seed. Although the size of integers in VHDL is implementation-dependent, it must be at least 28 bits for this package to work correctly (12 bits if integer overflow can be disabled). The actual random number is obtained by dividing the 48-bit seed by m. 4.2 Discrete Distributions: --------------------------- 4.2.1 Constant Distribution: ---------------------------- A convenient way for the user to replace a probability distribution with a single value (constant) which is specidfied as the mean parameter. The same effect can be achieved with the other distributions by replacing a distribution; e.g empirical distribution; with a single data point. For constant distribution, the only required parameter is the mean value. Note that the seed is not modified. 4.2.2 Uniform Distribution: --------------------------- The Discrete Uniform Distribution return an integral random value in the range [bound_l, bound_h]. All values are equally likely. Algorithm: X = bound_l + floor (bound_h - bound_l + 1.0) * U where floor function returns the largest integer less than or equal to function's argument U is random number [0,1) 4.2.3 Binomial Distribution: ---------------------------- The Binomial Distribution returns an integral value indicating the number of "successes" obtained from repeating an independent experiment a number of times equal to parameter trials, with the probability of success given by p_success. Algorithm: Generate U, for each trial count the number of successes Requires: p_success, trials as input parameters. 4.2.4 Geometric Distribution: ----------------------------- Algorithm: Generate U, count the number of trials before the first p-success. Requires: p_success as input parameter. 4.2.5 Poisson Distribution: --------------------------- The Poisson Distribution is widely used in modeling physical phenomena. The general form of the distributions is: Probability{X = i} = exp (-L) * Li/i! where: exp is (e) natural exponential L is a positive constant Algorithm: Similar to Geometric Distribution except that it uses the Poisson Distribution above. Requires value of L (lambda). 4.2.6 Empirical Distribution(s): -------------------------------- The discrete empirical distribution can be used to model any tabulated discrete distribution. Although the distribution is assumed to be discrete the possible values of the random variable need not be integral or evenly distributed. Algorithm: The algorithm uses an array provided by the user (size is user specified). The array contains pairs of numbers which are interpreted as points along the cumulative distribution graph. Since this is a cumulative distribution, the last value must have a probability value of 1. Also, for cummulative distribution, probability value must be non decreasing. 4.3 Continuous Distributions: ----------------------------- 4.3.1 Uniform (Continuous) Distribution: ---------------------------------------- Returns a random value in the range of [bound_l, bound_h]. All values are equally likely. Algorithm: X = bound_l + (bound_h - bound_l) * U where bound_l is Lower Bound value bound_h is Higher Bound Value U random number [0, 1) 4.3.2 Traingular (Continuous) Distribution: ------------------------------------------- Often computed as the sum of two uniformly distributed random variable. The mean parameter is actually the mode and indicates the peak of the traingle. The peak needs not be at the center of the range. Algorithm: f(x) = 0 if X =< bound_l (x - bound_l)/(mean - bound_l) * U if x =< mean, x > bound_l (bound_h - x)/(bound_h - mean) * U if X >= mean, x < bound_h 0 if X >= bound_h where f(x) is probability density function (pdf) Requires: mean, bound_l, bound_h 4.3.3 Exponential (Continuous) Distribution: -------------------------------------------- The exponential distribution requires a pdf according to the following: fx(t) = 0 t < 0, L * exp (-L * t) t => 0 4.3.4 Hyperexponential (Continuous) Distribution: ------------------------------------------------- A combination of two exponential distributions with rate parameters L1 and L2, such that the first distribution is used with probability p, and the second with probability (p-1). 4.3.5 Normal (Gaussian) Continuous Distribution: ------------------------------------------------ Widely used in statistical analysis. The required parameters are mean and standard deviation. This distribution is achieved by generating random numbers pairwise, and using the second value as seed for the next value of the first element in the pair. 4.3.6 Gamma (Continuous) Distribution: -------------------------------------- The Gamma distribution requires a pdf according to the following: fx(t) = 0 t =< 0 a (at)**r-1 exp(-at)/Gamma(a) t > 0 Where a is alpha (rate) parameter r is Gamma Function Order Gamma(a) Is the Gamma Function If r=1 Gamma Distribution Become Exponential Distribution with Rate a. 4.3.7 Erlang (Continuous) Distribution: --------------------------------------- Erlang Distribution Is Gamma Distribution with Integral Valuse for r. 4.3.8 Empirical (Continuous) Distribution: ------------------------------------------ Is obtained by entering a table of pairs of numbers representing points on probability curve (x) and cumulative probability at each value. The points do not have to be equally spaced. Cumulative probability has to be continuously increasing with last point having a probability value of 1. Since this distribution is continuous values of events can be integer and/or real. Values between given events can be linearily interpolated. 5. Testbench (entity rnd_test2): ----------------------------------- Entity rnd_test2 Architecture a2 of rnd_test2 Constants: imax = 100 Selected Maximum Number of Vectors; range integer jmax = 18 Selected Number of Bits In Test Vector; range integer Signals: ATGV bit_vector (0 to jmax-1) Is a Test Vector, type bit_vector (0 to 17). Can be made to fit your application Files: f: Text Is Out "rnd.out" This Output File Will Contains the Random Test Vectors Generated. System Dependent Path and/or Naming Rules Have to Be Followed. file_f: Text Is In "XYZ.IN" This Input File Is Used to Input rnd_rec using procedure rnd_record_read. If it works, One would be able to run the program for different seeds and different distributions by changing the contenets of input file. Process: This process generates random numbers according to empirical data with: distribution = rnd_empirical_c (random empirical continuous) mean = 2.0, std_dev = 1.0, bound_l = -10, bound_h = 10, seed = (0, 0, 0, 123), emp: rnd_empirical_vector_t := ( (0.0, 0.0), (1.0, 0.1), (2.0, 0.3), (3.0, 0.8), (4.0, 0.8), (5.0, 1.0)) It calls the random number procedure: rnd_random (rnd_rec, emp) to generate a number. For each number generated a '1' or '0' is generated. If random number (rnd_rec.random) < mean, I generate a '1' else I Generate a '0'. One can use other rules. Also you can generate other logic values by creating regions within bound_l, bound_h limits to correspond to different logic values as desired. The testbench also keeps track of statistics of numbers generted. We found out that the average value is very close to predicted mean ~2.5, Standard Deviation Is Close to ~.8, which means that the numbers are close together! Maximum run we had was for 200 vectors, 200*18 = 3600 random numbers generated. Not a large sample. You need to run 10,000 to 100,000 itterations to get a statistically significant sample.