10
$\begingroup$

In MATLAB, the outputs of the fft and/or ifft functions often require additional processing before being considered for analysis.

I have heard many differing opinions on what is correct:

  • Scaling

    Mathworks states that fft and ifft functions are based on the following equations: \begin{align} X[k] &= \frac{1}{1} \cdot \sum_{n=1}^{N} x[n] \cdot e^{\frac{-j \cdot 2 \pi \cdot (k-1) \cdot (n-1)}{N}}, \quad\textrm{where}\quad 1\leq k\leq N\\ x[n] &= \frac{1}{N} \cdot \sum_{k=1}^{N} X[k] \cdot e^{\frac{+j \cdot 2 \pi \cdot (k-1) \cdot (n-1)}{N}},\quad \textrm{where}\quad 1 \leq n\leq N \end{align}

  • Scaling by signal length

    My peers typically scale the data by $\small \frac{1}{N}$ immediately after the processing the fft.
    (We do not consider the raw fft data before scaling.)

    %% Perform fft
    X_f = fft(x, n_sample, 1) / n_sample; % fft must be normalized by the number of samples in the data. % This convention was set by the software developer (Mathworks).

    Is this correct?

    1. If so, why does the MATLAB ifft function expect that we have not scaled by $1/N$ already?
    2. Is there a MATLAB ifft function or function option which does not automatically scale by $1/N$?

    Alternatively, is there a better convention which we should be using in placing the $1/N$? For example, placing the $1/N$ in the fft rather than the ifft, or placing an $1/\sqrt{N}$ in both equations, instead of an $1/N$?

  • Scaling by sampling period

    I have heard that the fft and ifft functions assume that the sampling period $T_{\rm sampling} = 1/f_{\rm sampling} = 1$, and that for the functions to be true, the following would need to apply:

\begin{align} X[k] &= \frac{1}{T_{\rm sampling}} \cdot \sum_{n=1}^{N} x[n] \cdot e^{\frac{-j \cdot 2 \pi \cdot (k-1) \cdot (n-1)}{N}},\quad \textrm{where}\quad 1 \leq k \leq N\\ x[n] &= \frac{T_{\rm sampling}}{N} \cdot \sum_{k=1}^{N} X[k] \cdot e^{\frac{+j \cdot 2 \pi \cdot (k-1) \cdot (n-1)}{N}},\quad\textrm{where}\quad 1 \leq n \leq N \end{align}

