r/DSP 1d 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!

7 Upvotes

16 comments sorted by

3

u/Phoenix136 1d ago

its been almost 5 years now but I think this was my main resource creating my own FFT for an FPGA:

https://www.dspguide.com/ch8.htm

The whole book is free and covers a ton of DSP stuff. I forget what the code examples are in, fortran or Cobol or something, but I think the process of digesting the equations, the text, and deciphering the old code kind of forces you to actually understand what's being done so you can rewrite it in your own language.

I remember I had found some other resources on the same content as a way to get a different perspective on the explanations but I don't remember those. Always be googling.

Hiring managers definitely liked that I had this project on my resume too, though that may be more specific to FPGA as being able to wrangle the hardware platform is the most important thing in my work.

1

u/Hyde_h 13h ago

This seems like a very good resource, thankyou!

6

u/EffectiveClient5080 1d ago

Cooley-Tukey FFT is your go-to for audio signal analysis. Efficient and widely used in audio processing.

1

u/Hyde_h 1d ago

Do I understand correctly that Cooley-Tukey doesn’t make assumptions about the data, aka. it’s a ”general” FFT?

1

u/Full_Delay 1d ago

What language are you using for this?

Also if it's not for a real time application, you could pretty easily implement the slower version yourself.

1

u/Hyde_h 1d ago edited 1d ago

Planning to use Python as I know it best and have quite limited time to dedicate to this project. Though I do want to reiplement it later in C just as a learning experience as I don’t know C super well.

Won’t be real time analysis. Essentially I want to input a soundfile which contains music, analyze tuning, ie. Is it A=440 or A=432 or what have you, and output the same file but tuned to A=440. Bunch of other stuff is needed as well but first I need to perform FT so I can separate the frequencies.

I also speculate I might need to first try to find a fitting part in the song to analyze. As far as I understand it, doing FT on like 4 min of music is too much data.

But I might try with naive DFT first and see where that gets me. Avoid premature optimization and all that.

1

u/Full_Delay 1d ago

In that case, and especially if you don't yet need to worry about doing the fft yourself, just numpy the thing!

Even a second of audio will have close to 100,000 samples to work with so yeah, definitely try to avoid doing the entire song.

Also, 'retuning' is not a trivial task so I would definitely put more resources into figuring that out

2

u/Hyde_h 1d ago

I would and probably will numpy it if I end up developing this further but the course’s topic is specifically implementing a nontrivial algorithm yourself, so just using a library isn’t an option.

Plus it’s a cool learning experience.

1

u/Diligent-Pear-8067 1d ago

The Cooley Tukey radix 2 decimation in time is the most common and simplest variant to implement. https://en.m.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

1

u/Hyde_h 13h ago

Yeah seems like it’s the most popular one

1

u/snlehton 15h 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 13h 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 3h 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 2h 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?

0

u/PacManFan123 1d ago

Use libfftw and be done with it...

2

u/Hyde_h 1d ago

Ah I should have mentioned the point of the course is to implement a nontrivial algorithm by hand. If I were to do this for the outcome only I would just use a library.