1 Crore+ students have signed up on EduRev. Have you? 
FFT algorithm is designed to perform complex operations.
Explanation: 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.
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≤ N1, then what is the value of x2(n)?
Explanation: Given x(n)=x1(n)+jx2(n)
=>x*(n)= x1(n)jx2(n)
Upon subtracting the above two equations, we get x2(n)= (x(n)x*(n))/2j.
If X(k) is the DFT of x(n) which is defined as x(n)=x1(n)+jx2(n), 0≤ n≤ N1, then what is the DFT of x1(n)?
Explanation: We know that if x(n)=x1(n)+jx2(n) then x1(n)= (x(n)+x*(n))/2
On applying DFT on both sides of the above equation, we get
X1(k)= 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*(Nk)
=>X1(k)= 1/2 [X*(k)+X*(Nk)].
If X(k) is the DFT of x(n) which is defined as x(n)=x_{1}(n)+jx_{2}(n), 0≤ n≤ N1, then what is the DFT of x_{1}(n)?
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…N1?
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)= 1/2 [X*(k)+X*(Nk)] and X2(k)= 1/2j [X*(k)X*(Nk)] We know that g(n)= x1(n)+x2(n)
=>G(k)= X1(k)+W_{2}^{k}NX2(k), k=0,1,2…N1.
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,N1,…2N1?
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)= 1/2 [X*(k)+X*(Nk)] and X2(k)= 1/2j [X*(k)X*(Nk)] We know that g(n)= x1(n)+x2(n)
=>G(k)= X1(k)W_{2}^{k}NX2(k), k= N,N1,…2N1.
Decimationin frequency FFT algorithm is used to compute H(k).
Explanation: The Npoint DFT of h(n), which is padded by L1 zeros, is denoted as H(k). This computation is performed once via the FFT and resulting N complex numbers are stored. To be specific we assume that the decimationin frequency FFT algorithm is used to compute H(k). This yields H(k) in the bitreversed order, which is the way it is stored in the memory.
How many complex multiplications are need to be performed for each FFT algorithm?
Explanation: The decimation of the data sequence should be repeated again and again until the resulting sequences are reduced to one point sequences. For N=2^{v}, this decimation can be performed v=log_{2}N times. Thus the total number of complex multiplications is reduced to (N/2)log_{2}N.
How many complex additions are required to be performed in linear filtering of a sequence using FFT algorithm?
Explanation: The number of additions to be performed in FFT are Nlog_{2}N. But in linear filtering of a sequence, we calculate DFT which requires Nlog_{2}N complex additions and IDFT requires Nlog_{2}N complex additions. So, the total number of complex additions to be performed in linear filtering of a sequence using FFT algorithm is 2Nlog_{2}N.
How many complex multiplication are required per output data point?
Explanation: In the overlap add method, the Npoint data block consists of L new data points and additional M1 zeros and the number of complex multiplications required in FFT algorithm are (N/2)log_{2}N. So, the number of complex multiplications per output data point is [Nlog_{2}2N]/L.
32 videos76 docs64 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
32 videos76 docs64 tests








