# pypy / site-packages / numpy / fft / info.py

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