Allan variance

thumb|right|upright=1.25|A clock is most easily tested by comparing it with a far more accurate reference clock. During an interval of time τ, as measured by the reference clock, the clock under test advances by τy, where y is the average (relative) clock frequency over that interval. If we measure two consecutive intervals as shown, we can get a value of —a smaller value indicates a more stable and precise clock. If we repeat this procedure many times, the average value of is equal to twice the Allan variance (or Allan deviation squared) for observation time τ.

The Allan variance (AVAR), also known as two-sample variance, is a measure of frequency stability in clocks, oscillators and amplifiers. It is named after David W. Allan and expressed mathematically as <math>\sigma_y^2(\tau)</math>.

The Allan deviation (ADEV), also known as sigma-tau, is the square root of the Allan variance, <math>\sigma_y(\tau)</math>.

The M-sample variance is a measure of frequency stability using M samples, time T between measurements and observation time <math>\tau</math>. M-sample variance is expressed as

:<math>\sigma_y^2(M, T, \tau).</math>

The Allan variance is intended to estimate stability due to noise processes and not that of systematic errors or imperfections such as frequency drift or temperature effects. The Allan variance and Allan deviation describe frequency stability. See also the section Interpretation of value below.

There are also different adaptations or alterations of Allan variance, notably the modified Allan variance MAVAR or MVAR, the total variance, and the Hadamard variance. There also exist time-stability variants such as time deviation (TDEV) or time variance (TVAR). Allan variance and its variants have proven useful outside the scope of timekeeping and are a set of improved statistical tools to use whenever the noise processes are not unconditionally stable, thus a derivative exists.

The general M-sample variance remains important, since it allows dead time in measurements, and bias functions allow conversion into Allan variance values. Nevertheless, for most applications the special case of 2-sample, or "Allan variance" with <math>T = \tau</math> is of greatest interest.

thumb|right|upright=1.25|Example plot of the Allan deviation of a clock. At very short observation time τ, the Allan deviation is high due to noise. At longer τ, it decreases because the noise averages out. At still longer τ, the Allan deviation starts increasing again, suggesting that the clock frequency is gradually drifting due to temperature changes, aging of components, or other such factors. The error bars increase with τ simply because it is time-consuming to get a lot of data points for large τ.

[[File:5 regimes of Allan variance as a function of averaging time.png|thumb|upright=1.25|Diagram of Allan deviation as a function of averaging time, showing the 5 typical regimes.

1. white/flicker phase-modulation noise (PM): At the highest frequency, phase noise dominates. This corresponds to <math>\sigma(\tau) \propto \tau^{-1}</math>. However, White PM has <math>S[f] = f^3</math> but Flicker PM has <math>S[f] = f^2</math>. The Allan variance plot does not distinguish them. It requires modified Allan variance plot to distinguish them.

2. White frequency-modulation noise (FM): at a lower frequency, white noise in frequency dominates. This corresponds to <math>\sigma(\tau) \propto \tau^{-1/2}, S[f] = f^0</math>

3. Flicker FM: <math>\sigma(\tau) \propto \tau^0, S[f] \propto f^{-1}</math>. This is also called "pink noise".

4. Random Walk FM: <math>\sigma(\tau) \propto \tau^{+1/2}, S[f] \propto f^{-2}</math>. This is also called "brown noise" or "brownian noise". In this regime, the frequency of the system executes a random walk. In other words, <math>df/dt</math> becomes a white noise.

5. Frequency drift: <math>\sigma(\tau) \propto \tau^{+1}, S[f] \propto f^{-3}</math>. In this regime, the frequency of the system executes a pink noise walk. In other words, <math>df/dt</math> becomes a pink noise.]]

Background

When investigating the stability of crystal oscillators and atomic clocks, it was found that they did not have a phase noise consisting only of white noise, but also of flicker frequency noise. These noise forms become a challenge for traditional statistical tools such as standard deviation, as the estimator will not converge. The noise is thus said to be divergent. Early efforts in analyzing the stability included both theoretical analysis and practical measurements.

