Previous Table of Contents Next


Here, s is a constant greater than or equal to l and is relatively prime to 2q-1. The first restriction, sl, ensures that xn and xj for nj have no bits in common. The second restriction of relative primeness guarantees a full period 2q - 1 for xn. The following example illustrates this procedure for constructing l-bit words.

Example 26.5 Consider generation of 8-bit random numbers from the binary sequence of Example 26.4. The period 27 - 1 = 127 is a prime number. Therefore, any value of i greater than or equal to l = 8 can be used. Using s = 8, the successive 8-bit random numbers obtained are as follows:

x0 = 0.111111102 = 0.9921910

x1 = 0.000111012 = 0.1132810

x2 = 0.111001012 = 0.8945310

x3 = 0.100100102 = 0.2968810

x4 = 0.000001002 = 0.3632810

x5 = 0.010011002 = 0.4218810

The numbers in the middle are binary, and those on the right are the corresponding decimal numbers.

Tausworthe showed that the l-bit numbers generated using Equation (26.10) had the following property:

1.  The mean of the sequence is

2.  The variance of the sequence is

3.  The serial correlation is zero:

4.  The sequence is k distributed for all k’s up to ëq/lû. Briefly, this means that every k-tuple of l-bit numbers appears 2q-kl times over the full. period except the all-zero tuple, which appears one time less. The k-distributivity property is explained further in Section 27.5.

Using k = 1 and l = 1 in the last property, it follows that the complete period of the bit sequence contains 2q-1 ones and 2q-1 - 1 zeros. Also, if a window of length q slides along the sequence, each of the 2q - 1 nonzero k-tuples appears exactly once in a complete period.

Most of the polynomials used for generating Tausworthe sequences are trinomials, that is, they have just three nonzero terms. In this case, generation of each new bit requires just one exclusive-or operation. For example, if only cr and c0 are 1 and all other ci’ are zero, then

bn = bn-q+rbn-q (26.11)

This makes the computation of bits bi fast. However, to get random numbers, we still need to generate several bits. One way to simple random-number generation is to choose r and q such that 2rq. In this case, one can generate successive q-bits by using the following shift and an exclusive-or sequence. The individual bits in a word are read from the right. For example, the seed word would be bq-1bq-2...b0.

1.  Start with a q-bit seed Y1.
2.  Right shift Y1 by r bits, filling with zeros on the left. Call the result Y2.
3.  Exclusive-or Y1 and Y2. Call the result Y3. This completes the computation of the right q - r bits.
4.  Left shift Y3 by q - r bits, filling with zeros on the right. Call the result Y4
5.  Exclusive-or Y3 and Y4. The result Y5 is the new q-bit seed.

The following example illustrates the procedure.

Example 26.6 Consider the generation of 7-bit random numbers using the trinomial of Example 26.4:

x7 + x3 + 1

In this case, r = 3, q = 7, and q - r = 4. Therefore, we need a 3-bit right shift and a 4-bit left shift. Once again we start with a seed X = 1111111. The steps to generate the next 7 bits are as follows:
Step 1: Copy seed, Y1 = X = 1111111.
Step 2: Right shift by 3, Y2 = 0001111.
Step 3: Exclusive-or, Y3 = Y1Y2 = 1110000.
Step 4: Left shift by 4, Y4 = 0000000.
Step 5: Exclusive-or, Y5 = Y3Y4 = 1110000.
The next 7 bits (read from the right) are 0000111. The process can then be repeated:
Step 1: Copy seed, Y1 = X = 1110000.
Step 2: Right shift by 3, Y2 = 0001110.
Step 3: Exclusive-or, Y3 = Y1Y2 =1111110.
Step 4: Left shift by 4, Y4 = 1100000.
Step 5: Exclusive-or, Y5 = Y3Y4 = 0011110.
The next 7 bits (read from the right) are 0111100. As a check, we verify that the bit sequence is the same as that in Example 26.4.

If q is equal to the number of bits in the computer word (not counting the sign bit), the generation of q-bit words using the word-wide shift and exclusive-or instructions is straightforward. For a large q, the shifting procedure can be implemented in hardware. A list of primitive trinomials of degree 31 or less is given in Table 26.1.

A disadvantage of Tausworthe generators is the observation by Tootill et al. (1971) that while the sequence may produce good test results over the complete cycle, it may not have satisfactory local behavior. In particular, it performed negatively on the runs up and down test. Although the first-order serial correlation is almost zero, it is suspected that some primitive polynomials may give poor high-order correlations. Later, in Section 27.5, it is shown that not all primitive polynomials are equally good.

To construct l-bit random numbers xn from the binary sequence bn, Lewis and Payne (1973) proposed a slightly different method than that proposed by Tausworthe. In this method, called the Generalized Feedback Shift Register (GFSR), an l-bit sequence xn is generated from the binary sequence as follows:

xn = 0.bnbn+sbn+2s...bn+(l-1)s

Here, s is a “carefully selected delay.” The key advantage of their idea is that the sequence xn can be generated very efficiently using word-wide shift and exclusive-or instructions. However, it requires that an array of numbers be stored and that careful initialization of this array take place.

TABLE 26.1 List of Primitive Trinomialsa

x2 + x + 1 x3 + x + 1 x4 + x + 1 x5 + x2 + 1
x6 + x + 1 x7 + x + 1 x7 + x3 + 1 x9 + x4 + 1
x10 + x3 + 1 x11 + x2 + 1 x15 + x + 1 x15 + x1
x15 + x7 + 1 x177 + x3 + 1 x17 + x5 + 1 x17 + x6 + 1
x18 + x7 + 1 x20 + x3 + 1 x21 + x2 + 1 x22 + x + 1
x23 + x5 + 1 x23 + x9 + 1 x25 + x3 + 1 x25 + x7 + 1
x28 + x3 + 1 x28 + x9 + 1 x28 + x13 + 1 x29 + x2 + 1
x31 + x3 + 1 x31 + x6 + 1 x31 + x7 + 1 x31 + x13 +1


aIf xq + xr + 1 is listed, then xq + xq-r +1 is also primitive.


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.