Question

If g(n) is a real valued sequence of 2N points and x1(n)=g(2n) and x2(n)=g(2n+1), then what is the value of G(k), k=N,N-1,…2N-1?

(a) X1(k)-W2^kX2(k)

(b) X1(k)+W2^kNX2(k)

(c) X1(k)+W2^kX2(k)

(d) X1(k)-W2^kNX2(k)

This question was posed to me by my school principal while I was bunking the class.

Asked question is from Applications of FFT Algorithms in section DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Right answer is (d) X1(k)-W2^kNX2(k)

To elaborate: Given g(n) is a real valued 2N point sequence. The 2N point sequence is divided into two N point sequences x1(n) and x2(n)

Let x(n)=x1(n)+jx2(n)

=> X1(k)=\(\frac{1}{2} [X*(k)+X*(N-k)]\) and X2(k)=\(\frac{1}{2j} [X*(k)-X*(N-k)]\)

We know that g(n)=x1(n)+x2(n)

=>G(k)=X1(k)-W2^kNX2(k), k=N,N-1,…2N-1.