Zero Padding in Frequency
It was shown in Fourier Fit.doc .htm that a least squares fit to N data points with a penalty term that prevents high frequencies is given by
Equation 1
For all values of m, define
Equation 2
The DA in is not the forward transform of dA over N data points. For m’ = m+kN, the term D[m] in is such that D[m+kN] = D[m], but the term H((m+kN)/T) is not equal to H(m/T). As in the time domain ZeroPadding.doc .htm, if H has become and remains zero for |m| > N/2, the sum in can be extended to L´N terms.
Equation 3
The Discrete Fourier Transform is always defined for an infinite number of data points. But most of these are periodic repeats of the first N data points to an infinite set as shown in Figure 1. Zero padding adds zeroes to the end of the data. The time T is made larger by doing this. Since the frequencies are given by m/T, this places the frequencies closer and closer until as Tà¥, the Fourier sum produces a continuous D allowing the use of the integral in the back transform for finding d. A number of prominent authors have become almost irate about this subject - WhiteSpace.doc. This should indicate that it is common practice[i] and that in general it works. It is usually done to make N a power of 2 as is needed for the usual implementation of the Fast Fourier Transform. The problem is sufficiently subtle that users of this transform are frequently not even informed that the padding has taken place.
The forward transform for data unequal to zero only between IB and IE becomes
Equation 4
The frequencies are f = (m/T) while the times are i(T/N) . For i < IB (tB = IB Dt) or i > IE (tE = IE Dt), the assumption is that d[i] = 0. The frequencies in are closer spaced than those in a transform of IE-IB+1 points owing to the fact that T is larger than (IE-IB+1)´Dt. In the limit that Nà¥, the points DN becomes continuous. Code for this is in dftsumc.zip. For IB= - 9 and IE = 9 and N =256
Figure 1 DT=.17D0, T0=.2D0, W=.67D0. The red boxes are values of
. The line is the back
transform of the forward transform of 256 points – all zeroes except for the 19
points shown above.
Figure 2 Real and imaginary part of
D[m] versus m. The analytical values are
Details in GaussTimeFreq.doc
There is a perceptible difference between the curves caused by the fact that the largest t value in figure 4 has not yet reached zero.
For large values of w the problem with zero padding can be seen. Though not in the back transform using all of the forward transform points.
Figure 3 DT=.17D0, T0=.2D0, W=1.37D0. The red boxes are values of
. The line is the back
transform of the forward transform of 256 points – all zeroes except for the 19
points shown above.
Figure 4 Numerical and analytical D values.
If one were trying to analyze the frequencies, the discontinuities introduced by the sudden zero padding in figure 6 cause problems in figure 7. If the sole purpose is to operate in the frequency domain and then return to the time domain at exactly the same set of points there may be no harm at all. Hamming WhiteSpace.doc is correct that one should always be careful.
The code in dftsumd.zip uses only the d’s that have been defined to compute the forward transform. Then uses all D’s for the back transform. In principle this is 2 NtotalNdata operations. Unless Ndata is < log2Ntotal, the usual FFT is faster.