HP 48gII hp 48gII_user's manual_English_E_HDPMSG48E67_V2.pdf - Page 527

convolution: For Fourier transform applications, the operation of convolution is defined as ( f * g)(x) = 1 2π ⋅∫ f (x g(ξ ) ⋅ dξ. The following property holds for convolution: F{f*g} = F{f}⋅F{g}. Fast Fourier Transform (FFT) The Fast Fourier Transform is a computer algorithm by which one can calculate very efficiently a discrete Fourier transform (DFT). This algorithm has applications in the analysis of different types of time-dependent signals, from turbulence measurements to communication signals. The discrete Fourier transform of a sequence of data values {xj}, j = 0, 1, 2, ..., n-1, is a new finite sequence {Xk}, defined as ∑ X k = 1 n n−1 xj j=0 ⋅ exp(−i ⋅ 2πkj / n), k = 0,1,2,..., n −1 The direct calculation of the sequence Xk involves n2 products, which would involve enormous amounts of computer (or calculator) time particularly for large values of n. The Fast Fourier Transform reduces the number of operations to the order of n⋅log2n. For example, for n = 100, the FFT requires about 664 operations, while the direct calculation would require 10,000 operations. Thus, the number of operations using the FFT is reduced by a factor of 10000/664 ≈ 15. The FFT operates on the sequence {xj} by partitioning it into a number of shorter sequences. The DFT's of the shorter sequences are calculated and later combined together in a highly efficient manner. For details on the algorithm refer, for example, to Chapter 12 in Newland, D.E., 1993, "An Page 16-49