6
$\begingroup$

This question already has an answer here:

I understand zero-filling increases the resolution of an NMR signal in the frequency domain, but I fail to comprehend how. Why do the artifical points appear between the real points in the frequency domain? Is it a byproduct of the fast fourier transform algorithm? Can someone explain this to me? Thanks!

$\endgroup$

marked as duplicate by Mathew Mahindaratne, Mithoron, Todd Minehardt, Tyberius, Jon Custer Jul 16 at 1:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ This does not increase resolution but in effect interpolates between points already there. The effect is superficial, no extra information is extracted from the data, but nice smooth signals are produced. $\endgroup$ – porphyrin Jul 11 at 7:33
  • 1
    $\begingroup$ @porphyrin nailed it. This topic pops up at signal processing.SE, where zero padding is the name for zero filling. See the following if you want to see the math: dsp.stackexchange.com/a/24426/41790 $\endgroup$ – Ed V Jul 11 at 12:52
5
$\begingroup$

The key idea behind zero padding or zero filling is that the "resolution" or the step size of the frequency axis in the Discrete Fourier Transform is dependent on the number of points you have in the time domain. Zero filling is done before doing the Fourier transform. Thus after the FFT the resolution appears to be improved because you have more points in the spectrum and the spacing between each point appears to be decreased.

This is a result of a beautiful theorem (although this is casually mentioned in most textbooks), but never shown as a theorem. I found in Cooley's original paper from 1967 [1, p. 80].

Theorem 1

If $x(t), -∞ < t < ∞,$ and $a(f), -∞ < f < ∞,$ are a Fourier integral transform pair,

$$x(t) ↔ a(f),$$

then $Tx_p(jΔt), j = 0, 1, \cdots, N - 1,$ and $a_p(nΔf), n = 0, 1, 2, \cdots, N - 1,$ are a finite Fourier transform pair,

$$ \begin{align} Tx_p(jΔt) &= T\sum_{l = -∞}^∞{x(jΔt + lT)} ↔ \sum_{k = -∞}^∞{a(nΔf + kF)} \\ &= a_p(nΔf) \end{align} $$

where $Δf = 1/(NΔt) = 1/T.$

It is to be remembered that the finite Fourier transform pair

$$X(j) ↔ A(n)$$

is defined by

$$X(j) = \sum_{n = 0}^{N - 1}{A(n)W_N^{jn}}, \quad W_N = e^{2πi/N}$$

Thus, if two functions are Fourier transforms of one another, then the sequences obtained from them by aliasing and sampling in this fashion are finite Fourier transforms of one another.

Cooley & Tukey are the key persons who made Discrete Fourier Transform (DFT) possible by computers for lowly mortals like us, otherwise it was an elitist subject among the mathematicians. Here is a snippet of it. It took me several years to find an original paper which showed this theorem. However, math researchers told me this was known in 1754. Full discussion here: History of Integral Transform Theorem

References

  1. Cooley, J.; Lewis, P.; Welch, P. Application of the Fast Fourier Transform to Computation of Fourier Integrals, Fourier Series, and Convolution Integrals. IEEE Transactions on Audio and Electroacoustics 1967, 15 (2), 79–84. https://doi.org/10/bmw8z8.
$\endgroup$
  • 2
    $\begingroup$ Hmmm, what about Tukey, or Gauss? Do they not deserve mention :-) en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm $\endgroup$ – Buck Thorn Jul 12 at 12:36
  • 1
    $\begingroup$ Good catch. Both Cooley & Tukey later called their method a rediscovery. I really appreciate how honest and humble those scientists were during the golden era of modern science (60-80s) in the US. One of a leading scientist once lamented that "we gave up curiosity driven research long time ago". The impact factor, h-index, and citations counts have made science a business and a race of numbers. $\endgroup$ – M. Farooq Jul 12 at 13:47
  • $\begingroup$ @M.Farooq Nice work (+1)! But I have a small question: in the theorem statement, what is upper case F (in the second summation)? $\endgroup$ – Ed V Jul 15 at 13:20
  • $\begingroup$ I believe that it represents the maximum value frequency. Will send you the paper. Correct me if that is wrong. $\endgroup$ – M. Farooq Jul 15 at 14:17
  • $\begingroup$ @M.Farooq Many thanks for the paper! From it, F is the constant sampling frequency, i.e., twice the Nyquist frequency. $\endgroup$ – Ed V Jul 15 at 15:30

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