Return discrete Fourier transform of real or complex sequence.
The returned complex array contains y(0), y(1),..., y(n-1) where
y(j) = (x * exp(-2*pi*sqrt(-1)*j*np.arange(n)/n)).sum().
Parameters: | x : array_like
n : int, optional
axis : int, optional
overwrite_x : bool, optional
|
---|---|
Returns: | z : complex ndarray
|
Notes
The packing of the result is “standard”: If A = fft(a, n), then A[0] contains the zero-frequency term, A[1:n/2] contains the positive-frequency terms, and A[n/2:] contains the negative-frequency terms, in order of decreasingly negative frequency. So for an 8-point transform, the frequencies of the result are [0, 1, 2, 3, -4, -3, -2, -1]. To rearrange the fft output so that the zero-frequency component is centered, like [-4, -3, -2, -1, 0, 1, 2, 3], use fftshift.
For n even, A[n/2] contains the sum of the positive and negative-frequency terms. For n even and x real, A[n/2] will always be real.
This function is most efficient when n is a power of two, and least efficient when n is prime.
If the data type of x is real, a “real FFT” algorithm is automatically used, which roughly halves the computation time. To increase efficiency a little further, use rfft, which does the same calculation, but only outputs half of the symmetrical spectrum. If the data is both real and symmetrical, the dct can again double the efficiency, by generating half of the spectrum from half of the signal.
Examples
>>> from scipy.fftpack import fft, ifft
>>> x = np.arange(5)
>>> np.allclose(fft(ifft(x)), x, atol=1e-15) # within numerical accuracy.
True