The Circuit Farm

I’ve been kicking around the idea of making an accurate sidereal clock circuit for years now. I’ve discussed it all before, but the basic idea is that I want to be able to create a circuit that oscillates at 32857.715Hz (32768 ticks per sidereal second).

The fact that the required frequency is irrational means that something needs to be done to correct the achieved frequency to bring it closer to the required frequency.

I played around with the idea of somehow “pushing” a 32768Hz crystal to the desired frequency — This seems like one of those “adding a lot of error” class of solutions, where what you want is to be as error-free as possible.

I also played around with (and came up with a nice algorithm for — see previous post) using a standard 32kHz crystal, but setting up a second oscillator to “add” some ticks into the normal tick stream to bring the whole system up to frequency. This could work, but it would now have 2 sources of error: the original 32kHz crystal, plus any error that was uncorrected in my algorithm.

I saw a very cool clock algorithm for Arduino made by a guy in Brazil, but his (admittedly very awesome) algorithm only works for doing 1Hz sidereal, so while I could use it to make a clock, I really wanted a 32kHz sidereal replacement, so I kept looking. I did like the idea of breaking the “float” calculation into a “decmial” one.

Then I ran across Roman Black’s treatment of the problem. He was searching for a way to synthesize 1Hz (or 100Hz) signals out of random source crystals, and utilized Bresenham’s Line Algorithm in a very nifty way. Essentially, you maintain a counter, and when it passes a limit, you subtract that limit, but leave the remainder in the counter. Thus, all required ticks are accounted for, and the output frequency is “eventually consistent”.

I realized as soon as I saw this method that it would be perfect for what I was trying to do. I just needed to figure out how to set up the algorithm to produce the necessary ticks.

I checked my nearest Arduino, and found that it’s running a 16MHz crystal. Also, unlike PIC, Atmel chips don’t have a 4-cycle instruction set, so the chip really puts out 16 million instructions per second (one every 0.0625µS!).

To drive the algorithm, I needed 4 variables:
A – target_ticks – frequency in Hz of the output oscillation
B – cpu_ticks – frequency in Hz of CPU oscillation
C – timer_ticks – how many cpu_ticks before the timer overflows
D – bresenham_scalar – more on this in a second.

From these you synthesize:
E = B/C – max_ticks – number of timer overflows in 1 second

In my case, I needed:
A = 32857.715…
B = 16,000,000
C = 256 (8-bit Timer2 — won’t need tone() out of the Arduino for this)

The idea is:
Set up the timer to interrupt on overflow.
When it overflows, add target_ticks to the tick count.
Then check whether the tick count has exceeded max_ticks, and if it has:
– subtract max_ticks from the tick count
– toggle the output pin

… and that’s it. The pin will toggle whenever the tick count gets high enough, the remaining ticks will stay “in play”, and the output will be toggled the correct number of times (on average, over time).

In order to make the interrupt routine run as fast as possible, we want to store ticks as a 32-bit integer. Because the target_ticks is an irrational number (being a ratio of two irrational numbers), it would be nice to get some extra accuracy in the form of pulling out some decimal places of accuracy out of the irrational target frequency.

As a first pass, I just multiplied the target frequency and the max frequency by some multiple of 10, keeping both numbers less than 2^32 (the max size of a 32-bit int). However, that ended up leaving some accuracy on the table, because the max frequency can be scaled by more than 10^4 but less than 10^5 before overflowing maxint. So, we can pull a little extra accuracy out of the timer by choosing a scalar more carefully.

The choice of scalar is highly dependent upon all the variables (an 8MHz CPU cannot use a full 8-bit timer overflow for this — there are only 31250 overflows/sec but a required frequency of 32857… so you need to overflow faster, or otherwise synthesize a faster clock). But for the 16MHz/8-bit/32kHz target frequency, a scalar of 68,700 will pull 4.8 decimal places of accuracy out of the timer, as opposed to 4 decimal places with a 10,000 scalar. For a bunch of precalculated values, this is not a big loss of readability.

So I wrote myself up a little Python script to test my configuration; it didn’t wait for timer overflows; it just ran in a while loop and cranked out info. Here’s what I got, after a simulated 10,000 second (2.7 hour) run:

Notes:
These are 10-second intervals (62500 * 10 overflows between each)
At 10,000 seconds (62500 * 10000), the number of output ticks is accurate to all 4 decimal places (328577158 ticks = 32857.7158Hz for 10000 seconds)
At each of the snapshotted time segments, the remainder flows between close to 0 (a tiny bit extra left in the counter) and close to 2 (almost but not quite enough to overflow). There is jitter, but over time, the algorithm puts out the correct number of ticks.

In short, the Python script works perfectly.

Now I just need to translate it to Arduino, and then I can decide what to do with my newfound sidereal time base!

edit: I created an Arduino sketch for this, and have also included the Python script, for reference.