================ Fourier Analysis ================ Fourier Transform and Discrete Fourier Transform ================================================ Consider the Fourier transform pair [1]_: .. math:: :label: e:trans:forward \newcommand{\defeq}{\buildrel {\text{def}}\over{=}} F(\omega) = \mathcal{F}\left\{f(t)\right\}\defeq \int_{-\infty}^{\infty} f(x) e^{-i2\pi\omega x} dx \\ .. math:: :label: e:trans:backward f(x) = \mathcal{F}^{-1}\left\{F(\omega)\right\} \defeq \int_{-\infty}^{\infty} F(\omega) e^{i2\pi\omega x} d\omega :math:`x` denotes the temporal or spatial coordinate, and :math:`\omega` denotes the frequency coordinate. Equation :eq:`e:trans:forward` defines the forward Fourier transform from :math:`f(x)` to :math:`F(\omega)`. Equation :eq:`e:trans:backward` defines the backward (inverse) Fourier transform from :math:`F(\omega)` to :math:`f(x)`. Suppose the function :math:`f(x)` can be sampled in an interval :math:`[0, A]` with :math:`N` discrete points of the same sub-interval :math:`\Delta x = A/N` as: .. math:: f_n \defeq f(x_n) = f(n\Delta x), \quad n = 0, \ldots, N-1 The forward discrete Fourier transform (DFT) can be defined to be: .. math:: :label: e:trans:dft:forward \tilde{F}(\frac{k}{A}) \defeq \sum_{n=0}^{N-1} f(n\Delta x) e^{-i2\pi\frac{nk}{N}} There is a relationship between :math:`F(\omega)` (in Eq. :eq:`e:trans:forward`) and :math:`\tilde{F}(k/A)` (in Eq. :eq:`e:trans:dft:forward`), which will be derived in what follows. Assume :math:`f(x) = 0` for :math:`x < 0, x > A`. Equation :eq:`e:trans:forward` can then be rewritten as: .. math:: :label: e:trans:forward:A F(\omega) = \int_{0}^{A} f(x) e^{-i2\pi\omega x} dx To facilitate the derivation, the integrand in Eq. :eq:`e:trans:forward:A` be defined as: .. math:: :label: e:trans:integrand g(x) \defeq f(x) e^{-i2\pi\omega x} Aided by the trapezoid rule and Eq. :eq:`e:trans:integrand`, the integration of Eq. :eq:`e:trans:forward:A` can be approximated as: .. math:: :label: e:trans:forward:trapezoid F(\omega) \cong \frac{\Delta x}{2}\left[ g(0) + 2\sum_{n=1}^{N-2}g(x_n) + g(A) \right] Assume .. math:: g(0) = g(A) then Eq. :eq:`e:trans:forward:trapezoid` can be written as: .. math:: :label: e:trans:forward:approx F(\omega) \cong \Delta x \sum_{n=0}^{N-1}g(x_n) = \frac{A}{N}\sum_{n=0}^{N-1} f(x_n) e^{-i2\pi\omega x_n} Because the longest wave length that the sampling interval allows is :math:`A`, the frequency of the fundamental mode is .. math:: :label: e:trans:freqstep \Delta\omega = \frac{1}{A} which is the spacing of the frequency-domain (:math:`\omega`) grid that covers the frequency interval :math:`[-\Omega/2, \Omega/2]` with :math:`N` points. Aided by using Eq. :eq:`e:trans:freqstep`, it can be obtained that .. math:: \Omega = N\Delta\omega = \frac{N}{A} and thus .. math:: :label: e:trans:reciprocity1 A\Omega = N Because .. math:: \Delta x = \frac{A}{N}, \quad \Delta\omega = \frac{1}{A} it can be shown that .. math:: :label: e:trans:reciprocity2 \Delta x\Delta\omega = \frac{1}{N} Equations :eq:`e:trans:reciprocity1` and :eq:`e:trans:reciprocity2` are the *reciprocity relations*. To proceed, write .. math:: x_n\omega_k = (n\Delta x)(k\Delta\omega) = \frac{nA}{N}\frac{k}{A} = \frac{nk}{N} Equation :eq:`e:trans:forward:approx` becomes .. math:: F(\frac{k}{A}) \cong \frac{A}{N} \sum_{n=0}^{N-1} f(n\Delta x) e^{-i2\pi\frac{nk}{N}} Substituting Eq. :eq:`e:trans:dft:forward` into the previous equation gives: .. math:: :label: e:trans:scaling F(\frac{k}{A}) \cong \frac{A}{N}\tilde{F}(\frac{k}{A}) which defines the scaling relation between the Fourier transform (Eq. :eq:`e:trans:forward`) and the discrete Fourier transform (Eq. :eq:`e:trans:dft:forward`). Example Code ============ .. literalinclude:: ../../examples/num_trans/transform.py :language: python :start-after: # -*- coding: utf8 -*- :end-before: # vim: set :linenos: .. automodule:: pyengr.fourier :members: .. [1] William L. Briggs and Van Emden Henson, *The DFT: An Owners' Manual for the Discrete Fourier Transform*, SIAM, 1987. http://www.amazon.com/gp/product/0898713420/ .. vim: set spell ft=rst ff=unix fenc=utf8 ai et sw=4 ts=4 tw=79