Skip to main content

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!



Popular posts from this blog

Parasitic Quadrifilar Helical Antenna

This article was reprinted in OSCAR News, March 2018: If you want to receive Satellite Weather Pictures , then you need a decent antenna, otherwise you will receive more noise than picture. For polar orbit satellites, one needs an antenna with a mushroom shaped radiation pattern .  It needs to have strong gain towards the horizon where the satellites are distant, less gain upwards where they are close and as little as possible downwards, which would be wasted and a source of noise.  Most satellites are spin stabilized and therefore the antenna also needs circular polarization, otherwise the received signal will flutter as the antennas rotate through nulls. The helical antenna, first proposed by Kraus in 1948, is the natural solution to circular polarized satellite communications.  It is a simple twisted wire - there seems to be nothing to it.  Various papers have been published on helix antennas, so the operation is pretty well understood. Therefore,

Weather Satellite Turnstile Antennas for the 2 meter Band

NEC2, 2 m band, 146 MHz, Yagi Turnstile Simulation and Build This article describes a Turnstile Antenna for the 2 meter band, 146 MHz amateur satcom, 137 MHz NOAA and Russian Meteor weather satellites.  Weather satellite reception is described here .  A quadrifilar helical antenna is described here .   Engineering, is the art of making what you need,  from what you can get. Radiation Pattern of the Three Element Yagi-Uda Antenna Once one combine and cross two Yagis, the pattern becomes distinctly twisted. The right hand polarization actually becomes visible in the radiation pattern plot, which I found really cool. Radiation Pattern of Six Element Turnstile Antenna Only a true RF Geek can appreciate the twisted invisible inner beauty of a herring bone antenna... Six Element Turnstile Antenna Essentially, it is three crosses on a stick.  The driven elements are broken in the middle at the drive points.  The other elements can go straight throug

Patch Antenna Design with NEC2

The older free Numerical Electromagnetic Code version 2 (NEC2) from Lawrence Livermore Lab assumes an air dielectric.  This makes it hard (but not impossible) for a radio amateur to experiment with Printed Circuit Board Patch antennas and micro strip lines. Air Spaced Patch Antenna Radiation Pattern You could use the free ASAP simulation program , which handles thin dielectrics, you could shell out a few hundred Dollars for a copy of NEC4 , You could buy GEMACS if you live in the USA, or you could add distributed capacitors to a NEC2 model with LD cards (hook up one capacitor in the middle of each element.), but that is far too much money/trouble for most. More information on driving an array antenna can be found here: l Air Dielectric Patch   The obvious lazy solution is to accept the limitation and make an air dielectric patch antenna. An advantage of using air dielectric, is that the antenn