Part 1 of 1 · Keeping Time: Pacing Output and Following Clocks with a Phase-Locked Loop (PLL)

Keeping Time: Whose Clock?

Pacing output on your own clock needs exact arithmetic, not a feedback loop. Following someone else's clock is where the phase-locked loop belongs.

By M. Robert Martin·9 min read

• essay
• series

A transport stream at a constant bitrate is a promise about time. Every 188-byte packet occupies a fixed slot in the output. Some packets carry a sample of the encoder’s 27 MHz clock, its program clock reference, and a receiver uses those samples to reconstruct the encoder’s clock.¹ A sample is only true if the packet carrying it sits where the sample says it does.

I wanted to build new channels from the streams of incoming ones, and write each new channel at a fixed bitrate. So the output side needed something that would tell it, again and again, when the next packet was due.

My first answer was a software oscillator. A ticker fired at the packet rate, the writer reported back to a PID controller, and the controller nudged the ticker. It was a feedback loop wrapped around a timer, and the library that grew out of it was called pll. My research said a phase-locked loop was the standard tool for this.

It is the standard tool. It just isn’t the tool for that job.

A timer that adds

Here is the problem the feedback loop was really solving. At 19.392 Mbps, a 188-byte packet takes 77,557.76 nanoseconds. A timer that works in whole nanoseconds rounds that to 77,558 and adds it on every tick. Each tick is a quarter of a nanosecond late, nearly 13,000 ticks a second, so the schedule drifts by about 3 microseconds every second and 11 milliseconds every hour. Rates like 30000/1001 per second have no exact period in nanoseconds at all, so every timer that adds has to round somewhere.

A feedback loop can pull that drift back. But the drift exists only because the schedule is built by adding. Compute each slot’s time from its number instead, slot × 1504 bits ÷ 19,392,000 bits per second, with exact fractions, and round only at the end. Slot one billion is then exactly where it should be, because nothing was ever added up. There’s no error left for the loop to correct.

A loop with nothing to correct isn’t harmless. A PID controller has gains, and gains have consequences: overshoot after a disturbance, a settling time, a wind-up when the output stalls. Each is a behavior the schedule didn’t need and now has to be tuned and tested. The controller was compensating for an arithmetic mistake by adding dynamics.

What a pacer on its own clock actually needs is plainer:

• the exact time of every slot;
• which slots are due now, given that the program woke up whenever the operating system let it;
• what happens to slots that came due while it was asleep: send them late, or skip them.

None of that involves feedback. A program that wakes 20 milliseconds late should hand out 20 milliseconds of slots at once, each stamped with its own scheduled time. The pacing in pll is now exactly this: it numbers slots, says which are due, and never reads a clock itself.

Whose clock?

The phase-locked loop belongs where there are two clocks.

Each incoming channel was made by an encoder with its own 27 MHz clock, allowed to be off by up to 30 parts per million.¹ Its packets arrive over TCP or from a file, at whatever pace the network or the disk allows. To place an incoming packet in the outgoing stream at the right moment, and to rewrite its clock sample correctly, the muxer has to know how that encoder’s clock relates to its own. That relationship can’t be computed. It has to be estimated, from samples that arrive late and unevenly, and kept up to date as the two clocks drift. That’s the job a phase-locked loop does, and it’s the job receivers do with a PLL when they recover a broadcaster’s clock.²

The same shape shows up far from video. A sound card consumes samples at the rate of its own crystal, not yours. A sensor timestamps readings with a counter that runs a little fast. A remote service reports times you’d like to put on your timeline. In each case there’s a clock that isn’t yours, readings of it that reach you late, and a question: what time is it over there, in my time?

So the library split in two. A pacer keeps time on your own clock, exactly, with no loop. A follower is the phase-locked loop: fed readings of another clock, it estimates the offset and the rate between the two. The two meet in one place. When the thing you’re feeding runs on its own crystal, the follower’s rate estimate becomes a trim on the pacer, and your output keeps pace with the device instead of slowly overrunning it or starving it.

What the equations leave out

A second-order loop fits in two lines. Measure the phase error between where a reading arrived and where you predicted it would arrive. Correct the phase by a fraction of that error, and nudge the rate estimate in proportion to it. Choose a bandwidth and a damping, and the textbook gives you the gains.

