Chris@87: """ Chris@87: Discrete Fourier Transform (:mod:`numpy.fft`) Chris@87: ============================================= Chris@87: Chris@87: .. currentmodule:: numpy.fft Chris@87: Chris@87: Standard FFTs Chris@87: ------------- Chris@87: Chris@87: .. autosummary:: Chris@87: :toctree: generated/ Chris@87: Chris@87: fft Discrete Fourier transform. Chris@87: ifft Inverse discrete Fourier transform. Chris@87: fft2 Discrete Fourier transform in two dimensions. Chris@87: ifft2 Inverse discrete Fourier transform in two dimensions. Chris@87: fftn Discrete Fourier transform in N-dimensions. Chris@87: ifftn Inverse discrete Fourier transform in N dimensions. Chris@87: Chris@87: Real FFTs Chris@87: --------- Chris@87: Chris@87: .. autosummary:: Chris@87: :toctree: generated/ Chris@87: Chris@87: rfft Real discrete Fourier transform. Chris@87: irfft Inverse real discrete Fourier transform. Chris@87: rfft2 Real discrete Fourier transform in two dimensions. Chris@87: irfft2 Inverse real discrete Fourier transform in two dimensions. Chris@87: rfftn Real discrete Fourier transform in N dimensions. Chris@87: irfftn Inverse real discrete Fourier transform in N dimensions. Chris@87: Chris@87: Hermitian FFTs Chris@87: -------------- Chris@87: Chris@87: .. autosummary:: Chris@87: :toctree: generated/ Chris@87: Chris@87: hfft Hermitian discrete Fourier transform. Chris@87: ihfft Inverse Hermitian discrete Fourier transform. Chris@87: Chris@87: Helper routines Chris@87: --------------- Chris@87: Chris@87: .. autosummary:: Chris@87: :toctree: generated/ Chris@87: Chris@87: fftfreq Discrete Fourier Transform sample frequencies. Chris@87: rfftfreq DFT sample frequencies (for usage with rfft, irfft). Chris@87: fftshift Shift zero-frequency component to center of spectrum. Chris@87: ifftshift Inverse of fftshift. Chris@87: Chris@87: Chris@87: Background information Chris@87: ---------------------- Chris@87: Chris@87: Fourier analysis is fundamentally a method for expressing a function as a Chris@87: sum of periodic components, and for recovering the function from those Chris@87: components. When both the function and its Fourier transform are Chris@87: replaced with discretized counterparts, it is called the discrete Fourier Chris@87: transform (DFT). The DFT has become a mainstay of numerical computing in Chris@87: part because of a very fast algorithm for computing it, called the Fast Chris@87: Fourier Transform (FFT), which was known to Gauss (1805) and was brought Chris@87: to light in its current form by Cooley and Tukey [CT]_. Press et al. [NR]_ Chris@87: provide an accessible introduction to Fourier analysis and its Chris@87: applications. Chris@87: Chris@87: Because the discrete Fourier transform separates its input into Chris@87: components that contribute at discrete frequencies, it has a great number Chris@87: of applications in digital signal processing, e.g., for filtering, and in Chris@87: this context the discretized input to the transform is customarily Chris@87: referred to as a *signal*, which exists in the *time domain*. The output Chris@87: is called a *spectrum* or *transform* and exists in the *frequency Chris@87: domain*. Chris@87: Chris@87: Implementation details Chris@87: ---------------------- Chris@87: Chris@87: There are many ways to define the DFT, varying in the sign of the Chris@87: exponent, normalization, etc. In this implementation, the DFT is defined Chris@87: as Chris@87: Chris@87: .. math:: Chris@87: A_k = \\sum_{m=0}^{n-1} a_m \\exp\\left\\{-2\\pi i{mk \\over n}\\right\\} Chris@87: \\qquad k = 0,\\ldots,n-1. Chris@87: Chris@87: The DFT is in general defined for complex inputs and outputs, and a Chris@87: single-frequency component at linear frequency :math:`f` is Chris@87: represented by a complex exponential Chris@87: :math:`a_m = \\exp\\{2\\pi i\\,f m\\Delta t\\}`, where :math:`\\Delta t` Chris@87: is the sampling interval. Chris@87: Chris@87: The values in the result follow so-called "standard" order: If ``A = Chris@87: fft(a, n)``, then ``A[0]`` contains the zero-frequency term (the mean of Chris@87: the signal), which is always purely real for real inputs. Then ``A[1:n/2]`` Chris@87: contains the positive-frequency terms, and ``A[n/2+1:]`` contains the Chris@87: negative-frequency terms, in order of decreasingly negative frequency. Chris@87: For an even number of input points, ``A[n/2]`` represents both positive and Chris@87: negative Nyquist frequency, and is also purely real for real input. For Chris@87: an odd number of input points, ``A[(n-1)/2]`` contains the largest positive Chris@87: frequency, while ``A[(n+1)/2]`` contains the largest negative frequency. Chris@87: The routine ``np.fft.fftfreq(n)`` returns an array giving the frequencies Chris@87: of corresponding elements in the output. The routine Chris@87: ``np.fft.fftshift(A)`` shifts transforms and their frequencies to put the Chris@87: zero-frequency components in the middle, and ``np.fft.ifftshift(A)`` undoes Chris@87: that shift. Chris@87: Chris@87: When the input `a` is a time-domain signal and ``A = fft(a)``, ``np.abs(A)`` Chris@87: is its amplitude spectrum and ``np.abs(A)**2`` is its power spectrum. Chris@87: The phase spectrum is obtained by ``np.angle(A)``. Chris@87: Chris@87: The inverse DFT is defined as Chris@87: Chris@87: .. math:: Chris@87: a_m = \\frac{1}{n}\\sum_{k=0}^{n-1}A_k\\exp\\left\\{2\\pi i{mk\\over n}\\right\\} Chris@87: \\qquad m = 0,\\ldots,n-1. Chris@87: Chris@87: It differs from the forward transform by the sign of the exponential Chris@87: argument and the normalization by :math:`1/n`. Chris@87: Chris@87: Real and Hermitian transforms Chris@87: ----------------------------- Chris@87: Chris@87: When the input is purely real, its transform is Hermitian, i.e., the Chris@87: component at frequency :math:`f_k` is the complex conjugate of the Chris@87: component at frequency :math:`-f_k`, which means that for real Chris@87: inputs there is no information in the negative frequency components that Chris@87: is not already available from the positive frequency components. Chris@87: The family of `rfft` functions is Chris@87: designed to operate on real inputs, and exploits this symmetry by Chris@87: computing only the positive frequency components, up to and including the Chris@87: Nyquist frequency. Thus, ``n`` input points produce ``n/2+1`` complex Chris@87: output points. The inverses of this family assumes the same symmetry of Chris@87: its input, and for an output of ``n`` points uses ``n/2+1`` input points. Chris@87: Chris@87: Correspondingly, when the spectrum is purely real, the signal is Chris@87: Hermitian. The `hfft` family of functions exploits this symmetry by Chris@87: using ``n/2+1`` complex points in the input (time) domain for ``n`` real Chris@87: points in the frequency domain. Chris@87: Chris@87: In higher dimensions, FFTs are used, e.g., for image analysis and Chris@87: filtering. The computational efficiency of the FFT means that it can Chris@87: also be a faster way to compute large convolutions, using the property Chris@87: that a convolution in the time domain is equivalent to a point-by-point Chris@87: multiplication in the frequency domain. Chris@87: Chris@87: Higher dimensions Chris@87: ----------------- Chris@87: Chris@87: In two dimensions, the DFT is defined as Chris@87: Chris@87: .. math:: Chris@87: A_{kl} = \\sum_{m=0}^{M-1} \\sum_{n=0}^{N-1} Chris@87: a_{mn}\\exp\\left\\{-2\\pi i \\left({mk\\over M}+{nl\\over N}\\right)\\right\\} Chris@87: \\qquad k = 0, \\ldots, M-1;\\quad l = 0, \\ldots, N-1, Chris@87: Chris@87: which extends in the obvious way to higher dimensions, and the inverses Chris@87: in higher dimensions also extend in the same way. Chris@87: Chris@87: References Chris@87: ---------- Chris@87: Chris@87: .. [CT] Cooley, James W., and John W. Tukey, 1965, "An algorithm for the Chris@87: machine calculation of complex Fourier series," *Math. Comput.* Chris@87: 19: 297-301. Chris@87: Chris@87: .. [NR] Press, W., Teukolsky, S., Vetterline, W.T., and Flannery, B.P., Chris@87: 2007, *Numerical Recipes: The Art of Scientific Computing*, ch. Chris@87: 12-13. Cambridge Univ. Press, Cambridge, UK. Chris@87: Chris@87: Examples Chris@87: -------- Chris@87: Chris@87: For examples, see the various functions. Chris@87: Chris@87: """ Chris@87: from __future__ import division, absolute_import, print_function Chris@87: Chris@87: depends = ['core']