Fast Fourier Transform (FFT) vs my "lazy Discrete Fourier Transform" (LDFT)
34Here's a straight up comparison between the FFT (in blue) and my algorithm (in red), which so far I'll just call "lazy discrete Fourier transform" (LDFT)
This is audio sampled at 44100 Hz, the final notes of "Magnetic Rag" by Scott Joplin, as played by Alessandra Celletti.
FFT was taken with a 1024 sample cosine window (16-bit integers), which by Shannon-Nyquist gives us a 512 bins of 44100/1024 ~ 43 Hz bandwidth, from 0 Hz to 22050 Hz. In other words, the FFT spends A LOT of time, processing and memory on higher frequencies. But I don't care about those!
This is why I rolled out my own method, which I could dynamically bias towards the lower frequencies with different bandwidths. Couldn't find anything in the literature about this, so I came up with my own stupid algorithm. It's not really a sparse DFT or a straight up DFT either, from the looks of it. Haven't found anything similar. Doubt it's revolutionary, just a really lazy specific implementation of the general ideas.
My method here was biased towards the lower frequencies. I used 512 bins (each a 16-bit int).
For my specific purposes this method seems much better in terms of memory and computations. I'll load this up on the Arduino later this week and see how well it goes.
It certainly looks more promising than a 256 sample but 128 frequency bin Discrete Hartley Transform on that thing!
I'll work out the details of the theory behind this thing a little bit more and make a post about it somewhere. I'll let the experts tell me how stupid and trivial it is, which is fine, but I'm sure other people could benefit from it.
EDIT 1: A naive implementation is too slow, but there's several ways to optimize it. Will work on it more.
EDIT 2: Got it working in real time on the Arduino Uno now: https://www.youtube.com/watch?v=ON6XEtqmbgI