Question

What is the expression to compute yk(n) recursively?

(a) yk(n)=WN^-kyk(n+1)+x(n)

(b) yk(n)=WN^-kyk(n-1)+x(n)

(c) yk(n)=WNkyk(n+1)+x(n)

(d) None of the mentioned

The question was asked in an interview for internship.

My query is from Linear Filtering Approach to Computation of DFT topic in section DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Correct option is (b) yk(n)=WN^-kyk(n-1)+x(n)

The explanation is: We know that hk(n)=WN^-kn u(n)=yk(n)/x(n)

=> yk(n)=WN^-kyk(n-1)+x(n).