Saturday, October 17, 2009

My Favorite Invention

(UPDATE: I've added some photos to the end of this blog.)

My favorite invention is my Phase Meter (U.S. Patent 6,441,601), for a number of reasons:
  • It began as a simple insight, which led to further discoveries, and then to more complex implementation.

  • Its performance seems almost magical to me.

  • About a half dozen of these phase meters are being put into all new GPS satellites, where they will improve GPS accuracy, especially for military guided weapons.

  • It exemplifies how designs grow top-down rather than bottom-up.
Also, a number of friends and relatives have asked me to explain at least one of my inventions. With the help of some video demonstrations, I will explain the basic concepts of this invention in simple terms and how it gradually leads to more complex details (but I won't get into the details). The reader will get an understanding of how basic concepts are developed into working designs.

The Phase Meter compares the timing of two very different clocks with a surprising degree of accuracy. In a GPS satellite, accurate clock timing is necessary for accurate measurement of global positions, that is, for accurate navigation. The Phase Meter is accurate to within five picoseconds. (How small is that? Well, if you had a rocket that could go from New Jersey to California in one second, it would go only a hair's breadth in five picoseconds.)

Some Clock Basics

Basically, a clock is a device for counting oscillations. For example, a pendulum clock keeps track of the passage of time by using gears to count the swings of a pendulum. Traditionally, we divide each day into 24 hours, each hour into 60 minutes, and each minute into 60 seconds. So we adjust the length of the pendulum as best we can so that each swing to the left and right takes exactly one second; then we count 60 swings for each minute, and 60 minutes for each hour, etc.

The more precise digital watch uses digital counters to count the oscillations (vibrations) of a quartz crystal. (Instead of tick, tock, tick, tock, etc., digital oscilators create a 1010.. repeating sequence.) The rate of oscillation can be set by the cut of the crystal (and other factors), and good performance is obtained at about ten million oscillations per second (10 megahertz). So the crystal oscillator is typically set to 10 megahertz as accurately as possible, and ten million oscillations are counted to measure one second before counting off minutes and hours.

The most precise clocks now are atomic clocks, so called because they are based on the oscillation of atoms, typically rubidium or cesium atoms. However, the oscillation rate cannot be set to some convenient figure such as 10 megahertz. Instead, the rate is set by the laws of nature. For example, the oscillation rate of the cesium atoms in an atomic clock is 9,192,631,770 oscillations per second. The figure for a rubidium atomic clock is also an 'odd-ball' number.

The GPS Clock Situation

In each GPS satellite, a crystal oscillator with 10,230,000 oscillations per second is used to control the timing of the signals sent to GPS receivers. The timing accuracy of these signals determines the accuracy of all GSP navigation. The 10,230,000 rate is a convenient number for generating the signals, but the crystal oscillator isn't nearly as accurate as the atomic clocks on each GPS satellite. So the crystal oscillator clock needs to be compared to the atomic clock and then adjusted to make it just as accurate as the atomic clock.

But comparing these clocks with very different rates is tricky -- it's like comparing a poorly made yard stick, with inch markings, with a more accurate meter stick with centimeter markings.

Here is a video showing two rulers representing two clock signals. One ruler is represented by alternating blue and green line segments of equal length, equivalent to the 101010.. sequence of one of the GPS clocks. The other is represented by marks at equal intervals on a red line, each mark equivalent to a moment when the other GPS clock changes from 1 to 0. As you play the video, notice how the marks on the red ruler sometimes align with a blue section on the other ruler, and sometimes a green section. Suppose we colored the marks to match the color opposite it on the other ruler. Then we would get a sequence of blue and green marks in a seemingly random sequence. In a similar manner, whenever one GPS clock changes from 1 to 0, the state of the other clock is sampled, generating a seemingly random sequence of ones and zeros.



Observations Leading to the Invention

Sometimes a mark on the red ruler comes very close to a blue-green boundary, so that a small shift of one ruler relative to the other will change the color sequence. Likewise, a small shift of the timing of one GPS clock relative to the other changes the seemingly random sequence of ones and zeros (the 'sample' sequence). Because the sample sequence is sensitive to timing shifts, I tried to discover some way to decipher the sample sequence to measure the timing shift. The next videos illustrate the method that I discovered.

Suppose the blue/green ruler were wrapped around a circle with a diameter such that the blue segments always fall on one half of the circle and the green segments always fall on the other half of the circle. Suppose that the red ruler is also wound around the same circle. (Imagine that the rulers are so thin that they don't stack up on the circle, not making the path around the circle progressively longer.) Actually, we don't need to wrap the blue/green ruler around the circle; we can just mark the two halves of the circle blue and green to indicate where the blue/green ruler lands on the circle. When we wind the red ruler around the circle, we can see where the marks land on either the blue or green half.

In the video, the halves of the circle are marked as blue and green; and as the circle 'wheel' turns, winding on the ruler, the marks are moved slightly inside the circle when they land on the blue half, and are moved slightly outside the circle when they land on the green half. When you play this next video, notice that even though the marks are fairly far apart on the ruler, they become spread around the circle and eventually become closely spaced. It is this close spacing that allows more precise measurement than expected, because it is normally expected that the precision is the same as the ruler spacing.



So how can we calculate the offset alignment of the rulers from the positions of the green and red (one and zero) samples? Here is an analogous example that may suggest a method:

Suppose the famous "Old Faithful" geyser in Yellowstone Park in Wyoming erupts every one hour and 13 minutes exactly. (Actually, that's close to the average interval, but it varies, usually between 65 and 92 minutes, and sometimes about 45 or 125 minutes.) Now, suppose that the first eruption on some day is 41 minutes after midnight, and some one records a list of all the eruption times starting on that day and for one week, using a digital watch. They give us a copy of the list that doesn't include any of the numbers, but only the am/pm indicators, and ask us to figure out the time of the first eruption.

It's really simple to find the answer. We assume that the first eruption is at midnight, and advancing around a 24-hour circle at intervals of one hour and 13 minutes, we mark these locations on the circle "am" or "pm" according to the list. Unknowingly, we have started our list 41 minutes early, but when we look at our circle and see that the "am" marks begin at 11:19pm instead of midnight (12am on digital watches and clocks), it becomes obvious that our list started 41 minutes early, so we conclude (correctly) that the first eruption must have been at 12:41am.

How the Phase Meter Works

The phase meter uses a similar method. Starting at a "zero" position on the circle, positions are computed that are associated with "one" and "zero" samples (analogous to the "am" and "pm" marks). An early version of the invention used a list of these samples, which would become more costly with more samples. A later improvement reduced this cost by eliminating the list, making it practical for millions of samples to be processed.

In this later version, the circle is divided into three equal parts, and the number of "one" samples falling in each third of the circle are counted, using three counters. We figured out how to estimate the angle of the line that best divides the region of the 'one' samples from the region of the "zero" samples from these three counts. (This is a little tricky, but we will skip these details.)

In the next video, you can see these three counts increasing as the samples arrive on the circle, and you can see the estimated angle (computed from these counts) becoming more accurate as the counts increase. The marks outside the circle represent "one" samples, which are counted, and the marks inside the circle represent "zero" samples, which are not counted. The thirds of the circle are divided by black lines, and the estimated angle is indicated by a magenta line.



You can see that the result is not perfect, but in this demonstration, we have only 50 samples. A phase meter in a GPS satellite can process about 30 million samples every 1.5 seconds, and the error is about one ten-thousandth of the circle.

Conclusion

When all the details are worked out, we get something fairly complex, even though the initial concepts were relatively simple. The following is a "block diagram" of the final design; there are more details inside each rectangular block:


The yellow area and the blue area below it do most of the operations illustrated by the last video above, exept that the computation of the estimated angle is done by a computer elsewhere. The areas above allow a computer to set up the measurement parameters, and the areas on the left control the measurement timing. (Click on the diagram for a larger view.)

Designs like this are not developed one detail at a time, but rather one idea at a time. The big idea leads to middle-sized ideas, ... and finally to lots of details. That is the essence of what is called "top-down design".

============================================

I recently found some photos from the time that the phase meter prototype was tested. Here is a photo of the phase meter prototype 'test bed'. Most of the circuit board is a microprocessor with its support circuits (because part of the phase meter function is software). The phase meter hardware is the small black integrated circuit in the white square at the upper-left corner of the gridded area at the near end of the board.


The next photo shows the test team gathered around the test bed, with related instrumentation in the background. In the foreground is John Petzinger, co-inventor for the second phase meter patent, who worked with me in Clifton, NJ. I don't recall the names of the other two, but one is a software engineer from San Diego, CA, and the other a hardware engineer from Ft. Wayne, IN. We worked together by email and occasional phone call for months, before meeting for the first time in Clifton for the test.


Finally, I found this graph showing the results of one of the tests. Two stable clock signals with different frequencies were compared by the phase meter prototype at 1.5-second intervals ('epochs') for five minutes, and the variation of the measurements were recorded here. Assuming that neither clock signal was jittery, we assumed that all the variation was due to phase meter errors. Sometimes the error was plus or minus two picoseconds, but the average (rms) was 1 psec -- that is 0.000,000,000,001 second.