21. The following butterfly diagram is used in the computation of __________
A. Decimation-in-time FFT
B. Decimation-in-frequency FFT
C. All of the mentioned
D. None of the mentioned
Answer: A
The above-given diagram is the basic butterfly computation in the decimation-in-time FFT algorithm.
21. FFT algorithm is designed to perform complex operations.
A. True
B. False
Answer: A
The FFT algorithm is designed to perform complex multiplications and additions, even though the input data may be real-valued. The basic reason for this is that the phase factors are complex and hence, after the first stage of the algorithm, all variables are basically complex-valued.
22. If x1(n) and x2(n) are two real valued sequences of length N, and let x(n) be a complex valued sequence defined as x(n)=x1(n)+jx2(n), 0≤n≤N-1, then what is the value of x1(n)?
A. \(\frac{x(n)-x^* (n)}{2}\)
B. \(\frac{x(n)+x^* (n)}{2}\)
C. \(\frac{x(n)-x^* (n)}{2j}\)
D. \(\frac{x(n)+x^* (n)}{2j}\)
Answer: B
Given x(n)=x1(n)+jx2(n)
=>x*(n)= x1(n)-jx2(n)
Upon adding the above two equations, we get
x1(n)=\(\frac{x(n)+x*(n)}{2}\).
23. If x1(n) and x2(n) are two real valued sequences of length N, and let x(n) be a complex valued sequence defined as x(n)=x1(n)+jx2(n), 0≤ n≤ N-1, then what is the value of x2(n)?
A. \(\frac{x(n)-x*(n)}{2}\)
B. \(\frac{x(n)+x*(n)}{2}\)
C. \(\frac{x(n)+x*(n)}{2j}\)
D. \(\frac{x(n)-x*(n)}{2j}\)
Answer: D
Given x(n)=x1(n)+jx2(n)
=>x*(n) = x1(n)-jx2(n)
Upon subtracting the above two equations, we get
x2(n)=\(\frac{x(n)-x*(n)}{2j}\).
24. If X(k) is the DFT of x(n) which is defined as x(n)=x1(n)+jx2(n), 0≤ n≤ N-1, then what is the DFT of x1(n)?
A. \(\frac{1}{2} [X*(k)+X*(N-k)]\)
B. \(\frac{1}{2} [X*(k)-X*(N-k)]\)
C. \(\frac{1}{2j} [X*(k)-X*(N-k)]\)
D. \(\frac{1}{2j} [X*(k)+X*(N-k)]\)
Answer: A
We know that if
x(n)=x1(n)+jx2(n) then
x1(n)=\(\frac{x(n)+x*(n)}{2}\)
On applying DFT on both sides of the above equation, we get
X1(k)=\(\frac{1}{2} {DFT[x(n)]+DFT[x*(n)]}\)
We know that if X(k) is the DFT of x(n), the DFT[x*(n)]=X*(N-k)
=>X1(k)=\(\frac{1}{2} [X*(k)+X*(N-k)]\).
25. If X(k) is the DFT of x(n) which is defined as x(n)=x1(n)+jx2(n), 0≤ n≤ N-1, then what is the DFT of x1(n)?
A. \(\frac{1}{2} [X*(k)+X*(N-k)]\)
B. \(\frac{1}{2} [X*(k)-X*(N-k)]\)
C. \(\frac{1}{2j} [X*(k)-X*(N-k)]\)
D. \(\frac{1}{2j} [X*(k)+X*(N-k)]\)
Answer: C
We know that if x(n)=x1(n)+jx2(n) then
x2(n)=\(\frac{x(n)-x^* (n)}{2j}\).
On applying DFT on both sides of the above equation, we get
X2(k)=\(\frac{1}{2j} {DFT[x(n)]-DFT[x*(n)]}\)
We know that if X(k) is the DFT of x(n), the DFT[x*(n)]=X*(N-k)
=>X2(k)=\(\frac{1}{2j} [X*(k)-X*(N-k)]\).
26. 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)-W2kNX2(k)
B. X1(k)+W2kNX2(k)
C. X1(k)+W2kX2(k)
D. X1(k)-W2kX2(k)
Answer: B
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)+W2kNX2(k), k=0,1,2…N-1.
27. 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)-W2kX2(k)
B. X1(k)+W2kNX2(k)
C. X1(k)+W2kX2(k)
D. X1(k)-W2kNX2(k)
Answer: D
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)-W2kNX2(k), k=N,N-1,…2N-1.
28. Decimation-in frequency FFT algorithm is used to compute H(k).
A. True
B. False
Answer: A
The N-point DFT of h(n), which is padded by L-1 zeros, is denoted as H(k). This computation is performed once via the FFT and the resulting N complex numbers are stored.
To be specific we assume that the decimation-in-frequency FFT algorithm is used to compute H(k). This yields H(k) in the bit-reversed order, which is the way it is stored in the memory.
29. How many complex multiplications are needed to be performed for each FFT algorithm?
A. (N/2)logN
B. Nlog2N
C. (N/2)log2N
D. None of the mentioned
Answer: C
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.
30. How many complex additions are required to be performed in linear filtering of a sequence using FFT algorithm?
A. (N/2)logN
B. 2Nlog2N
C. (N/2)log2N
D. Nlog2N
Answer: B
The number of additions to be performed in FFT are Nlog2N. But in linear filtering of a sequence, we calculate DFT which requires Nlog2N complex additions and IDFT requires Nlog2N complex additions.
So, the total number of complex additions to be performed in linear filtering of a sequence using FFT algorithm is 2Nlog2N.
