I need to compute Fourier series of an audio stream. But DFT/FFT is slow.
Are there any ways to compute Fourier series of a signal without using the Fourier transform to check if whether a frequency is present or not?
$\begingroup$
$\endgroup$
-
$\begingroup$ Please clarify; the "looping through" refers to what? And you are dealing with DFS or CFS? A mathematical statement is more appreciated if possible. An what is your overal goal, target or expectation in doing this? $\endgroup$ – Fat32 Jun 5 '17 at 15:15
-
$\begingroup$ I've edited the question $\endgroup$ – Juju17ification Jun 5 '17 at 15:29
-
1$\begingroup$ is your audio stream a periodic or quasi-periodic function? why Fourier series? are you looking for a small number of specific frequencies that you know of in advance? there is something like Goertzel's algorithm which works real good for sliding DFT and becomes, essentially, a filter. $\endgroup$ – robert bristow-johnson Jun 5 '17 at 15:37
-
4$\begingroup$ Then I know no faster way to do so than to calculate the FFT. $\endgroup$ – Deve Jun 5 '17 at 16:53
-
1$\begingroup$ are you trying to get a list of discrete frequency components? this is what we call sinusoidal modeling. then it's a matter of what the window function is, and the Fourier transform of the window. you can identify main lobes in the output of the FFT. then you can subtract that frequency component and look for the next lobe. $\endgroup$ – robert bristow-johnson Jun 6 '17 at 2:54
$\begingroup$
$\endgroup$
Make sure you do not mix up FFT and DFT, they gives identical results, but are different. DFT complexity is about $O(N^2)$ while FFT complexity is $\frac{34}{9}N\log_2(N)$. This makes a huge difference is computation time.
I do not know any faster algorithm for computing a complete spectrum than the FFT. If you need a subset of the spectrum (only few frequency bins), you could look at Goertzel Algorithm.
According to wikipedia, as a rule of thumb, Gortzel algorithm will be faster than FFT if : $$ M < \frac{5N_2}{6N}\log_2(N_2)$$
Where
- $M$ : Number of frequency bin you need
- $N$ : Number of point in your dataset
- $N_2$ : The first power of 2 bigger than N.
$\begingroup$
$\endgroup$
If you know the exact number of non-zero sinusoids in the audio stream signal, then you can use parametric methods such as MUSIC or ESPIRIT : http://cnx.org/content/m10588/latest/
