1. 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.

2. 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}\).

3. 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}\).

4. 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)]\).

5. 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)]\).

6. 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.

7. 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.

8. 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.

9. 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.

10. How many complex additions are required to be performed in linear filtering of a sequence using FFT algorithm?

A. (N/2)logN
B. 2Nlog_{2}N
C. (N/2)log_{2}N
D. Nlog_{2}N

Answer: B

The number of additions to be performed in FFT is Nlog2N. But in linear filtering of a sequence, we calculate DFT which requires Nlog_{2}N 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.