DFT Efficient Computation MCQ Quiz – Objective Question with Answer for DFT Efficient Computation

The steps to be done in one of the algorithms of the divide and conquer method is

i) Store the signal column-wise
ii) Compute the M-point DFT of each row
iii) Multiply the resulting array by the phase factors WNlq.
iv) Compute the L-point DFT of each column.
v) Read the result array row-wise.

According to one of the algorithms describing the divide and conquer method, if we store the signal column-wise, then compute the M-point DFT of each row and multiply the resulting array by the phase factors WNlq and then compute the L-point DFT of each column and read the result row-wise.

According to the second algorithm of the divide and conquer approach, if the input signal is stored row-wise, then the result must be read column-wise.

According to the second algorithm of the divide and conquer approach, if the input signal is stored row-wise, then we calculate the L point DFT of each column and we multiply the resulting array by the factor WN^pm.

Let us consider the computation of the N=2v point DFT by the divide and conquer approach. We select M=N/2 and L=2. This selection results in a split of 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), respectively, that is

f1(n)=x(2n)

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

Thus f1(n) and f2(n) are obtained by decimating x(n) by a factor of 2, and hence the resulting FFT algorithm is called a decimation-in-time algorithm.

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)+ WNk F2(k).

We know that F1(k) and F2(k) are periodic, with period N/2, we have

F1(k+N/2) = F1(k) and F2(k+N/2)= F2(k). In addition, the factor WNk+N/2 = -WNk.

Thus we get, X(k+N/2)= F1(k)- WN^k F2(k).

We observe that the direct computation of F1(k) requires (N/2)2 complex multiplications.

The same applies to the computation of F2(k). Furthermore, there are N/2 additional complex multiplications required to compute WN^k. Hence it requires N(N+1)/2 complex multiplications to compute X(k).

The decimation of the data sequence should be repeated again and again until the resulting sequences are reduced to one-point sequences.

For N=2v, this decimation can be performed v=log2N times. Thus the total number of complex multiplications is reduced to (N/2)log2N.

The decimation of the data sequence should be repeated again and again until the resulting sequences are reduced to one-point sequences. For N=2v, this decimation can be performed v=log2N times. Thus the total number of complex additions is reduced to Nlog2N.

In the decimation-in-time FFT algorithm, the input is taken in bit reversal order and the output is obtained in the order.

In the decimation-in-frequency FFT algorithm, the input is taken in order and the output is obtained in the bit reversal order.