Inspiration for "Allan Variance"
David Allan gives the background to the history of how he came up with the Allan
Variance, a clock algorithm in the generation of international time.
by David W. Allan
June 27, 2012
In 1964 a special meeting was assembled by the IEEE and by NASA because of the confusion regarding how to characterize and properly use precision frequency standards and clocks. The meeting was held at the Goddard Space Flight Center in Greenbelt, Maryland. Jim Barnes and I prepared and gave a paper at that conference, which was well received proposing time averages of finite differences of the phase or the time-residual readings as a reasonable measure. Specifically, we showed how the second-difference and third-difference phase residuals were well behaved even in the presence of non-stationary noise processes like flicker-noise. Classical statistics techniques do not adequately describe the random variations one uses as models for the observed deviations in precision clocks and oscillators.
Using the results from the paper we presented at this special conference, Jim went on in 1965 to write his PhD thesis and to develop the NBS time-scale for providing an official time and frequency reference for the USA. During the same time, I was working on my Master's thesis, also using the results from our previous paper. The thesis was entitled,
The Statistics of Atomic Frequency Standards.
The problem I was dealing with was a very challenging one because the models we had shown were reasonable for the instabilities in clocks and oscillators covered a variety of noise processes, and the classical variance was mathematically non-convergent for some of these processes; and hence, it was not useful. I was throwing in the face of the classical statisticians that they did not have an answer for us in characterizing the instabilities in clocks and oscillators.
My thesis looked at the effects on the classical variance as a function of how long the frequency was averaged (the averaging time, τ), how many samples were included in the variance, N, how much dead-time there was between frequency averages, T-τ (in those days it took time for a frequency counter to reset after a frequency had been measured over some interval τ; so T was the time between the beginning of one measurement to the next), and how it depended on the measurement system bandwidth,
fh. We developed a set of spectral density, power-law noise models that covered the characterization of the different kinds of instabilities we were observing (as perceived) – resulting from the noise of the measurement system, the clocks, and from environmental influences.
Jim had shown me a book by Lighthill on Generalized Functions… that had a table on page 43, which I still remember, I used it so much, that would help us transform these mathematically non-stationary noise models that seemed to be appropriate from the frequency-domain to the time-domain and vice versa. I spent long hours and remember staying at the lab all one night trying to sort out and work through all these parameters and Fourier transforms needed to develop what we called a "time-domain" instability characterization of the clocks being measured.
At this same time a major change in our plans was taking place orchestrated by the Lord. A call was extended to me to serve in the Boulder Ward bishopric in our church, which would be very demanding of my time and change our plans toward getting a doctorate and moving back to Utah. I made it an intense mater of fasting (3 plus days) and prayer and received a profound answer, which changed my life forever. I am totally convinced that the insights needed and were given for the following work, would not have come had I rejected the call to serve. Once I learned this profound and important lesson that if we will do things the Lord's way, He will bless us greatly, I became the praying physicist and have been able to make seven other major contributions that have impacted the world community in my field of endeavor. I thank the Lord for His enormous and continual blessings in my life. We have been so blessed. Isaac Newton is one of my mentors. He is listed as second of the 100 "Most Influential Persons in History." Prof. Steven Jones in studying Newton's personal life has discovered that Isaac spent more time studying the Bible than he did science. I believe like Newton that as we seek the will of the Father to best serve His children, we will accomplish the greatest good and fulfill our missions in mortality. This will bring the greatest fulfillment and joy to us personally as well as be most pleasing to Him whom we are serving. As we best serve His children, we are best serving Him.
Joseph Smith's thoughts on this topic seem most poignant:
"THE SPIRIT OF REVELATION is in connection with these blessings. A
person may profit by noticing the first intimation of the spirit of
revelation; for instance, when you feel pure intelligence flowing into you, it
may give you sudden strokes of ideas, so that by noticing it, you may find it
fulfilled the same day or soon; (i. e.) those things that were presented unto
your minds by the Spirit of God, will come to pass; and thus by learning the
Spirit of God and understanding it, you may grow into the principle of
revelation, until you become perfect in Christ Jesus. [Joseph Smith, History
of The Church of Jesus Christ of Latter-day Saints, 7 vols., introduction
and notes by B. H. Roberts [Salt Lake City: The Church of Jesus Christ of
Latter-day Saints, 1932-1951], 3: 381.)]
I give credit to the Lord for the ideas that have come to me in striving to do His will with the goal that they may be a blessing to His children. Self aggrandizement needs be removed from our motivation and replaced by true humility (teachability) for the Spirit to best work with us.
Few people have something named after them while they are still alive; nor did I seek for this. No one at the time had any idea of how useful the "Allan variance" would become. It is not my variance, it is the Lord's revelation, and I thank Him for His continual guidance.
W. H. Murray profoundly stated:
Until one is committed There is hesitancy, the chance to draw back, Always ineffectiveness. Concerning all acts of initiative (and creation), There is one elementary truth, The ignorance of which kills countless ideas And splendid plans: That the moment one definitely commits oneself, Then Providence moves too. All sorts of things occur to help one That would never otherwise have occurred. A whole stream of events issues from the decision Raising in one's favor all manner Of unforeseen incidents and meetings And material assistance, Which no man could have dreamt Would have come his way. I have learned a deep respect for one of Goethe's couplets: "Whatever you can do, or dream you can, begin it. Boldness has genius, power, and magic in it."
In 1968, we had a very interesting clock comparison "shoot off" at NBS Boulder, as it were. Bob Vessot brought his hydrogen maser from Smithsonian Astronomical Observatory in Boston. Harry Peters brought his hydrogen maser from NASA Goddard, Beltsville, Maryland. Len Cutler brought his Hewlett Packard cesium-beam, atomic clock from Palo Alto, CA. We had the NBS primary frequency standard and data acquisition systems. And of course, we had the US Primary Frequency cesium-beam Standard at NBS. This resulted in a very important 12 author paper.
It was my responsibility at that time to provide the NBS reference time-scale for comparing all of these clocks. The Lord gave me an algorithm that is still being used to this day (27 June 2012) with several refinements by Tom Parker and Judah Levine and with help from Jim Barnes at the time. I had a PDP-8 computer that we had recently acquired for the time-scale. It had 5k of memory and was an 8-bit machine using punched paper tape as the read write input-output. The language was Fortran IV. I was able to accommodate eight atomic clocks. This time scale algorithm was a major application of the "Allan variance."
| It is a really fun algorithm providing time for the nation then -- replacing the one that Jim Barnes had written and has been used until now -- for 44 years:|
|Its software clock output is better than the best clock providing input;|
|Even the worst clock enhances the output;|
|If a clock misbehaves, it is rejected and not used – avoiding unnecessary perturbations;|
|Each clock gets an optimum weighting factor for including it in the time computation;|
|The weights are adaptive so that if a clock improves over time, its weight increases and vise-versa;|
|The optimum time of each clock as well as the optimum estimate of the frequency of each clock are estimated at each measurement cycle;|
|Both the short-term as well as the long-term stability of the software ensemble output are optimized;|
|It is able to deal with white-noise FM, flicker-noise FM, and random-walk FM, which are the kinds of noise processes that well model the atomic clocks being used;|
|With eight clocks in the ensemble, it used 94 lines of code and provided error messages.|
It is interesting looking back, at the same time the Kalman filter was being developed for the tracking system used in the Apollo program. At that time, I was invited to consult regarding the clocks needed for the Apollo program. Sam Stein showed years later that the above algorithm is like a Kalman filter. However, the Kalman filter approach becomes overly complicated in dealing with flicker-noise. Sam later wrote a time scale algorithm based on Kalman theory. Judah Levine compared them and they seemed comparable, so they stayed with the one I wrote as it had some simple elegance to it and it belonged to NBS, since I was their employee. I saw cases where three of the eight clocks would be rejected at a particular measurement cycle and the algorithm rejected them properly and made it through.
When I first wrote it, the hydrogen masers of Harry Peters and Bob Vessot would take over because of their outstanding short-term stability. Then I came to the realization that ever clock was looking at itself to some degree through its particular weighting factor. So, under the assumption of a normal distribution of errors, I designed a de-weighting technique that compensated for this effect. This worked well. This was fun because the algorithm would come up with an optimum estimate of the performance of each clock as if it was being observed by an almost perfect reference. When you compare two clocks, you can never know which one is better. In an optimally weighted ensemble, one can sort out the individual clock performance statistics.
As the GPS program was being developed during the '70s, the "Allan variance" was used extensively in characterizing the clocks needed for it, and after it was launched, for over a decade I was asked by the GPS program office to monitor and characterize the clocks on board the satellites to help optimize system performance.
Over the years, the applications for the "Allan variance" have broadened into several other disciplines; navigation and telecommunications, for example.
In March 2011 I was invited to attend the International Telecommunications Sync Forum (ITSF) in Edinburgh, Scotland to receive "The Time Lord" award. To me the award seemed sacrilegious, and I turned down their offer. They approached me again and I felt that perhaps it was my opportunity to tell them who the True-Time Lord is, and that if they would pay expenses for Edna and me we would come. They agreed to do that... Having never been to Scotland and having our expert tour guide and friend, Ken Brown, living right here in Fountain Green and being over there at that time and being willing to give us a tour after the conference, I thought, "this sounds perfect."
Edinburgh is a very significant historic city for Scotland. The Edinburgh castle is most impressive. Edinburgh is the birth place of Robert Burns, Alexander Graham Bell, and Robert Lewis Stevenson among others. Another is the famous poet Allan Ramsay, whose son of same name is a famous artist. This name struck us between the eyes, because my wife's name was Edna Love Ramsay before our marriage. We need to go back and do some genealogy research. They have an excellent archive library there as well.
Once I accepted, then they asked me to give the keynote address at the conference. So I had to prepare two talks. It was fun preparing them. Synchronizing clocks in telecommunications is a major problem, and I have been involved with their problems a lot over the years. When back in Boulder, the telecom community asked us to help them, and we developed a metric for measuring a telecommunication network’s performance called TVAR (Time Variance) – the square root of which is called TDEV. TDEV has been adopted internationally as a standard measurement metric in the telecom industry, and the ITSF conference grew out of this work.
In addition, the conference was very interesting. As a fascinating aside, the banking and financial world are synchronizing transactions at the 10 millionths of a second level. They say that decisions at that level of timing amount to $100,000 to them, and they want to push their accuracy down to one millionth of a second. We know how to help them do that inexpensively with some new technology the Lord has inspired us to develop. More about that later.
Page posted by Sterling
D. Allan June 27, 2012
Page last updated April 21, 2013
visits since June 27, 2012