"All
waveforms, no matter what you scribble or observe in the universe, are
actually just the sum of simple sinusoids of different frequencies."

Hi,

I am just refreshing the basics of fourier transform. I am not an expert. Now I did a small audio spectrum analyzer(0 - 10KHz) on a 16x2 character lcd using an atmega32 microcontroller. Since I am refreshing from the basics, so I started with simple DFT. Also, I believe I should learn to walk before running. So I am not straight away going towads the FFT, which is nothing but the fastest and a bit complicated algorithm to find DFT.(I will try it later, as soon as possible)

DFT is too slow compared to FFT. My lcd spectum analyzer doesn't need a great speed like that of an FFT, now if it is capable of providing a speed of around 30 frame/second, then it is more than enough for visualizing the audio spectrum on an LCD. But any way, in my case I can roughly achieve around 100 frames/second(any way it is too high refresh rate for a 16x2 lcd, not recommended also :-)). My audio sampling rate is 20KHz for 32 point DFT. Since the transform result is symmetric, I need to use only the first half, ie the first 16 results. So, it means, it can display upto 10KHz spectrum. So the resolution is 10KHz/16 = 625Hz.

I have tried to improve the speed of DFT computation. If it is an N point DFT, it needs to find (N^2)/2 sin and cos values. For a 32 point DFT, it needs to find 512 sine and cosine. Before finding the sine and cosine, we need to find the angle(degree) which takes some processor time, so I implemented a lookup table for that. Next two tables are for sine and cosine. I didn't used any float or double since it takes more processing time in 8 bit avr, instead I implemented the sine and cosine lookups as 16bit intiger, by multiplying the real sine and cosine values by 10000. Then after finding the transform, finally I need to divide each result by 10000. This eliminates the need of using float or double and makes it more faster.

*Now I can calculate 120 32-point DFT operation/sec which is more than enough for my small spectrum analyzer.*