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=0,1,2…N-1?

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

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

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

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

The question was asked at a job interview.

The above asked question is from Applications of FFT Algorithms in portion DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

The correct option is (b) X1(k)+W2^kNX2(k)

Easiest explanation: 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=0,1,2…N-1.