1
$\begingroup$

After an interesting recent answer, I'm doing some research on proper DFT normalization for sinusoidal peak estimation. It's clear that to get the correct amplitude from DFT peaks we need to normalize by the window gain \begin{equation} S_w \triangleq \sum_{n=0}^{N-1} w[k] \end{equation} Which becomes $S_w = N$ for the rect window.

Now I'd like to find some rough demonstration, Harris has one (see equations 12 and 13 in the article below), but he chooses the easiest path by making exponentials cancel out. Well he actually does a pretty good job, it's me that thought it could be inferred to some more general relation.

For the rectangular window I've come up with this. Let's say we have a sampled analytic sinusoidal signal $x[n]$, with frequency of $m/N$ cycles per sample (or $m$ cycles in $N$ samples), and compute the DFT $X[k]$

\begin{equation} x[n] = A \ e^{j 2\pi m n/N} \end{equation}

\begin{align} X[k] & = A\sum_{n=0}^{N-1}e^{j \frac{2\pi n}{N} m} e^{-j \frac{2\pi n}{N} k} \\ \\ & = A\sum_{n=0}^{N-1}e^{-j \frac{2\pi n}{N} (k-m)}\notag \\ \\ & = A \ \dfrac{1-e^{-j2\pi(k-m)}}{1-e^{-j\frac{2\pi}{N}(k-m)}} \\ \\ & = AN\delta \left[ k-m\right] \end{align}

where $\delta[k]$ is the Kronecker delta. To get the correct amplitude in freq space we need to divide by $N$.

Now, let's say we have a windowed signal, let me call it $x[n]$ again

\begin{equation} x[n] = w[n] \ A \ e^{j 2\pi m n/N} \end{equation}

and its transform, again overloading notation

\begin{equation} X[k] = A\sum_{n=0}^{N-1} w[n] e^{-j \frac{2\pi n}{N} (k-m)} \end{equation}

From here I'm not sure how to proceed, guess the result should be $$ \require{cancel}\cancel{X[k] \overset{?}{=} A \ S_w \ \delta[k-m]} $$

Edit: after some discussion with Robert I believe the previous equation is just wrong. It works for the rectangular window only, while for the other windows the only thing we can say is about the peak $k=m$, which can be easily demonstrated just from the sum.

G. Heinzel et al - Spectrum and spectral density estimation by the DFT, including a comprehensive list of window functions and some new flat-top windows

F. J. Harris - On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform

$\endgroup$
  • $\begingroup$ i'm pretty sure that what you mean by "$\delta(n+m)$" is the Kronecker delta, not the Dirac delta. correct? if so, may i edit your question to make use of the most common convention DSP texts (and i think even the IEEE lit) use for discrete-time or discrete-frequency sequences? we use brackets "$x[n]$" instead of subscripts (which we leave for elements of a vector of signals) and instead of parenths (which are for continuous-time or continuous-frequency functions). $\endgroup$ – robert bristow-johnson Jan 22 '16 at 0:30
  • $\begingroup$ i fixed the notation anyway. besides notation, you had a sign reversal regarding the DFT exponent that i also fixed. $\endgroup$ – robert bristow-johnson Jan 22 '16 at 1:29
  • $\begingroup$ Thanks for the edit @robertbristow-johnson, yup you're right's it's Kronecker, mixed continuous and discrete notation. About notation, sorry... different backgrounds, different conventions, I'll try to follow dsp ones in the future. $\endgroup$ – filippo Jan 22 '16 at 2:15
  • $\begingroup$ the last edit you made might be a mistake. i might have screwed it up too. there is a cyclical nature the output of the DFT, namely that $X[k+N] = X[k]$ for all $k$. $\endgroup$ – robert bristow-johnson Jan 22 '16 at 4:05
  • $\begingroup$ Maybe I'm getting confused by dsp kronecker notation, isn't $AN\delta[k-m]$ equivalent to $AN\delta_{km}$? and if so, isn't it correct (let's say we limit ourselves in the $k=0,1\ldots, N-1$ range to avoid confusion)? I guess it is, pretty easy to see from the sum if $k=m$ but it can be also shown from the closed form I believe. See e.g. engineeringproductivitytools.com/stuff/T0001/PT13.HTM $\endgroup$ – filippo Jan 22 '16 at 4:21
1
$\begingroup$

okay, since this is about scaling, i should be anal about definitions.

discrete-time signal: $x[n]$ where $n$ are only integer values.