An important side consequence of having these types of noise was that, since the various methods of measurements did not agree with each other, the key aspect of repeatability of a measurement could not be achieved. This limits the possibility to compare sources and make meaningful specifications to require from suppliers. Essentially all forms of scientific and commercial uses were then limited to dedicated measurements, which hopefully would capture the need for that application.

To address these problems, David Allan introduced the M-sample variance and (indirectly) the two-sample variance. While the two-sample variance did not completely allow all types of noise to be distinguished, it provided a means to meaningfully separate many noise-forms for time-series of phase or frequency measurements between two or more oscillators. Allan provided a method to convert between any M-sample variance to any N-sample variance via the common 2-sample variance, thus making all M-sample variances comparable. The conversion mechanism also proved that M-sample variance does not converge for large M, thus making them less useful. IEEE later identified the 2-sample variance as the preferred measure.

An early concern was related to time- and frequency-measurement instruments that had a dead time between measurements. Such a series of measurements did not form a continuous observation of the signal and thus introduced a systematic bias into the measurement. Great care was spent in estimating these biases. The introduction of zero-dead-time counters removed the need, but the bias-analysis tools have proved useful.

Another early aspect of concern was related to how the bandwidth of the measurement instrument would influence the measurement, such that it needed to be noted. It was later found that by algorithmically changing the observation <math>\tau</math>, only low <math>\tau</math> values would be affected, while higher values would be unaffected. The change of <math>\tau</math> is done by letting it be an integer multiple <math>n</math> of the measurement timebase <math>\tau_0</math>:

:<math>\tau = n \tau_0.</math>

The physics of crystal oscillators were analyzed by D. B. Leeson,

Interpretation of value

Allan variance is defined as one half of the time average of the squares of the differences between successive readings of the frequency deviation sampled over the sampling period. The Allan variance depends on the time period used between samples, therefore, it is a function of the sample period, commonly denoted as τ, likewise the distribution being measured, and is displayed as a graph rather than a single number. A low Allan variance is a characteristic of a clock with good stability over the measured period.

Allan deviation is widely used for plots (conventionally in log–log format) and presentation of numbers. It is preferred, as it gives the relative amplitude stability, allowing ease of comparison with other sources of errors.

An Allan deviation of 1.3 at observation time 1 s (i.e. τ = 1 s) should be interpreted as there being an instability in frequency between two observations 1 second apart with a relative root mean square (RMS) value of 1.3. For a 10 MHz clock, this would be equivalent to 13 mHz RMS movement. If the phase stability of an oscillator is needed, then the time deviation variants should be consulted and used.

One may convert the Allan variance and other time-domain variances into frequency-domain measures of time (phase) and frequency stability.

Formulations

M-sample variance

Given a time-series <math>x(t)</math>, for any positive real numbers <math>T, \tau</math>, define the real number sequence<math display="block">\bar y_i = \frac{x(iT + \tau) - x(iT)}{\tau} \quad i = 0, 1, 2, ...</math>Then the <math>M</math>-sample variance is defined provided an improved tool, as measurements were overlapped in n overlapped series out of the original series. The overlapping Allan variance estimator was introduced by Howe, Allan and Barnes. and ETSI standards for comparable measurements such as needed for telecommunication qualification.

Modified Allan variance

In order to address the inability to separate white phase modulation from flicker phase modulation using traditional Allan variance estimators, an algorithmic filtering reduces the bandwidth by n. This filtering provides a modification to the definition and estimators and it now identifies as a separate class of variance called modified Allan variance. The modified Allan variance measure is a frequency stability measure, just as is the Allan variance.

Time stability estimators

A time stability (σx) statistical measure, which is often called the time deviation (TDEV), can be calculated from the modified Allan deviation (MDEV). The TDEV is based on the MDEV instead of the original Allan deviation, because the MDEV can discriminate between white and flicker phase modulation (PM). The following is the time variance estimation based on the modified Allan variance:

:<math>\sigma_x^2(\tau) = \frac{\tau^2}{3}\bmod\sigma_y^2(\tau),</math>

and similarly for modified Allan deviation to time deviation:

