2
$\begingroup$

I have a simple problem I would like to figure out for fourier analysis of seismic data.

Let us say that we have a signal $z[n]$, of length $N$. If I take its (same size) FFT, I will get $Z[k]$, also of length $N$.

I know that zero-padding will not improve my resolution, however, what I am trying to figure out is: If I take an $N$ length FFT, is there ANY risk that I will be missing some information, that would have otherwise shown up had I taken a greater than $N$ length FFT instead?

The case I worry about is if my seismic signal has energy at a frequency that lies between frequency bins. How well would it show up - or not show up - if I do not zero-pad? I would not want to miss this signal should it in fact exist. Cheers.

|improve this question
$\endgroup$
  • $\begingroup$ Part of what makes this site work is accepting an answer once there is a satisfactory one. Please ask for clarification if you need it :) $\endgroup$ – DanielSank May 19 '14 at 0:30
6
$\begingroup$

zero-padding will not "improve resolution" in the sense that it would help you separate two peaks in the spectrum that are very close (too close) to each other.

but zero-padding, as well as interpolation in the frequency domain, does improve resolution in the sense that it help you to more precisely estimate the location of an isolated peak in the spectrum. in fact, zero-padding in the time domain is equivalent to interpolating in the frequency domain using the sinc() function (actually the dirichlet function) as the interpolation kernel.

|improve this answer
$\endgroup$
  • $\begingroup$ @RBJ I realize all that. What I am trying to ascertain is if taking a same size FFT runs the risk of not showing significant energy of my signal (in adjacent bins), if the energy falls between bins. $\endgroup$ – TheGrapeBeyond Dec 23 '13 at 16:59
  • 3
    $\begingroup$ No. Parseval's theorem ensures that all energy is maintained regardless of frequency resolution (as long as the sampling theorem is met). Changing FFT size and alignment may shuffle energy around between bins but the total energy is preserved. $\endgroup$ – Hilmar Dec 23 '13 at 17:20
  • $\begingroup$ @Hilmar That condition about the sampling theorem being met can get you into trouble. Also consider what happens if there are low frequency signals. Suppose you sample $\cos(2\pi f t)$ with $f=0.001$ and $t$ in $[0,1]$. Although the analog power in the cosine is $(1/2)$ the cosine appears nearly constant over the sampling interval and therefore contribues a power of $\approx 1$. The point is that while Perseval's theorem guarantees that the sampled points' power is preserved by the DFT, it can't promise anything about the analog power. $\endgroup$ – DanielSank Jun 17 '15 at 9:24
  • $\begingroup$ In fact, the "discrete power" found from a sampled analog sinusoid of unit amplitude is an oscillating function of the analog frequency. It goes to 1 near frequency = 0 and oscillates about 1/2 for higher frequencies, going exactly to 1/2 for frequencies which are commensurate with the sampling window. $\endgroup$ – DanielSank Jun 17 '15 at 9:30
3
$\begingroup$

Windowing plays an important role, too. With a "rectangular" window (actually, none at all) a signal with a frequency that fall between two bins will be mapped to a sampled sinc in the frequency domain, and thus the energies of adjacent bins would have to be added to reach a good estimate.

Some window functions were designed to allow better peak energy measurement (usually called "flat top").

|improve this answer
$\endgroup$
2
$\begingroup$

Here are some basic facts:

Define discrete Fourier transform of a series of $N$ points $x_n$ as

$$X_k = \frac{1}{N}\sum_{n=0}^{N-1} x_n \exp^{-i 2 \pi n x k / N}$$

We get N unique frequency bins at frequencies $k/N$ were k runs from 0 to $N-1$. If the actual time of the series is $T$ then the width of the frequency bins is $1/T$, and the highest frequency bin is $(N-1)/T$.

If the signal you're measuring is real then $X_k = X_{N-k}^*$.

Ok, now let's get to your questions.

Suppose we measure a 2 Hz complex sinusoid for 1 second, with 20 points. Then the 2nd bin (numbering from zero) will be nonzero, but all the others will be zero. This is all nice and neat because 2 Hz fits exactly into the 1 second measurement window, eg. exactly 2 oscillations.

Now what happens if we measure a signal at 12.2 Hz? In this case the signal sits at a frequency that is between two frequency bins. What happens is essentially that the power shows up mostly in the 12Hz bin, but "leaks" into neighboring bins as well. This is illustrated in the figure below. There we plot the computed Fourier coefficients (blue dots) and the expected result of the DFT that I computed by doing the sum explicitly (red lines).

You can see that most of the power is at bin number 12, but there is also significant power in the neighboring bins. This power in the "wrong" place is called "spectral leakage." In this sense, having too coarse a set of bins does lead to loss of information because you can't tell whether the power in bins 11 and 13 are from leakage or from actual tones. One thing that affects the particulars of how spectral power leaks into neighboring bins is the window you use in the DFT. This is a rich topic and there's too much for me to describe here, but if you search the 'net for "fourier transform window" you'll find what you need.

Now going back to the list of facts I put forth in the beginning you can see that if we had simply measured for longer we'd have a finer set of bins and at least partially mitigated this problem. If you do this by zero padding you do get more points, and therefore finer frequency bins, but as you already said you don't actually have any more information because these zero padded points are completely made up. How do you reconcile that with the fact that you have more frequency bins? It all fits together when we realize that zero padding is essentially interpolation in the frequency domain.

