Digital Signal Processing Reference
In-Depth Information
Appendix A: Generation of Pseudo Random Binary
Sequences
In many applications, random sequences of binary numbers are needed. These
applications include random number generation for games, automatic test
pattern generation, data encryption and decryption, data compression, and data
error coding. Since a properly operating digital circuit never produces a random
result, these sequences are called pseudo random. A long pseudo-random binary
sequence appears to be random at first glance.
Table A.1 shows how to make an "n" bit pseudo-random binary sequence
generator. Here is how it works for n = 8. Build an 8-bit shift register that shifts
left one bit per clock cycle. Find the entry in Table A.1 for n = 8. This entry
shows that bits 8,6,5,4 should all XORed or XNORed together to generate the
next shift input used as the low bit in the shift register. Recall that the order of
XOR operations does not matter. Note that the low-bit number is "1" and not
"0" in this table.
A state machine that is actually a non-binary counter is produced. The counter
visits all 2
n
-1 non-zero states once in a pseudo-random order and then repeats.
Since the counter visits every state once, a uniform distribution of numbers
from 1 to 2
n
-1 is generated. In addition to a shift register, only a minimal
number of XOR or XNOR gates are needed for the circuit. The circuit is easy to
synthesize in a HDL such as VHDL since only a few lines are required to shift
and XOR the appropriate bits. Note that the next value in the random sequence
is actually 2x or 2x + 1 the previous value, x. For applications that may require
a more truly random appearing sequence order, use a larger random sequence
generator and select a disjoint subset of the bits and shuffle the output bits.
The initial value loaded in the counter is called the seed. The seed or the
random number is never zero in this circuit. If a seed of zero is ever loaded in
the shift register it will stay stuck at zero. If needed, the circuit can be modified
so that it generates 2
n
states. For the same initial seed value, the circuit will
always generate the same sequence of numbers. In applications that wait for
input, a random seed can be obtained by building a counter with a fast clock
and saving the value of the counter for the seed when an input device such as a
pushbutton is activated.
Additional information on pseudo-random binary sequence generators can be
found in
HDL Chip Design
by D.J. Smith, Doone Publications, 1996, and
Xilinx Application Note 52, 1996.
