Question

If we split the N point data sequence into two N/2 point data sequences f1(n) and f2(n) corresponding to the even numbered and odd numbered samples of x(n) and F1(k) and F2(k) are the N/2 point DFTs of f1(k) and f2(k) respectively, then what is the N/2 point DFT X(k) of x(n)?

(a) F1(k)+F2(k)

(b) F1(k)-WN^k F2(k)

(c) F1(k)+WN^k F2(k)

(d) None of the mentioned

I had been asked this question during a job interview.

Enquiry is from Efficient Computation of DFT FFT Algorithms in chapter DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

The correct answer is (c) F1(k)+WN^k F2(k)

Easy explanation: From the question, it is given that

f1(n)=x(2n)

f2(n)=x(2n+1), n=0,1,2…N/2-1

X(k)=\(\sum_{n=0}^{N-1} x(n) W_N^{kn}\), k=0,1,2..N-1

=\(\sum_{n \,even} x(n) W_N^{kn}+\sum_{n \,odd} x(n) W_N^{kn}\)

=\(\sum_{m=0}^{(\frac{N}{2})-1} x(2m)W_N^{2km}+\sum_{m=0}^{(\frac{N}{2})-1} x(2m+1) W_N ^{k(2m+1)}\)

=\(\sum_{m=0}^{(\frac{N}{2})-1} f_1(m) W_{N/2}^{km} + W_N^k \sum_{m=0}^{(N/2)-1} f_2(m) W_{(\frac{N}{2})}^{km}\)

X(k)=F1(k)+ WN^k F2(k).