Lazy Discrete Fourier Transform on the Arduino Uno
44I got around to implementing my "Lazy Discrete Fourier Transform" algorithm on the Arduino Uno yesterday. Not all the optimizations are in place yet, but it's running nicely so far, pretty much real time.
The data comes from the ADXL345 digital accelerometer, which is set to a sampling rate of 800 Hz, detecting +/- 4g at 10 bits of precision.
The code first grabs around 3000 samples of the Z acceleration, and uses it to compensate for the gravity and the orientation of the sensor.
The data is ran through my LDFT algorithm, which finds the amplitude at frequencies from 0 to 299 Hz with precision of slightly more than 1 Hz per bin (bins always overlap with this method, AFAIK), each bin at 16 bits integer precision. Absolute value of the transform is shown in the OLED in the 0-127 Hz range, so it's 1 bin per column.
You can see it detecting a peak reliably at around 13-14 Hz, which is the resonant frequency of my table (which I measured before with more precise methods). At the end you can see it detecting 0 Hz (constant gravity) plus some sensor noise as I tilt the sensor.
The whole idea behind the algorithm wasn't implemented yet, and I don't think I'll need it in practice given current results, but it would allow many other different optimizations. I'll have to study more signal processing theory to really see what's going on and see if it's more than a silly hack.
The main point is that I'm more interested in lower frequencies than higher frequencies, so Fast Fourier/Hartley Transforms would require me to store a lot of samples to detect those reliably. With limited memory, as in the Arduino Uno where I only have 2048 bytes of SRAM, I cannot afford that approach. Those transforms also extract the entire spectrum, so they spend a lot of computation on the higher frequencies I don't care about.
The low frequency vibrations I'll be detecting are also short lived, so the whole FFT/FHT approach wouldn't work well enough because windowing at different times could mess it all up, especially since the windows have to be large.
Wavelet transforms might have helped, but it's not trivial to implement and it seems to me they would perform badly on the Arduino as well.
My algorithm is an alternative take on the problem that takes all these issues under consideration. It's optimized to detect amplitudes of lower frequencies in short bursts of signals. (So in principle, it sounds similar to wavelets, but I'm not using anything like wavelets.)
But, as opposed to FFT/FHTs/wavelets, the result is not a complete representation of the data. Part of the optimization is that I explicitly discard a lot of the information in the signal based on certain assumptions of regularity and the frequencies of interest. This is one of the ideas behind the algorithm, so applicability may be really limited.
I'll have to study the approach and signal processing theory in more detail (and more algorithms that do similar things) before I give out any specific details on this, as maybe there's something worth publishing more formally in here, instead of just copying and pasting my code online.
Probably not, as I'm a pretty stupid person, so I doubt I'd stumble upon something big.
It's just nice to see my own little hack working.