Random numbers are used in a wide range of applications, data encryption and simulations are but
of a few applications. However, when generating a random sequence using an algorithm is known
as pseudo-random generation.
In this project, we intend to implement a pseudo-random number generator. Among the techniques
used for such an application are the linear feedback shift register (LFSR).
An LFSR is a shift register whose input bit is a linear function of its previous state. The most
commonly used linear function of single bits is the exclusive-or (XOR).
The initial value of the LFSR is called the seed, and because the operation of the register is
deterministic, the values produced by the register is completely determined by its current (or
previous) state (Figure 1). Likewise, because the register has a finite number of possible states, it
must eventually enter a repeating cycle. However, an LFSR with a well-chosen feedback
function can produce a sequence of bits that appears random and has a very long cycle.
Applications of LFSRs include generating pseudo-random numbers, pseudo-noise sequences, fast
digital counters, and whitening sequences. Both hardware and software implementations of LFSRs
are common.
Figure 1: Example of an 8-bit LFSR
The goal of this project is to find all possible 8-bit structures, also known as polynomial
generators.
Program:
1. Write a function that given an LFSR generator, and a seed, should generate a sequence of
numbers. An animation is provided in [1], it helps understand how an LFSR works. The
sequence of numbers (255) should be saved in external memory starting at address 200H.
Call this function GENERATE.
To implement the function, GENERATE, you need to know that the main use of the XOR
gates it to check the parity; if the number of ones is ODD, a XOR gate produces the value
1 and if the number of ones is even it produces the value 0. You also need to know that the
XOR operator is associative and commutative.
2. Write a function that given the starting address of the generated data (i.e. 200H), should
check that whether any of the values is repeated in the sequence, if it is the case it should
return the value 1 in Register R1 and 0 if there is any repetition in register R1. Call this
function CHECK.
To implement the function CHECK, you may need to first sort the numbers in memory and
check that they are in ascending order without repetitions.
3. The main function should read the LFSR structure from port 0, and the seed from port 1.
The 2 values are sent to the function in part 1(GENERATE). The latter produces the list of
random numbers.
The code should then call the function in part 2 (CHECK), and if there are no repetitions,
the value of the LFSR structure should be in saved in external memory starting at address
400H.
4. Finally, a function should display the values of the valid LFSR structures on Port 3, with a
delay of 1 second between each value and the next one.
