Mathematical Foundations of CmpE  Programming Assignment #2

ECE 3020 – Mathematical Foundations of CmpE 
Programming Assignment #2

You are required to complete this assignment INDIVIDUALLY.
Complete this programming assignment using a high-level procedural programming language (e.g., Java,
C, C++; not MATLAB) of your choice. Carefully read the instructions below regarding printouts and other
documentation; note that you do NOT submit an executable copy of your program.
The deliverables for this assignment must be submitted electronically on the Canvas “Assignments” page
no later than 11:00 pm on the due date listed above. A single pdf file is the preferred format. Clearly
PRINT your name at the top of each sheet. You are responsible for ensuring that your submitted file(s) are
readable and successfully uploaded to Canvas.
While hardware modules exist that use physical phenomena to generate truly random numbers, most
computing systems use either hardware or software pseudo-random number generators (PRNGs) that
produce sequences of values that appear to be random. PRNGs can be initialized to a specific value,
allowing the same sequence of (seemingly) random values to be generated repeatedly, which is helpful in
program debugging. Most programming languages and operating systems provide a built-in function to
generate random numbers uniformly distributed in the range (0, 1); these values then can be either (a)
appropriately scaled to yield a desired continuous random function or (b) divided into proportionallysized ranges for discrete random functions.
The accuracy of program results (e.g., simulations) obviously depends on the randomness of the PRNGs.
This randomness can be evaluated, to some extent, by applying various mathematical measures to the
generated sequences and comparing the results with those of truly random sequences. Obvious measures
include the mean value and, for discrete functions, how often each value occurs. Such tests are of limited
value, however, since a counter that repeatedly cycles through the numbers 1 through 6 would generate
values with the same frequency as a true six-sided die, even though it clearly is not random.
Other mathematical measures also can be used to measure randomness; for example, when flipping a
coin, the actual frequency of various runs of consecutives heads or tails can be compared to the expected
frequency of occurrence. This assignment compares PRNGs using the simple mathematical measures of
mean and variance, considering both short and long sequences of random values.
Linear Feedback Shift Registers (LFSRs) are commonly implemented
in hardware for applications including low-cost counters (with an
unusual sequence), random number generators, coding, and signature
generation (e.g., checksums) for blocks of data. The circuit to the right
illustrates an 8-bit LFSR, consisting of an 8-bit shift register and a
multiple-input XOR gate. On each clock cycle, the existing value is
shifted left and a new least-significant bit value is loaded. The
“characteristic polynomial” specifies which bits of the current value
are XORed to compute the next value of the least-significant-bit. For
appropriate polynomials, the LFSR produces a maximum-length cycle
of 2n
– 1 values, excluding only the all-zero value. Other hardware
implementations are also used in various applications, but this
configuration is easily simulated in software. Dividing the LFSR value
by 2n
yields a result in the range (0, 1).
Numerous categories of software algorithms also exist for generating random sequences. A simple one is
the Linear Congruential Generator (LCG), defined by the relation: Xn+1 = (a Xn + c) mod m. The
resulting value or a specified subset of bits is used to generate the output value. (The lower-order bits are
not always used, since they may not exhibit the same quality of mathematical randomness.)
8 1
Characteristic polynomial:
x
8 + x6 + x5 + x4 + 1
Note that LFSR bits are normally
numbered 1 through n, rather than 0
through n-1 as for binary numbers.
The n-input XOR performs a bit-wise
XOR of its inputs, so the XOR output
equals 1 when an odd number of its
input bits are equal to 1.
8-bit shift register
1) Using the high-level programming language of your choice, write a program that compares your
system’s built-in random number generation function with LFSR and LCG implementations of
pseudo-random number generators. Program specifications:
a) Write functions RAN_LFSR and RAN_LCG that generate random 24-bit values using the
methods described above. Each time one of these functions is called, it should use the
appropriate algorithm to generate the next random number in its sequence. Use the following
parameters for the LFSR and LCG:
LFSR: x
24 + x23 + x22 + x17 + 1
LCG: a = 1140671485 (0x43FD43FD), c = 12820163 (0xC39EC3), m = 224;
use all 24 bits to generate the value
After generating the next 24-bit value, the function should return a real number in the range
(0, 1) that is generated by dividing its 24-bit value by 224
.
b) Initialize the LFSR and the LCG to 0xFFFFFF (24 bits, all ‘1’s) when the program starts.
c) Generate 10,000 sets of random values using your system’s built-in random number function,
RAN_LFSR, and RAN_LCG. As the program runs, it should generate the following results:
i. A table, similar to the following, showing the first 25 random values generated by each
method. (The following are not the actual values that should be generated.)
Built-In Function LFSR LCG
0.038965 0.703815 0.416631
0.405642 0.007629 0.033824
ii. A summary table, similar to the following, listing the mean and variance of the random
values generated by each method. In calculating the variance, you may use the theoretical
mean rather than the actual mean, which will vary as more values are generated.
Print this table after 25, 50, 100, 500, 1000, 5000, and 10000 sets of random numbers. The
first row in the summary table should correspond to the random numbers from part (i) above,
allowing you to verify your calculations. (The following are not the actual expected values.)
# of values Built-In Function LFSR LCG
generated mean variance mean variance mean variance
25 0.543 0.163 0.502 0.278 0.458 0.106
50 0.493 0.069 0.521 0.135 0.503 0.092
2) Briefly summarize and interpret the results obtained, comparing your results to the theoretical values.
(The theoretical mean is obviously 0.500; can you figure out the theoretical value of the variance?)
Are these three options for generating random numbers essentially equivalent, or do they have
distinctive characteristics? Consider both what happens initially and the long-term trends. If
possible, explain any observed differences between the LFSR and LCG implementations.
Submit the following materials, preferably combined into a single .pdf file:
(a) A listing of your program source code (.pdf or .txt); an executable version is NOT required.
(b) The program output (written to a file or captured from your computer screen), showing the
execution of your program and its generation of both the table of the first 25 random values and
the summary tables of statistics, as described above.
(c) Your summary and interpretation of the results.