DFT on an Arduino

You read that right. DFT, not FFT. Discrete Fourier Transform, DFT.

Why would I do such a thing you ask? Why not just simply use the faster and simpler FFT (Fast Fourier Transform)? It even has Fast as part of its name!

Well, I was still on chapter 11 of this amazing book The Scientist and Engineer's Guide to Digital Signal Processing by, Steven W. Smith as this experiment. FFT was the next chapter. There's an on-line abridged version too: http://www.dspguide.com/

 Why? Letsee... About a month back (2013Dec), Ashok asked me on facebook whether I knew anything about embedded systems and microelectronics. I replied that I did, but I had never actually used one. I told him that there some cool stuff around - Arduino and such, that make prototyping super easy. I then remembered an old memory. I always wanted to learn DSP properly and new exactly what I wanted to do with that knowledge. Back in college I had absolutely wasted away my DSP course by slacking off. Regretful :(



Some time in my junior year at college, I went overboard on a project where I was to simply make something around a 555 timer chip... and made this:

That was just a lot of opamps and LEDs. Kinda simple really. Bandpass filters being mutiplexed one LED column at a time, by a 555 timer chip. See, I used a 555 chip there. The very next semester I had DSP. I knew I had to digitize the Audio Visualizer. I just had to. But, as I was slacking off, I couldn't really get what Proakis and Oppenheim (The two college recommended books) had to offer. Three years down the road, NOW, I looked around for a DSP book that I could actually learn (not study) from. That books is the one from Steve Smith. Amazing book, really. Has a brilliant and very understandable intro to DSP. Think of it like a Dummies Guide to DSP. Another good book would be DSP book by Richard Lyon. It's far more in-depth. But, I wanted something that would get me started as fast as possible. Smith does just that.


Alright! Getting right to it. I wanted to make the Audio Visualizer using DSP on a cheap microcontroller setup. Arduino fit the bill just right. Looking around, I found that Simple Labs had a pretty awesome Arduino clone, the Induino. So, I went ahead and got myself the Induino Learner's kit. It came with an 16x2 character LCD which was perfect for the Audio Visualizer I had in mind. I am not going to explain DSP or DFT here. It would be grossly redundant. Read the book. Nothing I have come across could explain it better.  Also, this ain't a Arduino tutorial. You kinda need to know that stuff before jumping to something funny like DFT. If you have an Induino, this is a good place to learn - Induino Tutorial

Prerequisite knowledge:

• Control over character LCD. link
• Control over ADC - not just the Arduino analogRead(), but the actual Atmega328 ADC. link
• Knowledge of how to store and read content from the flash memory. link

Before sketching on the Arduino, it's always best to check your algorithm. So, I used Octave for that. I really hope you know what Octave is. Ever used Matlab? Ya? Well, Octave is just that - but free! Gnu licensed, open source. This - http://en.wikipedia.org/wiki/Window_function - is very good place to understand various windowing functions. Without windows we end up with very annoying spectral leakage. Spectral Leakage, such a cool word... sounds very haunted.

64pt DFT with Hamming Window

64pt DFT with Rectangular Window, ie: No window. Look at that awful Spectral Leakage.

All Source Code : on Github

Now, lets get to the main course. The Arduino Sketch. Looking at the Octave code, it's kinda obvious that one cannot generate those coefficients on the arduino during run time. Hence, we ought to store those coefficients in a neat LUT (Look-up Table) - nothing fancy, just some arrays stored in a header file. Get those LUTs from Octave by saving those matrices. So, this is how I am going to do this, here. Below is the whole code. You can just copy it and flash it right away, after setting up the right ports in the code. Explanation follows that, though the comments are kinda self-explanatory.

Remember that the Atmega328 used in the Arduino is build on the Harvard architecture. The space for instruction and dara is separate. With 2KB ram, its impossible to store huge arrays of coefficients in the small sram, hence you'd need to store it in the code space, which is huge - 32KB. The dftcons.h contains LUTs for:

• Cosine coefficients - REx_cons[DFT_Nb2][DFT_N] - 8bit signed
• Sine coefficients - IMx_cons[DFT_Nb2][DFT_N] - 8bit signed
• Hamming window - window[DFT_N] - 8bit signed
• Log Power level - logMag[128] - 18*log2(x) - 8bit unsigned
• Bands[16] - Selects which band goes to which column of the 16x2 LCD - 8bit unsigned 

DFT_N is the number of sample points on which DFT is preformed. It is the specification of the DFT, and in this case, 64. It pretty much decides everything - memory size, operation performance, spectral resolution, etc. Read the book.

DFT_Nb2 is exactly what you think it is - N/2+1, ie 33 in this case.

If you have read the book, you'll know that the Frequency spectrum is redundant over the centre (-pi/2 to pi/2). It's basically mirrored. To check this out, in the Octave code, do a DFT over all 64 points. Hence, you only need just half the spectrum. This goes hand in hand with the concept of Nyquist Theorem where you maximum knowledge of the input signal you can have is half the sampling rate, ie: N/2+1

The 0th band is the Zero frequency power - DC signal, hence you always need the +1. Yes.

LOG2_Nb2 is the log2(64/2) = 5. This is important during Magnitude correction... rather, calling it Normalization would be more accurate.

The dft_C.ino is the arduino sketch.

PART 2