One more thing. If all you care about is the total power then spectral leakage isn't much of a problem. When power leaks out of one bin into the neighboring ones the total power doesn't change much, if at all.$^{[a]}$ The only time you have to worry about spectral leakage messing up the total power in the DFT is at the very lowest frequency bins. If you need details on this I can provide. Just ask.

$[a]$: The details of whether it's precisely conserved are actually a lot more complicated than other people may have you believe. Watch out for people who cite Perseval's theorem too readily.

Illustration of spectral leakage

|improve this answer
$\endgroup$
  • $\begingroup$ Very nice and long answer DanielSank, thank you for being thorough. My question is quite specific, perhaps I should have put it in the question more clearly: I am not so much concerned about which bins the energy goes to during leakage. What I want to make sure it that my spectrum still 'shows' that there is energy due to this signal, if I just use an $N$ length FFT, instead of a zero-padded FFT. Does that make sense? If not ill be glad to expand. I basically just want to make sure I do not 'lose' information for detection by just taking an $N$ length FFT. $\endgroup$ – TheGrapeBeyond Dec 24 '13 at 1:40
  • $\begingroup$ I understand your question. The answer isn't a simple "yes you lose information or "no you don't lose information"; it depends on what information you care about. That's why I gave the long answer. As you can see in the plot in my answer, a signal in between two bins does indeed show up, it doesn't just disappear. If you could state exactly what you are trying to do I can try to provide more information. $\endgroup$ – DanielSank Dec 24 '13 at 1:48
  • $\begingroup$ Ok, we have a detector we are using, that measures 'peakiness' of the spectrum, (max over the mean or something like that), for specific earthquake data. What I am trying to avoid is a scenario, where I use an $N$ length FFT, and miss a detection, because the spectrum isnt peaky enough. This is earthquake data so I would rather not have misses like this! Does using an $N$ length FFT make my spectrum 'less peaky' than one where I zero-padded a lot? This is the whole story. $\endgroup$ – TheGrapeBeyond Dec 24 '13 at 1:55
  • $\begingroup$ (Forgot to mention: All the above is for a signal that is in between bins of course). $\endgroup$ – TheGrapeBeyond Dec 24 '13 at 2:00
  • $\begingroup$ Oh! I'm glad you explained this. There are very specific algorithms for peak finding. I very strongly recommend getting a copy of Numerical Recipes, as it contains a section dedicated to exactly what you're trying to do. $\endgroup$ – DanielSank Dec 24 '13 at 2:02
1
$\begingroup$

In non-zero noise, a shorter FFT contains less samples, therefore both less energy and less information about any signal. So it will "miss" more of the signal because of the lesser information in a shorter window upon the signal. A shorter FFT will also move a larger portion of a signal into the DC and Fs/2 bins where some information can be lost in the windowing process, depending on phase.

In stationary Gaussian noise, the longer the FFT window, the greater the likelihood that a stationary signal will appear above the noise floor, and/or allow a more accurate interpolation of its spectrum (peaks, etc.)

A shorter FFT or window could also potentially completely miss a non-stationary event in time (e.g. If it occurs before or after the window).

Zero-padding before the FFT will do the same as high-quality interpolation after, in showing stuff "between bins".

|improve this answer
$\endgroup$
1
$\begingroup$

Do you know what sort of window function is applied before the FFT? With strictly rectangular windowing, the "scalloping" due to the sinx/x response of the window functions is greatest, so that a tone exactly between bins will have its energy suppressed a bit by the minimum of the scalloping. There are fancy window functions that reduce this (e.g., flat-top windows), but there are tradeoffs regarding resolving the frequency of the energy.

As mentioned, if it is possible to use a longer FFT to increase the processing gain that may serve you better than zero-padding.

|improve this answer
$\endgroup$
  • $\begingroup$ I am assuming a fixed aperture length. So for a fixed aperture length, what is my worst case power loss if I have a frequency fall between two bins? (As far as a window, let us assume two cases, a rectangular and a hamming window). Cheers. $\endgroup$ – TheGrapeBeyond Dec 30 '13 at 22:47
  • $\begingroup$ I wasn't as clear as I should have been, but allow me to try to clarify. The peak magnitudes seen with a tone exactly between bins is suppressed the most with a rectangular window and less so with more aggressive windows. Zero-padding so that the true peak of the sinx/x is sampled restores that magnitude, rather than just having samples with less magnitude that straddle the peak. This is the sort of thing that you can get back from zero-padding. If you search for papers by fred harris on windowing there are tables that show "scalloping loss" for many common functions. $\endgroup$ – Eric Jacobsen Jan 1 '14 at 18:36
  • $\begingroup$ Thank you for your polite clarification, @EJ. Some followups: 1) The term "scalloping loss" is then, a measure of loss of amplitude peak due to falling between bins? Is this the technical term? 2) The scalloping loss tables you mention in the paper, I assume this was put together without any zero-padding? 3) Finally, are you saying that zero-padding reduces scalloping loss? Thank you. $\endgroup$ – TheGrapeBeyond Jan 2 '14 at 12:21
  • $\begingroup$ Yes, "scalloping loss" is the degradation in peak amplitude comparing an on-bin tone and a tone exactly between bins. For the between-bin case there were will be two adjacent equal samples at a magnitude smaller than the single-sample peak in the on-bin case. "Scalloping loss" is a term often used to describe this, particularly in papers having to do with window functions. And, yes, that description assumes no zero-padding. If one zero-padded from N to 2N, the "peak" value of a tone initially exactly between bins would now have a peak sample, so the scalloping loss would not be apparent. $\endgroup$ – Eric Jacobsen Jan 4 '14 at 21:37

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.