Question

According to Goertzel Algorithm, if the computation of DFT is expressed as a linear filtering operation, then which of the following is true?

(a) yk(n)=\(\sum_{m=0}^N x(m)W_N^{-k(n-m)}\)

(b) yk(n)=\(\sum_{m=0}^{N+1} x(m)W_N^{-k(n-m)}\)

(c) yk(n)=\(\sum_{m=0}^{N-1} x(m)W_N^{-k(n+m)}\)

(d) yk(n)=\(\sum_{m=0}^{N-1} x(m)W_N^{-k(n-m)}\)

The question was asked during an online exam.

I would like to ask this question from Linear Filtering Approach to Computation of DFT topic in chapter DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Right option is (d) yk(n)=\(\sum_{m=0}^{N-1} x(m)W_N^{-k(n-m)}\)

The best explanation: Since WN^-kN = 1, multiply the DFT by this factor. Thus

X(k)=WN^-kN\(\sum_{m=0}^{N-1} x(m)W_N^{-km}=\sum_{m=0}^{N-1} x(m)W_N^{-k(N-m)}\)

The above equation is in the form of a convolution. Indeed, we can define a sequence yk(n) as

yk(n)=\(\sum_{m=0}^{N-1} x(m)W_N^{-k(n-m)}\)