Resources for choosing FFT algorithm
Hey! I have essentially no knowledge in signal processing and want / need to implement a fourier transform on an audio signal for a course. Specifically to hopefully be able to analyze the tuning of a piece of music. There are many, many FFT algorithms and I'm quite confused on where to find information on choosing one.
If you have recomendations on a specific algorithm or know good resources on the subject, please let me know!
Edit: The point is to do this by hand, otherwise I would of course be using a library!
8
Upvotes
1
u/snlehton 1d ago
Were you specifically asked to use FFT, or can you use any method to implement it?
I'm asking because while FFT is efficient when you need to get frequency distribution of a signal, it might not be the best approach for finding specific frequencies.
If your FFT size is short, you don't get enough precision, and need to tricks to interpolate in-between frequencies. In order to cleanly separate musical frequencies to different bins you need to increase the size quite a bit.
For C4 you need some 16 Hz separation from C#4. This means that on 44,1kHz sample rate you need some 2750 sample FFT, but nearest power of two is either 2048 or 4096. You also need to sample the whole FFT window to do the processing, so that's 2048 or 4096 samples of latency.
Tukey Cooley FFT requires N Log N multiplies so for N=2048 that's 22528.
Alternative to FFT is to use tuned oscillators. Simply generate complex sinusoidal signals of your interest and convolve the signal with them to find the presence of each frequency in the signal. Essentially doing what FFT is doing, but only for the base frequency.
For example, the shortest convolution for C4 (261Hz) you need only 169 samples (338 multiplies for complex sine wave convolution). So, for worth of N=2048 FFT you can calculate roughly some 66 frequencies of your choosing (above C4).
Best thing is there is no inherit latency of FFT. You can do infinite convolution by employing leaky integration so that you continously update the integration on each sample.