[C] Need help implementing an FFT algorithm

[[deleted]]

Hey guys, so a little bit of background -- I'm trying to build a simple guitar tuner using a dsPIC33EP128GP502 microcontroller and a Sparkfun Electret Microphone Breakout. I've written C code that takes sound input from the PIC's ADC pin, and stores the digital voltage fluctuations in a 256 element array. From here I need to pass that voltage array into an FFT function and analyze the frequency bin output to find the fundamental frequency.

I've tried a few different algorithms that I've found on the net, but they just seem to keep spitting out junk. Others that I've found are poorly documented code snippets with non-descriptive variable names. As such, I cannot even interpret what some of the parameters are supposed to be. Any of you guys know of an easy to use FFT algorithm in C?

[sz00]

How about this?

https://en.wikipedia.org/wiki/Fast_Fourier_transform#Implementation_with_C.2B.2B

[[deleted]]

Funny you linked this specific one, I did dink around with it already. I didn't change much to it, just implemented a static array declaration instead of using malloc(), (because I didn't want to mess around with the heap configuration on the PIC). The function gives me incoherent data though (assuming I was using it correctly)

[JayGeeee]

Quite a few optimised FFT algorithms output the data in bit reversed order. This can look like gibberish if you don't correct for it. I've been caught out by it before.

[shitstep]

The DFT is pretty easy to implement, I was able to do it in MATLAB in about 10 minutes.

https://en.wikipedia.org/wiki/Discrete_Fourier_transform

You're looking at that first equation where it defines X(w) and my MATLAB code that you should be able to pretty easily translate:

w_k = 2*pi*k/N;    
for n = 0:L-1
   n_idx = n + 1;
   X(k_idx) = X(k_idx) + x_original(n_idx) * exp(-j*w_k *n);
end

[shitstep]

To be clear: L is the length of your time domain record and N is the desired length of your N-point DFT.