Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sometimes the forward DFT is defined with a negative exp, sometimes with a positive and occasionally, including the 1/N term. I see this all over the place online. I don't see how the forward and the reverse are equivalent, at minimum they have opposite exponential signs and a 1/N factor for the inverse DFT.

What's the deal?

Thanks Math.stackexchange :)

share|improve this question
    
They are never the same if the authors are not making a mistake. But you have to check their initial assumptions. Do they assume the sampling freq. in Hz or rad/s. Are they normalizing or not? These kind of nonstandard stuff cause different presentations of the material. Just derive one time and one time for all and try to obtain the rest by yourself. But you will never get the sign change in the exponential at least that part is settled as a convention. –  user13838 Aug 17 '11 at 21:21
    
Great response, thank you. Yes, I have derived it myself and settled on my own convention, it's simply frustrating. When you say "But you will never get the sign change in the exponential...", are you saying that DFT and DFT^-1 are both exp(+)? –  nick_name Aug 17 '11 at 21:26
    
Oh no, sorry maybe I got it wrong. If you are asking why the inverse DFT has a sign change in the exponential, then the story is different. But keep in mind that it is essentially the same with the continuous version. Just plug in the forward DFT definition into the inverse DFT definition and you can see that it is clever to define that way. –  user13838 Aug 17 '11 at 21:35
    
Man, now I see what you mean. Excuse my stupidity. I forgot to mention that the inverse DFT can have a negative sign or positive because the signal is usually real valued. Hence the resulting DFT is symmetric with respect to zero. Therefore the sum doesn't change if you start from the left or right. –  user13838 Aug 17 '11 at 21:39
    
There we go! Thanks for the insightful response. :) –  nick_name Aug 18 '11 at 7:55
show 1 more comment

2 Answers

up vote 3 down vote accepted

Simply convention. Wikipedia seems to get it quite right:

... the normalization factor multiplying the DFT and IDFT (here 1 and 1/N) and the signs of the exponents are merely conventions, and differ in some treatments. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be 1/N.

A normalization of $1/\sqrt{N}$ for both the DFT and IDFT makes the transforms unitary, which has some theoretical advantages, but it is often more practical in numerical computation to perform the scaling all at once as above (and a unit scaling can be convenient in other ways).

(The convention of a negative sign in the exponent is often convenient because it means that X_k is the amplitude of a "positive frequency" 2πk / N. Equivalently, the DFT is often thought of as a matched filter: when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1.)

Regarding the last paragraph about exponent signs, it means that the common convention of having negative exponents in the DFT (which might appear a little unnatural) sounds natural when we think our signal as a juxtaposition (linear combination) of sinusoids (complex exponentials), which is the same as writing the IDFT equation (which, in this convention will have positive exponents) :

$$x[n] = \sum_k X(k) \; \exp{(i 2 \pi k n /N)}$$

so, $X(k)$ is the "weight" associated with the sinusoid of frequency $k$. (In other words, the convention seems more natural when we think in terms of synthesis rather than analysis.)

Regarding the normalization factor: The convention is less universal here, in my experience. I actually tend to divide by $N$ in the DFT, so that the fourier transform at frequency zero gives me the average value of the signal ("DC component"). It's true that using $1/\sqrt{N}$ makes everything more mathematically elegant (DFT is a unitary transform, and the inverse is just the Hermitian transpose), but it's also true this is seldom useful in numerical work.

share|improve this answer
    
It might prove illustrative if somebody shows an instance where the convention is to have "-" for the forward transform, and another instance where "+" is the forward transform. That being said, the convention I'm used to has "-" as the forward transform. Mathematica is the only system I've seen so far that conventionally normalizes by $\frac1{\sqrt N}$... –  J. M. Aug 29 '11 at 1:40
    
Actually, I don't recall + for the forward transform in the usual context of the transform (time <-> frecuency). In other contexts, one might argue that, in probability, the "characteristic function" is a forward Fourier transform with positive exponent, for example. en.wikipedia.org/wiki/… –  leonbloy Aug 29 '11 at 1:59
1  
Putting the 1/N factor on the inverse DFT is convenient for computing convolution using the frequency domain. Otherwise you'd have to track the number of 1/N terms multiplied and scale accordingly. Also, 1/N corresponds to Δf in the Riemann sum approximation of the inverse Discrete-Time Fourier Transform (DTFT). –  eryksun May 11 '12 at 4:15
add comment

Not using a negative exp in the definition of the forward DFT is a really bad idea. I know that Numerical Recipes uses a positive exp, but it's still a bad idea. I fear that most uses of the positive exp can be traced to be influenced by Numerical Recipes (*).

Whether you include the 1/N term in the forward or backward transform or not at all is really just a convention. There are at least two good reasons to not include the 1/N term:

  1. The FFTW library is a de facto reference implementation of the FFT, and it doesn't include the 1/N term.
  2. It would be unclear whether it should be included in the forward or backward transform, and hence a constant source of confusion.

Another reason in favor of not including the 1/N term is that it has become common practice (**) to define the (continuous) Fourier transform in a way that no normalization factors are needed (by using the frequency $\xi$ instead of the angular frequency $\omega$):

$\hat{f}(\xi) = \int_{-\infty}^{\infty} f(x)\ e^{- 2\pi i x \xi}\,dx$

$f(x) = \int_{-\infty}^{\infty} \hat{f}(\xi)\ e^{2 \pi i x \xi}\,d\xi$

So omitting the 1/N term from the DFT makes the definition look more similar to the continuous case. However, I have to admit that I have the habit of including the 1/N factor in the forward transform, because then the DFT of a constant function is independent of N.

(*) You probably don't believe me ("It's just a convention, why should it matter?"), but I recently googled for NFFT (nonequispaced FFT) and read some of the related papers. One of the authors used the positive exp in his thesis, but changed to the negative exp in later papers and presentations. While reading one of his later presentations, I was surprised by the amount of sign mistakes and surprising differences in sign conventions between closely related definitions.

(**) I think this change must have occurred only in the last few years. Wikipedia claims that the mathematics literature always used the "frequency convention" and only the physics literature used the "angular frequency convention", but this doesn't match with my own experience.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.