Those two lines leave questions open:

• Readings that cross a network arrive late, and never early. Should the loop believe every reading, or only the ones that arrived least late?
• When a reading is wildly off, is it an outlier to ignore, or did the other clock really jump? How much evidence should it take to decide?
• If no readings arrive for half a minute, what should the mapping do, and how should the program find out?
• If the rate changes while a pacer is mid-stream, which slot gets the new rate, and does the schedule jump?
• What happens when readings are rare?

The last one is where the textbook answer was wrong for us. The equations in the first draft of the specification were the standard discrete ones, with gains proportional to the time between readings. They work when readings are frequent. But a second-order loop updated every Δt seconds goes unstable once the natural frequency times Δt grows past about one. A sensor that reports every few seconds, behind a loop tuned for a sound card, would have made the estimate oscillate and grow. The fix, now a sentence in the specification, was to cap the time step the gains use at half the loop’s time constant. For frequent readings nothing changes. For rare ones the gains stop growing, so a reading that comes an hour after the last one corrects the estimate no harder than one that comes after a short gap. With readings evenly spaced, at any interval, the capped update equations are stable for every damping the library accepts; that’s a short calculation. Gaps that vary are harder to analyze, so there the evidence is tests that feed readings seconds and hours apart and check that the estimate settles. Neither says the estimate stays accurate across a long gap. The other clock keeps drifting while nothing reads it, and the loop can only correct what it sees.

Another answer was wrong in a way no review caught. The first reference implementation kept its anchor, the local time the mapping is measured from, as a float64 count of nanoseconds. That’s precise to the nanosecond until about 104 days. A program timing from boot can easily run longer than that. The fuzzer found it in its first minute: a reading far past 2⁵³ nanoseconds that came back mapped 12 nanoseconds off. The anchor is now whole nanoseconds plus a fraction, and there’s a test that runs a thousand simulated days.

How do we know?

The pacer can be checked the way any exact computation can. A deliberately naive reference recomputes every slot time from scratch with arbitrary-precision fractions, with no fast path and no shortcuts. Random sequences of operations run through both, including rates with 64-bit terms, slot numbers near 2⁶⁴, and times near the largest a Go duration can hold, and every answer has to match. Change one comparison in the rounding code and the test fails at once, printing the operations that exposed it.

The follower can’t be checked that way, because its answers aren’t exact. They’re estimates, and a good estimate is one that’s close, not one that’s equal. So it gets checked twice. A literal model of the loop equations confirms that the code computes what the specification says, update by update. Then a simulator asks the question the equations can’t answer: does it work? It runs the follower against clocks that are fast, slow, drifting, changing rate and jumping, with readings delivered late, in bunches and through outages, and holds each run to thresholds.

The simulator has a limit, and it’s worth saying plainly. It tests the clocks I thought to simulate. A real network can misbehave in ways no scenario anticipated. The thresholds say the loop works on these clocks, not on every clock.

The same answers in other languages

I want pll in more than one language, and the two halves port very differently.

The pacer’s promise is exactness, and exactness travels if the arithmetic does. The Go version multiplies 64-bit numbers into 128-bit products and falls back to arbitrary precision when even that isn’t enough. A port needs the same reach: Python’s integers have it built in, JavaScript has BigInt, and other languages have libraries. The answers then have to match bit for bit, and a shared reference with a shared harness can hold every implementation to that.

The follower’s promise is closeness, and closeness doesn’t travel as neatly. Every language here uses the same 64-bit floating-point numbers, so it seems the follower’s estimates should match exactly too. But the same formula can round differently depending on how it’s compiled. Go’s specification, for instance, allows a compiler to fuse a multiply and an add into one operation that rounds once instead of twice, unless the code forces the intermediate rounding.³ The result is a little more accurate and a little different. So the specification has to choose. It can pin down the order of every operation, or it can require that implementations agree within a tolerance and describe what that tolerance means.

That choice, and the shared specification, reference and harness that enforce it, come next, with the ports.

Keeping time turned out to be two jobs. Keep your own time exactly, by arithmetic rather than correction. Follow someone else’s time carefully, by estimation, with a loop that knows what it can’t know. Most of the work is noticing which job you’re doing.