0
$\begingroup$

I am having some troubles understanding the algorithm.

My algorithm looks like this.

enter image description here

  1. how come am i able to compute the DFT coefficient using this algoritm. As far as i know $$ X[k] = \sum_{i=0}^{N-1}x(n)W_N^k $$

which using Goertzel is the same as $$X(k) = y_k(N) $$ and since $$y_k(n) = v_k(n) -W_n^kv_k(n-1)$$ and $$v_k(n) =2cos(\frac{2 \pi k}{N}v_k(n-1)-v_k(n-2)+x(n)$$ which means $$X(k) = y_k(N) = v_k(N) -W_n^kv_k(N-1)$$ which isn't the same as $$X[k] = \sum_{i=0}^{N-1}x(n)W_N^k$$ ??

  1. how come is Goertzel using $$|X(k)^2|$$ to compute the amplitude spectrum, where DFT uses $$|X(k)|$$ to compute the amplitude spectrum. ??
$\endgroup$
2
$\begingroup$

It looks to me as if you are asking two completely separate questions here.

First question: Indeed the two formulas aren't identical; it isn't obvious that the Goertzel algorithm computes what it does. You can find a sketchy proof based on the $z$-transform on the Wikipedia page about the Goertzel algorithm, or you can do a more direct proof by mathematical induction. Or you can just take it on trust -- for most practical purposes all that matters is that it does what it does, rather than why.

Second question:

With both the Goertzel algorithm and the complete DFT, |X|^2 is the power at a particular frequency. This is a sensible thing to compute because, e.g., when you do a DFT the sum of all the powers (|Fourier coefficients|^2) equals the total power in the signal (= sum of |signal values|^2, up to a normalizing constant factor).

If the frequency you're using is one of the ones processed by a DFT, the output of the Goertzel algorithm is (aside from "numerical" considerations like roundoff error) exactly the same as one bin of the DFT.

$\endgroup$
1
$\begingroup$

In your initial formula, you should observe that $W_N^k+W_N^{-k}=2\cos(2\pi\tfrac{k}{N})$ and, by definition of the powers, $W_N^k\cdot W_N^{-k}=1$. Thus the denominator factors as

$$(1-2\cos(2\pi\tfrac{k}{N})z^{-1}+z^{-2})=(1-W_N^kz^{-1})(1-W_N^{-k}z^{-1})$$

and the first factor cancels against the numerator. Thus

$$\frac1{1-W_N^{-k}z^{-1}}=\sum_{j=0}^\infty W_N^{-kj}z^{-j}$$

remains, the application to a signal gives the desired Fourier coefficient at the $N$th position, i.e., with index $N-1$.

The whole point of the complication of the Goertzel algorithm is that the computation of the filtered signal for any real valued input signal can be kept in the real numbers until the last step. And even then the computation of the complex results can be avoided if only the amplitude is desired.

Of course, you chose the right power of the norm or adapt the threshold value to avoid square roots.

$\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.