EE4253 Linear Recursive Sequences


	EE4253 Digital Communications Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Polynomials and Linear Recursive Sequences

One of the practical applications of polynomials is in the definition and description of linear recursive sequence generators. These sequential circuits, based on shift registers and exclusive-OR (XOR) gates, find use in the generation of random numbers, with many applications in modern cryptography and digital communications.

A Pseudo-Random Number Generator

The generation of binary sequences with random properties using this approach is limited somewhat in that the output of any digital sequential circuit is deterministic (predictable), and a shift register with N-stages can only take on 2^N different states. Consequently, the bit sequences produced in this way will only appear random in the short term. Ultimately the circuit output is periodic, although that period can be arbitrarily long and may span many human lifetimes. These are properly called pseudo-random sequences.

A Linear Recursive Sequence Generator
The circuit above produces an output bit stream with a random appearance
and a period 31 bits long, as 1000010110101000111011111001001....

The ideal random sequence generator will produce the longest possible period before repeating. Note that if the state of the above circuit becomes all zeros it will never change, so this condition must be avoided. Therefore, the maximal length sequence is given by L = 2^N-1, where N is the number of flip flops. In the above example, with five flip flops, the maximal length sequence with a 31-bit period was obtained.

A maximal length sequence has the statistical properties expected of random bits, such as "an equal number of 1's and 0's", which is almost true, but not exactly possible with the odd number of bits L = 2^N-1. The above sequence has 16 ones and 15 zeros. This difference is less important if N is very large.

What Circuits Give Maximal Length Sequences?

The circuit above essentially does polynomial division, giving a quotient which is periodic, much as in decimal we find 1/7 = 0.142857142857142857...

The sequential circuit is defined by the divisor, a polynomial P(x) which is reflected in the XOR gates in the circuit. Each coefficient in the polynomial describes a 'tap' connection to the shift registers. In the above circuit, the taps are 101111 and the polynomial describing this circuit is:

P(x) = x⁵ + x³ + x² + x + 1

It is necessary to identify the polynomials which describe maximum length sequences.

1. The polynomial P(x) must be prime.

If a polynomial P(x) of degree N gives a maximum length sequence, the length will be L = 2^N-1.

On the other hand, there are some prime polynomials which do not work here. A second distinction is necessary.

2. The polynomial P(x) must be a primitive prime.

For a prime P(x) to give a maximum length sequence of length L, P(x) must be a factor of x^L+1 (and of no other smaller L). Such a prime is called primitive.

Illustrative Examples

Example 1

With P(x) = x⁵ + x³ + x² + x + 1

The polynomial P(x) is prime. (Try it!) We might expect a sequence of length L = 2⁵-1 = 31.
AND (x³¹ + 1) / P(x) gives zero remainder, (Try it!) so this prime polynomial leads to a period of 31 (the maximum length sequence).
Therefore, P(x) is a primitive prime.

Example 2

With P(x) = x⁴ + x³ + x² + x + 1

The polynomial P(x) is prime. (Try it!) we might expect a sequence of length L = 2⁴-1 = 15.
AND (x¹⁵ + 1) / P(x) gives zero remainder. (Try it!)
BUT (x⁵ + 1) / P(x) also gives zero remainder, (Try it!) So this prime polynomial leads to a period of 5 (not the maximum length sequence).
Therefore, P(x) is not a primitive prime.

Example 3

Question: What polynomials might give maximal length sequence of L=31?

Answer: Only prime polynomials of degree 5 need be considered, giving length L = 2⁵-1 = 31.

Furthermore, only primitive polynomials will be used: those primes which which are factors of x³¹+1 and which are not factors of any smaller x^L+1

The prime factors of x³¹+1 are: (Try it!)

(11)(100101)(101001)(101111)(110111)(111011)(111101)

Only these six prime factors of degree 5 could give sequences of length 31. They must each be checked to be certain they do not factor a smaller x^L+1. In this case, all six of them do lead to a maximal length sequence.

Finally, note the symmetry between pairs of these six results. There are three pairs of polynomials which are mirror images of each other. This is another property of primitive primes.

See all prime polynomials from 0..511

Online Linear Recursive Sequence Tool


Mon May 20 02:46:53 ADT 2013 Last Updated: 23 NOV 2003	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...