Design of a Mechanical Analog Autocorrelator to Demonstrate Properties of Pseudonoise (PN) Sequences

Sean E. O'Connor

Introduction

Pseudonoise sequences are bit streams used in communications engineering for spread spectrum communications, radio distance measurements, and analyzing concert hall acoustics during live performances.

This is due to their sharply peaked autocorrelation properties. We'll show how their properties can be derived directly from Galois field arithmetic. We'll generalize to mod p arithmetic, leaving the binary PN sequences as a special case when p=2.

We'll conclude by showing how to build a mechanical autocorrelator as a teaching tool which dramatically demonstrates their properties. This is a new and unique design for which there exists no prior art to the best of my knowledge.

Prerequisites: Knowledge of Galois (finite) field theory.

Finite Field Review

Notation: Let the unique Galois field with elements be denoted

Let a primitive monic polynomial which generates it be

The exponential and polynomial forms of the field elements are

Example: The field with 16 elements, is generated by the primitive polynomial, which has as elements, and

Pseudonoise Sequences

Definition. The pseudonoise (PN) sequence of length is the sequence where and constant coefficient of the polynomial representation of field element When the Galois field elements are written out as a list of polynomial coefficients, the PN sequence is the last column.

Example: reading off the constant coefficient of the polynomials in our example field we get which generates the length 15 sequence

Difference Equation

We don't need to generate the field and do time consuming finite field arithmetic to find a PN sequence, but can use a recursive method instead.

Note that, and so

Expanding out we get

Now applying the mod operation throughout,

Take the constant coefficient of each polynomial term,

And rearrange to get the difference equation,

for

with initial conditions

That is, the all zeros except for the first coefficient.

Example:

are the initial conditions and the difference equation is

which generates the same PN sequence as before, (Note that we can omit the -1 since -1 = 1 (mod 2)).

We continue shifting until we come back to the initial state at

Hardware Implementation

Software Implementation

In the C language, we can emulate the hardware bit operations with bit shifting and masking. Here is sample C code which computes values of a binary PN sequence.

The program output is,

pn 1 = 1, pn 2 = 0, pn 3 = 0, pn 4 = 0, pn 5 = 1, pn 6 = 0

pn 7 = 0, pn 8 = 1, pn 9 = 1, pn 10 = 0, pn 11 = 1, pn 12 = 0

pn 13 = 1, pn 14 = 1, pn 15 = 1

Circular Autocorrelation

The circular autocorrelation of the PN sequence

is defined to be

where indices are taken modulo We will show that in the binary case p=2, the autocorrelation has a sharp peak at j=0 and is flat elsewhere.

Example.

Our sample sequence has autocorrelation,

We get

The autocorrelation is very sharply peaked:

I tossed a penny 15 times to get a random sequence,

and the autocorrelation was much less sharply peaked:

Theorem. The circular autocorrelation of the PN sequence,

is

Proof.

Case j=0.

Case

where indices are taken modulo

Now we digress to note that since

is a primitive element of the field we can write

for

where Z(j) is called the Zech's logarithm of j.

since the unique inverse of 1 is p-1, which will not happen.

rewriting into polynomial form, taking mod f(x) and p, and looking

at the constant term gives,

Then

where the last step follows because the indices are merely shifted modulo

Now consider the sum for even p and odd p cases.

Now each group of odd p constant coefficients has an extra unpaired 1.

Number of groups = (total number of field elements) / p =

Mechanical Autocorrelator

To illustrate the autocorrelation properties of the PN sequence, I've designed a mechanical autocorrelator.

The device is made of two plastic disks which rotate on a common axis. Each disk has magnets equally spaced along its rim. A ratchet and pawl mechanism contrains the magnets to hold positions in which they line up facing each other when the disks are rotated. When rotated, the disks attract each other in all positions (autocorrelation minima) except one --- in that position (autocorrelation maximum), they repel very strongly.

The figure shows a mechanical autocorrelator based on the binary PN sequence of our examples of length 15.

Let's demonstrate the connection between the autocorrelation formula just proved and our analog computer.

Theorem. When similar magnets line up, the disks repel with a force of magnet pairs, corresponding to the autocorrelation peak at j=0. In all other positions, the disks attract with the force of 1 magnet pair, corresponding to the autocorrelation minima of -1.

Proof. We set up a direct correspondence between the equations and the mechanism. As Sherlock Holmes would say, "The parallel is exact".

References

• M. R. Schoeder, NUMBER THEORY IN SCIENCE AND COMMUNICATION, 2^nd enlarged edition, Springer-Verlag, 1986.

Copyright © 1986-2008 by Sean Erik O'Connor. All Rights Reserved.     last updated 23 Feb 08.