See links:

  • Link 1 (see comment to Matt Szelistowski by Dr Seis)
  • Link 2 (see answer by Rick Rosson vs that of Dr Seis)
  • Link 3 (see comment by Matt (Message: 7/16) and comment by Poorya (14/16)
  • Link 4 (see pg. 10, slide [1,1])
  • Link 5 (see pg. 8+9) [it seems he is using inverse convention for fft and ifft].

Is this true?

I'm particularly piqued because I cannot find any DFT or DTFT equations on Wikipedia which include the sampling period.

$\endgroup$
  • 2
    $\begingroup$ BTW, kando is just stating it as it is (with MATLAB): $$\begin{align} X[k] &= \sum_{n=1}^{N} x[n] \cdot e^{\frac{-j 2 \pi (k-1)(n-1)}{N}}, \quad\textrm{where}\quad 1\le k\le N\\ x[n] &= \frac{1}{N} \cdot \sum_{k=1}^{N} X[k] \cdot e^{\frac{+j 2 \pi (k-1)(n-1)}{N}},\quad \textrm{where}\quad 1 \le n\le N \end{align}$$ but i have to say that this hardwired convention of MATLAB to put DC into bin #1 (or the amplitude of frequency component $k$ into bin $k+1$) drives me fucking nutz!!!! $\endgroup$ – robert bristow-johnson Jul 6 '16 at 18:49
6
$\begingroup$

Whether or not to scale the forward FFT by 1/N depends on which result you want for further analysis: energy (preserving Parseval's identity), or amplitude (measuring height or volts, etc.).

If you want to measure or analyze energy, then don't scale by 1/N, and a longer sinusoid of the same amplitude will produce a larger FFT result, proportional to the greater energy of a longer signal.

Slightly more commonly, if you want to measure or analyze amplitudes, then to get a longer sinusoid (thus with more total energy at the exact same amplitude) to produce about the same FFT result as a shorter signal, you will need to scale down the FFT summation by an ratio proportional to the length. The ratio could be reference_length/N, which is sometimes 1/N if the system input gain is 1.0 for whatever dimensions or units, including the time interval dimensions, that you choose to use in your further analysis. You need to scale down proportionally because a DFT is a summation: the more you sum up similar items, the bigger the result.

So. Energy or amplitude. Which do you want?

Now if you scale down the forward FFT, then you should not scale the inverse so that IFFT(FFT(x)) == x. Or do vice versa.

The 1/sqrt(N) for scaling seems to me to be for either when one needs a formal symmetry for some proof, or when building some sort of hardware pipeline where the latency and/or number of arithmetic units/gates for the DFT and for the IDFT needs to be identical. But you get neither a good direct measurement of either energy or amplitude for any typical type of engineering analysis.

$\endgroup$
  • $\begingroup$ When you say "if you want to measure energy, then don't scale by $1/N$"... wouldn't I need to scale by $1/\sqrt N$ so that the transform is unitary and preserves energy? Or is it because I need to square the whole signal to get the energy which yields $1/N$ effectively? If that's true, however, what is the spectrum scaled by $1/\sqrt N$ actually showing me then? $\endgroup$ – LCsa Aug 24 '17 at 9:59
  • $\begingroup$ Additionally,when saying "thus with more energy at the exact same amplitude"...wouldn't you rather mean "frequency"? $\endgroup$ – LCsa Aug 24 '17 at 10:09
6
$\begingroup$

The scaling convention used by Matlab is common in DSP. You could also use the unitary DFT where both the DFT and the IDFT are scaled by a factor of $1/\sqrt{N}$. You could also use the factor $1/N$ for the DFT and the factor $1$ for the IDFT. As long as you're consistent it doesn't really matter (apart from numerical considerations, especially when using fixed-point implementations). So there are no "better" conventions, there are just "conventions", and you just need to agree on which one you use.

The comment

% fft must be normalized by the number of samples in the data.
% This convention was set by the software developer (Mathworks).

is wrong. Nobody says that you must normalize the result of the FFT. If you want to you're free to do it.

Also, the FFT doesn't assume anything about the sampling period $T$. Note that the DFT can be used for data that are discrete by nature without any sampling involved. Depending on your data and on what you want to do with the result, you must take $T$ into account accordingly. E.g., if you want to use the DFT (implemented by the FFT) to approximate the continuous-time Fourier transform, you get the following expression:

$$X\left(\frac{2\pi k}{NT}\right)\approx T\sum_{n=0}^{N-1}x(nT)e^{-j2\pi kn/N},\quad 0\le k< N\tag{1}$$

where $T$ is the sampling period, $N$ is the DFT length, $x(t)$ is the continuous-time signal, and $X(\omega)$ is its continuous-time Fourier transform. The right-hand side of $(1)$ is just the DFT of $N$ samples of $x(t)$, scaled by $T$, where we assume that the relevant part of $x(t)$ is in the range $t\in [0,NT]$. More details about using the DFT for approximating the continuous-time Fourier transform can be found in this answer.

$\endgroup$
  • 2
    $\begingroup$ What's the downvote for? Please comment. $\endgroup$ – Matt L. Jul 6 '16 at 19:34
  • 1
    $\begingroup$ i usually vote by secret ballot, but i'll make an exception this time. depending on what one is doing with the DFT, there are certainly "better" conventions than others. (but no convention is better than the others in all circumstances.) $\endgroup$ – robert bristow-johnson Jul 6 '16 at 20:22
5
$\begingroup$

particularly since this is a question about convention, i will not reinforce the ridiculous convention of MATLAB and will answer only with the right and proper convention or conventions. i.e. MATLAB's indexing for the DFT is not right and proper, but i am pretty much agnostic about the which of the three common scaling conventions.

also, i am not restricting $0 \le n < N$ nor $0 \le k < N$, they can be any integers because i am pretty much fascistic about the fundamental meaning of the Discrete Fourier Transform: The DFT and the Discrete Fourier Series are one and the same. The DFT maps a periodic sequence $x[n]$ with period $N$ to another periodic sequence $X[k]$ also with period $N$ and the iDFT maps it back.

so $$ x[n+N] = x[n] \quad\quad \forall \ n \in \mathbb{Z} $$ $$ X[k+N] = X[k] \quad\quad \forall \ k \in \mathbb{Z} $$

also, circular convolution in either the "time domain" ($x[n]$) or "frequency domain" ($X[k]$) are defined consistently with all conventions:

$$ h[n] \circledast x[n] \triangleq \sum_{i=0}^{N-1} h[i] x[n-i] = \sum_{i=0}^{N-1} x[i] h[n-i] $$ $$ W[k] \circledast X[k] \triangleq \sum_{i=0}^{N-1} W[i] X[k-i] = \sum_{i=0}^{N-1} X[i] W[k-i] $$

so the only advantage of one convention over the other (assuming both conventions are valid) can be regarding simplicity of expression of some of the theorems.


the most common scaling convention for the DFT:

$$ \begin{align} \mathcal{DFT}\{x[n]\} & \triangleq X[k] \triangleq \sum_{n=0}^{N-1} x[n] \, e^{-j 2\pi kn/N} \\ \mathcal{iDFT}\{X[k]\} & \triangleq x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] \, e^{+j 2\pi kn/N} \\ \end{align} $$

has the advantage of simplicity regarding circular convolution in the "time domain"

$$ \mathcal{DFT}\{h[n] \circledast x[n]\} = H[k] \cdot X[k] $$

but there is a scaling factor you have to worry about if you're convolving in the "frequency domain":

$$ \mathcal{iDFT}\{W[k] \circledast X[k]\} = \frac{1}{N} \cdot w[n] \cdot x[n] $$

Parseval's theorem has a scaling factor to worry about too.

$$ \sum_{n=0}^{N-1} \Big|x[n]\Big|^2 = \frac{1}{N} \sum_{k=0}^{N-1} \Big|X[k]\Big|^2 $$

and the Duality theorem:

$$ \mathcal{DFT}\{X[n] \} = N \cdot x[-k] $$ $$ \mathcal{iDFT}\{x[k] \} = \frac{1}{N} \cdot X[-n] $$


the other common scaling convention for the DFT:

$$ \begin{align} \mathcal{iDFT}\{X[k]\} & \triangleq x[n] \triangleq \sum_{k=0}^{N-1} X[k] \, e^{+j 2\pi kn/N} \\ \mathcal{DFT}\{x[n]\} & \triangleq X[k] = \frac{1}{N} \sum_{n=0}^{N-1} x[n] \, e^{-j 2\pi kn/N} \\ \end{align} $$

has the advantage of being a tiny bit closer, conceptually, to the Fourier series, where $e^{j \omega_k n} \triangleq e^{j (2\pi k/N) n}$ are the Fourier basis functions and $X[k]$ are the Fourier coefficients. so if you're looking at raw time-domain data, $x[n]$, and see a sinusoid with $k$ cycles in the buffer of $N$ samples and with (zero-to-peak) amplitude $A$, that would mean that $\Big|X[k]\Big| = \Big|X[-k]\Big| = \Big|X[N-k]\Big| = \frac{A}{2}$.

it also has more simplicity regarding circular convolution in the frequency domain

$$ \mathcal{iDFT}\{W[k] \circledast X[k]\} = w[n] \cdot x[n] $$

but there is a scaling factor you have to worry about if you're convolving in the time domain:

$$ \mathcal{DFT}\{h[n] \circledast x[n]\} = \frac{1}{N} \cdot H[k] \cdot X[k] $$

Parseval's theorem has a scaling factor to worry about too.

$$ \frac{1}{N} \sum_{n=0}^{N-1} \Big|x[n]\Big|^2 = \sum_{k=0}^{N-1} \Big|X[k]\Big|^2 $$

and the Duality theorem:

$$ \mathcal{DFT}\{X[n] \} = \frac{1}{N} \cdot x[-k] $$ $$ \mathcal{iDFT}\{x[k] \} = N \cdot X[-n] $$


the unitary scaling convention for the DFT is identical in scaling with its inverse and preserves energy across the transform or inverse transform:

$$ \begin{align} \mathcal{DFT}\{x[n]\} & \triangleq X[k] \triangleq \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x[n] \, e^{-j 2\pi kn/N} \\ \mathcal{iDFT}\{X[k]\} & \triangleq x[n] = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} X[k] \, e^{+j 2\pi kn/N} \\ \end{align} $$

