9
$\begingroup$

I'm wondering why evaluating a sinusoid that matches one of the frequencies of the DFT basis functions has a magnitude of $N / 2$. Using this definition of the Discrete Fourier transform, it looks like this holds (I guess for non-zero $k$ and $N \geq 3$):

$$ \left| \sum_{n=0}^{N - 1} a \cdot \sin \left( 2 \pi \frac{k n}{N} \right) \cdot e^{ -i 2 \pi \frac{k n}{N}} \right| ~=~ a \cdot \frac{N}{2} $$

In other words: Taking the DFT of a sinusoid that exactly matches one of the frequencies used by the DFT results in the corresponding coefficient taking a value of amplitude times half the sample length.

What surprises me about this: The common normalization of the DFT is to divide by $N$, i.e., the full sample length. Therefore my intuitive expectation was that these magnitudes actually are $a \cdot N$ instead of $a \cdot N / 2$.

Is there an intuitive way to see where this factor of $1 / 2$ is coming from?

Bonus question: Why hasn't dividing by $N / 2$ become a standard for normalization? When creating e.g. a periodogram, isn't it a nice property that after normalizing by $N / 2$ one could directly read off the amplitudes of the DFT coefficients? The normalization by $N$ feels awkward in comparison, because one has to double the coefficients to actually obtain their original sinusoidal amplitudes. What am I missing that explains why dividing by $N$ is "better"?

$\endgroup$

3 Answers 3

11
$\begingroup$

The DFT is providing the coefficients of the basis functions given as samples of $e^{j\omega t}$ not cosines or sines. Review the formula for the inverse DFT which shows this relationship:

$$x[n]= \frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{jk \omega_o n}$$

Where $\omega_o= 2\pi f_s/N$ with $f_s$ as the sampling rate.

Given Euler’s formula relating sinusoids and exponentials we see how the 1/2 factor makes sense and why we get two peaks in the DFT result for a sinusoid:

$$\cos(\omega_o n) = \frac{1}{2}e^{j\omega_o n}+ \frac{1}{2}e^{-j\omega_o n}$$

$\endgroup$
2
  • 2
    $\begingroup$ Great first sentence -- it immediately started to make sense from that perspective. Adding an intuition why inserting Eulers formula yields $N / 2$: Basically the terms with the same sign in the exponent $e^{-...} \cdot e^{-...}$ are still distributed uniformly on the unit circle in the complex plane, just with "double the rotation". Due to the uniform distribution their sum becomes 0. The terms with the mixed signs $e^{+...} \cdot e^{-...}$ all become 1, and there are $N$ terms with that factor of $1/2$. $\endgroup$
    – bluenote10
    Jun 13, 2023 at 21:02
  • 1
    $\begingroup$ @bluenote10 Very perceptive of you to immediately see $e^{j\omega t}$ as a spinning phasor with time. Seeing these rotate on a complex plane is very intuitive including "positive and negative frequencies" which is just the direction of rotation ($e^{+j\omega t}$ vs $e^{-j\omega t})$. This also explains why all real time domain waveforms have a complex conjugate spectrum: for every positive rotating freq on the complex plane there is a negative rotating frequency, the sum stays on the real axis! For complex time domain waveforms the positive and negative frequencies are independent. $\endgroup$ Jun 13, 2023 at 22:47
10
$\begingroup$

To add to Dan’s answer, and focus on your “bonus” question:

Keep in mind that DFT normalization/scaling is a matter of convention. Quoting the wikipedia article that you linked to in your question:

