A source of ``random'' numbers if often needed to accomplish programming tasks. The reasons for this are varied and sometimes surprising. The programming task might simple be to produced a display of randoming flashing lights. Often random numbers are added to signal to increase the amount noise. This is beneficial in picture signals since very clean digital images have a number of artifacts including jagged lines and noticable contours on smoothly shaded surfaces. Making the signal noisy hides these artifacts from the eye, without really damaging the underlying information.
Since computers act entirely predictably, it is not possible for a computer to generate truely random numbers. Inside, we dream up processes which produce a stream of numbers which look random even though they follow an entirely predictable pattern. These numbers are called pseudorandom. There are many pseudorandom number generators, some of which are extremely sophisticated. Encryption of data, for example, depends on pseudorandom number generation for which finding any pattern in the number stream is extremely difficult. Since almost everyone's financial security and privacy depends on the quality of these pseudorandom number generators, you can imagine how carefully the areas has been studied!
Our pseudorandom number generator will not be of this quality. It is a simple shift register where the vacated bit of is filled with the exclusive-or of two other bits in the shift register.
Here is a 4 bit shift-register pseudorandom number generator:
+----->(+)-----------+
| | |
| +---+---+---+---+ |
+-| 4 | 3 | 2 | 1 |<-+
+---+---+---+---+
At each time step:
0001 0010 0100 1001 0011 0110 1101 1010 0101 1011 0111 1111 1110 1100 1000 0001The pattern repeats endlessly. The length of the pattern in 15 different bit combinations. This is the maximum possible. There are at most 16 different bit combinations in a 4 bit register (2 to the power 4) however the combination 0000 is not a real possibility, since if the register is ever at 0000 it will remain forever at 0000.
It is very important to note that not every choice of two bits to exclusive-or will work equally as well. Here is a bad choice for the 4 bit shift-register:
+--------->(+)-------+
| | |
| +---+---+---+---+ |
+-| 4 | 3 | 2 | 1 |<-+
+---+---+---+---+
BAD CHOICE
This bad choice gives a shorter sequence of bit patterns:
0001 0010 0101 1010 0100 1000 0001
The previous section gave an illustration of a pseudorandom generator for 4 bits and showed that it was possible to get the maximum length sequence of 15 = (2 to the power 4) - 1 by tapping at bit 3, but not by tapping at bit 2. It turns out that bit 1 is also OK to tap.
We now generalize to n bits tapping at bit location m. We give a table for the selection of m such that the resulting sequence is of length (2 power n)-1. Note that each entry is actually two entries. It can be proven using mathematics that if m is a good choice for a given n, then so is n-m. For example: in the previous section we showed that n=4 and m=3 was a good choice. Then so is m=4-3=1.
The shift-register pseudorandom number generators are calculating the successive powers of an unknown x in a finite number field called the Galois (gall-wah) of order 2 to the n. To understand, first consider the simplist finite number field. Take a prime p and consider the integers mod p. They are 0, 1, 2, etc. up to p-1, with addition and multiplication mod p. Since p is prime (and only if p is prime!) with the exception of 0, for each x there is a y such that x*y = 1 mod p. That is, each number except zero has an inverse mod p without resorting to the invention of fractions.
Example: For the prime p=7,
Exercise: Make a table of inverses for p=11.
The next step is to find a number and take its successive powers mod p and see what happens. For a good choice of number the successive powers will cycle through all the possible numbers mod p in a pseudorandom way. This is the basis of the presented shift-register pseudorandom number generator.
Example: For the prime p=7, the number m=3 cycles nicely:
Exercise: Find a number m such that m to the 2, 3, 4, ..., 11 cycles through all 10 non-zero values mod the prime p=11.
Although these example illustrate conceptually how our shift-registers work, the "numbers" which are stored in the shift-registers, and the multiplication by successive powers, might be unusual to the beginner in mathematics.
The numbers used here are the polynomials with coefficients mod 2. Think of these polynomials as the integers, and we take them modulo another polynomial, which also must be prime, that means a polynomial which does not factor. The coefficients of the polynomial are mod 2, that means that the values for the coefficients are either 0 or 1, and 1+1=0. Each location in the shift-register is the coefficient for a power of x, and shifting to the left is multiplication by x. The feedback using the exclusive-or does the modulus arithmetic. Just as going over p in the integers mod p wraps back to a smaller integer, shifting-out of the highest bit in the shift-register is making x too high a power, and it wraps back to a combination of lower power x's. The choice of which bits to include in the exclusive-or is a choice of polynomial for the modulus, and the table given in the previous section indicates which polynomials are prime.
Example of polynomials: Here are all the polynomials with coefficients mod 2 for small degree:
Example of addition: Adding polynomials mod 2 is the same as adding "normal" polynomials except that the coefficient arithmetic is mod 2, that is 1+1=0.
Example of multiplication: Multiplying polynomials mod 2 is the same as multiplying "normal" polynomials except the required additions are done mod 2, as above.
It is important to keep track of two types of modular arithmetic which are being done simultaneously: the coefficients are mod 2, but the polynomials are also viewed modulo a given polynomial Q. Making the parallel with integers mod a prime, after arithmetic with the polynomials it is reduced mod Q by dividing by Q and considering the remainder as the result of the arithmetic.
In our situation, it is easy to use repeated subtraction rather than division (which is the same thing) because the only operation we will do is multiplication by x. So the polynomials only get a very little bit larger, and can be reduced if need be by a single subtraction.
Example of modular arithmetic: Let Q=x^4+x+1. Then reduce each polynomial by taking its remainder after division by Q. If the polynomial to be reduced has no term higher than x^3, then leave it alone. If it has a term x^4, then add Q to the polynomial. This is legal since mod Q the polynomial Q acts as zero, so adding it does not change the value. The effect is to replace x^4 by x+1. We will not worry about x^i, for i greater than 4, because our shift-register never generates such results.
We began our discussion with the following 4 bit shift-register:
+----->(+)-----------+
| | |
| +---+---+---+---+ |
+-| 4 | 3 | 2 | 1 |<-+
+---+---+---+---+
In our table, this example is n=4 and m=3.
Each pattern of bits in the shift register corresponds to a polynomial
with coefficients mod 2. The mapping is:
For instance, 0101 is polynomial x^3+x. Because m=3,
the polynomial chosen for modular arithmetic is Q=x^4+x+1. Each shifting
left is taking x^i to x^(i+1). The overflow of (x^3)*x=x^4 is reduced
mod x^4+x+1 by changing the x^4 into x+1. That is, bit 3
(which represents x^3) becomes bit 4 (which represents x^0=1)
and also bit 1 (which represents x^1)
but only if the current bit 4 was 0 - else the result is
adding x to (1)*x and therefore there should be no x term in the result.
We will demonstrate the arithmetic in full by showing side by side the bit patterns according to shifting and exclusive-or, and the successive powers of x with reduction by the polynomial x^4+x+1, and you will see that the two procedures continuously correspond:
0001 is x 0010 is (x)*x = x^2 0100 is (x^2)*x = x^3 1001 is (x^3)*x = x^4 = x+1 (mod x^4+x+1) 0011 is (x+1)*x = x^2+x 0110 is (x^2+x)*x = x^3+x^2 1101 is (x^3+x^2)*x = x^4+x^3 = x^3+x+1 (mod x^4+x+1) 1010 is (x^3+x+1)*x = x^4+x^2+x = x^2+1 (mod x^4+x+1) 0101 is (x^2+1)*x = x^3+x 1011 is (x^3+x)*x = x^4+x^2 = x^2+x+1 (mod x^4+x+1) 0111 is (x^2+x+1)*x = x^3+x^2+x 1111 is (x^3+x^2+x)*x = x^4+x^3+x^2 = x^3+x^2+x+1 (mod x^4+x+1) 1110 is (x^3+x^2+x+1)*x = x^4+x^3+x^2+x = x^3+x^2+1 (mod x^4+x+1) 1100 is (x^3+x^2+1)*x = x^4+x^3+x = x^3+1 (mod x^4+x+1) 1000 is (x^3+1)*x = x^4+x = 1 (mod x^4+x+1) 0001 is (1)*x = x
On the other hand, the following shift-register does not work as we wish:
+--------->(+)-------+
| | |
| +---+---+---+---+ |
+-| 4 | 3 | 2 | 1 |<-+
+---+---+---+---+
BAD CHOICE
For this example, where m=2, the table mapping bits
to coefficients of x^i is:
And the idea is that x^4 is replaced by 1 and x^2, if there isn't
already an x^2 shifting in from bit 4 (which represents x^1).
Hence the polynomial to reduce by is x^4+x^2+1.
Here's the result, giving corresponding bit manipulations and
polynomial arithmetic manipulations:
0001 is x^2 0010 is (x^2)*x = x^3 0101 is (x^3)*x = x^4 = x^2+1 (mod x^4+x^2+1) 1010 is (x^2+1)*x = x^3+x 0100 is (x^3+x )*x = x^4+x^2 = 1 (mod x^4+x^2+1) 1000 is (1)*x = x 0001 is (x)*x = x^2
So what's the difference between the two examples? The polynomial x^4+x+1 is prime, but the polynomial x^4+x^2+1 is not (where we continue to assume the coefficients are mod 2). Here is the factors of x^4+x^2+1,
(x^2+x+1) * (x^2+x+1) = x^4 + 2x^3 + 3x^2+ 2x + 1 = x^4 + x^2 + 1 (coefficients mod 2)In the example of the integers mod 7, we found an inverse for every integer except 0, and this depended on the fact that 7 is prime. In any cycle of numbers generated by successive powers, every number on in the sequence must has an inverse. For instance, if x has inverse y then x^2 has inverse y^2, and so on. So in order to have the sequence contain all numbers except 0, all numbers except zero must have inverses, and so the modulus must be prime.
Pseudorandom numbers can be generated by a simple shift-register by taking successive powers of x in the field of polynomials with coefficients mod 2 modulo a prime polynomial. This exotic sort of arithmetic is actually very simple in reality: the polynomials are represented in an n-bit shift-register where each bit gives the coefficient 0 or 1 for x^i; multiplication by x is a left shift; and reduction modulo the polynomial Q=x^n+x^k+1 is accomplished with an exclusive-or of the overflow bit into the bit which corresponds to x^k (the least significant in the shift register) along with the implied shifting of the overflow bit into the bit which corresponds to x^0.
To get the maximum length cycles, Q must not factor as a polynomial with coefficients in mod 2, and x must cycle through all 2^n-1 non-zero polynomials mod Q. A table is given which shows what m values achieve this goal.
The arithmetic on the polynomials with coefficients mod 2, taken modulo a prime polynomial Q is called the Galois Field on 2^n elements and is used often in coding, error correction, computer science, and so on. Here we have one example of its use.
Copyright (c) 1997 Burton Rosenberg. All rights reserved.
Last modified: Tue Oct 28 13:52:53 EST 1997
Fri Sep 28 2018