0
$\begingroup$

During DFT of a input sequence of length N, we find X(k).

We find inner product with a basis vector to get the coefficient:
X(k) = <x[n], e[k, n]>    |  k = 0, 1, 2, ... (N-1)
where e(k, n) = [e-2kπ/N e-2kπ.2/N e-2kπ.3/N ... e-2kπ(N-1)/N ]

For each value of k, I get a coefficient. Similarly I got coefficients for all basis in the vector space.

Now to reconstruct the original signal, isn't it enough to multiply the coefficients with appropriate basis vectors and add them? Why is each element in IDFT(X(k)), N times the original value in x[n]? Why does it need a division by N at the end?

I can't understand this division part intuitively. Sorry if that was a dumb question. Please help me understand this.

Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

Got it folks. Ok, the reason is:

In FFT, we work with orthogonal basis, but the basis vectors are not orthonormal.! Each basis vector has magnitude of √N, the magnitude of each of basis vector. How? Each component of any basis vector is a complex number. Sin2θ + Cos2θ becomes 1 for each component when we do <e(k, n), e(k, n)>. So the magnitude of any basis vector is √[N×1] = √N.

During DFT, find inner product of x[n] with complex sine wave of different frequencies (The basis vectors) to get the constant that says how much of that frequency is present. Then, we should ideally divide the net result by √N, but we don't. Consider a matrix containing twiddle factors, say W. Assume each column represents a basis vector. For IDFT, we simply need scale each frequency component with amplitude indicated by X(k). That is, the basis vector represented by kth column of W needs to be multiplied by X(k), and sum up all the frequencies' contributions to reconstruct the original signal. On expanding that product and rearranging the terms, you'll find it is same as inner product between X(k) and rows of W . Therefore in matrix form it becomes X*WT (X is a column vector and W is N×N; n is row index, k is col index). And finally divide by √N once, because the basis vectors in W are not normalized, and once more by √N if our X(k) was calculated from W which is not normalized. Hence divide just by √N.√N=N while taking IDFT. Some authors prefer to maintain symmetry and divide by √N or √(2π) in case of continuous domain in both DFT and IDFT. Many prefer N or 2π just during IDFT for simplicity. May be because its simple to divide by N and avoid calculating square root in computer. The beauty is that WT is same as W* (complex conjugate of W), and hence the formula for IDFT remains same as DFT except a change in sign of exponent of e (if you choose to preserve the symmetry. Else don't forget to divide by N )

Hope that helped someone.

$\endgroup$
1
  • $\begingroup$ You can also accept this as the answer. It will remove it form the unanswered list and help organize the site better. $\endgroup$ Apr 23, 2014 at 21:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .