by nick_name
Last Updated September 21, 2018 02:20 AM

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 :)

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:

- The FFTW library is a de facto reference implementation of the FFT, and it doesn't include the 1/N term.
- 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.

Simply convention. The Wikipedia gets 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: that means that the common convention of having negative exponents in the DFT (which might appear a little unnatural) looks natural when we think our signal as a juxtaposition (linear combination) of sinusoids (complex exponentials). And this corresponds to 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 that $X(k)$ is the "weight" associated with the sinusoid of frequency $k$. In other words, the convention looks 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 the average value of the signal (the "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 this is seldom useful in numerical work.

- Serverfault Help
- Superuser Help
- Ubuntu Help
- Webapps Help
- Webmasters Help
- Programmers Help
- Dba Help
- Drupal Help
- Wordpress Help
- Magento Help
- Joomla Help
- Android Help
- Apple Help
- Game Help
- Gaming Help
- Blender Help
- Ux Help
- Cooking Help
- Photo Help
- Stats Help
- Math Help
- Diy Help
- Gis Help
- Tex Help
- Meta Help
- Electronics Help
- Stackoverflow Help
- Bitcoin Help
- Ethereum Help