Today (Wed., 3/30/11) I am taking notes and trying to figure out exactly how to *correctly* derive the expected Allan deviation given the quantization error and an oscillator model. I've decided I want to use a Gaussian white noise model for the inherent frequency fluctuations in the oscillator. (Other behavior should show up in the Allan deviations for larger window sizes.)
Key parameters are:
1. Standard deviation of oscillator frequency (when averaged over 1-s window sizes) in cycles per nominal second. (We can plot the result as a function of this, and use that to do a Bayesan back-calculation of the probabilities of different standard deviations given the raw deviation data. Actually, this dist would be sharply peaked, given the large amount of data available - so we can just do a direct reverse lookup of the standard deviation given the Allan deviation.)
2. Fractional part only of mean oscillator frequency, in [0,1] say, because the integer part is irrelevant to the quantization error.
And computational variables include:
3. The possible values of the quantized frequency deviation samples d1=x1-2x2+x3 for adjacent 1-second windows. These are small integers; a range [-10,+10] would be more than adequate. For this we scan through the range of possible values.
4. Given d1, always let x1=0, and then scan possible values of x2. These will always be integers in a range close to the integer part of mean oscillator frequency. For example, 10,000,012 +/- 10. Given d1 and x2, compute x3=d1+2*x2.
5. Phase error phi1 of first (x1) measurement in oscillator cycles, in the range [-1/2, 1/2]. This is uniformly distributed so we can just integrate over the range. The actual initial phase is Phi1=x1-phi1.
6. Actual frequencies F1=Phi2-Phi1 and F2=Phi3-Phi2 can then be integrated over the range of values that will yield the target values of x2 and x3. And, at each value, the probability density values can be looked up from the normal dist. Overall answer of the integrations over phi1, F2, and F3: A probability for the particular (d1,x2) configuration in question. Add these up for the possible x2s, and you get a probability for the given d1 value. Get the probs for all d1 values and you can compute the RMS value of that distribution, half of that is the sigma_y(1) Allan dev.
Assuming this is a good model, the sigma_y(1) Allan deviation value should tell us, quite accurately, what the most likely standard deviation of the 1s-window oscillator frequency F is. And similarly, looking at the y values should tell us the mean frequency (although we know this drifts over time).
I think my next step is to write a short C or Matlab or Mathematica program to actually do this calculation. Only advantage of Mathematica: Maybe we can use it to evaluate the integral analytically. If not, I can do it numerically.
Wednesday, March 30, 2011
Monday, March 28, 2011
Journal Quest
Main task today: Working on some write-up of my recent analysis for the journal paper.
Gordon came by and I showed him the recent stuff. We looked at how to determine the time uncertainty from the Allan deviation. That would be a good thing to include in the paper.
Met with Ray, we went over the status of everything in the COSMICi system (HW at least).
Emailed Brian Stearns (contact at DeLorme) to ask him if the 0.2 ppm frequency instability we are seeing could be attributable to the TCXO used in the kit, requested part # for datasheet lookup. Also told him about the (10/20/200/400) millisecond glitches.
I'm wondering now if it is really a good assumption for us to say that quantization errors of neighboring phase readings are independent. Suppose the real OCXO frequency is close to an integer; the the quantization errors will be almost totally correlated, and will vanish from the y values. Or, if the OCXO frequency is close to a half-integer, then the quantization errors will be offset from each other by 0.5, and will tend to add up constructively in the y value, but then will tend to cancel again in the d (deviation) determination.
I'm thinking I need to make a more detailed model of the quantization error. Some parameters:
a - quantization error for first (x1) phase measurement, in cycles, in range [-0.5, +0.5). (That is, actual phase at the time of the PPS edge was the measured value minus a.)
f1 - fractional part of actual average frequency (phase accum. btw. PPS edges) during 1st second, in range [0, 1).
b - can be derived from f1 and a
f2 - fractional part of actual average frequency (phase accum. btw. PPS edges) during 2nd second, in range [0, 1). This can be derived from f1 and a model of the "real" instability, as a normal distribution.
c - can be derived from f2 and b.
Then, y1 and y2 can be derived from this, their error (relative to f1 and f2) can be derived, and the d=y2-y1 can be derived, and the error between this and the real delta of f2-f1 can be derived.
We can sweep through values of f1 and a, and plot the distribution of deviation measurement, including the effect of quantization error, as a function of the "real" underlying deviation.
This is all well and good, but I think the argument for phase offsets being pretty well independent for larger window sizes is pretty strong, otherwise I think we'd see some variation in the adjusted Allan deviation measurements depending on the window size, which we don't see except for very small window sizes. Still, doing the above more detailed calculation would be a good sanity check on our earlier calculations.
Gordon came by and I showed him the recent stuff. We looked at how to determine the time uncertainty from the Allan deviation. That would be a good thing to include in the paper.
Met with Ray, we went over the status of everything in the COSMICi system (HW at least).
Emailed Brian Stearns (contact at DeLorme) to ask him if the 0.2 ppm frequency instability we are seeing could be attributable to the TCXO used in the kit, requested part # for datasheet lookup. Also told him about the (10/20/200/400) millisecond glitches.
I'm wondering now if it is really a good assumption for us to say that quantization errors of neighboring phase readings are independent. Suppose the real OCXO frequency is close to an integer; the the quantization errors will be almost totally correlated, and will vanish from the y values. Or, if the OCXO frequency is close to a half-integer, then the quantization errors will be offset from each other by 0.5, and will tend to add up constructively in the y value, but then will tend to cancel again in the d (deviation) determination.
I'm thinking I need to make a more detailed model of the quantization error. Some parameters:
a - quantization error for first (x1) phase measurement, in cycles, in range [-0.5, +0.5). (That is, actual phase at the time of the PPS edge was the measured value minus a.)
f1 - fractional part of actual average frequency (phase accum. btw. PPS edges) during 1st second, in range [0, 1).
b - can be derived from f1 and a
f2 - fractional part of actual average frequency (phase accum. btw. PPS edges) during 2nd second, in range [0, 1). This can be derived from f1 and a model of the "real" instability, as a normal distribution.
c - can be derived from f2 and b.
Then, y1 and y2 can be derived from this, their error (relative to f1 and f2) can be derived, and the d=y2-y1 can be derived, and the error between this and the real delta of f2-f1 can be derived.
We can sweep through values of f1 and a, and plot the distribution of deviation measurement, including the effect of quantization error, as a function of the "real" underlying deviation.
This is all well and good, but I think the argument for phase offsets being pretty well independent for larger window sizes is pretty strong, otherwise I think we'd see some variation in the adjusted Allan deviation measurements depending on the window size, which we don't see except for very small window sizes. Still, doing the above more detailed calculation would be a good sanity check on our earlier calculations.
Tying Loose Ends
The rest of last week was just spent wrapping up bits of the analysis from Monday. Getting ready to start writing. Oh, and the XMath PO finally got generated.
Wednesday, March 23, 2011
Mathematica FAIL
* Ray & I discussed strategy w.r.t. how to proceed with FEDM board testing. We'll wait a few more days to hopefully get documentation from Sachin/Vaibhav, since they have been ill.
* Took forms to Lee hall to get Xmath past EIT approval. The secretary said, the guy who does the approvals is supposed to be in tomorrow.
* Since the result from Mathematica was wrong, I manually constructed a symmetrized version of the distribution of frequency drift values we'd expect to see as a result of quantization error; & updated Monday's notes accordingly. Today planning to numerically calculate the distribution in C to make sure the curve is correct.
* Checked our NetBeans installation to see if it had C/C++ support installed. No; apparently I only installed it with Java support before. Uninstalling & reinstalling to add support for other languages. In the meantime, maybe I should just use Python...
* Had trouble registering NetBeans with Oracle, so Python won the day. Here is my Python code:
def dist(d):
if d > 100:
return 0.25*(2-(d/100))**2;
elif d < -100:
return 0.25*(2+(d/100))**2;
else:
return 0.25*(2-(d/100)**2);
count = {}
for d in range(-200, 200):
count[d] = 0
for x1 in range(-50,50):
for x2 in range(-50,50):
for x3 in range(-50,50):
y1 = x2 - x1
y2 = x3 - x2
d = y2 - y1
count[d] = count[d] + 1
tot = 0
totd = 0
for d in range(-200,200):
print(d, count[d], dist(d), sep='\t')
tot = tot + count[d]
totd = totd + dist(d)
print("TOT", tot, totd)
The two columns, when normalized, are identical, except for tiny discrepancies which can be chalked up to the imprecision that's inherent to the numerical integration. So, this confirms my previous belief that the solution from Mathematica was correct except for the gap.
* Took forms to Lee hall to get Xmath past EIT approval. The secretary said, the guy who does the approvals is supposed to be in tomorrow.
* Since the result from Mathematica was wrong, I manually constructed a symmetrized version of the distribution of frequency drift values we'd expect to see as a result of quantization error; & updated Monday's notes accordingly. Today planning to numerically calculate the distribution in C to make sure the curve is correct.
* Checked our NetBeans installation to see if it had C/C++ support installed. No; apparently I only installed it with Java support before. Uninstalling & reinstalling to add support for other languages. In the meantime, maybe I should just use Python...
* Had trouble registering NetBeans with Oracle, so Python won the day. Here is my Python code:
def dist(d):
if d > 100:
return 0.25*(2-(d/100))**2;
elif d < -100:
return 0.25*(2+(d/100))**2;
else:
return 0.25*(2-(d/100)**2);
count = {}
for d in range(-200, 200):
count[d] = 0
for x1 in range(-50,50):
for x2 in range(-50,50):
for x3 in range(-50,50):
y1 = x2 - x1
y2 = x3 - x2
d = y2 - y1
count[d] = count[d] + 1
tot = 0
totd = 0
for d in range(-200,200):
print(d, count[d], dist(d), sep='\t')
tot = tot + count[d]
totd = totd + dist(d)
print("TOT", tot, totd)
The two columns, when normalized, are identical, except for tiny discrepancies which can be chalked up to the imprecision that's inherent to the numerical integration. So, this confirms my previous belief that the solution from Mathematica was correct except for the gap.
Monday, March 21, 2011
Just call me a quant...
In the car on Friday I was thinking about analyzing the quantization error a little more precisely, so that we can more accurately subtract it out from other influences on the Allan deviation to get a clearer idea of how much of the deviation is due to actual frequency instability.
The nice thing about quantization error is that it can be well modeled by a simple uniform distribution over the interval [-50 ns, +50 ns], since 100 ns is the clock period of our OCXO, and we are doing a simple single-edge triggered input capture on the PPS signal from the GPS.
Actually, we could improve this to [-25 ns, +25 ns] by using a dual edge-triggered flip-flop: I found a VHDL gate-level structural design for this online the other day. I tested it just now and it works. Let's put that off until later, however...
For now, we can express the distribution over the value of a single y(t_1, t_2)=x(t_2)-x(t_1) between two adjacent times t_1 & t_2 (1 second apart) by integrating a delta function as follows (with x_1=x(t_1), x_2=x(t_2)):
We should be able to solve this in Mathematica. Actually, I know what the answer is already from visualizing it geometrically; it's a sawtooth distribution. Mathematica confirms it (here using the scale 1=50ns):
But really, what we are interested in is the distribution over values of the frequency drift between adjacent windows, d(t_1) = y(t_2)-y(t_1) = x(t_1) - 2x(t_2) + x(t_3). So then this is the triple integral:
p(d) = \int_{x_1=-50 ns}^{50 ns} \int_{x_2=-50 ns}^{50 ns} \int_{x_3=-50 ns}^{50 ns} \delta(d - (x_1-2x_2+x_3)) dx_3 dx_2 dx_1, or (with y=d, a=x_1, b=x_2, c=x_3, and letting 1/2=50ns):
I found this too hard to solve exactly in my head, but I got (a trial version of) Mathematica to evaluate it for me using this expression:
Simplify[Integrate[DiracDelta[d - (a - 2*b + c)], {a, -1/2, 1/2}, {b, -1/2, 1/2}, {c, -1/2, 1/2}]]
The answer should be a piecewise quadratic function in four parts, restricted to the range [-2,+2]. Unfortunately, Mathematica does not solve it properly - it has a missing piece:
Of course, the correct answer should be symmetrical around d=0. We could fill in the missing piece in [-2,-1] by mirroring the piece in [1,2]. Doing that, we get the answer:
The middle two cases can also be expressed as (d-2)^2/4, (d+2)^2/4. We can check the normalization by integrating it over [-2,2], and we get the expected result (1), so this is a real probability distribution.
Even with just three points, this is already starting to take on the character of a normal distribution, as would be expected from adding/subtracting independent random variables.
Anyway, we can model each experimental "d" sample as a sum of a sample d from the above distribution, plus a d value obtained from a normal-distribution model of the frequency deviations in each second.
However, we note that for larger window sizes, the magnitude of the quantization error stays the same (since no matter how large the windows get, the only thing that matters for the quantization error is still just the quantization error for the 3 points at the window boundaries), so it is effectively scaled down by a factor of the window size. Meanwhile, the magnitude of the inherent deviation of the frequency means (as an effect of sample size) scales down with the square root of window size. So, for larger window sizes the quantization error becomes insignificant.
Still, let's see if we can estimate its contribution. If we treat the above quadratic distribution as if it were a statistical population, we can find its variance by integrating y^2 times this distribution for y in [-2,2], and that result is just 1/2. So the standard deviation of this distribution is just 1/sqrt(2), or 0.7071, meaning (with 1=100ns) 70.71 ns.
Using the quadrature rule for the sum of the "real" frequency deviation d(real) and the quantization error d(quant), we have that the measured d is:
d^2 = d(real)^2 + d(quant)^2
And since d(quant) = 0.7071e-7, d(quant)^2 is 0.000,000,000,000,005 = 0.5e-14 sec^2 (exactly, it turns out).
So, we can write:
d(real)^2 = d^2 - 0.5e-14 sec^2
d(real) = sqrt(d^2 - 0.5e-14)
I put this calculation in my spreadsheet, and found that even in the worst case (1-second windows), the quantization error only accounts for a mere 4.2% of the deviation measured! And the proportion goes downwards from there inversely with the window size. What is happening?
Let's look at the worst case (window size 1). The "corrected" (inferred) frequency deviation sigma is about 167 ns. The standard deviation of the frequency deviation caused by quantization error is (as mentioned above) 70.7 ns, divided by sqrt(2) because of the factor of 1/2 in the Allan deviation expression, gives 50 ns. Putting these together in quadrature, the expected overall deviation is sqrt(166^2 + 50^2) = 174 ns, which is the measured deviation. In other words, because of the way errors combine in quadrature, even though the expected magnitude of the quantization error, considered by itself, is 50/174 = 29% of the measured deviation, it cannot by itself account for more than about 4% of the measured deviation.
The nice thing about quantization error is that it can be well modeled by a simple uniform distribution over the interval [-50 ns, +50 ns], since 100 ns is the clock period of our OCXO, and we are doing a simple single-edge triggered input capture on the PPS signal from the GPS.
Actually, we could improve this to [-25 ns, +25 ns] by using a dual edge-triggered flip-flop: I found a VHDL gate-level structural design for this online the other day. I tested it just now and it works. Let's put that off until later, however...
For now, we can express the distribution over the value of a single y(t_1, t_2)=x(t_2)-x(t_1) between two adjacent times t_1 & t_2 (1 second apart) by integrating a delta function as follows (with x_1=x(t_1), x_2=x(t_2)):
We should be able to solve this in Mathematica. Actually, I know what the answer is already from visualizing it geometrically; it's a sawtooth distribution. Mathematica confirms it (here using the scale 1=50ns):
But really, what we are interested in is the distribution over values of the frequency drift between adjacent windows, d(t_1) = y(t_2)-y(t_1) = x(t_1) - 2x(t_2) + x(t_3). So then this is the triple integral:
p(d) = \int_{x_1=-50 ns}^{50 ns} \int_{x_2=-50 ns}^{50 ns} \int_{x_3=-50 ns}^{50 ns} \delta(d - (x_1-2x_2+x_3)) dx_3 dx_2 dx_1, or (with y=d, a=x_1, b=x_2, c=x_3, and letting 1/2=50ns):
I found this too hard to solve exactly in my head, but I got (a trial version of) Mathematica to evaluate it for me using this expression:Simplify[Integrate[DiracDelta[d - (a - 2*b + c)], {a, -1/2, 1/2}, {b, -1/2, 1/2}, {c, -1/2, 1/2}]]
The answer should be a piecewise quadratic function in four parts, restricted to the range [-2,+2]. Unfortunately, Mathematica does not solve it properly - it has a missing piece:
Of course, the correct answer should be symmetrical around d=0. We could fill in the missing piece in [-2,-1] by mirroring the piece in [1,2]. Doing that, we get the answer:
The middle two cases can also be expressed as (d-2)^2/4, (d+2)^2/4. We can check the normalization by integrating it over [-2,2], and we get the expected result (1), so this is a real probability distribution.Even with just three points, this is already starting to take on the character of a normal distribution, as would be expected from adding/subtracting independent random variables.
Anyway, we can model each experimental "d" sample as a sum of a sample d from the above distribution, plus a d value obtained from a normal-distribution model of the frequency deviations in each second.
However, we note that for larger window sizes, the magnitude of the quantization error stays the same (since no matter how large the windows get, the only thing that matters for the quantization error is still just the quantization error for the 3 points at the window boundaries), so it is effectively scaled down by a factor of the window size. Meanwhile, the magnitude of the inherent deviation of the frequency means (as an effect of sample size) scales down with the square root of window size. So, for larger window sizes the quantization error becomes insignificant.
Still, let's see if we can estimate its contribution. If we treat the above quadratic distribution as if it were a statistical population, we can find its variance by integrating y^2 times this distribution for y in [-2,2], and that result is just 1/2. So the standard deviation of this distribution is just 1/sqrt(2), or 0.7071, meaning (with 1=100ns) 70.71 ns.
Using the quadrature rule for the sum of the "real" frequency deviation d(real) and the quantization error d(quant), we have that the measured d is:
d^2 = d(real)^2 + d(quant)^2
And since d(quant) = 0.7071e-7, d(quant)^2 is 0.000,000,000,000,005 = 0.5e-14 sec^2 (exactly, it turns out).
So, we can write:
d(real)^2 = d^2 - 0.5e-14 sec^2
d(real) = sqrt(d^2 - 0.5e-14)
I put this calculation in my spreadsheet, and found that even in the worst case (1-second windows), the quantization error only accounts for a mere 4.2% of the deviation measured! And the proportion goes downwards from there inversely with the window size. What is happening?
Let's look at the worst case (window size 1). The "corrected" (inferred) frequency deviation sigma is about 167 ns. The standard deviation of the frequency deviation caused by quantization error is (as mentioned above) 70.7 ns, divided by sqrt(2) because of the factor of 1/2 in the Allan deviation expression, gives 50 ns. Putting these together in quadrature, the expected overall deviation is sqrt(166^2 + 50^2) = 174 ns, which is the measured deviation. In other words, because of the way errors combine in quadrature, even though the expected magnitude of the quantization error, considered by itself, is 50/174 = 29% of the measured deviation, it cannot by itself account for more than about 4% of the measured deviation.
Friday, March 18, 2011
Why the -1/2 power law?
Juan is coming by in a bit to finish setting up the bootloader on the Acer after installing the XP partition.
I realized after my way out on Wednesday that my interpretation of the power-law scaling of the OCXO's Allan deviation was completely wrong - it would have predicted a -2 scaling, rather than the -1/2 that we see!
I discussed this with Ray this morning, and he thinks it is due to a sample-size effect. The standard deviation sigma_mean of a measurement of a mean from a sample is 1/sqrt(N) times the standard deviation sigma of the underlying distribution, where N is the number of elements of the sample. So, if we think of Allan deviation as being a measurement of the mean frequency displacement between adjacent averaging windows, where the displacement is a difference of frequencies, and the mean frequencies are both measured over windows of size N containing N elements, and the instantaneous frequency fluctuates with a standard deviation of sigma, then one would expect the mean frequency measurements to have fluctuations of magnitude 1/sqrt(N) lower than the magnitude of the real underlying frequency fluctuations.
I realized after my way out on Wednesday that my interpretation of the power-law scaling of the OCXO's Allan deviation was completely wrong - it would have predicted a -2 scaling, rather than the -1/2 that we see!
I discussed this with Ray this morning, and he thinks it is due to a sample-size effect. The standard deviation sigma_mean of a measurement of a mean from a sample is 1/sqrt(N) times the standard deviation sigma of the underlying distribution, where N is the number of elements of the sample. So, if we think of Allan deviation as being a measurement of the mean frequency displacement between adjacent averaging windows, where the displacement is a difference of frequencies, and the mean frequencies are both measured over windows of size N containing N elements, and the instantaneous frequency fluctuates with a standard deviation of sigma, then one would expect the mean frequency measurements to have fluctuations of magnitude 1/sqrt(N) lower than the magnitude of the real underlying frequency fluctuations.
Wednesday, March 16, 2011
Still hangin' with Allan...
* Mike had problems this morning & couldn't make it to meet the Symmetricom rep. He said he'd leave a catalog outside the door but I didn't find it when I got here.
* Re: The Allan deviation computations. I realized after leaving last night that I forgot to divide the sum of squares by the number of samples to get the mean. I also didn't normalize to dimensionless units (dividing by the nominal oscillator frequency) as is normally done. That is fixed now. Also, on Ray's advice, I vectorized the Allan deviation calculation, so now it is much faster. I dumped the data to a CSV file and graphed it in OpenOffice calc. Chekkit out! (Click on image to enlarge.) The red line, for comparison purposes, indicates the 1/2 power-law slope that would be expected if all of the deviation was due entirely to the (fixed) quantization error of oscillator phase measurement (which is at most +/- 100 ns), where the magnitude of these errors gets divided by the window size τ twice - the 1st time because there are τ independent phase samples that contribute to the overall phase offset for each data point, so the errors get averaged away by a factor of τ, and the 2nd time because the magnitude of the frequency delta gets divided by the window size to get a rate of frequency drift. (The starting point is sqrt(1/2)*1e-7, which is the expected deviation based on 1/sqrt(12) - the variance of the uniform distribution over [0,1], and the quadrature rules for combining x1+2x2+x3; though I'm still unsure if this is the right calculation.)
* Interestingly, the Allan deviation attains a minimum at a window size of almost exactly 1 day (86,400 seconds). Perhaps this means that, despite the OCXO's corrections, environmental temperature deviations over the course of the day are responsible for some of the frequency variation that we're seeing on smaller (multi-hour) timescales. Then, when you look at adjacent pairs of window longer than 1 day, you lose alignment with the day boundaries, so some of the error re-occurs. This suggests that we should also see minima at 2-day, 3-day, etc. window sizes. This is not the case, so perhaps this theory is wrong. It might just be a coincidence.
* Re: The Allan deviation computations. I realized after leaving last night that I forgot to divide the sum of squares by the number of samples to get the mean. I also didn't normalize to dimensionless units (dividing by the nominal oscillator frequency) as is normally done. That is fixed now. Also, on Ray's advice, I vectorized the Allan deviation calculation, so now it is much faster. I dumped the data to a CSV file and graphed it in OpenOffice calc. Chekkit out! (Click on image to enlarge.) The red line, for comparison purposes, indicates the 1/2 power-law slope that would be expected if all of the deviation was due entirely to the (fixed) quantization error of oscillator phase measurement (which is at most +/- 100 ns), where the magnitude of these errors gets divided by the window size τ twice - the 1st time because there are τ independent phase samples that contribute to the overall phase offset for each data point, so the errors get averaged away by a factor of τ, and the 2nd time because the magnitude of the frequency delta gets divided by the window size to get a rate of frequency drift. (The starting point is sqrt(1/2)*1e-7, which is the expected deviation based on 1/sqrt(12) - the variance of the uniform distribution over [0,1], and the quadrature rules for combining x1+2x2+x3; though I'm still unsure if this is the right calculation.)
* Interestingly, the Allan deviation attains a minimum at a window size of almost exactly 1 day (86,400 seconds). Perhaps this means that, despite the OCXO's corrections, environmental temperature deviations over the course of the day are responsible for some of the frequency variation that we're seeing on smaller (multi-hour) timescales. Then, when you look at adjacent pairs of window longer than 1 day, you lose alignment with the day boundaries, so some of the error re-occurs. This suggests that we should also see minima at 2-day, 3-day, etc. window sizes. This is not the case, so perhaps this theory is wrong. It might just be a coincidence.
Subscribe to:
Posts (Atom)