Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

[SOLVED] Why divide by N (length of input sequence) during IDFT?

Status
Not open for further replies.

Kaushik Sv

Newbie level 3
Joined
Apr 18, 2014
Messages
4
Helped
1
Reputation
2
Reaction score
1
Trophy points
3
Location
Chennai, India
Activity points
34
Hi folk

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


X(k) = <x[n], e[k, n]>
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 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.

Code:

Thanks.

Kaushik
SMK Fomra Inst of Tech, Chennai
India
 
Last edited:

Kaushik Sv

Newbie level 3
Joined
Apr 18, 2014
Messages
4
Helped
1
Reputation
2
Reaction score
1
Trophy points
3
Location
Chennai, India
Activity points
34
Got it folks. Ok, the reason is:

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

We conveniently divide the net result by √N (ideally). Consider a matrix containing twiddle factors, say W. Assume each column represents a basis vector. For IDFT, we simply need to multiply each freq component's amplitude with corresponding basis vector (complex sine wave), and sum up, thereby reconstructing the original signal. On expanding that product and rearranging, 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 made 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π in just IDFT for simplicity. May be because its simple to divide by N and avoid calculating square root in computer. The beauty is that conj(W) is same at WT, and hence the formula for IDFT remains same as DFT except a change in sign (if you choose to preserve the symmetry)

Hope that helped someone. And do correct me if I'm wrong. Have a great day :)
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top