1"""
2Discrete Fourier Transform (:mod:`numpy.fft`)
3=============================================
4
5.. currentmodule:: numpy.fft
6
7The SciPy module `scipy.fft` is a more comprehensive superset
8of ``numpy.fft``, which includes only a basic set of routines.
9
10Standard FFTs
11-------------
12
13.. autosummary::
14 :toctree: generated/
15
16 fft Discrete Fourier transform.
17 ifft Inverse discrete Fourier transform.
18 fft2 Discrete Fourier transform in two dimensions.
19 ifft2 Inverse discrete Fourier transform in two dimensions.
20 fftn Discrete Fourier transform in N-dimensions.
21 ifftn Inverse discrete Fourier transform in N dimensions.
22
23Real FFTs
24---------
25
26.. autosummary::
27 :toctree: generated/
28
29 rfft Real discrete Fourier transform.
30 irfft Inverse real discrete Fourier transform.
31 rfft2 Real discrete Fourier transform in two dimensions.
32 irfft2 Inverse real discrete Fourier transform in two dimensions.
33 rfftn Real discrete Fourier transform in N dimensions.
34 irfftn Inverse real discrete Fourier transform in N dimensions.
35
36Hermitian FFTs
37--------------
38
39.. autosummary::
40 :toctree: generated/
41
42 hfft Hermitian discrete Fourier transform.
43 ihfft Inverse Hermitian discrete Fourier transform.
44
45Helper routines
46---------------
47
48.. autosummary::
49 :toctree: generated/
50
51 fftfreq Discrete Fourier Transform sample frequencies.
52 rfftfreq DFT sample frequencies (for usage with rfft, irfft).
53 fftshift Shift zero-frequency component to center of spectrum.
54 ifftshift Inverse of fftshift.
55
56
57Background information
58----------------------
59
60Fourier analysis is fundamentally a method for expressing a function as a
61sum of periodic components, and for recovering the function from those
62components. When both the function and its Fourier transform are
63replaced with discretized counterparts, it is called the discrete Fourier
64transform (DFT). The DFT has become a mainstay of numerical computing in
65part because of a very fast algorithm for computing it, called the Fast
66Fourier Transform (FFT), which was known to Gauss (1805) and was brought
67to light in its current form by Cooley and Tukey [CT]_. Press et al. [NR]_
68provide an accessible introduction to Fourier analysis and its
69applications.
70
71Because the discrete Fourier transform separates its input into
72components that contribute at discrete frequencies, it has a great number
73of applications in digital signal processing, e.g., for filtering, and in
74this context the discretized input to the transform is customarily
75referred to as a *signal*, which exists in the *time domain*. The output
76is called a *spectrum* or *transform* and exists in the *frequency
77domain*.
78
79Implementation details
80----------------------
81
82There are many ways to define the DFT, varying in the sign of the
83exponent, normalization, etc. In this implementation, the DFT is defined
84as
85
86.. math::
87 A_k = \\sum_{m=0}^{n-1} a_m \\exp\\left\\{-2\\pi i{mk \\over n}\\right\\}
88 \\qquad k = 0,\\ldots,n-1.
89
90The DFT is in general defined for complex inputs and outputs, and a
91single-frequency component at linear frequency :math:`f` is
92represented by a complex exponential
93:math:`a_m = \\exp\\{2\\pi i\\,f m\\Delta t\\}`, where :math:`\\Delta t`
94is the sampling interval.
95
96The values in the result follow so-called "standard" order: If ``A =
97fft(a, n)``, then ``A[0]`` contains the zero-frequency term (the sum of
98the signal), which is always purely real for real inputs. Then ``A[1:n/2]``
99contains the positive-frequency terms, and ``A[n/2+1:]`` contains the
100negative-frequency terms, in order of decreasingly negative frequency.
101For an even number of input points, ``A[n/2]`` represents both positive and
102negative Nyquist frequency, and is also purely real for real input. For
103an odd number of input points, ``A[(n-1)/2]`` contains the largest positive
104frequency, while ``A[(n+1)/2]`` contains the largest negative frequency.
105The routine ``np.fft.fftfreq(n)`` returns an array giving the frequencies
106of corresponding elements in the output. The routine
107``np.fft.fftshift(A)`` shifts transforms and their frequencies to put the
108zero-frequency components in the middle, and ``np.fft.ifftshift(A)`` undoes
109that shift.
110
111When the input `a` is a time-domain signal and ``A = fft(a)``, ``np.abs(A)``
112is its amplitude spectrum and ``np.abs(A)**2`` is its power spectrum.
113The phase spectrum is obtained by ``np.angle(A)``.
114
115The inverse DFT is defined as
116
117.. math::
118 a_m = \\frac{1}{n}\\sum_{k=0}^{n-1}A_k\\exp\\left\\{2\\pi i{mk\\over n}\\right\\}
119 \\qquad m = 0,\\ldots,n-1.
120
121It differs from the forward transform by the sign of the exponential
122argument and the default normalization by :math:`1/n`.
123
124Type Promotion
125--------------
126
127`numpy.fft` promotes ``float32`` and ``complex64`` arrays to ``float64`` and
128``complex128`` arrays respectively. For an FFT implementation that does not
129promote input arrays, see `scipy.fftpack`.
130
131Normalization
132-------------
133
134The argument ``norm`` indicates which direction of the pair of direct/inverse
135transforms is scaled and with what normalization factor.
136The default normalization (``"backward"``) has the direct (forward) transforms
137unscaled and the inverse (backward) transforms scaled by :math:`1/n`. It is
138possible to obtain unitary transforms by setting the keyword argument ``norm``
139to ``"ortho"`` so that both direct and inverse transforms are scaled by
140:math:`1/\\sqrt{n}`. Finally, setting the keyword argument ``norm`` to
141``"forward"`` has the direct transforms scaled by :math:`1/n` and the inverse
142transforms unscaled (i.e. exactly opposite to the default ``"backward"``).
143`None` is an alias of the default option ``"backward"`` for backward
144compatibility.
145
146Real and Hermitian transforms
147-----------------------------
148
149When the input is purely real, its transform is Hermitian, i.e., the
150component at frequency :math:`f_k` is the complex conjugate of the
151component at frequency :math:`-f_k`, which means that for real
152inputs there is no information in the negative frequency components that
153is not already available from the positive frequency components.
154The family of `rfft` functions is
155designed to operate on real inputs, and exploits this symmetry by
156computing only the positive frequency components, up to and including the
157Nyquist frequency. Thus, ``n`` input points produce ``n/2+1`` complex
158output points. The inverses of this family assumes the same symmetry of
159its input, and for an output of ``n`` points uses ``n/2+1`` input points.
160
161Correspondingly, when the spectrum is purely real, the signal is
162Hermitian. The `hfft` family of functions exploits this symmetry by
163using ``n/2+1`` complex points in the input (time) domain for ``n`` real
164points in the frequency domain.
165
166In higher dimensions, FFTs are used, e.g., for image analysis and
167filtering. The computational efficiency of the FFT means that it can
168also be a faster way to compute large convolutions, using the property
169that a convolution in the time domain is equivalent to a point-by-point
170multiplication in the frequency domain.
171
172Higher dimensions
173-----------------
174
175In two dimensions, the DFT is defined as
176
177.. math::
178 A_{kl} = \\sum_{m=0}^{M-1} \\sum_{n=0}^{N-1}
179 a_{mn}\\exp\\left\\{-2\\pi i \\left({mk\\over M}+{nl\\over N}\\right)\\right\\}
180 \\qquad k = 0, \\ldots, M-1;\\quad l = 0, \\ldots, N-1,
181
182which extends in the obvious way to higher dimensions, and the inverses
183in higher dimensions also extend in the same way.
184
185References
186----------
187
188.. [CT] Cooley, James W., and John W. Tukey, 1965, "An algorithm for the
189 machine calculation of complex Fourier series," *Math. Comput.*
190 19: 297-301.
191
192.. [NR] Press, W., Teukolsky, S., Vetterline, W.T., and Flannery, B.P.,
193 2007, *Numerical Recipes: The Art of Scientific Computing*, ch.
194 12-13. Cambridge Univ. Press, Cambridge, UK.
195
196Examples
197--------
198
199For examples, see the various functions.
200
201"""
202
203from . import _pocketfft, helper
204from ._pocketfft import *
205from .helper import *
206
207__all__ = _pocketfft.__all__.copy()
208__all__ += helper.__all__
209
210from numpy._pytesttester import PytestTester
211test = PytestTester(__name__)
212del PytestTester