:<math>\sigma_x(\tau) = \frac{\tau}{\sqrt{3\bmod\sigma_y(\tau).</math>

The TDEV is normalized so that it is equal to the classical deviation for white PM for time constant τ = τ0. To understand the normalization scale factor between the statistical measures, the following is the relevant statistical rule: For independent random variables X and Y, the variance (σz2) of a sum or difference (z = x − y) is the sum square of their variances (σz2 = σx2 + σy2). The variance of the sum or difference (y = x2τ − xτ) of two independent samples of a random variable is twice the variance of the random variable (σy2 = 2σx2). The MDEV is the second difference of independent phase measurements (x) that have a variance (σx2). Since the calculation is the double difference, which requires three independent phase measurements (x2τ − 2xτ + x), the modified Allan variance (MVAR) is three times the variances of the phase measurements.

Other estimators

Further developments have produced improved estimation methods for the same stability measure, the variance/deviation of frequency, but these are known by separate names such as the Hadamard variance, modified Hadamard variance, the total variance, modified total variance and the Theo variance. These distinguish themselves in better use of statistics for improved confidence bounds or ability to handle linear frequency drift.

Confidence intervals and equivalent degrees of freedom

Statistical estimators will calculate an estimated value on the sample series used. The estimates may deviate from the true value and the range of values which for some probability will contain the true value is referred to as the confidence interval. The confidence interval depends on the number of observations in the sample series, the dominant noise type, and the estimator being used. The width is also dependent on the statistical certainty for which the confidence interval values forms a bounded range, thus the statistical certainty that the true value is within that range of values. For variable-τ estimators, the τ0 multiple n is also a variable.

Confidence interval

The confidence interval can be established using chi-squared distribution with df degrees of freedom by using the distribution of the sample variance:

:<math>\chi^2 = \frac{\text{df}\,s^2}{\sigma^2},</math>

where s2 is the sample variance of our estimate, σ2 is the true variance value, df is the degrees of freedom for the estimator, and χ2 is calculated based on the inverse cumulative density distribution of a χ2 with df degrees of freedom. For a 90% probability, covering the range from the 5% to the 95% range on the probability curve, the upper and lower limits can be found using the inequality

:<math>\chi^2(0.05) \le \frac{\text{df}\,s^2}{\sigma^2} \le \chi^2(0.95),</math>

which after rearrangement for the true variance becomes

:<math>\frac{\text{df}\,s^2}{\chi^2(0.95)} \le \sigma^2 \le \frac{\text{df}\,s^2}{\chi^2(0.05)}.</math>

Effective degrees of freedom

The degrees of freedom represents the number of free variables capable of contributing to the estimate. Depending on the estimator and noise type, the effective degrees of freedom varies. Estimator formulas depending on N (number of total sample points) and n (integer multiple of τ0) has been found empirically: and in modern forms.

The Allan variance is unable to distinguish between WPM and FPM, but is able to resolve the other power-law noise types. In order to distinguish WPM and FPM, the modified Allan variance needs to be employed.

The above formulas assume that

:<math>\tau \gg \frac{1}{2\pi f_H},</math>

and thus that the bandwidth of the observation time is much lower than the instruments bandwidth. When this condition is not met, all noise forms depend on the instrument's bandwidth.

α–μ mapping

The detailed mapping of a phase modulation of the form

:<math>S_x(f) = \frac{1}{4\pi^2} h_\alpha f^{\alpha - 2} = \frac{1}{4\pi^2} h_\alpha f^\beta,</math>

where

:<math>\beta \equiv \alpha - 2,</math>

or frequency modulation of the form

:<math>S_y(f) = h_\alpha f^\alpha</math>

into the Allan variance of the form

:<math>\sigma_y^2(\tau) = K_\alpha h_\alpha \tau^\mu</math>

can be significantly simplified by providing a mapping between α and μ. A mapping between α and Kα is also presented for convenience: and allows conversion between different M and T values.

These bias functions are not sufficient for handling the bias resulting from concatenating M samples to the Mτ0 observation time over the MT0 with the dead-time distributed among the M measurement blocks rather than at the end of the measurement. This rendered the need for the B3 bias. as

:<math>B_3(N, M, r, \mu) = \frac{\left\langle\sigma_y^2(N, M, T, \tau)\right\rangle}{\left\langle\sigma_y^2(N, T, \tau)\right\rangle},</math>

where

:<math>T = M T_0,</math>

:<math>\tau = M \tau_0.</math>

The B3 bias function is useful to adjust non-overlapping and overlapping variable τ estimator values based on dead-time measurements of observation time τ0 and time between observations T0 to normal dead-time estimates.

The bias function becomes after analysis (for the N = 2 case)

: <math>B_3(2, M, r, \mu) = \frac{2M + MF(Mr) - \sum_{n=1}^{M-1} (M - n) \left[ 2F(nr) - F\big((M + n)r\big) + F\big((M - n)r\big) \right]}{M^{\mu+2} [F(r) + 2]},</math>

where

: <math>F(A) = 2A^{\mu+2} - (A + 1)^{\mu+2} - |A - 1|^{\mu+2}.</math>

τ bias function

While formally not formulated, it has been indirectly inferred as a consequence of the α–μ mapping. When comparing two Allan variance measure for different τ, assuming same dominant noise in the form of same μ coefficient, a bias can be defined as

:<math>B_\tau(\tau_1, \tau_2, \mu) = \frac{\left\langle\sigma_y^2(2, \tau_2, \tau_2)\right\rangle}{\left\langle\sigma_y^2(2, \tau_1, \tau_1) \right\rangle}.</math>

The bias function becomes after analysis

:<math>B_\tau(\tau_1, \tau_2, \mu) = \left( \frac{\tau_2}{\tau_1} \right)^\mu.</math>

Conversion between values

In order to convert from one set of measurements to another the B1, B2 and τ bias functions can be assembled. First the B1 function converts the (N1, T1, τ1) value into (2, T1, τ1), from which the B2 function converts into a (2, τ1, τ1) value, thus the Allan variance at τ1. The Allan variance measure can be converted using the τ bias function from τ1 to τ2, from which then the (2, T2, τ2) using B2 and then finally using B1 into the (N2, T2, τ2) variance. The complete conversion becomes

:<math>\left\langle \sigma_y^2(N_2, T_2, \tau_2) \right\rangle = \left( \frac{\tau_2}{\tau_1} \right)^\mu \left[ \frac{B_1(N_2, r_2, \mu) B_2(r_2, \mu)}{B_1(N_1, r_1, \mu) B_2(r_1, \mu)} \right] \left\langle \sigma_y^2(N_1, T_1, \tau_1) \right\rangle,</math>

where

:<math>r_1 = \frac{T_1}{r_1},</math>

:<math>r_2 = \frac{T_2}{r_2}.</math>

Similarly, for concatenated measurements using M sections, the logical extension becomes

:<math>\left\langle \sigma_y^2(N_2, M_2, T_2, \tau_2) \right\rangle = \left( \frac{\tau_2}{\tau_1} \right)^\mu \left[ \frac{B_3(N_2, M_2, r_2, \mu) B_1(N_2, r_2, \mu) B_2(r_2, \mu)}{B_3(N_1, M_1, r_1, \mu) B_1(N_1, r_1, \mu) B_2(r_1, \mu)} \right] \left\langle \sigma_y^2(N_1, M_1, T_1, \tau_1) \right\rangle.</math>

Measurement issues

When making measurements to calculate Allan variance or Allan deviation, a number of issues may cause the measurements to degenerate. Covered here are the effects specific to Allan variance, where results would be biased.

Measurement bandwidth limits

A measurement system is expected to have a bandwidth at or below that of the Nyquist rate, as described within the Shannon–Hartley theorem. As can be seen in the power-law noise formulas, the white and flicker noise modulations both depend on the upper corner frequency <math>f_H</math> (these systems are assumed to be low-pass filtered only). Considering the frequency filter property, it can be clearly seen that low-frequency noise has greater impact on the result. For relatively flat phase-modulation noise types (e.g. WPM and FPM), the filtering has relevance, whereas for noise types with greater slope the upper frequency limit becomes of less importance, assuming that the measurement system bandwidth is wide relative the <math>\tau</math> as given by

:<math>\tau \gg \frac{1}{2\pi f_H}.</math>

When this assumption is not met, the effective bandwidth <math>f_H</math> needs to be notated alongside the measurement. The interested should consult NBS TN394. for the TDEV measurement.

It can be recommended that the first <math>\tau_0</math> multiples be ignored, such that the majority of the detected noise is well within the passband of the measurement systems bandwidth.

Further developments on the Allan variance was performed to let the hardware bandwidth be reduced by software means. This development of a software bandwidth allowed addressing the remaining noise, and the method is now referred to modified Allan variance. This bandwidth reduction technique should not be confused with the enhanced variant of modified Allan variance, which also changes a smoothing filter bandwidth.

Dead time in measurements

Many measurement instruments of time and frequency have the stages of arming time, time-base time, processing time and may then re-trigger the arming. The arming time is from the time the arming is triggered to when the start event occurs on the start channel. The time-base then ensures that minimal amount of time goes prior to accepting an event on the stop channel as the stop event. The number of events and time elapsed between the start event and stop event is recorded and presented during the processing time. When the processing occurs (also known as the dwell time), the instrument is usually unable to do another measurement. After the processing has occurred, an instrument in continuous mode triggers the arm circuit again. The time between the stop event and the following start event becomes dead time, during which the signal is not being observed. Such dead time introduces systematic measurement biases, which needs to be compensated for in order to get proper results. For such measurement systems will the time T denote the time between the adjacent start events (and thus measurements), while <math>\tau</math> denote the time-base length, i.e. the nominal length between the start and stop event of any measurement.

Dead-time effects on measurements have such an impact on the produced result that much study of the field have been done in order to quantify its properties properly. The introduction of zero-dead-time counters removed the need for this analysis. A zero-dead-time counter has the property that the stop event of one measurement is also being used as the start event of the following event. Such counters create a series of event and time timestamp pairs, one for each channel spaced by the time-base. Such measurements have also proved useful in order forms of time-series analysis.

Measurements being performed with dead time can be corrected using the bias function B1, B2 and B3. Thus, dead time as such is not prohibiting the access to the Allan variance, but it makes it more problematic. The dead time must be known, such that the time between samples T can be established.

Measurement length and effective use of samples

Studying the effect on the confidence intervals that the length N of the sample series have and the effect of the variable τ parameter n, the confidence intervals may become very large since the effective degree of freedom may become small for some combination of N and n for the dominant noise form (for that τ).

The effect may be that the estimated value may be much smaller or much greater than the real value, which may lead to false conclusions of the result.

It is recommended that:

The confidence interval be plotted along with the data, such that the reader of the plot knows of the statistical uncertainty of the values.
The length of the sample sequence (i.e. the number of samples N) must be kept as high as possible to ensure that confidence interval is small over the τ range of interest.
Estimators providing better degrees of freedom values be used in replacement of the Allan variance estimators or as complementing them where they outperform the Allan variance estimators. Among those the total variance and Theo variance estimators should be considered.
The τ range as swept by the τ0 multiplier n is limited in the upper end relative N, such that the reader of the plot may not be confused by highly unstable estimator values.

Dominant noise type

A large number of conversion constants, bias corrections and confidence intervals depends on the dominant noise type. For proper interpretation shall the dominant noise type for the particular τ of interest be identified through noise identification. Failing to identify the dominant noise type will produce biased values. Some of these biases may be of several order of magnitude, so it may be of large significance.

Linear drift

Systematic effects on the signal is only partly cancelled. Phase and frequency offset is cancelled, but linear drift or other high-degree forms of polynomial phase curves will not be cancelled and thus form a measurement limitation. Curve fitting and removal of systematic offset could be employed. Often removal of linear drift can be sufficient. Use of linear-drift estimators such as the Hadamard variance could also be employed. A linear drift removal could be employed using a moment-based estimator.

Measurement instrument estimator bias

Traditional instruments provided only the measurement of single events or event pairs. The introduction of the improved statistical tool of overlapping measurements by J. J. Snyder but for longer τ the effect is gradually removed, and the lower-τ region of the measurement has biased values. This bias is providing lower values than it should, so it is an overoptimistic (assuming that low numbers is what one wishes) bias, reducing the usability of the measurement rather than improving it. Such smart algorithms can usually be disabled or otherwise circumvented by using time-stamp mode, which is much preferred if available.

Practical measurements

While several approaches to measurement of Allan variance can be devised, a simple example may illustrate how measurements can be performed.

Measurement

All measurements of Allan variance will in effect be the comparison of two different clocks. Consider a reference clock and a device under test (DUT), and both having a common nominal frequency of 10 MHz. A time-interval counter is being used to measure the time between the rising edge of the reference (channel A) and the rising edge of the device under test.

In order to provide evenly spaced measurements, the reference clock will be divided down to form the measurement rate, triggering the time-interval counter (ARM input). This rate can be 1 Hz (using the 1 PPS output of a reference clock), but other rates like 10 Hz and 100 Hz can also be used. The speed of which the time-interval counter can complete the measurement, output the result and prepare itself for the next arm will limit the trigger frequency.

A computer is then useful to record the series of time differences being observed.

Post-processing

The recorded time-series require post-processing to unwrap the wrapped phase, such that a continuous phase error is being provided. If necessary, logging and measurement mistakes should also be fixed. Drift estimation and drift removal should be performed, the drift mechanism needs to be identified and understood for the sources. Drift limitations in measurements can be severe, so letting the oscillators become stabilized, by long enough time being powered on, is necessary.

The Allan variance can then be calculated using the estimators given, and for practical purposes the overlapping estimator should be used due to its superior use of data over the non-overlapping estimator. Other estimators such as total or Theo variance estimators could also be used if bias corrections is applied such that they provide Allan variance-compatible results.

To form the classical plots, the Allan deviation (square root of Allan variance) is plotted in log–log format against the observation interval τ.

Equipment and software

The time-interval counter is typically an off-the-shelf counter commercially available. Limiting factors involve single-shot resolution, trigger jitter, speed of measurements and stability of reference clock. The computer collection and post-processing can be done using existing commercial or public-domain software. Highly advanced solutions exists, which will provide measurement and computation in one box.

Research history

The field of frequency stability has been studied for a long time. However, during the 1960s it was found that coherent definitions were lacking. A NASA-IEEE Symposium on Short-Term Stability in November 1964 resulted in the special February 1966 issue of the IEEE Proceedings on Frequency Stability.

The NASA-IEEE Symposium brought together many fields and uses of short- and long-term stability, with papers from many different contributors. The articles and panel discussions concur on the existence of the frequency flicker noise and the wish to achieve a common definition for both short-term and long-term stability.

Important papers, including those of David Allan, L. S. Cutler and C. L. Searle from 1974, which in chapter 8 has "Statistics of Time and Frequency Data Analysis". This is the extended variant of NBS Technical Note 394 and adds essentially in measurement techniques and practical processing of values.

An important addition will be the Properties of signal sources and measurement methods.

50th anniversary

In 2016, IEEE-UFFC is going to be publishing a "Special Issue to celebrate the 50th anniversary of the Allan Variance (1966–2016)". A guest editor for that issue will be David's former colleague at NIST, Judah Levine, who is the most recent recipient of the I. I. Rabi Award.

References

External links

UFFC Frequency Control Teaching Resources
NIST Publication search tool
David W. Allan's Allan Variance Overview
David W. Allan's official web site
JPL Publications – Noise Analysis and Statistics
William Riley publications
Stable32 , Software for Frequency Stability Analysis, by William Riley
Stefano Bregni publications
Enrico Rubiola publications
Allanvar: R package for sensor error characterization using the Allan Variance
Alavar windows software with reporting tools; Freeware
AllanTools open-source python library for Allan variance
MATLAB AVAR open-source MATLAB application