0
$\begingroup$

I heard about Fast Fourier Transform can decompose any waves.

But it seems like it was hitting for "all frequencies", namely, n HAVE TO be from 0 to N-1!

What if I want to decompose the wave into the frequencies I want!?

Such as, for example, 5Hz, 14Hz, 37Hz, 42Hz, 59Hz, etc.!?

Is there any algorithm that could do the job!?

PS. My understanding of FFT is from Google, and the degree of understanding is VERY limited! So PLEASE forgive me for my lack of knowledge and any stupid comments!

$\endgroup$
  • $\begingroup$ If you apply the method in my answer to a signal using frequencies of 0Hz, 1Hz, 2Hz, 3Hz, 4Hz, 5Hz, 6Hz, and 7Hz with a sampling rate of eight samples per second for a duration of a second (don't include the trailing point), you will have done the equivalent of an eight point DFT. $\endgroup$ – Cedron Dawg Dec 14 '19 at 16:24
  • $\begingroup$ Got it! Much appreciated! $\endgroup$ – PiggyChu001 Dec 14 '19 at 17:05
  • $\begingroup$ Great, glad to hear it. If you aren't that comfortable with complex numbers you may want to check out two of my blog articles: dsprelated.com/showarticle/754.php and dsprelated.com/showarticle/1238.php. $\endgroup$ – Cedron Dawg Dec 14 '19 at 17:13
1
$\begingroup$

If you have a mixed signal of various known frequencies, the Goertzel answer mentioned above will you correct values only if you have chosen a frame size which has a whole number of cycles for each frequency. Otherwise, if the frequencies are spread far enough apart you will get an approximation. In general, you need to work harder than that to get the correct values.

To simplify, this example will use two of your frequencies, and I'll keep it real (as in not complex).

First you have to construct a cosine (C) and sine (S) signal (vector) for each frequency the length of your frame. Then you want to find the best fit solution to:

$$ x = a_5 C_5 + b_5 S_5 + a_{14} C_{14} + b_{14} S_{14} $$

Where $x$ is your signal as a vector. The $C$s and $S$s are called basis vectors. Dot your signal with each of them:

$$ \begin{aligned} C_5 \cdot x &= a_5 C_5 \cdot C_5 + b_5 C_5 \cdot S_5 + a_{14} C_5 \cdot C_{14} + b_{14} C_5 \cdot S_{14} \\ S_5 \cdot x &= a_5 S_5 \cdot C_5 + b_5 S_5 \cdot S_5 + a_{14} S_5 \cdot C_{14} + b_{14} S_5 \cdot S_{14} \\ C_{14} \cdot x &= a_5 C_{14} \cdot C_5 + b_5 C_{14} \cdot S_5 + a_{14} C_{14} \cdot C_{14} + b_{14} C_{14} \cdot S_{14} \\ S_{14} \cdot x &= a_5 S_{14} \cdot C_5 + b_5 S_{14} \cdot S_5 + a_{14} S_{14} \cdot C_{14} + b_{14} S_{14} \cdot S_{14} \end{aligned} $$

These equations can be put into convenient matrix form:

$$ \begin{bmatrix} C_5 \cdot x \\ S_5 \cdot x \\ C_{14} \cdot x \\ S_{14} \cdot x \end{bmatrix} = \begin{bmatrix} C_5 \cdot C_5 & C_5 \cdot S_5 & C_5 \cdot C_{14} & C_5 \cdot S_{14} \\ S_5 \cdot C_5 & S_5 \cdot S_5 & S_5 \cdot C_{14} & S_5 \cdot S_{14} \\ C_{14} \cdot C_5 & C_{14} \cdot S_5 & C_{14} \cdot C_{14} & C_{14} \cdot S_{14} \\ S_{14} \cdot C_5 & S_{14} \cdot S_5 & S_{14} \cdot C_{14} & S_{14} \cdot S_{14} \end{bmatrix} \begin{bmatrix} a_5 \\ b_5 \\ a_{14} \\ b_{14} \end{bmatrix} $$

Then it is simply a matter of multiplying both sides with the inverse of the square matrix:

$$ \begin{bmatrix} a_5 \\ b_5 \\ a_{14} \\ b_{14} \end{bmatrix} = \begin{bmatrix} C_5 \cdot C_5 & C_5 \cdot S_5 & C_5 \cdot C_{14} & C_5 \cdot S_{14} \\ S_5 \cdot C_5 & S_5 \cdot S_5 & S_5 \cdot C_{14} & S_5 \cdot S_{14} \\ C_{14} \cdot C_5 & C_{14} \cdot S_5 & C_{14} \cdot C_{14} & C_{14} \cdot S_{14} \\ S_{14} \cdot C_5 & S_{14} \cdot S_5 & S_{14} \cdot C_{14} & S_{14} \cdot S_{14} \end{bmatrix}^{-1} \begin{bmatrix} C_5 \cdot x \\ S_5 \cdot x \\ C_{14} \cdot x \\ S_{14} \cdot x \end{bmatrix} $$

So, for each frequency you have an $a$ and $b$ value. Your 5Hz component will be $ a_5 C_5 + b_5 S_5 $.

You can use the following to convert that into a phase and amplitude.

$$ A \cos( \omega t + \phi ) = A \cos( \omega t ) \cos( \phi ) - A \sin( \omega t ) \sin( \phi ) $$

From there, match:

$$ a = A \cos( \phi ) $$ $$ b = -A \sin( \phi ) $$

Which leads to:

$$ A = \sqrt{ a^2 + b^2 } $$

$$ \phi = \operatorname{atan2}(-b,a) $$

This is how a DFT actually works. When you select basis vectors that are a whole number of cycles, the square matrix turns out to be a multiple of the identity matrix and thus the inverse is trivial.

The Goertzel gives you a method of calculating $C_n \cdot x$ and $S_n \cdot x$ on the fly.

| improve this answer | |
$\endgroup$
  • $\begingroup$ In the case of 5Hz, will the ω be 1/5!? $\endgroup$ – PiggyChu001 Dec 14 '19 at 14:31
  • $\begingroup$ @PiggyChu001 If your units of time (t) are seconds, then for 5Hz, $\omega = 5 \cdot 2\pi$, so that for every second you are generating five cycles. When you pick a sampling rate $f_s$, then you get $n = t \cdot f_s$ or $t = \frac{n}{f_s}$. $\endgroup$ – Cedron Dawg Dec 14 '19 at 14:42
  • $\begingroup$ OK... thanks! So the C5 and S5 in your matrix is essentially cos(10πt) and sin(10πt)!? $\endgroup$ – PiggyChu001 Dec 14 '19 at 15:04
  • $\begingroup$ @PiggyChu001 Yes, and when you build your arrays in code, the $n$ is the array index and $t$ can be calculated from that. $\endgroup$ – Cedron Dawg Dec 14 '19 at 15:22
  • $\begingroup$ OK, I "think" I got it! Thanks trillions! $\endgroup$ – PiggyChu001 Dec 14 '19 at 15:58
2
$\begingroup$

You could use the Goertzel algorithm to compute the discrete Fourier transformation for just the frequencies you want to detect.

The Goertzel algorithm is used to detect single bins from the DFT. You implement a bunch of them, each set to one of your desired frequencies, and calculate them for each audio sample.

Anything that doesn't fit your selected bins is ignored. If you implemented it for the frequencies given in your example (5Hz, 14Hz, 37Hz, 42Hz, and 59Hz) but your audio was a sine wave at 100Hz, then your software could not detect that 100Hz signal.

The Goertzel algirithm can be "tuned" to make the bins narrower. You would probably need to do that to separate the frequencies given in your example. They are very close together, so you would need to use very large $N$ to calculate the coefficients for each bin. This has the side effect of making the algorithm respond slowly - quickly changing frequencies would not be detected properly.

| improve this answer | |
$\endgroup$
0
$\begingroup$

When the number of frequencies that you are interestedin is much less than computed by the FFT / DFT, then instead you can try the Goertzel algorithm for efficient computation of a single frequency.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.