| Fourier transforms |
|---|
Inmathematics, thediscrete Fourier transform (DFT) converts a finite sequence of equally-spacedsamples of afunction into a same-length sequence of equally-spaced samples of thediscrete-time Fourier transform (DTFT), which is acomplex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence.[A][1] An inverse DFT (IDFT) is aFourier series, using the DTFT samples as coefficients ofcomplexsinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be afrequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous (and periodic), and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.
The DFT is used in theFourier analysis of many practical applications.[2] Indigital signal processing, the function is any quantity orsignal that varies over time, such as the pressure of asound wave, aradio signal, or dailytemperature readings, sampled over a finite time interval (often defined by awindow function[3]). Inimage processing, the samples can be the values ofpixels along a row or column of araster image. The DFT is also used to efficiently solvepartial differential equations, and to perform other operations such asconvolutions or multiplying large integers.
Since it deals with a finite amount of data, it can be implemented incomputers bynumerical algorithms or even dedicatedhardware. These implementations usually employ efficientfast Fourier transform (FFT) algorithms;[4] so much so that the terms "FFT" and "DFT" are often used interchangeably. Prior to its current usage, the "FFT"initialism may have also been used for the ambiguous term "finite Fourier transform".
Thediscrete Fourier transform transforms asequence ofNcomplex numbers into another sequence of complex numbers, which is defined by:
| Eq.1 |
The transform is sometimes denoted by the symbol, as in or or.[B]
Eq.1 can be interpreted or derived in various ways, for example:
Eq.1 can also be evaluated outside the domain, and that extended sequence is-periodic. Accordingly, other sequences of indices are sometimes used, such as (if is even) and (if is odd), which amounts to swapping the left and right halves of the result of the transform.[5]
The inverse transform is given by:
| Eq.2 |
Eq.2. is also-periodic (in index n). InEq.2, each is a complex number whose polar coordinates are the amplitude and phase of a complex sinusoidal component of function (seeDiscrete Fourier series) The sinusoid'sfrequency is cycles per samples.
The normalization factor multiplying the DFT and IDFT (here 1 and) and the signs of the exponents are the most commonconventions. The only actual requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be An uncommon normalization of for both the DFT and IDFT makes the transform-pair unitary.
This example demonstrates how to apply the DFT to a sequence of length and the input vector
Calculating the DFT of usingEq.1
results in
The DFT is a linear transform, i.e. if and, then for any complex numbers:
Reversing the time (i.e. replacing by)[D] in corresponds to reversing the frequency (i.e. by).[6]: p.421 Mathematically, if represents the vectorx then
If then.[6]: p.423
This table shows some mathematical operations on in the time domain and the corresponding effects on its DFT in the frequency domain.
| Property | Time domain | Frequency domain |
|---|---|---|
| Real part in time | ||
| Imaginary part in time | ||
| Real part in frequency | ||
| Imaginary part in frequency |
The vectors, for, form anorthogonal basis over the set ofN-dimensional complex vectors:
where is theKronecker delta. (In the last step, the summation is trivial if, where it is1 + 1 + ⋯ =N, and otherwise is ageometric series that can be explicitly summed to obtain zero.) This orthogonality condition can be used to derive the formula for the IDFT from the definition of the DFT, and is equivalent to the unitarity property below.
If and are the DFTs of and respectively thenParseval's theorem states:
where the star denotescomplex conjugation. ThePlancherel theorem is a special case of Parseval's theorem and states:
These theorems are also equivalent to the unitary condition below.
The periodicity can be shown directly from the definition:
Similarly, it can be shown that the IDFT formula leads to a periodic extension of.
Multiplying by alinear phase for some integerm corresponds to acircular shift of the output: is replaced by, where the subscript is interpretedmoduloN (i.e., periodically). Similarly, a circular shift of the input corresponds to multiplying the output by a linear phase. Mathematically, if represents the vectorx then
Theconvolution theorem for thediscrete-time Fourier transform (DTFT) indicates that a convolution of two sequences can be obtained as the inverse transform of the product of the individual transforms. An important simplification occurs when one of sequences is N-periodic, denoted here by because is non-zero at only discrete frequencies (seeDTFT § Periodic data), and therefore so is its product with the continuous function That leads to a considerable simplification of the inverse transform.
where is aperiodic summation of the sequence:
Customarily, the DFT and inverse DFT summations are taken over the domain. Defining those DFTs as and, the result is:
In practice, the sequence is usually lengthN or less, and is a periodic extension of an N-length-sequence, which can also be expressed as acircular function:
Then the convolution can be written as:
which gives rise to the interpretation as acircular convolution of and[7][8] It is often used to efficiently compute their linear convolution. (seeCircular convolution,Fast convolution algorithms, andOverlap-save)
Similarly, thecross-correlation of and is given by:
As seen above, the discrete Fourier transform has the fundamental property of carrying convolution into componentwise product. A natural question is whether it is the only one with this ability. It has been shown[9][10] that any linear transform that turns convolution into pointwise product is the DFT up to a permutation of coefficients. Since the number of permutations of n elements equals n!, there exists exactly n! linear and invertible maps with the same fundamental property as the DFT with respect to convolution.
It can also be shown that:
Thetrigonometric interpolation polynomial
where the coefficientsXk are given by the DFT ofxn above, satisfies the interpolation property for.
For evenN, notice that theNyquist component is handled specially.
This interpolation isnot unique: aliasing implies that one could addN to any of the complex-sinusoid frequencies (e.g. changing to) without changing the interpolation property, but givingdifferent values in between the points. The choice above, however, is typical because it has two useful properties. First, it consists of sinusoids whose frequencies have the smallest possible magnitudes: the interpolation isbandlimited. Second, if the are real numbers, then is real as well.
In contrast, the most obvious trigonometric interpolation polynomial is the one in which the frequencies range from 0 to (instead of roughly to as above), similar to the inverse DFT formula. This interpolation doesnot minimize the slope, and isnot generally real-valued for real; its use is a common mistake.
Another way of looking at the DFT is to note that in the above discussion, the DFT can be expressed as theDFT matrix, aVandermonde matrix,introduced by Sylvester in 1867,
where is a primitiveNth root of unity.
For example, in the case when,, and
(which is aHadamard matrix) or when as in theDiscrete Fourier transform § Example above,, and
The inverse transform is then given by the inverse of the above matrix,
Withunitary normalization constants, the DFT becomes aunitary transformation, defined by a unitary matrix:
where is thedeterminant function. The determinant is the product of the eigenvalues, which are always or as described below. In a real vector space, a unitary transformation can be thought of as simply a rigid rotation of the coordinate system, and all of the properties of a rigid rotation can be found in the unitary DFT.
The orthogonality of the DFT is now expressed as anorthonormality condition (which arises in many areas of mathematics as described inroot of unity):
IfX is defined as the unitary DFT of the vectorx, then
and theParseval's theorem is expressed as
If we view the DFT as just a coordinate transformation which simply specifies the components of a vector in a new coordinate system, then the above is just the statement that thedot product of two vectors is preserved under a unitary DFT transformation. For the special case, this implies that the length of a vector is preserved as well — this is justPlancherel theorem,
A consequence of thecircular convolution theorem is that the DFT matrixF diagonalizes anycirculant matrix.
A useful property of the DFT is that the inverse DFT can be easily expressed in terms of the (forward) DFT, via several well-known "tricks". (For example, in computations, it is often convenient to only implement a fast Fourier transform corresponding to one transform direction and then to get the other transform direction from the first.)
First, we can compute the inverse DFT by reversing all but one of the inputs (Duhamelet al., 1988):
(As usual, the subscripts are interpretedmoduloN; thus, for, we have.)
Second, one can also conjugate the inputs and outputs:
Third, a variant of this conjugation trick, which is sometimes preferable because it requires no modification of the data values, involves swapping real and imaginary parts (which can be done on a computer simply by modifyingpointers). Define as with its real and imaginary parts swapped—that is, if then is. Equivalently, equals. Then
That is, the inverse transform is the same as the forward transform with the real and imaginary parts swapped for both input and output, up to a normalization (Duhamelet al., 1988).
The conjugation trick can also be used to define a new transform, closely related to the DFT, that isinvolutory—that is, which is its own inverse. In particular, is clearly its own inverse:. A closely related involutory transformation (by a factor of) is, since the factors in cancel the 2. For real inputs, the real part of is none other than thediscrete Hartley transform, which is also involutory.
Theeigenvalues of the DFT matrix are simple and well-known, whereas theeigenvectors are complicated, not unique, and are the subject of ongoing research. Explicit formulas are given with a significant amount of number theory.[11]
Consider the unitary form defined above for the DFT of lengthN, where
This matrix satisfies thematrix polynomial equation:
This can be seen from the inverse properties above: operating twice gives the original data in reverse order, so operating four times gives back the original data and is thus theidentity matrix. This means that the eigenvalues satisfy the equation:
Therefore, the eigenvalues of are the fourthroots of unity: is +1, −1, +i, or −i.
Since there are only four distinct eigenvalues for this matrix, they have somemultiplicity. The multiplicity gives the number oflinearly independent eigenvectors corresponding to each eigenvalue. (There areN independent eigenvectors; a unitary matrix is neverdefective.)
The problem of their multiplicity was solved by McClellan and Parks (1972), although it was later shown to have been equivalent to a problem solved byGauss (Dickinson and Steiglitz, 1982). The multiplicity depends on the value ofNmodulo 4, and is given by the following table:
| sizeN | λ = +1 | λ = −1 | λ = −i | λ = +i |
|---|---|---|---|---|
| 4m | m + 1 | m | m | m − 1 |
| 4m + 1 | m + 1 | m | m | m |
| 4m + 2 | m + 1 | m + 1 | m | m |
| 4m + 3 | m + 1 | m + 1 | m + 1 | m |
Otherwise stated, thecharacteristic polynomial of is:
No simple analytical formula for general eigenvectors is known. Moreover, the eigenvectors are not unique because any linear combination of eigenvectors for the same eigenvalue is also an eigenvector for that eigenvalue. Various researchers have proposed different choices of eigenvectors, selected to satisfy useful properties likeorthogonality and to have "simple" forms (e.g., McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiyev and Wolf, 1997; Candanet al., 2000; Hannaet al., 2004; Gurevich and Hadani, 2008).
One method to construct DFT eigenvectors to an eigenvalue is based on the linear combination of operators:[12][13][14]
For an arbitrary vector, vector satisfies:
hence, vector is, indeed, the eigenvector of DFT matrix. Operators project vectors onto subspaces which are orthogonal for each value of.[13] That is, for two eigenvectors, and we have:
However, in general, projection operator method does not produce orthogonal eigenvectors within one subspace.[14] The operator can be seen as a matrix, whose columns are eigenvectors of, but they are not orthogonal. When a set of vectors, spanning-dimensional space (where is the multiplicity of eigenvalue) is chosen to generate the set of eigenvectors to eigenvalue, the mutual orthogonality of is not guaranteed. However, the orthogonal set can be obtained by further applying orthogonalization algorithm to the set, e.g.Gram-Schmidt process.[15]
A straightforward approach to obtain DFT eigenvectors is to discretize an eigenfunction of the continuousFourier transform,of which the most famous is theGaussian function.Sinceperiodic summation of the function means discretizing its frequency spectrumand discretization means periodic summation of the spectrum,the discretized and periodically summed Gaussian function yields an eigenvector of the discrete transform:
The closed form expression for the series can be expressed byJacobi theta functions as
Several other simple closed-form analytical eigenvectors for special DFT periodN were found (Kong, 2008 and Casper-Yakimov, 2024):
For DFT periodN = 2L + 1 = 4K + 1, whereK is an integer, the following is an eigenvector of DFT:
For DFT periodN = 2L = 4K, whereK is an integer, the following are eigenvectors of DFT:
For DFT periodN = 4K - 1, whereK is an integer, the following are eigenvectors of DFT:
The choice of eigenvectors of the DFT matrix has become important in recent years in order to define a discrete analogue of thefractional Fourier transform—the DFT matrix can be taken to fractional powers by exponentiating the eigenvalues (e.g., Rubio and Santhanam, 2005). For thecontinuous Fourier transform, the natural orthogonal eigenfunctions are theHermite functions, so various discrete analogues of these have been employed as the eigenvectors of the DFT, such as theKravchuk polynomials (Atakishiyev and Wolf, 1997). The "best" choice of eigenvectors to define a fractional discrete Fourier transform remains an open question, however.
If the random variableXk is constrained by
then
may be considered to represent a discreteprobability mass function ofn, with an associated probability mass function constructed from the transformed variable,
For the case of continuous functions and, theHeisenberg uncertainty principle states that
where and are the variances of and respectively, with the equality attained in the case of a suitably normalizedGaussian distribution. Although the variances may be analogously defined for the DFT, an analogous uncertainty principle is not useful, because the uncertainty will not be shift-invariant. Still, a meaningful uncertainty principle has been introduced by Massar and Spindel.[16]
However, the Hirschmanentropic uncertainty will have a useful analog for the case of the DFT.[17] The Hirschman uncertainty principle is expressed in terms of theShannon entropy of the two probability functions.
In the discrete case, the Shannon entropies are defined as
and
and theentropic uncertainty principle becomes[17]
The equality is obtained for equal to translations and modulations of a suitably normalizedKronecker comb of period where is any exact integer divisor of. The probability mass function will then be proportional to a suitably translatedKronecker comb of period.[17]
There is also a well-known deterministic uncertainty principle that uses signal sparsity (or the number of non-zero coefficients).[18] Let and be the number of non-zero elements of the time and frequency sequences and, respectively. Then,
As an immediate consequence of theinequality of arithmetic and geometric means, one also has. Both uncertainty principles were shown to be tight for specifically chosen "picket-fence" sequences (discrete impulse trains), and find practical use for signal recovery applications.[18]
It follows that for even and are real-valued, and the remainder of the DFT is completely specified by just complex numbers.
It is possible to shift the transform sampling in time and/or frequency domain by some real shiftsa andb, respectively. This is sometimes known as ageneralized DFT (orGDFT), also called theshifted DFT oroffset DFT, and has analogous properties to the ordinary DFT:
Most often, shifts of (half a sample) are used.While the ordinary DFT corresponds to a periodic signal in both time and frequency domains, produces a signal that is anti-periodic in frequency domain () and vice versa for.Thus, the specific case of is known as anodd-time odd-frequency discrete Fourier transform (or O2 DFT).Such shifted transforms are most often used for symmetric data, to represent different boundary symmetries, and for real-symmetric data they correspond to different forms of the discretecosine andsine transforms.
Another interesting choice is, which is called thecentered DFT (orCDFT). The centered DFT has the useful property that, whenN is a multiple of four, all four of its eigenvalues (see above) have equal multiplicities (Rubio and Santhanam, 2005)[19]
The term GDFT is also used for the non-linear phase extensions of DFT. Hence, GDFT method provides a generalization for constant amplitude orthogonal block transforms including linear and non-linear phase types. GDFT is a frameworkto improve time and frequency domain properties of the traditional DFT, e.g. auto/cross-correlations, by the addition of the properly designed phase shaping function (non-linear, in general) to the original linear phase functions (Akansu and Agirman-Tosun, 2010).[20]
The discrete Fourier transform can be viewed as a special case of thez-transform, evaluated on the unit circle in the complex plane; more general z-transforms correspond tocomplex shiftsa andb above.
The ordinary DFT transforms a one-dimensional sequence orarray that is a function of exactly one discrete variablen. The multidimensional DFT of a multidimensional array that is a function ofd discrete variables for in is defined by:
where as above and thed output indices run from. This is more compactly expressed invector notation, where we define and asd-dimensional vectors of indices from 0 to, which we define as:
where the division is defined as to be performed element-wise, and the sum denotes the set of nested summations above.
The inverse of the multi-dimensional DFT is, analogous to the one-dimensional case, given by:
As the one-dimensional DFT expresses the input as a superposition of sinusoids, the multidimensional DFT expresses the input as a superposition ofplane waves, or multidimensional sinusoids. The direction of oscillation in space is. The amplitudes are. This decomposition is of great importance for everything fromdigital image processing (two-dimensional) to solvingpartial differential equations. The solution is broken up into plane waves.
The multidimensional DFT can be computed by thecomposition of a sequence of one-dimensional DFTs along each dimension. In the two-dimensional case the independent DFTs of the rows (i.e., along) are computed first to form a new array. Then the independent DFTs ofy along the columns (along) are computed to form the final result. Alternatively the columns can be computed first and then the rows. The order is immaterial because the nested summations abovecommute.
An algorithm to compute a one-dimensional DFT is thus sufficient to efficiently compute a multidimensional DFT. This approach is known as therow-column algorithm. There are also intrinsicallymultidimensional FFT algorithms.
For input data consisting ofreal numbers, the DFT outputs have a conjugate symmetry similar to the one-dimensional case above:
where the star again denotes complex conjugation and the-th subscript is again interpreted modulo (for).
The DFT has seen wide usage across a large number of fields; we only sketch a few examples below (see also the references at the end). All applications of the DFT depend crucially on the availability of a fast algorithm to compute discrete Fourier transforms and their inverses, afast Fourier transform.
When the DFT is used forsignal spectral analysis, the sequence usually represents a finite set of uniformly spaced time-samples of some signal, where represents time. The conversion from continuous time to samples (discrete-time) changes the underlyingFourier transform of into adiscrete-time Fourier transform (DTFT), which generally entails a type of distortion calledaliasing. Choice of an appropriate sample-rate (seeNyquist rate) is the key to minimizing that distortion. Similarly, the conversion from a very long (or infinite) sequence to a manageable size entails a type of distortion calledleakage, which is manifested as a loss of detail (a.k.a. resolution) in the DTFT. Choice of an appropriate sub-sequence length is the primary key to minimizing that effect. When the available data (and time to process it) is more than the amount needed to attain the desired frequency resolution, a standard technique is to perform multiple DFTs, for example to create aspectrogram. If the desired result is a power spectrum and noise or randomness is present in the data, averaging the magnitude components of the multiple DFTs is a useful procedure to reduce thevariance of the spectrum (also called aperiodogram in this context); two examples of such techniques are theWelch method and theBartlett method; the general subject of estimating the power spectrum of a noisy signal is calledspectral estimation.
A final source of distortion (or perhapsillusion) is the DFT itself, because it is just a discrete sampling of the DTFT, which is a function of a continuous frequency domain. That can be mitigated by increasing the resolution of the DFT. That procedure is illustrated at§ Sampling the DTFT.
Steps to Perform Spectral Analysis of Audio Signal
1.Recording and Pre-Processing the Audio Signal
Begin by recording the audio signal, which could be a spoken password,music, or any othersound. Once recorded, the audio signal is denoted as x[n], where n represents the discrete time index. To enhance the accuracy of spectral analysis, any unwanted noise should be reduced using appropriatefiltering techniques.
2.Plotting the Original Time-Domain Signal
Afternoise reduction, the audio signal is plotted in the time domain to visualize its characteristics over time. This helps in understanding the amplitude variations of the signal as afunction of time, which provides an initial insight into the signal's behavior.
3.Transforming the Signal from Time Domain to Frequency Domain
The next step is to transform the audio signal from the time domain to the frequency domain using the Discrete Fourier Transform (DFT). The DFT is defined as:
where N is the total number of samples, k represents the frequency index, and X[k] is the complex-valued frequency spectrum of the signal. The DFT allows for decomposing the signal into its constituent frequency components, providing a representation that indicates which frequencies are present and their respective magnitudes.
4.Plotting the Magnitude Spectrum
The magnitude of the frequency-domain representation X[k] is plotted to analyze the spectral content. The magnitude spectrum shows how the energy of the signal is distributed across different frequencies, which is useful for identifying prominent frequency components. It is calculated as:
Analyze a discrete-time audio signal in the frequency domain using the DFT to identify its frequency components
Let's consider a simple discrete-time audio signal represented as:
where n represents discrete time samples of the signal.
1.Time-Domain Signal Representation
The given time-domain signal is:
The DFT is calculated using the formula:
where N is the number of samples (in this case, N=4).
Let's compute X[k] for k=0,1,2,3
For k=0:
For k=1:
For k=2:
For k=3:
The magnitude of X[k] represents the strength of each frequency component:
The resulting frequency components indicate the distribution of signal energy at different frequencies. The peaks in the magnitude spectrum correspond to dominant frequencies in the original signal.
The discrete Fourier transform is widely used with spatial frequencies in modeling the way that light, electrons, and other probes travel through optical systems and scatter from objects in two and three dimensions. The dual (direct/reciprocal) vector space of three dimensional objects further makes available a three dimensional reciprocal lattice, whose construction from translucent object shadows (via theFourier slice theorem) allows tomographic reconstruction of three dimensional objects with a wide range of applications e.g. in modern medicine.
See§ FFT filter banks and§ Sampling the DTFT.
The field of digital signal processing relies heavily on operations in the frequency domain (i.e. on the Fourier transform). For example, severallossy image and sound compression methods employ the discrete Fourier transform: the signal is cut into short segments, each is transformed, and then the Fourier coefficients of high frequencies, which are assumed to be unnoticeable, are discarded. The decompressor computes the inverse transform based on this reduced number of Fourier coefficients. (Compression applications often use a specialized form of the DFT, thediscrete cosine transform or sometimes themodified discrete cosine transform.)Some relatively recent compression algorithms, however, usewavelet transforms, which give a more uniform compromise between time and frequency domain than obtained by chopping data into segments and transforming each segment. In the case ofJPEG2000, this avoids the spurious image features that appear when images are highly compressed with the originalJPEG.
Discrete Fourier transforms are often used to solvepartial differential equations, where again the DFT is used as an approximation for theFourier series (which is recovered in the limit of infiniteN). The advantage of this approach is that it expands the signal in complex exponentials, which are eigenfunctions of differentiation:. Thus, in the Fourier representation, differentiation is simple—we just multiply by. (However, the choice of is not unique due to aliasing; for the method to be convergent, a choice similar to that in thetrigonometric interpolation section above should be used.) Alinear differential equation with constant coefficients is transformed into an easily solvable algebraic equation. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called aspectral method.
Suppose we wish to compute the polynomial productc(x) =a(x) ·b(x). The ordinary product expression for the coefficients ofc involves a linear (acyclic) convolution, where indices do not "wrap around." This can be rewritten as a cyclic convolution by taking the coefficient vectors fora(x) andb(x) with constant term first, then appending zeros so that the resultant coefficient vectorsa andb have dimensiond > deg(a(x)) + deg(b(x)). Then,
Wherec is the vector of coefficients forc(x), and the convolution operator is defined so
But convolution becomes multiplication under the DFT:
Here the vector product is taken elementwise. Thus the coefficients of the product polynomialc(x) are just the terms 0, ..., deg(a(x)) + deg(b(x)) of the coefficient vector
With afast Fourier transform, the resulting algorithm takesO(N log N) arithmetic operations. Due to its simplicity and speed, theCooley–Tukey FFT algorithm, which is limited tocomposite sizes, is often chosen for the transform operation. In this case,d should be chosen as the smallest integer greater than the sum of the input polynomial degrees that is factorizable into small prime factors (e.g. 2, 3, and 5, depending upon the FFT implementation).
The fastest knownalgorithms for the multiplication of very largeintegers use the polynomial multiplication method outlined above. Integers can be treated as the value of a polynomial evaluated specifically at the number base, with the coefficients of the polynomial corresponding to the digits in that base (ex.). After polynomial multiplication, a relatively low-complexity carry-propagation step completes the multiplication.
When data isconvolved with a function with wide support, such as for downsampling by a large sampling ratio, because of theConvolution theorem and the FFT algorithm, it may be faster to transform it, multiply pointwise by the transform of the filter and then reverse transform it. Alternatively, a good filter is obtained by simply truncating the transformed data and re-transforming the shortened data set.
| Note | ||
|---|---|---|
| Frequency shift theorem | ||
| Time shift theorem | ||
| Real DFT | ||
| from thegeometric progression formula | ||
| from thebinomial theorem | ||
| is a rectangularwindow function ofW points centered onn=0, whereW is anodd integer, and is asinc-like function (specifically, is aDirichlet kernel) | ||
| Discretization andperiodic summation of the scaledGaussian functions for. Since either or is larger than one and thus warrants fast convergence of one of the two series, for large you may choose to compute the frequency spectrum and convert to the time domain using the discrete Fourier transform. |
The DFT can be interpreted as a complex-valuedrepresentation of the finitecyclic group. In other words, a sequence of complex numbers can be thought of as an element of-dimensional complex space or equivalently a function from the finite cyclic group of order to the complex numbers,. So is aclass function on the finite cyclic group, and thus can be expressed as a linear combination of the irreducible characters of this group, which are the roots of unity.
From this point of view, one may generalize the DFT to representation theory generally, or more narrowly to therepresentation theory of finite groups.
More narrowly still, one may generalize the DFT by either changing the target (taking values in a field other than the complex numbers), or the domain (a group other than a finite cyclic group), as detailed in the sequel.
Many of the properties of the DFT only depend on the fact that is aprimitive root of unity, sometimes denoted or (so that). Such properties include the completeness, orthogonality, Plancherel/Parseval, periodicity, shift, convolution, and unitarity properties above, as well as many FFT algorithms. For this reason, the discrete Fourier transform can be defined by using roots of unity infields other than the complex numbers, and such generalizations are commonly callednumber-theoretic transforms (NTTs) in the case offinite fields. For more information, seenumber-theoretic transform anddiscrete Fourier transform (general).
The standard DFT acts on a sequencex0,x1, ...,xN−1 of complex numbers, which can be viewed as a function {0, 1, ...,N − 1} →C. The multidimensional DFT acts on multidimensional sequences, which can be viewed as functions
This suggests the generalization toFourier transforms on arbitrary finite groups, which act on functionsG →C whereG is afinite group. In this framework, the standard DFT is seen as the Fourier transform on acyclic group, while the multidimensional DFT is a Fourier transform on a direct sum of cyclic groups.
Further, Fourier transform can be on cosets of a group.
There are various alternatives to the DFT for various applications, prominent among which arewavelets. The analog of the DFT is thediscrete wavelet transform (DWT). From the point of view oftime–frequency analysis, a key limitation of the Fourier transform is that it does not includelocation information, onlyfrequency information, and thus has difficulty in representing transients. As wavelets have location as well as frequency, they are better able to represent location, at the expense of greater difficulty representing frequency. For details, seecomparison of the discrete wavelet transform with the discrete Fourier transform.
This is the most important numerical algorithm of our lifetime...
{{cite journal}}: CS1 maint: multiple names: authors list (link){{cite web}}: CS1 maint: location (link){{cite journal}}: CS1 maint: multiple names: authors list (link)