DTFT: $$ X\left( e^{j\omega} \right) \triangleq \sum\limits_{n=-\infty}^{+\infty} x[n] \ e^{-j \omega n} $$

it is necessarily the case that $ X\left( e^{j(\omega + 2 \pi)} \right) = X\left( e^{j\omega} \right) $ for all real $\omega$.

DFT: $$ \begin{align} X[k] & \triangleq \sum\limits_{n=0}^{N-1} x[n] \ e^{-j 2 \pi \frac{k}{N} n} \\ & = X\left( e^{j\omega} \right) \Bigg|_{\omega=2 \pi \frac{k}{N}} \quad \quad \text{if } x[n] = 0 \text{ for } n<0 \text{ or } n \ge N\\ \end{align} $$

it is also necessarily the case that $X[k+N]=X[k]$ for all integer $k$.

and another fact is that $ X\left( e^{j0} \right) = X(1) = \sum\limits_{n=-\infty}^{+\infty} x[n] $

and $ X[0] = \sum\limits_{n=0}^{N-1} x[n] $

if x[n] is a "low-pass" function, we will expect $X[k]$ to peak at $k=0$. and the value of that peak is shown as $X[0]$ above.

so, now consider a window function $w[n]$ that has DFT defined the same way

$$ W[k] = \sum\limits_{n=0}^{N-1} w[n] \ e^{-j 2 \pi \frac{k}{N} n} $$

normally we think of the window function as always non-negative, $w[n] \ge 0$, but it wouldn't necessarily have to be that. nonetheless, just like $x[n]$, the window function has a DC component:

$$ W[0] = \sum\limits_{n=0}^{N-1} w[n] \triangleq S_w $$

and the DFT of the window function must also be periodic, $W[k+N] = W[k]$, for all integer $k$.


now there is a "translation property" of all forms of the Fourier Transform that has a particular expression for the DFT:

$$ \begin{align} \text{DFT} \left\{ x[n] e^{j 2 \pi \frac{m}{N}} \right\} & = \sum\limits_{n=0}^{N-1} \left( x[n] e^{j 2 \pi \frac{m}{N}} \right) \ e^{-j 2 \pi \frac{k}{N} n} \\ & = X[k-m] \\ \end{align} $$

for $m$ equal to an integer.

same applies for $w[n]$ with an amplitude scaling factor of $A$.

$$ \begin{align} \text{DFT} \left\{ w[n] \ A e^{j 2 \pi \frac{m}{N}} \right\} & = \sum\limits_{n=0}^{N-1} \left( w[n] \ A e^{j 2 \pi \frac{m}{N}} \right) \ e^{-j 2 \pi \frac{k}{N} n} \\ & = A \ W[k-m] \\ \end{align} $$


now we do expect the window function to be a "low-pass" function. that's how we design them, so we also expect $W[k]$ to peak at $k=0$ (or any other integer multiple of $N$) and we expect the expression above to peak when $k-m=0$ (or $k=m$) and the value of that peak is

$$ A \ W[0] = A \ S_w $$

so if $A$ is the amplitude we're trying to find, we would take the value of the peak, wherever $k=m$, and divide that value by $S_w$ to get the amplitude of the complex sinusoid.

it's as simple as that, but it is also shown to be too simple. we know that a real sinusoid is the sum of two complex sinusoid, so there will be overlapping interference (a.k.a. "leakage") of one onto the other. we also expect that the frequency will not be exactly an integer number of cycles $m$ during the time of $N$ samples. then the math gets a little more involved, but the scaling issues should, if $N$ is large enough, approach the result we have above.

$\endgroup$
  • $\begingroup$ Nice! I knew it couldn't be so easy as some author seemed to imply. So, this normalization works, but with some caution. $\endgroup$ – filippo Jan 22 '16 at 23:17
  • $\begingroup$ I believe your are looking for the coherent gain of the window - see the Harris paper referenced above for the definition. If the frequency does not fall exactly on an FFT bin i.e. it is inbetween then the simple correction won't work, similarly if multiple frequencies are present. $\endgroup$ – David Jan 23 '16 at 13:12
  • $\begingroup$ @David, yup I read the paper, the thing I wanted to really understand is how safe is it to normalize the DFT by the window sum. It definitely works if you sample the DFT densely enough with zero padding and the window has good resolution and leakage rejection for the frequencies you need to analyze. I thought you could demonstrate some more general relation, but as always when sampling is involved you need to be really careful about its consequences. $\endgroup$ – filippo Jan 23 '16 at 15:06

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.