DSP on an Embedded Processor

Doing digital signal processing on a teeny weeny Arduino processor requires some trade-offs, since it is slow and doesn't have much memory.  However, bear in mind that today's embedded processors are faster than yesteryear's DSPs, so all you need to do, is use yesteryear's methods!

What it mostly amounts to, is careful use of integers and shifts, instead of floating point numbers and multiplies.  If you can, limit multiplies, divides and buffer sizes to powers of 2.  That affords enormous speed optimizations.

Circular Buffers

For example, let's filter input from an 8 or 10 bit A/D on a little 16 bit embedded processor.  This usually requires a low pass filter.  A simple low pass filter is a moving average and to do that, you need to keep a buffer of old data values.

If you are smart, then you will set up a circular buffer with 10 values, but if you are smarter, then you will use a buffer with 8 or 16 values instead - why?

If the buffer size is a power of 2, then you can make the index wrap around automagically with a simple bit wise AND function, thus making management of the circular buffer quite trivial.

Say the data buffer size is 16, with a read and write index r and w:

unsigned int buffer[16];

unsigned int r = 0;

unsigned int w = 0;

Then you can post increment the index with w++ and make it wrap with AND 0x000F, like so:

buffer[w++] = data;

w &= 0x000F;

The index w will then wrap around to zero when it reaches 16, without the use of any complicating ifs, thens elses or buts!

Do the same thing when you read from the buffer.

How do you know when the buffer is full/empty?

Easy, when r == w, then you are in trouble and the buffer is either full or empty, depending on what you are doing.  As easy as pi...

Maintaining Precision

When doing mathematics in integers, the fractional amounts that you can lose during calculations can add up over time and cause wild inaccuracy.  You can mitigate this problem by scaling.

Simply multiply the A/D input value by 16 immediately and eventually when you output a result, divide by 16.  That provides 4 fractional bits for precision on the bottom end and you still have a few bits on the top end for overflows.

The above example then becomes:

buffer[w++] = data << 4;

w &= 0x000F;

Hanning Filter

Everybody uses some sort of moving average low pass filters, so just to be different, I'll describe a Hanning filter instead.

y[k] = (x[k] + 2x[k-1] + x[k-2]) / 4

This filter only needs 4 variables, and you can multiply with one shift and divide with two shifts:

y[k] = (x[k] + x[k-1]<<1 + x[k-2]) >>2

You can use a 4 long data buffer and rotate the index through it in a circle, same as above:

Save new data, pointer++, pointer & 0x0003
Read old data, pointer++, pointer & 0x0003
Read older data, pointer++, pointer & 0x0003

You are now ready to save new data again.

So with a little bit of head scratching you can implement a Hanning filter very efficiently.

Moving Average

A rolling mean can be calculated on the fly without a buffer:
Take 1/8 of the current input data x(k) and add it to 7/8 of the previous output data y(k-1).  
This yields the new output data y(k).

y[k] = (7 * y[k-1] + x[k]) / 8

Now how do you do that on a small processor that cannot multiply and divide efficiently?

Divide by 8 is easy:
y = x >> 3

Multiply by seven?  Multiply by 8 and subtract again
y = x << 3
y -= x

The result has similar complexity to the Hanning filter above.

GPS Position Filter

To use a GPS receiver in a toy, one needs to stabilize the received position data.  The cheap toy GPS data typically varies by +-7 meters or worse.  Considering that a typical backyard is not much bigger, this makes it hard to use GPS for navigation of a model car or airplane.

A toy car moves slowly, so you can use a heavy handed low pass filter on the latitude and longitude as above, but it really is only useful when you play in a large park and you have a large battery and good obstacle avoidance sensors, since GPS alone won't keep your toy on a pathway.

La voila!

Herman