Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/numpy/fft/__init__.py: 100%

Shortcuts on this page

r m x   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

8 statements  

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