Discrete Fourier transformation

Consider a sample of n observations yQ, y, . .., yn i and define its discrete Fourier transform by 

Let (yD, , . .., yn represent the sampled values of a continuous function f, i.e., yk = f(kAt), where At is the length of the sampling interval. It is interesting to see how the discrete transforms ak are related to the sampled values F(kAt) of the Fourier transform of the continuous function f. Assume first that f vanishes outside the interval [0,T], where T = nAt is the sampling time, and f(0) = f(T). Estimating the integral in (4.31) by the trapezium rule we have 

Let F(v) denote the sum on the right hand side of (4.39), and define the sampling interval Av in the frequency domain by 

for our special function f, F(kAv) Atak. If the yk values are real, 

However, unless special care is exercised, generally the discrete spectrum does not estimate very well the sampled continuous spectrum. The problems we face are as follows. 

As already mentioned above, in a laser-controlled FT spectrometer, the interfer-ogram is digitised and eonsists of A/discrete, equidistant points. That means that instead of Eq. (5.9) we have to use the discrete Fourier transformation  

The use of the discrete FT can lead to spectral artefacts the picket fence effect and aliasing. 

---

In practical applications, x(t) is not a continuous function, and the data to be transformed are usually discrete values obtained by sampling at intervals. Under such circumstances, I hi discrete Fourier transform (DFT) is used to obtain the frequency function. Let us. suppose that the time-dependent data values are obtained by sampling at regular intervals separated by [Pg.43]

The fast Fourier transform (FFT) is used to calculate the Fourier transform as well as the inverse Fourier transform. A discrete Fourier transform of length N can be written as the sum of two discrete Fourier transforms, each of length N/2. 

The discrete Fourier transform can also be used for differentiating a function, and this is used in the spectral method for solving differential equations. Suppose we have a grid of equidistant points... 

From the time function F t) and the calculation of [IT], the values of G may be found. One way to calculate the G matrix is by a fast Fourier technique called the Cooley-Tukey method. It is based on an expression of the matrix as a product of q square matrices, where q is again related to N by = 2 . For large N, the number of matrix operations is greatly reduced by this procedure. In recent years, more advanced high-speed processors have been developed to carry out the fast Fourier transform. The calculation method is basically the same for both the discrete Fourier transform and the fast Fourier transform. The difference in the two methods lies in the use of certain relationships to minimize calculation time prior to performing a discrete Fourier transform. 

Much of the regularity in classical systems can often be best discerned directly by observing their spatial power spectra (see section 6.3). We recall that in the simplest cases, the spectra consist of few isolated discrete peaks in more complex chaotic evolutions, we might get white noise patterns (such as for elementary additive rules). A discrete fourier transform (/ ) of a typical quantum state is defined in the most straightforward manner ... 

In the discrete case, the convolution by the PSF is diagonalized by using the discrete Fourier transform (DFT) ... 

Note that Eq. (37) also enters into a sine discrete Fourier transform approximation of the second derivative. 

Now replacing the continuous integral (or Fourier transform) in the square brackets by discrete Fourier transforms as in Eqs. (41) we obtain... 

The fast Fourier transform can be carried out by rearranging the various terms in the summations involved in the discrete Fourier transform. It is, in effect, a special book-keeping scheme that results in a very important simplification of the numerical evaluation of a Fburier transform. It was introduced into the scientific community in the mid-sixties and has resulted in what is probably one of the few significant advances in numerical methods of analysis since the invention of the digital computer. 

The discrete Fourier transform can also be used for differentiating a function, and this is used in the spectral method for solving differential equations [Gottlieb, D., and S. A. Orszag, Numerical Analysis of Spectral Methods Theory and Applications, SIAM, Philadelphia (1977) Trefethen, L. N., Spectral Methods in Matlab, SIAM, Philadelphia (2000)]. Suppose we have a grid of equidistant points... 

The solution is known at each of these grid points jyi.v, j . First the discrete Fourier transform is taken ... 

Discrete Fourier transform (DFT), non-adiabatic coupling, Longuet-Higgins phase-based treatment, two-dimensional two-surface system, scattering calculation, 153-155 Discrete variable representation (DVR) direct molecular dynamics, nuclear motion Schrodinger equation, 364-373 non-adiabatic coupling, quantum dressed classical mechanics, 177-183 formulation, 181-183... 

The resulting stress was measured, and a discrete Fourier transform was performed to obtain the elastic and viscous moduli. The experimental variables in FTMS are the fundamental frequency, f, and the strain amplitudes, Yi, at each frequency, i. Each of the other frequencies are harmonics (integer multiples) of the fundamental frequency. The fundamental frequency was set at 1 rad/s, while the harmonics were chosen to be 2, 5, 10, 25, 40, 50, and 60 rad/s. The summation of the strain amplitudes at each frequency was below the linear viscoelastic limit of the NOA 61 sample. 

As for the velocity field, the (discrete) Fourier-transformed scalar field AK can be defined by... 

J = The discrete Fourier transform for that case. x = actual data. i = increment in the series. w = frequency. t = time. 

Equation 1 is a discrete Fourier transform, it is discrete rather than continuous because the crystalline lattice allows us to sum over a limited set of indices, rather than integrate over structure factor space. The discrete Fourier transform is of fundamental importance in crystallography - it is the mathematical relationship that allows us to convert structure factors (i.e. amplitudes and phases) into the electron density of the crystal, and (through its inverse) to convert periodic electron density into a discrete set of structure factors. 

The action of the radial differential operator is accomplished through the use of discrete Fourier transforms as proposed by Kosloff [20,37]. If we take the example of the action of the differential operator in the scattering coordinate, then... 

The analysis proceeds as in section IIIC, except that iteration numbers are used in performing a discrete Fourier transform rather than a trapezoid rule integration over time. 

---