Standard FFTs#

Real FFTs#

Hermitian FFTs#

Helper routines#

Background information#

Fourier analysis is fundamentally a method for expressing a function as asum of periodic components, and for recovering the function from thosecomponents. When both the function and its Fourier transform arereplaced with discretized counterparts, it is called the discrete Fouriertransform (DFT). The DFT has become a mainstay of numerical computing inpart because of a very fast algorithm for computing it, called the FastFourier Transform (FFT), which was known to Gauss (1805) and was broughtto light in its current form by Cooley and Tukey[CT]. Press et al.[NR]provide an accessible introduction to Fourier analysis and itsapplications.

Because the discrete Fourier transform separates its input intocomponents that contribute at discrete frequencies, it has a great numberof applications in digital signal processing, e.g., for filtering, and inthis context the discretized input to the transform is customarilyreferred to as asignal, which exists in thetime domain. The outputis called aspectrum ortransform and exists in thefrequencydomain.

Implementation details#

There are many ways to define the DFT, varying in the sign of theexponent, normalization, etc. In this implementation, the DFT is definedas

The DFT is in general defined for complex inputs and outputs, and asingle-frequency component at linear frequency\(f\) isrepresented by a complex exponential\(a_m = \exp\{2\pi i\,f m\Delta t\}\), where\(\Delta t\)is the sampling interval.

The values in the result follow so-called “standard” order: IfA=fft(a,n), thenA[0] contains the zero-frequency term (the sum ofthe signal), which is always purely real for real inputs. ThenA[1:n/2]contains the positive-frequency terms, andA[n/2+1:] contains thenegative-frequency terms, in order of decreasingly negative frequency.For an even number of input points,A[n/2] represents both positive andnegative Nyquist frequency, and is also purely real for real input. Foran odd number of input points,A[(n-1)/2] contains the largest positivefrequency, whileA[(n+1)/2] contains the largest negative frequency.The routinenp.fft.fftfreq(n) returns an array giving the frequenciesof corresponding elements in the output. The routinenp.fft.fftshift(A) shifts transforms and their frequencies to put thezero-frequency components in the middle, andnp.fft.ifftshift(A) undoesthat shift.

When the inputa is a time-domain signal andA=fft(a),np.abs(A)is its amplitude spectrum andnp.abs(A)**2 is its power spectrum.The phase spectrum is obtained bynp.angle(A).

The inverse DFT is defined as

It differs from the forward transform by the sign of the exponentialargument and the default normalization by\(1/n\).

Type Promotion#

numpy.fft promotesfloat32 andcomplex64 arrays tofloat64 andcomplex128 arrays respectively. For an FFT implementation that does notpromote input arrays, seescipy.fftpack.

Normalization#

The argumentnorm indicates which direction of the pair of direct/inversetransforms is scaled and with what normalization factor.The default normalization ("backward") has the direct (forward) transformsunscaled and the inverse (backward) transforms scaled by\(1/n\). It ispossible to obtain unitary transforms by setting the keyword argumentnormto"ortho" so that both direct and inverse transforms are scaled by\(1/\sqrt{n}\). Finally, setting the keyword argumentnorm to"forward" has the direct transforms scaled by\(1/n\) and the inversetransforms unscaled (i.e. exactly opposite to the default"backward").None is an alias of the default option"backward" for backwardcompatibility.

Real and Hermitian transforms#

When the input is purely real, its transform is Hermitian, i.e., thecomponent at frequency\(f_k\) is the complex conjugate of thecomponent at frequency\(-f_k\), which means that for realinputs there is no information in the negative frequency components thatis not already available from the positive frequency components.The family ofrfft functions isdesigned to operate on real inputs, and exploits this symmetry bycomputing only the positive frequency components, up to and including theNyquist frequency. Thus,n input points producen/2+1 complexoutput points. The inverses of this family assumes the same symmetry ofits input, and for an output ofn points usesn/2+1 input points.

Correspondingly, when the spectrum is purely real, the signal isHermitian. Thehfft family of functions exploits this symmetry byusingn/2+1 complex points in the input (time) domain forn realpoints in the frequency domain.

In higher dimensions, FFTs are used, e.g., for image analysis andfiltering. The computational efficiency of the FFT means that it canalso be a faster way to compute large convolutions, using the propertythat a convolution in the time domain is equivalent to a point-by-pointmultiplication in the frequency domain.

Higher dimensions#

In two dimensions, the DFT is defined as

which extends in the obvious way to higher dimensions, and the inversesin higher dimensions also extend in the same way.

References#

Examples#

For examples, see the various functions.