convolution in either time domain or frequency domain has the same scaling factor to worry about:

$$ \mathcal{DFT}\{h[n] \circledast x[n]\} = \frac{1}{\sqrt{N}} \cdot H[k] \cdot X[k] $$

$$ \mathcal{iDFT}\{W[k] \circledast X[k]\} = \frac{1}{\sqrt{N}} \cdot w[n] \cdot x[n] $$

but Parseval's theorem has no scaling factor to worry about.

$$ \sum_{n=0}^{N-1} \Big|x[n]\Big|^2 = \sum_{k=0}^{N-1} \Big|X[k]\Big|^2 $$

nor does the Duality theorem:

$$ \mathcal{DFT}\{X[n] \} = x[-k] $$ $$ \mathcal{iDFT}\{x[k] \} = X[-n] $$


$\endgroup$
  • $\begingroup$ When talking about DFT conventions, it's usually only about the scaling factors, not about the non-issue of indexing. If you thought that I was referring to the indexing when I said that that's the common DSP convention, then it was a misunderstanding. Of course I referred to the scaling; the indexing is totally irrelevant, because it has nothing to do with the definition of the DFT (and the scaling has). $\endgroup$ – Matt L. Jul 6 '16 at 20:04
  • $\begingroup$ it's not a fucking "non-issue" when, in MATLAB, you use the max(abs(X)) function to find where a spectral peak is and you forget to subtract 1 from the returned index and you're gonna do math on it. it's an issue. and a sad one at that. the indexing origin has as much to do with the "definition of the DFT" as does scaling. it has to do with what bookkeeping is required or not. $\endgroup$ – robert bristow-johnson Jul 6 '16 at 20:11
  • $\begingroup$ could've been me, but this time it ain't :) But still, I don't agree with the importance you attach to the indexing, but I appreciate that that's personal. Again, no downvote because I appreciate the time you put into the answer. $\endgroup$ – Matt L. Jul 6 '16 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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