16
$\begingroup$

I've tried googling and wikipedia-ing it, but I haven't gotten any answers beyond 'it's because the frequency of the input signal is sitting between two bins'.

I understand that this is the reason, but what I can't understand is why the leakage seems to extend to several adjacent bins rather than only one adjacent bin.

To illustrate what I'm talking about, here's some simulated data (code at the end of the post) : Freq_10

Above is the FFT spectrum (plotted on a log scale) of a sine wave of frequency 10. The sampling rate is one, and the number of samples is 100. The graph has been FFT-shifted. There's clearly only a peak at bin 10, and the rest is on the order of numerical error, or there about.

Freq_10_1

This is the frequency spectrum at a generated frequency of 10.1. Clearly there is 'leakage' into more bins than just the immediately adjacent bin.

freq_10_5

This is the plot for a frequency of 10.5.

Question: Why is there this leakage, and why does it extend to all the other bins, rather than the immediate adjacent bin?


Code, for anyone who's interested (Python code)

import numpy as np
import matplotlib.pyplot as plt

xFreq = 10.5
xSize = 100.0
xPeriod = xSize/xFreq
x = np.linspace(1,xSize,xSize)

data = np.sin(2*np.pi*x/xPeriod)
fft = np.fft.fft(data)
fft = np.fft.fftshift(fft)

fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(abs(fft), "o")
ax.set_yscale('log')
plt.show()

I changed the xFreq value from 10.0 to 10.5, etc.

$\endgroup$
  • $\begingroup$ Any signal that doesn't fit exactly into the window length of the FFT produces a discontinuity when you wrap it around. Discontinuities, like impulses or step functions, contain some of all frequencies. $\endgroup$ – endolith Sep 6 '13 at 21:55
11
$\begingroup$

An FFT has finite length, and thus constitutes a default rectangular window on a data stream. A window in the time domain results in a convolution in the frequency domain with the transform of the window. Note that the transform of a rectangular window is a Sinc function (sin(x)/x), which has infinite width. It's not just 2 bins in width. Thus the ripples of the Sinc function will show up as "leakage" far from any spectral peak that is not perfectly periodic in the FFT's length.

The picture below shows part of the frequency response of the sinc function. When the tone is centered on one of the bins all of the other points are lined up with the nulls in the frequency response. If it isn't centered on a bin then it's like shifting the whole frequency response, which causes the other bins to fall on non-null portions of the frequency respoonse.

enter image description here

Another way to look at it is that an FFT is just a filter bank, where each filter stop-band floor has lots of ripples, and is certainly not infinite in attenuation more than 1 bin away from center frequency. Some windows (von Hann,etc.) other than rectangular have lower stop bands, which is one reason for their popular use.

$\endgroup$
  • 1
    $\begingroup$ Note that so-called spectral "leakage" does not show up in the FFT of exactly bin-centered periodic inputs because the Sinc function is exactly zero (between sign changes) at all the other bin center frequencies (completely orthogonal to those filter kernels and FFT basis vectors). $\endgroup$ – hotpaw2 Jul 29 '13 at 18:13
  • $\begingroup$ I hope you don't mind the edit. Feel free to toss it if you don't like it. $\endgroup$ – Jim Clay Jul 29 '13 at 18:40
  • $\begingroup$ @Jim Clay : Thanks for the added graph. I couldn't figure out how to submit one from my iPhone. $\endgroup$ – hotpaw2 Jul 29 '13 at 18:56
  • 1
    $\begingroup$ Thank you, thank you, thank you. Thank you for NOT explaining leakage by saying, "The FFT assumes that its input sequence is periodic." That silly notion of 'assumed periodicity' is, sadly, repeated far too often in the literature of DSP. [-Rick-] $\endgroup$ – user5133 Jul 29 '13 at 22:10
  • $\begingroup$ Occasionally, the assumption of input periodicity is useful, when doing shaft rotation synchronous sampling of FFT frame length (or creating classroom synthetic examples), for instance. But with audio (etc.), sectioning and windowing data frames unrelated to any periodicity lengths is more common, making the assumption usually false for work in those areas. $\endgroup$ – hotpaw2 Jul 30 '13 at 1:56
0
$\begingroup$

hotpaw2's answer is good but I'd like to elaborate a bit on user5133's comment:

Thank you for NOT explaining leakage by saying, "The FFT assumes that its input sequence is periodic." That silly notion of 'assumed periodicity' is, sadly, repeated far too often in the literature of DSP

and at the same time answer the question too. Note that I am note an expert in this field --- feel free to comment, correct or confirm.

The Discrete-Time Fourier Transform (DTFT) is defined over $\mathbb{Z}$ (and not just $\{1,2,\dots, N\}$!) by

$$X(\omega )=\sum _{n=-\infty }^{\infty }x[n]\,e^{-i\omega n}.$$

In practice, measured signals are finite; denote the length by $N$. A finite signal can be extended by $N$-periodicity over $\mathbb{Z}$. The Discrete Fourier Transform (DFT) is defined by $${\displaystyle X_{k}\ {\stackrel {\text{def}}{=}}\ \sum _{n=0}^{N-1}x_{n}\cdot e^{-2\pi ikn/N},\quad k\in \mathbb {Z} \,}$$ which corresponds to the discrete frequencies $X(2\pi k/N)$ of the DTFT except when $n$ in not in $\{1,2,\dots, N\}$. In other words, it corresponds to the DTFT of $x[n]w[n]$ where $w$ is a rectangular function equals to 1 when $n\in\{1,\dots,N\}$ and 0 everywhere else.

But the Fourier transform of a product is the convolution of the Fourier transforms:

$$\mathcal{F}\{f \cdot g\}= \mathcal{F}\{f\}*\mathcal{F}\{g\} $$

so that the DFT of the original signal is the convolution of the DTFT of it's "periodicized" version with the Fourier transform of a rectangular window... which is a $\text{sinc}$ because (in the continuous framework and centered on 0 to simplify...):

$$\int_{-\infty}^\infty w(f)e^{-j\omega t} dt = \int_{-\tau}^{\tau} e^{-j\omega t}dt =2\tau \text{sinc}(\omega \tau)$$

The convolution with a $\text{sinc}$ produces the observed side-lobes (except in some specific cases).

$\endgroup$

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.