Discrete Fourier Transform NR (2ed) Ch. 12 OUTLINE 1. Versatility of Fourier Transform methods (Ch. 13 has a lot, but there is even more!) - Power spectral estimation and peak bagging - Signal and image processing - Interpolation / regridding - PDEs - Integral equations 2. Reminder of FT properties (eqs. 12.01 ff) - Definition & inverse, using f = omega / 2pi - symmetries - scaling - time shift - frequency shift - convolution theorem - Wiener-Khinchin theorem - Parseval's theorem 3. FT of sampled data (\S 12.1) - Nyquist frequency - Sampling theorem - Aliasing 4. DFT (\S 12.2) - Definition & inverse - All FT properties hold EXACTLY (except roundoff error)! - O(N^2) time (on the face of it) - FFT can be computed in O(N log N) - FFT most efficient when N is a power of 2. - Arrangement of storage (very important!!) 5. Software - Octave & MATLAB fft, ifft, detrend - NR disadvantages - N = power of 2 - single precision - storage of complex numbers in consecutive locations - unit offset, messes with DFT definition - FFTW - www.fftw.org - Octave uses FFTW. 6. Example(s) - Fourier interpolation using FFTW - Power spectra and peak bagging? - Digital filtering? - Integral equations?