The normalization factor multiplying the DFT and IDFT (here 1 and $\frac{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 $\frac{1}{N}$. A normalization of $\sqrt{\frac{1}{N}}$ for both the DFT and IDFT, for instance, makes the transforms unitary.

You should read the documentation of whichever DFT implementation you are using to see which scaling coefficient is being applied (unless you write your own, of course). Similarly to the definition you use in your question, matlab, scipy and numpy do not apply a scaling factor to their forward DFT.

You seem to be interested in keeping the amplitudes intact for analysis. In this case, assuming you're working with real signals, a standard approach is to discard the negative DFT coefficients and scale (i.e. multiply) the positive DFT coefficients $X[k]$ by $2/N$ except for $X[0]$, which should be scaled by $1/N$ (see this answer). As Dan pointed out in the comments, if the DFT length $N$ is even, $X[N/2]$ should also be scaled by $1/N$.

Bottom line, sure, you can divide the coefficients by $N/2$ (equivalent to multiplying by $2/N$), but you'd have to also apply a $1/2$ scaling factor to $X[0]$ (and $X[N/2]$ if $N$ is even) and discard the negative coefficients to stay energy-consistent.

Note: the actual correct scaling factor is $\sum_{i=0}^{N-1} w_i$, where $w$ is the weighting window used before computing the DFT, usually to avoid spectral leakage.
In the case of a rectangular window, this effectively equals $N$.

Here is some Matlab code that performs the aforementioned for both even and odd DFT length cases:

fs = 1000;
T = 1/fs;
L = 1500; % even FFT length
% L = 1501; % odd FFT length
t = (0:L-1)*T;

% create example signal
s = 0.8*sin(2*pi*80*t) + sin(2*pi*400*t) + 1; % two sinusoids + DC component
win = rectwin(L); % window function
x = s .* win'; % window the signal

% length L DFT
X = abs(fft(x,L));

% scale magnitude by the window sum
X = X./sum(win);

% keep positive frequencies
X = X(1:L/2+1); % L even
% X = X(1:(L+1)/2); % L odd

% scale positive frequencies (remember matlab does not have 0-index)
X(2:end-1) = 2*X(2:end-1); % L even: do not scale X[0] AND X[L/2] 
% X(2:end) = 2*X(2:end); % L odd: do not scale X[0]

% frequency vector
f = (0:L/2)*fs/L; % L even
% f = (0:(L-1)/2)*fs/L; % L odd

plot(f, X);
$\endgroup$
0
5
$\begingroup$

The answer lies in the meaning of "negative frequency". It couldn't be any other way but $1/N$ and the resulting $1/2$.

Full article: What is the physical significance of negative frequencies? The shortest most relevant part is a visual:

A misconception is, spectrogram discards phase and isn't invertible. The spectrogram is invertible within a global phase shift - that's strong inversion. One might think, if we overlap the right complex pulse with the left one, and get a symmetric |STFT|, that whether the result is complex-valued depends on the original phases - that is, just like for FFT, symmetric |FFT| doesn't guarantee a real-valued signal. One will find, this is false.

The significance is that negative frequency encodes "spin", or direction of complex rotation, which is an independent degree of freedom, and is fundamental and irreducible. The DFT is a decomposition into complex-, not real-valued, bases, which defines the interpretations of all results. A "real-valued" signal is the result of complex rotations being mirrored for all $t$, canceling along the "imaginary" part and combining along the real. Since real-valuedness requires a combination, and all bases are of equal intensity by design, the only possibility is that each such basis is $1/2$ the intensity of the result.

Mathematically, the DFT inverts by summing various $e^{\pm j 2\pi k n/N}$ (with scalings & phase shifts), and we have the well-known identity

$$ \cos(\omega t) = \frac{1}{2} e^{-j\omega t} + \frac{1}{2} e^{j\omega t} $$

This answer will make more sense after reading the planned followup to what I've linked, which one can be notified of by "Follow"-ing it. It'll also intuitively explain why the general $\cos(\omega t + \phi)$ only changes the phases of cisoids in above equation, but forces conjugate symmetry.

The growth with $N$ reflects growing strength of similarity with the input. That's all the DFT is, a measure of strengths of similarities, and the more samples there are, the more the similarity's been "confirmed". Mathematically, it's a dot product: out[k] = sum(x * basis[k]). Dividing by $N$ normalizes the result, and makes similarities comparable across different $N$: if $N$ is doubled but the $1/N$ result is same (for a given bin), it implies the only difference is in sample count. Indeed, fft([x, x]) simply inserts a zero between each bin of fft(x), for any x, and doubles existing bins: we have "more of the same", and each bin is twice as large, unless we make length a non-factor.

Additional detail expressed in code, also handling windowing, is provided here - it's relevant but optional reading. The most important is negative frequencies (rather, distinction between positives and negatives, neither being special). Lastly, if the "rotation" stuff sounds unfamiliar, I recommend this excellent video: But what is the Fourier transform? A visual introduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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