Contents
2. #Fourier Sum Definition – does not contain time or frequency
3. #Time and Frequency Equations (3.7) and (3.8) define the Discrete Fourier Transform for all N.
4. #Periodicity Shows that the Fourier sum is periodic in F=1/Dt and T = NDt.
5. #Symmetric Range and continuous limit Equations (5.1) and (5.2) show the relation of the sum to the Fourier integral. With even N, these are the same as the definitions in Fourier Sum Definitions.doc
7. #Reality condition – For real d[i], D[-m]=D*[m]
Sum Orthogonality
The basis for evaluating sums is the relation
(1.1)
So that
If
(1.3)
Then the numerator of (1.2) is zero for all values of m. The denominator is also zero if m = K´N. If m=K´N, all z’s on the left side of (1.2) are 1 so that explicitly
Fourier Sum Definition 1
Begin with a set of data points {d[i]} and define the transform by
- See Partial Sum.doc to break this down for large numbers of points.
Then multiply by exp(-j2pkm/N) and sum on m
(2.2)
Use (1.4) to evaluate the last sum
For 1£k£N, there is a single term in the sum that satisfies the Kronecker delta so that explicitly
Time and Frequency
Define
(3.1)
And
(3.3)
Note that
(3.5)
Then
(3.6)
Then multiply (2.1) by Dt to form
And multiply (2.4) by NDf to form
The result of transforming forward and then backward is to multiply by Df Dt = 1/N so that equations (2.1) and (2.4) are consistent with (3.7) and (3.8) with one difference. The fm and tk have not been restricted to lie in the region 0 to f or 0 to T.
Periodicity
Use (3.7) to define D[fm] for all m. Then with F as defined by (3.4), F=1/Dt.
Then with T=NDt, use (3.8) to define d[ti] for all i
The resulting d is periodic with period T = NDt. An interesting relevant fact about equations (4.1) and (4.2). The terms D[m] d[k] and exp(-j2pmk) are unchanged when màm+N or kàk+N, This means that every term in the sum is present if the sum starts at any value, so that once D and d have been found for all values
(4.3)
Figure 1 The red dots are the original 19 Gaussian points. The line is a forward transform followed by a back transform. The transform range is 19 points, but the transform is made for 256 points. The original data was -9Dt to 9Dt. This was transferred to the range 1 to 19 using the periodicity of d before the initial transform.
Figure 2 The blocks are the real and imaginary parts of the numerical transforms. The line is an analytical transform from - ¥ to ¥ of the same Gaussian.
Code is in dftsume.zip
Symmetric Range
Start the sums in (3.7) and (3.8) at -N/2
The division by 2 is supposed to be truncated to an integer, i.e. -19/2 = -9. The upper limit of the sum is different for an odd number of points and an even number of points. This comes about because 0 is special. In the 1 to N sum, this term was actually at N.
For large f or t and D(f) or d(t) large, the trapezoidal rule in (5.2)
and (5.1)
is not a good approximation. For D(f) à0
as f becomes large and d(t) à0 as t becomes large, this becomes a very good
approximation. The code in the section #Periodicity uses the periodicity of D and d to make
the actual summations in (5.1) and (5.2)
go to the range 1 to N.
The Fourier integral is discussed along with its relationship to more usual physics definitions and its meaning in terms of delta functions in Fourier.doc.
Zero Padding
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 sum in (5.1) produces a continuous D allowing the use of the integral in (5.2) 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[1] 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 (5.1) for data unequal to zero only between IB and IE becomes
The frequencies are for all frequencies of interest. These in (6.1) are closer spaced than those in (5.1) owing to the fact that N is larger than the actual number of points, IE-IB+1. 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 3 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 4 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 5 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 6 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.
Reality condition
The function D[m] is complex, while in many cases the data d[t] is real.
For N odd, let nb = -N/2. Code with nb = -N/2 is in dftsumNb.zip. Then write the code in three sections
And
(7.3)
In the first and last sections let mà-m, reverse the order in which these sections appear in {}, and also note that for d real and m = 0 that (2.1) gives a real D[0] so that
Equation (7.4) is the same as (7.2) for all k, and odd N if and only if
For N even, the sum in (7.2) has an extra term
And
(7.7)
The new item in this is that . So make this change and the mà-m change
Equation (7.8) is the same as (7.6) for all k, and even N if and only if
This means that a knowledge of the real and imaginary parts of D for m ³ 0 and the fact that d(t) is real is sufficient to give the complete transform.