Created by
Matthew Earl
on March 05, 2015.

*Update*: I just noticed that this technique is known. I’m leaving this up here in case anyone finds my particular derivation interesting. :-)

I’ve recently been working on a telescope clock-drive project. The idea is that I attach a motor to a telescope to make it turn at the same rate as the earth so that long exposure photographs don’t come out blurred. I’ll (hopefully) post more on this soon, but in this post I’ll discuss an algorithm I stumbled across while designing a DAC as part of the clock-drive project.

My problem was to generate an output voltage to use as a reference for driving the DC motor attached to the telescope. The voltage would be determined by some logic in an AVR on the control board, and a low-pass RC filter would be attached to one of the digital output pins. A timer would be running on the AVR triggering an interrupt service routine (ISR) at regular intervals. The timer ISR would set the state of the output pin either high or low in order to attain the required output voltage after the filter stage. This post discusses the algorithm to use in the ISR.

Before I discuss the improved algorithm, let’s look at the naive scheme for generating a PWM signal:

…and here’s the result, for `P = 32`

and `T = 20`

.

The green line is the unfiltered output, the red line is the filtered output
(with an RC time period of 16) and the blue line is the target voltage (```
20. /
32 == 0.625
```

).

As expected the filtered curve follows the green curve, according to the equations of capacitor discharge in an RC circuit.

Note that there are lots of points where the ISR is invoked and the filtered signal is below the target voltage, yet the output signal remains low, and vice-versa. It would seem that a better algorithm would set the output high when the filtered output is below the target voltage, and low when the filtered output is above the target voltage.

Intuitively, it would seem that an algorithm which seeks to maintain a running average as close to the target voltage as possible would work well. That is, generate a sequence \( o_i \) such that:

is minimized for all \( N \in \mathbb{N} \).

Let’s give this a go:

…and here’s the result, with the same parameters as the above plot:

Much better. Note how, once stabilized, whenever the ISR fires the output state is adjusted to follow the target voltage. As a result the filtered signal deviates much less from the target voltage.

However, there are a few problems with the above routine:

- Use of division. This isn’t necessarily going to be feasible, or even possible on your MCU.
- Use of two variables. Again, this could be an issue on an embedded system where resources are right.
- Unbounded integers.
`time`

and`sum`

will increase indefinitely, and will soon overflow.

So what can we do? Well, firstly let’s get rid of that division by multiplying
the condition by `P * time`

:

The `time > 0 and `

check is now redundant, so let’s get rid of it:

Still though, multiplication is relatively expensive. Let’s perform a change of variables to eliminate it:

`sum2 == P * sum`

`time2 == T * time`

This is good. But if you look closely the output of the routine depends only on
`sum2 - time2`

. So let’s trim the code down to just one variable, ```
h = sum2 -
time2
```

:

Now substitute `h2 == h + T`

in a bid to stop underflow, and move the
subtraction into the else block to avoid overflow:

Some basic analysis shows that `h2`

must be greater than or equal to `0`

, but
less than or equal to `P`

. As such, a full 8-bits of DAC accuracy can be
obtained with a single 8-bit variable (when `P = 256`

), with a relatively low
RC time-constant.

Wait a minute, this looks familiar:

This is a slightly simplified Bresenham’s Line Algorithm for the octant \( \delta x, \delta y > 0 \land \delta x > \delta y \). Note the correspondence between variables:

`h2`

corresponds with`y_err`

.`T`

corresponds with`dx`

.`P`

corresponds with`dy`

.`x`

corresponds with`time`

.`y`

corresponds with`sum`

.

This isn’t too surprising when you notice the formula the algorithm was derived from seeks to approximate the gradient of the line running through the origin to \( (\sum o_i, N) \) as \( \frac{T}{P} \).

Just for fun let’s plot the output of the algorithm (incrementing `x`

at each
step, and incrementing `y`

at each positive output) against the line running
though \( \frac{T}{P} \):

The Bresenham PWM algorithm is useful if both of the following are true:

- Your timer interrupt is constrained to run at a fixed interval. For example, if your timer is also used within the MCU for other periodic tasks.
- The timer interval cannot be set arbitrarily low. For example either because the MCU is operating at a low clock frequency or there is CPU contention such that the ISR cannot complete before the next triggering.

If either of the above are false, then naive PCM can be used with a reduced
period. In the case where the timer period can be changed, it would be changed
to fire at alternating periods of `P`

and `T - P`

, flipping the output state
each time.

The main benefit of the Bresenham PWM algorithm is it can be coupled with an RC-filter operating at a lower time constant to acheive a given voltage stability. The knock-on benefits of this are:

- Lower output impedence.
- Faster convergence on the target voltage. (Important if your target voltage is changing.)