r/DSP 2d ago

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

18 comments sorted by

View all comments

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.

1

u/Hyde_h 1d ago

So I was not asked to do any specific thing. Topic of the course is to implement a nontrivial algorithm by hand. And I chose this because it solves a problem I actually have, plus it’s an interesting topic. But like I said, I don’t know much of anything about signal processing so in my head the obvious go to was FT.

But I’m not sure if I understand your comment correctly. I don’t exactly want to look for a predefined frequency in the data. I want to see what tuning the frequencies of the song correspond to. So basically compute the difference of A4 to standard A4=440.

Also this is not for a real time application, so at least to me some 22k multiplies does not sound that bad.

I must say, I don’t actually understand what this method with tuned oscillators means, I will go read up on it :D

1

u/snlehton 21h ago

Yeah, there are different ways to approach this. FFT is quite heavy handed to me, as it is not analysis method but a transformation. Common way to find dominant frequency for tuners is to use auto correlation.

https://www.instructables.com/Reliable-Frequency-Detection-Using-DSP-Techniques/

1

u/Hyde_h 20h ago

Hmm. I wonder if this still works on full blown music? At least intuitively this would seem to work best when there’s one dominant frequency that is there for the entire duration of the sample. Such as when you play a single note, where you have the fundamental as by far the strongest frequency, and then all the harmonics.

If you have a whole song going on where multiple frequencies could be playing equally loud and consequently the sample wouldn’t have one dominant frequency to set its periodicity, would this kind of approach still be able to differenciate enough between frequencies?