The discrete Fourier transformation

Modem signal processing in analytical chemistry is usually performed by computer. Therefore, signals are digitized by taking uniformly spaced samples from the continuous signal, which is measured over a finite time. 

The expressions for the forward and backward Fourier transforms of a data array of 2N+ 1 data points with the origin in the centre point are [3]  

The frequency associated with F n) is v . This frequency should be equal to n times the basis frequency, which is equal to l/(27 ) (this is the period of a sine or cosine which exactly fits in the measurement time). Thus v = n/(2T ) = n/(2NAt). It should be noted that in literature one may find other conventions for the normalization factor used in front of the integral and summation signs. 

---

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. 

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

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 ... 

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 discrete Fourier transform gives us the ability to compute the numbers representing one cycle of F(co) from the numbers representing one cycle of f (x) and vice versa. We may adjust scale factors, number of samples, sample... 

The reader may wish to extend the type of analysis shown in Fig. 3 by considering the effects of boxcar averaging. In this process, /(x) is convolved with a rect(x) function before sampling. Each sample then represents a uniformly weighted average. It is instructive to consider the effect of varying the number of samples used for the transform. In Chapter 9, Howard introduces the mathematics needed for practical application of the discrete Fourier transform. 

The discrete Fourier transform (DFT) of the data is evaluated to take advantage of the considerable speed and accuracy of the fast-Fourier-transform algorithm as calculated by modern digital computers. For most... 

As with the continuous Fourier transform, we could treat the equations of the discrete Fourier transform (DFT) completely independently, derive all the required theorems for them, and work entirely within this closed system. However, because the data from which the discrete samples are taken are usually continuous, some discussion of sampling error is warranted. Further, the DFT is inherently periodic, and the limitations and possible error associated with a periodic function should be discussed. 

We discovered in Chapter 9 that the spatial function as given by the discrete Fourier transform (DFT) is a discrete Fourier series. Letting u(k) denote the (known) series consisting of only low-frequency terms and v(k) the series consisting of only high-frequency terms, we want to determine the unknown coefficients in v(k) that best satisfy the constraints. Expressing deviations of the total function forbidden by the constraints as some function of u(k) + v(k), we shall try to determine the coefficients of v(k) that minimize these deviations. Sum-of-squares expressions for these measures of the error have been found to result in the most efficient computational schemes. 

A well known result states that the values of the discrete Fourier transform of a stationary random process are normally distributed complex variables when the length of the Fourier transform is large enough (compared to the decay rate of the noise correlation function) [Brillinger, 1981], This asymptotic normal behavior leads to a Rayleigh distributed magnitude and a uniformly distributed phase (see [McAulay and Malpass, 1980, Ephraim andMalah, 1984] and [Papoulis, 1991]). 

Frequency Analysis. The Discrete Fourier Transform (and its fast implementation, the Fast Fourier Transform [Brigham, 1974]) (FFT) as well as its cousin, the Discrete Cosine Transform [Rao and Yip, 1990] (DCT) require block operations, as opposed to single sample inputs. The DFT can be described recursively, with the basis being the 2 point DFT calculated as follows ... 

Frequency domain functions are denoted by upper case letters. Of importance for the TDFRS experiment is the discrete Fourier transform of an array of N data points within a period of N At ... 

Bayesian probability theory157 can also be applied to the problem of NMR parameter estimation this approach incorporates prior knowledge of the NMR parameters and is particularly useful at short aquisition times158 and when the FID contains few data points.159 Bayesian analysis gives more precise estimates of the NMR parameters than do methods based on the discrete Fourier transform (DFT).160 The amplitudes can be estimated independently of the phase, frequency and decay constants of the resonances.161 For the usual method of quadrature detection, it is appropriate to apply this technique to the two quadrature signals in the time domain.162-164... 

Just as the discrete Fourier transform generates discrete frequencies from sampled data, the discrete wavelet transform (often abbreviated as DWT) uses a discrete sequence of scales aj for j < 0 with a = 21/v, where v is an integer, called the number of voices in the octave. The wavelet support — where the wavelet function is nonzero — is assumed to be -/<72, /<72. For a signal of size N and I < aJ < NIK, a discrete wavelet / is defined by sampling the scale at a] and time (for scale 1) at its integer values, that is... 

The original literature on Fourier series and transforms involved applications to continuous datasets. However, in chemical instrumentation, data are not sampled continuously but at regular intervals in time, so all data are digitised. The discrete Fourier transform (DFT) is used to process such data and will be described below. It is important to recognise that DFTs have specific properties that distinguish them from continuous FTs. 

The discrete Fourier transform provides a useful and efficient means of extracting information on the frequency components present in a time-varying signal and displaying the amplitudes of these components as a spectrum. However, a number of potential artifacts must be avoided if we are to obtain a faithful representation of the information actually present in the time domain signal. 

When we have discrete stochastic models, as those introduced through the polystochastic chains, we can obtain their image by using different methods the Z transformation, the discrete Fourier transformation, the characteristic function of... 

The computer algorithms that carry out the discrete Fourier transform calculation work most efficiently if the number of data points (np) is an integral power of 2. Generally, for basic H and C spectra, at least 16,384 (referred to as 16K ) data points, and 32,768 ( 32K ) points should be collected for full H and spectral windows, respectively. With today s higher field instruments and large-memory computers, data sets of 64K for H and 64-128K for and other nuclei are now commonly used. 

J.Warren Sparse filter banks for binary subdivision schemes. pp427-438 in Mathematics of Surfaces VII (eds Goodman and Martin) 1997 Leif Kobbelt Using the discrete fourier transform to analyze the convergence of subdivision schemes. Applied and Computational Harmonic Analysis, Volume 5(1), pp68-91, 1998... 

---