Content deleted Content added
→Variants of the Fourier transform: note DTFT |
|||
Line 36:
:<math>x_k = \frac{1}{n} \sum_{j=0}^{n-1} f_j e^{2\pi ijk/n} \quad \quad k = 0,\dots,n-1</math>
where ''f''<sub>''j''</sub> are the Fourier amplitudes. Although applying this formula directly would require O(''n''<sup>2</sup>) operations, it can be computed in only O(''n'' log ''n'') operations using a [[fast Fourier transform]] (FFT) algorithm (see [[Big O notation]]), which makes Fourier transformation a practical and important operation on computers.
The DFT is a special case of (and is sometimes used as an approximation for) the [[discrete-time Fourier transform]] (DTFT), in which the ''x''<sub>''k''</sub> are defined over discrete but infinite domains, and thus the spectrum is continuous and periodic. The DTFT is essentially the inverse of the Fourier series.
These Fourier variants can also be generalized to Fourier transforms on arbitrary [[locally compact]] [[abelian]] [[topological group]]s, which are studied in [[harmonic analysis]]; there, one transforms from a group to its [[dual group]]. This treatment also allows a general formulation of the [[convolution theorem]], which relates Fourier transforms and [[convolution]]s. See also the [[Pontryagin duality]] for the generalized underpinnings of the Fourier transform.
| |||