Discrete Fourier transform
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the discrete Fourier transform (DFT) is a specific kind of discrete transform
Discrete transform
In signal processing, discrete transforms are mathematical transforms, often linear transforms, of signals between discrete domains, such as between discrete time and discrete frequency....

, used in Fourier analysis. It transforms one function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

into another, which is called the frequency domain
Frequency domain
In electronics, control systems engineering, and statistics, frequency domain is a term used to describe the domain for analysis of mathematical functions or signals with respect to frequency, rather than time....

representation, or simply the DFT, of the original function (which is often a function in the time domain
Time domain
Time domain is a term used to describe the analysis of mathematical functions, physical signals or time series of economic or environmental data, with respect to time. In the time domain, the signal or function's value is known for all real numbers, for the case of continuous time, or at various...

). But the DFT requires an input function that is discrete and whose non-zero values have a limited (finite) duration. Such inputs are often created by sampling
Sampling (signal processing)
In signal processing, sampling is the reduction of a continuous signal to a discrete signal. A common example is the conversion of a sound wave to a sequence of samples ....

a continuous function, like a person's voice. Unlike the discrete-time Fourier transform
Discrete-time Fourier transform
In mathematics, the discrete-time Fourier transform is one of the specific forms of Fourier analysis. As such, it transforms one function into another, which is called the frequency domain representation, or simply the "DTFT", of the original function . But the DTFT requires an input function...

(DTFT), it only evaluates enough frequency components to reconstruct the finite segment that was analyzed. Using the DFT implies that the finite segment that is analyzed is one period of an infinitely extended periodic signal; if this is not actually true, a window function
Window function
In signal processing, a window function is a mathematical function that is zero-valued outside of some chosen interval. For instance, a function that is constant inside the interval and zero elsewhere is called a rectangular window, which describes the shape of its graphical representation...

has to be used to reduce the artifacts in the spectrum. For the same reason, the inverse DFT cannot reproduce the entire time domain, unless the input happens to be periodic (forever). Therefore it is often said that the DFT is a transform for Fourier analysis of finite-domain discrete-time functions. The sinusoidal basis functions of the decomposition have the same properties.

The input to the DFT is a finite sequence of real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

or complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

s (with more abstract generalizations
Discrete Fourier transform (general)

discussed below), making the DFT ideal for processing information stored in computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...

s. In particular, the DFT is widely employed in signal processing
Digital signal processing
Digital signal processing is concerned with the representation of discrete time signals by a sequence of numbers or symbols and the processing of these signals. Digital signal processing and analog signal processing are subfields of signal processing...

and related fields to analyze the frequencies contained in a sampled signal, to solve partial differential equations, and to perform other operations such as convolution
Convolution
In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...

s or multiplying large integers. A key enabling factor for these applications is the fact that the DFT can be computed efficiently in practice using a fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

(FFT) algorithm.

FFT algorithms are so commonly employed to compute DFTs that the term "FFT" is often used to mean "DFT" in colloquial settings. Formally, there is a clear distinction: "DFT" refers to a mathematical transformation or function, regardless of how it is computed, whereas "FFT" refers to a specific family of algorithms for computing DFTs. The terminology is further blurred by the (now rare) synonym finite Fourier transform
Finite Fourier transform
In mathematics the finite Fourier transform may refer to either* another name for the discrete Fourier transformor* another name for the Fourier series coefficientsor...

for the DFT, which apparently predates the term "fast Fourier transform" (Cooley et al., 1969) but has the same initialism.

## Definition

The sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...

of N complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

s x0, ..., xN−1 is transformed into another sequence of N complex numbers according to the DFT formula:

The transform is sometimes denoted by the symbol , as in or or As a linear transformation
Linear transformation
In mathematics, a linear map, linear mapping, linear transformation, or linear operator is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. As a result, it always maps straight lines to straight lines or 0...

on a finite-dimensional vector space
Dimension (vector space)
In mathematics, the dimension of a vector space V is the cardinality of a basis of V. It is sometimes called Hamel dimension or algebraic dimension to distinguish it from other types of dimension...

, the DFT expression can also be written in terms of a DFT matrix
DFT matrix
A DFT matrix is an expression of a discrete Fourier transform as a matrix multiplication.-Definition:An N-point DFT is expressed as an N-by-N matrix multiplication as X = W x, where x is the original input signal, and X is the DFT of the signal.The transformation W of size N\times N can be defined...

; when scaled appropriately it becomes a unitary matrix and the Xk can thus be viewed as coefficients of x in an orthonormal basis
Orthonormal basis
In mathematics, particularly linear algebra, an orthonormal basis for inner product space V with finite dimension is a basis for V whose vectors are orthonormal. For example, the standard basis for a Euclidean space Rn is an orthonormal basis, where the relevant inner product is the dot product of...

.

The inverse discrete Fourier transform (IDFT) is given by:

These formulas can be interpreted or derived in various ways; for example, they can be interpreted as arising from the discrete-time Fourier transform (DTFT)
Discrete-time Fourier transform
In mathematics, the discrete-time Fourier transform is one of the specific forms of Fourier analysis. As such, it transforms one function into another, which is called the frequency domain representation, or simply the "DTFT", of the original function . But the DTFT requires an input function...

and its inverse when applied to a periodic sequence. (See:  Sampling the DTFT and A derivation of the discrete Fourier transform
A derivation of the discrete Fourier transform
In mathematics, computer science, and electrical engineering, the discrete Fourier transform , occasionally called the finite Fourier transform, is a transform for Fourier analysis of finite-domain discrete-time signals. As with most Fourier analysis, it expresses an input function in terms of a...

.)

An intuitive description of is that the complex numbers represent the amplitude and phase of the different sinusoidal components of the input "signal" . shows how to compute the as a sum of sinusoidal components with frequency
Frequency
Frequency is the number of occurrences of a repeating event per unit time. It is also referred to as temporal frequency.The period is the duration of one cycle in a repeating event, so the period is the reciprocal of the frequency...

cycles per sample. By writing the equation in this form, we are making extensive use of Euler's formula
Euler's formula
Euler's formula, named after Leonhard Euler, is a mathematical formula in complex analysis that establishes the deep relationship between the trigonometric functions and the complex exponential function...

to express sinusoids in terms of complex exponentials, which are much easier to manipulate. By writing in polar form, we obtain the sinusoid amplitude and phase from the complex modulus and argument of , respectively:

where atan2
Atan2
In trigonometry, the two-argument function atan2 is a variation of the arctangent function. For any real arguments and not both equal to zero, is the angle in radians between the positive -axis of a plane and the point given by the coordinates on it...

is the two-argument form of the arctan function. Note that the normalization factor multiplying the DFT and IDFT (here 1 and 1/N) and the signs of the exponents are merely conventions
Sign convention
In physics, a sign convention is a choice of the physical significance of signs for a set of quantities, in a case where the choice of sign is arbitrary. "Arbitrary" here means that the same physical system can be correctly described using different choices for the signs, as long as one set of...

, and differ in some treatments. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be 1/N. A normalization of for both the DFT and IDFT makes the transforms unitary, which has some theoretical advantages, but it is often more practical in numerical computation to perform the scaling all at once as above (and a unit scaling can be convenient in other ways).

(The convention of a negative sign in the exponent is often convenient because it means that is the amplitude of a "positive frequency" . Equivalently, the DFT is often thought of as a matched filter
Matched filter
In telecommunications, a matched filter is obtained by correlating a known signal, or template, with an unknown signal to detect the presence of the template in the unknown signal. This is equivalent to convolving the unknown signal with a conjugated time-reversed version of the template...

: when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1.)

In the following discussion the terms "sequence" and "vector" will be considered interchangeable.

### Completeness

The discrete Fourier transform is an invertible, linear transformation
Linear transformation
In mathematics, a linear map, linear mapping, linear transformation, or linear operator is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. As a result, it always maps straight lines to straight lines or 0...

with C denoting the set of complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

s. In other words, for any N > 0, an N-dimensional complex vector has a DFT and an IDFT which are in turn N-dimensional complex vectors.

### Orthogonality

The vectors
form an orthogonal basis
Orthogonal basis
In mathematics, particularly linear algebra, an orthogonal basis for an inner product space is a basis for whose vectors are mutually orthogonal...

over the set of N-dimensional complex vectors:

where is the Kronecker delta. 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.

### The Plancherel theorem and Parseval's theorem

If Xk and Yk are the DFTs of xn and yn respectively then the Plancherel theorem
Plancherel theorem
In mathematics, the Plancherel theorem is a result in harmonic analysis, proved by Michel Plancherel in 1910. It states that the integral of a function's squared modulus is equal to the integral of the squared modulus of its frequency spectrum....

states:

where the star denotes complex conjugation
Complex conjugate
In mathematics, complex conjugates are a pair of complex numbers, both having the same real part, but with imaginary parts of equal magnitude and opposite signs...

. Parseval's theorem
Parseval's theorem
In mathematics, Parseval's theorem usually refers to the result that the Fourier transform is unitary; loosely, that the sum of the square of a function is equal to the sum of the square of its transform. It originates from a 1799 theorem about series by Marc-Antoine Parseval, which was later...

is a special case of the Plancherel theorem and states:

These theorems are also equivalent to the unitary condition below.

### Periodicity

If the expression that defines the DFT is evaluated for all integers k instead of just for , then the resulting infinite sequence is a periodic extension of the DFT, periodic with period N.

The periodicity can be shown directly from the definition:

Similarly, it can be shown that the IDFT formula leads to a periodic extension.

### The shift theorem

Multiplying by a linear phase for some integer m corresponds to a circular shift of the output : is replaced by , where the subscript is interpreted modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

N (i.e., periodically). Similarly, a circular shift of the input corresponds to multiplying the output by a linear phase. Mathematically, if represents the vector x then
if

then

and

### Circular convolution theorem and cross-correlation theorem

The convolution theorem
Convolution theorem
In mathematics, the convolution theorem states that under suitableconditions the Fourier transform of a convolution is the pointwise product of Fourier transforms. In other words, convolution in one domain equals point-wise multiplication in the other domain...

for the continuous and discrete time Fourier transforms indicates that a convolution of two infinite sequences can be obtained as the inverse transform of the product of the individual transforms. With sequences and transforms of length N, a circularity
Circular convolution
The circular convolution, also known as cyclic convolution, of two aperiodic functions occurs when one of them is convolved in the normal way with a periodic summation of the other function.  That situation arises in the context of the Circular convolution theorem...

arises:

The quantity in parentheses is 0 for all values of m except those of the form  , where p is any integer. At those values, it is 1. It can therefore be replaced by an infinite sum of Kronecker delta functions, and we continue accordingly. Note that we can also extend the limits of m to infinity, with the understanding that the x and y sequences are defined as 0 outside [0,N-1]:

which is the convolution of the sequence with a sequence extended by periodic summation:

Similarly, it can be shown that:

which is the cross-correlation
Cross-correlation
In signal processing, cross-correlation is a measure of similarity of two waveforms as a function of a time-lag applied to one of them. This is also known as a sliding dot product or sliding inner-product. It is commonly used for searching a long-duration signal for a shorter, known feature...

of    and

A direct evaluation of the convolution or correlation summation (above) requires operations for an output sequence of length N.  An indirect method, using transforms, can take advantage of the efficiency of the fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

(FFT) to achieve much better performance. Furthermore, convolutions can be used to efficiently compute DFTs via Rader's FFT algorithm
Rader's algorithm is a fast Fourier transform algorithm that computes the discrete Fourier transform of prime sizes by re-expressing the DFT as a cyclic convolution...

and Bluestein's FFT algorithm
Bluestein's FFT algorithm
Bluestein's FFT algorithm , commonly called the chirp z-transform algorithm , is a fast Fourier transform algorithm that computes the discrete Fourier transform of arbitrary sizes by re-expressing the DFT as a convolution...

.

Methods have also been developed to use circular convolution as part of an efficient process that achieves normal (non-circular) convolution with an or sequence potentially much longer than the practical transform size (N). Two such methods are called overlap-save
Overlap-save method
Overlap–save is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal x[n] and a finite impulse response filter h[n]:...

### Convolution theorem duality

It can also be shown that:
which is the circular convolution of and .

### Trigonometric interpolation polynomial

The trigonometric interpolation polynomial for N even
Even and odd numbers
In mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...

, for N odd,
where the coefficients Xk are given by the DFT of xn above, satisfies the interpolation property for .

For even N, notice that the Nyquist component
Nyquist frequency
The Nyquist frequency, named after the Swedish-American engineer Harry Nyquist or the Nyquist–Shannon sampling theorem, is half the sampling frequency of a discrete signal processing system...

is handled specially.

This interpolation is not unique: aliasing implies that one could add N to any of the complex-sinusoid frequencies (e.g. changing to ) without changing the interpolation property, but giving different 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 is bandlimited
Bandlimited
Bandlimiting is the limiting of a deterministic or stochastic signal's Fourier transform or power spectral density to zero above a certain finite frequency...

. 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 does not minimize the slope, and is not generally real-valued for real ; its use is a common mistake.

### The unitary DFT

Another way of looking at the DFT is to note that in the above discussion, the DFT can be expressed as a Vandermonde matrix:

where

is a primitive Nth root of unity. The inverse transform is then given by the inverse of the above matrix:

With unitary
Unitary operator
In functional analysis, a branch of mathematics, a unitary operator is a bounded linear operator U : H → H on a Hilbert space H satisfyingU^*U=UU^*=I...

normalization constants , the DFT becomes a unitary transformation
Unitary transformation
In mathematics, a unitary transformation may be informally defined as a transformation that respects the inner product: the inner product of two vectors before the transformation is equal to their inner product after the transformation....

, defined by a unitary matrix:

where det  is the determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

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 an orthonormality condition (which arises in many areas of mathematics as described in root of unity
Root of unity
In mathematics, a root of unity, or de Moivre number, is any complex number that equals 1 when raised to some integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, field theory, and the discrete...

):

If is defined as the unitary DFT of the vector then

and the Plancherel theorem
Plancherel theorem
In mathematics, the Plancherel theorem is a result in harmonic analysis, proved by Michel Plancherel in 1910. It states that the integral of a function's squared modulus is equal to the integral of the squared modulus of its frequency spectrum....

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 the dot 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 just Parseval's theorem
Parseval's theorem
In mathematics, Parseval's theorem usually refers to the result that the Fourier transform is unitary; loosely, that the sum of the square of a function is equal to the sum of the square of its transform. It originates from a 1799 theorem about series by Marc-Antoine Parseval, which was later...

:

### Expressing the inverse DFT in terms of the DFT

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 the inputs:

(As usual, the subscripts are interpreted modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

N; 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 modifying pointers). Define swap() as with its real and imaginary parts swapped—that is, if then swap() is . Equivalently, swap() 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 (Duhamel et al., 1988).

The conjugation trick can also be used to define a new transform, closely related to the DFT, that is involutary—that is, which is its own inverse. In particular, is clearly its own inverse: . A closely related involutary transformation (by a factor of (1+i) /√2) is , since the factors in cancel the 2. For real inputs , the real part of is none other than the discrete Hartley transform
Discrete Hartley transform
A discrete Hartley transform is a Fourier-related transform of discrete, periodic data similar to the discrete Fourier transform , with analogous applications in signal processing and related fields. Its main distinction from the DFT is that it transforms real inputs to real outputs, with no...

, which is also involutary.

### Eigenvalues and eigenvectors

The eigenvalues of the DFT matrix are simple and well-known, whereas the eigenvectors are complicated, not unique, and are the subject of ongoing research.

Consider the unitary form defined above for the DFT of length N, where
This matrix satisfies the matrix polynomial
Matrix polynomial
In mathematics, a matrix polynomial is a polynomial with matrices as variables. Examples include:In mathematics, a matrix polynomial is a polynomial with matrices as variables. Examples include:...

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 the identity matrix
Identity matrix
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...

. This means that the eigenvalues satisfy the equation:
Therefore, the eigenvalues of are the fourth roots of unity: is +1, −1, +i, or −i.

Since there are only four distinct eigenvalues for this matrix, they have some multiplicity. The multiplicity gives the number of linearly independent eigenvectors corresponding to each eigenvalue. (Note that there are N independent eigenvectors; a unitary matrix is never defective
Defective matrix
In linear algebra, a defective matrix is a square matrix that does not have a complete basis of eigenvectors, and is therefore not diagonalizable. In particular, an n × n matrix is defective if and only if it does not have n linearly independent eigenvectors...

.)

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 by Gauss
Carl Friedrich Gauss
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...

(Dickinson and Steiglitz, 1982). The multiplicity depends on the value of N modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

4, and is given by the following table:
align="bottom" | Multiplicities of the eigenvalues λ of the unitary DFT matrix U as a function of the transform size N (in terms of an integer m).
size N λ = +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, the characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....

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 like orthogonality
Orthogonality
Orthogonality occurs when two things can vary independently, they are uncorrelated, or they are perpendicular.-Mathematics:In mathematics, two vectors are orthogonal if they are perpendicular, i.e., they form a right angle...

and to have "simple" forms (e.g., McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiyev and Wolf, 1997; Candan et al., 2000; Hanna et al., 2004; Gurevich and Hadani, 2008).

A straightforward approach is to discretize the eigenfunction of the continuous Fourier transform
Fourier transform
In mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...

,
namely the Gaussian function.
Since periodic summation of the function means discretizing its frequency spectrum
and discretization means periodic summation of the spectrum,
the discretized and periodically summed Gaussian function yields an eigenvector of the discrete transform:
• .
A closed form expression for the series is not known, but it converges rapidly.

Two other simple closed-form analytical eigenvectors for special DFT period N were found (Kong, 2008):

For DFT period N = 2L + 1 = 4K +1, where K is an integer, the following is an eigenvector of DFT:

For DFT period N = 2L = 4K, where K is an integer, the following is an eigenvector of DFT:

The choice of eigenvectors of the DFT matrix has become important in recent years in order to define a discrete analogue of the fractional Fourier transform
Fractional Fourier transform
In mathematics, in the area of harmonic analysis, the fractional Fourier transform is a linear transformation generalizing the Fourier transform. It can be thought of as the Fourier transform to the n-th power where n need not be an integer — thus, it can transform a function to an...

—the DFT matrix can be taken to fractional powers by exponentiating the eigenvalues (e.g., Rubio and Santhanam, 2005). For the continuous Fourier transform
Continuous Fourier transform
The Fourier transform is a mathematical operation that decomposes a function into its constituent frequencies, known as a frequency spectrum. For instance, the transform of a musical chord made up of pure notes is a mathematical representation of the amplitudes of the individual notes that make...

, the natural orthogonal eigenfunctions are the Hermite functions, so various discrete analogues of these have been employed as the eigenvectors of the DFT, such as the Kravchuk polynomials
Kravchuk polynomials
Kravchuk polynomials or Krawtchouk polynomials are discrete orthogonal polynomials associated with the binomial distribution, introduced by .The first few polynomials are:...

(Atakishiyev and Wolf, 1997). The "best" choice of eigenvectors to define a fractional discrete Fourier transform remains an open question, however.

### Uncertainty principle

If the random variable is constrained by:

then may be considered to represent a discrete probability mass function
Probability mass function
In probability theory and statistics, a probability mass function is a function that gives the probability that a discrete random variable is exactly equal to some value...

of n, with an associated probability mass function constructed from the transformed variable:

For the case of continuous functions P(x) and Q(k), the Heisenberg uncertainty principle states that:

where and are the variances of and respectively, with the equality attained in the case of a suitably normalized Gaussian 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.

However, the Hirschman uncertainty
Hirschman uncertainty
In quantum mechanics, information theory, and Fourier analysis, the Hirschman uncertainty is defined as the sum of the temporal and spectral Shannon entropies. It turns out that Heisenberg's uncertainty principle can be expressed as a lower bound on the sum of these entropies...

will have a useful analog for the case of the DFT.. The Hirschman uncertainty principle is expressed in terms of the Shannon entropy of the two probability functions. In the discrete case, the Shannon entropies are defined as:

and

and the Hirschman uncertainty principle becomes:

The equality is obtained for equal to translations and modulations of a suitably normalized Kronecker comb of period A where A is any exact integer divisor of N. The probability mass function will then be proportional to a suitably translated Kronecker comb of period B=N/A.

### The real-input DFT

If are real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s, as they often are in practical applications, then the DFT obeys the symmetry:

The star denotes complex conjugation
Complex conjugate
In mathematics, complex conjugates are a pair of complex numbers, both having the same real part, but with imaginary parts of equal magnitude and opposite signs...

. The subscripts are interpreted modulo N.

Therefore, the DFT output for real inputs is half redundant, and one obtains the complete information by only looking at roughly half of the outputs . In this case, the "DC" element is purely real, and for even N the "Nyquist" element is also real, so there are exactly N non-redundant real numbers in the first half + Nyquist element of the complex output X.

Using Euler's formula, the interpolating trigonometric polynomial can then be interpreted as a sum of sine and cosine functions.

## Generalized/shifted DFT

It is possible to shift the transform sampling in time and/or frequency domain by some real shifts a and b, respectively. This is sometimes known as a generalized DFT (or GDFT), also called the shifted DFT or offset 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 an odd-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 discrete cosine
Discrete cosine transform
A discrete cosine transform expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy compression of audio and images A discrete cosine transform...

and sine
Discrete sine transform
In mathematics, the discrete sine transform is a Fourier-related transform similar to the discrete Fourier transform , but using a purely real matrix...

transforms.

Another interesting choice is , which is called the centered DFT (or CDFT). The centered DFT has the useful property that, when N is a multiple of four, all four of its eigenvalues (see above) have equal multiplicities (Rubio and Santhanam, 2005)

The discrete Fourier transform can be viewed as a special case of the z-transform
Z-transform
In mathematics and signal processing, the Z-transform converts a discrete time-domain signal, which is a sequence of real or complex numbers, into a complex frequency-domain representation....

, evaluated on the unit circle in the complex plane; more general z-transforms correspond to complex shifts a and b above.

## Multidimensional DFT

The ordinary DFT transforms a one-dimensional sequence or array
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

that is a function of exactly one discrete variable n. The multidimensional DFT of a multidimensional array that is a function of d discrete variables for in is defined by:

where as above and the d output indices run from . This is more compactly expressed in vector
Coordinate vector
In linear algebra, a coordinate vector is an explicit representation of a vector in an abstract vector space as an ordered list of numbers or, equivalently, as an element of the coordinate space Fn....

notation, where we define and as d-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 of plane wave
Plane wave
In the physics of wave propagation, a plane wave is a constant-frequency wave whose wavefronts are infinite parallel planes of constant peak-to-peak amplitude normal to the phase velocity vector....

s, or multidimensional sinusoids. The direction of oscillation in space is . The amplitudes are . This decomposition is of great importance for everything from digital image processing
Digital image processing
Digital image processing is the use of computer algorithms to perform image processing on digital images. As a subcategory or field of digital signal processing, digital image processing has many advantages over analog image processing...

(two-dimensional) to solving partial differential equations. The solution is broken up into plane waves.

The multidimensional DFT can be computed by the composition
Function composition
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...

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 of y 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 above commute.

An algorithm to compute a one-dimensional DFT is thus sufficient to efficiently compute a multidimensional DFT. This approach is known as the row-column algorithm. There are also intrinsically multidimensional FFT algorithms.

### The real-input multidimensional DFT

For input data consisting of real 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 ).

## Applications

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, a fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

.

### Spectral analysis

When the DFT is used for spectral analysis, the sequence usually represents a finite set of uniformly-spaced time-samples of some signal , where t represents time. The conversion from continuous time to samples (discrete-time) changes the underlying Fourier transform
Continuous Fourier transform
The Fourier transform is a mathematical operation that decomposes a function into its constituent frequencies, known as a frequency spectrum. For instance, the transform of a musical chord made up of pure notes is a mathematical representation of the amplitudes of the individual notes that make...

of x(t) into a discrete-time Fourier transform
Discrete-time Fourier transform
In mathematics, the discrete-time Fourier transform is one of the specific forms of Fourier analysis. As such, it transforms one function into another, which is called the frequency domain representation, or simply the "DTFT", of the original function . But the DTFT requires an input function...

(DTFT), which generally entails a type of distortion called aliasing
Aliasing
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...

. Choice of an appropriate sample-rate (see Nyquist frequency
Nyquist frequency
The Nyquist frequency, named after the Swedish-American engineer Harry Nyquist or the Nyquist–Shannon sampling theorem, is half the sampling frequency of a discrete signal processing system...

) 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 called leakage
Spectral leakage
Spectral leakage is an effect in the frequency analysis of finite-length signals or finite-length segments of infinite signals where it appears as if some energy has "leaked" out of the original signal spectrum into other frequencies....

, which is manifested as a loss of detail (aka 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 a spectrogram
Spectrogram
A spectrogram is a time-varying spectral representation that shows how the spectral density of a signal varies with time. Also known as spectral waterfalls, sonograms, voiceprints, or voicegrams, spectrograms are used to identify phonetic sounds, to analyse the cries of animals; they were also...

. 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 the variance
Variance
In probability theory and statistics, the variance is a measure of how far a set of numbers is spread out. It is one of several descriptors of a probability distribution, describing how far the numbers lie from the mean . In particular, the variance is one of the moments of a distribution...

of the spectrum (also called a periodogram
Periodogram
The periodogram is an estimate of the spectral density of a signal. The term was coined by Arthur Schuster in 1898 as in the following quote:...

in this context); two examples of such techniques are the Welch method
Welch method
In physics, engineering, and applied mathematics, Welch's method, named after P.D. Welch, is used for estimating the power of a signal at different frequencies: that is, is is an approach to spectral density estimation. The method is based on the concept of using periodogram spectrum estimates,...

and the Bartlett method; the general subject of estimating the power spectrum of a noisy signal is called spectral estimation.

A final source of distortion (or perhaps illusion) 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 in the discrete-time Fourier transform article.
• The procedure is sometimes referred to as zero-padding, which is a particular implementation used in conjunction with the fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

(FFT) algorithm. The inefficiency of performing multiplications and additions with zero-valued "samples" is more than offset by the inherent efficiency of the FFT.
• As already noted, leakage imposes a limit on the inherent resolution of the DTFT. So there is a practical limit to the benefit that can be obtained from a fine-grained DFT.

### Data compression

The field of digital signal processing relies heavily on operations in the frequency domain (i.e. on the Fourier transform). For example, several lossy 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, the discrete cosine transform
Discrete cosine transform
A discrete cosine transform expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy compression of audio and images A discrete cosine transform...

or sometimes the modified discrete cosine transform
Modified discrete cosine transform
The modified discrete cosine transform is a Fourier-related transform based on the type-IV discrete cosine transform , with the additional property of being lapped: it is designed to be performed on consecutive blocks of a larger dataset,...

.)

### Partial differential equations

Discrete Fourier transforms are often used to solve partial differential equations, where again the DFT is used as an approximation for the Fourier series
Fourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...

(which is recovered in the limit of infinite N). The advantage of this approach is that it expands the signal in complex exponentials einx, which are eigenfunctions of differentiation: d/dx einx = in einx. Thus, in the Fourier representation, differentiation is simple—we just multiply by i n. (Note, however, that the choice of n is not unique due to aliasing; for the method to be convergent, a choice similar to that in the trigonometric interpolation section above should be used.) A linear differential equation
Linear differential equation
Linear differential equations are of the formwhere the differential operator L is a linear operator, y is the unknown function , and the right hand side ƒ is a given function of the same nature as y...

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 a spectral method
Spectral method
Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain Dynamical Systems, often involving the use of the Fast Fourier Transform. Where applicable, spectral methods have excellent error properties, with the so called "exponential...

.

### Polynomial multiplication

Suppose we wish to compute the polynomial product c(x) = a(x) · b(x). The ordinary product expression for the coefficients of c involves a linear (acyclic) convolution, where indices do not "wrap around." This can be rewritten as a cyclic convolution by taking the coefficient vectors for a(x) and b(x) with constant term first, then appending zeros so that the resultant coefficient vectors a and b have dimension d > deg(a(x)) + deg(b(x)). Then,

Where c is the vector of coefficients for c(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 polynomial c(x) are just the terms 0, ..., deg(a(x)) + deg(b(x)) of the coefficient vector

With a fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

, the resulting algorithm takes O (N log N) arithmetic operations. Due to its simplicity and speed, the Cooley–Tukey FFT algorithm, which is limited to composite
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....

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).

#### Multiplication of large integers

The fastest known algorithms for the multiplication of very large integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s 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. After polynomial multiplication, a relatively low-complexity carry-propagation step completes the multiplication.

## Some discrete Fourier transform pairs

Some DFT pairs
Note
Shift theorem
Real DFT
from the geometric progression
Geometric progression
In mathematics, a geometric progression, also known as a geometric sequence, is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed non-zero number called the common ratio. For example, the sequence 2, 6, 18, 54, ... is a geometric progression...

formula
from the binomial theorem
Binomial theorem
In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the power n into a sum involving terms of the form axbyc, where the exponents b and c are nonnegative integers with , and the coefficient a of...

is a rectangular window function
Window function
In signal processing, a window function is a mathematical function that is zero-valued outside of some chosen interval. For instance, a function that is constant inside the interval and zero elsewhere is called a rectangular window, which describes the shape of its graphical representation...

of W points centered on n=0, where W is an odd integer, and is a sinc-like function (specifically, is a Dirichlet kernel)
Discretization
Discretization
In mathematics, discretization concerns the process of transferring continuous models and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerical evaluation and implementation on digital computers...

and periodic summation of the scaled Gaussian 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.

### Representation theory

The DFT can be interpreted as the complex-valued representation theory
Representation theory
Representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studiesmodules over these abstract algebraic structures...

of the finite cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

. In other words, a sequence of n complex numbers can be thought of as an element of n-dimensional complex space or equivalently a function from the finite cyclic group of order n to the complex numbers,
This latter may be suggestively written to emphasize that this is a complex vector space whose coordinates are indexed by the n-element set

From this point of view, one may generalize the DFT to representation theory generally, or more narrowly to the representation theory of finite groups
Representation theory of finite groups
In mathematics, representation theory is a technique for analyzing abstract groups in terms of groups of linear transformations. See the article on group representations for an introduction...

.

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.

### Other fields

Many of the properties of the DFT only depend on the fact that is a primitive 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 in fields
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

other than the complex numbers, and such generalizations are commonly called number-theoretic transforms (NTTs) in the case of finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

s. For more information, see number-theoretic transform and discrete Fourier transform (general)
Discrete Fourier transform (general)

.

### Other finite groups

The standard DFT acts on a sequence x0, 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 to Fourier transforms on arbitrary finite groups, which act on functions GC where G is a finite group
Finite group
In mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...

. In this framework, the standard DFT is seen as the Fourier transform on a cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

, while the multidimensional DFT is a Fourier transform on a direct sum of cyclic groups.

## Alternatives

there are various alternatives to the DFT for various applications, prominent among which are wavelets. The analog of the DFT is the discrete wavelet transform
Discrete wavelet transform
In numerical analysis and functional analysis, a discrete wavelet transform is any wavelet transform for which the wavelets are discretely sampled...

(DWT). From the point of view of time–frequency analysis, a key limitation of the Fourier transform is that it does not include location information, only frequency 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, see comparison of the discrete wavelet transform with the discrete Fourier transform.

• DFT matrix
DFT matrix
A DFT matrix is an expression of a discrete Fourier transform as a matrix multiplication.-Definition:An N-point DFT is expressed as an N-by-N matrix multiplication as X = W x, where x is the original input signal, and X is the DFT of the signal.The transformation W of size N\times N can be defined...

• Fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

• List of Fourier-related transforms
• FFTW
FFTW
FFTW, for "Fastest Fourier Transform in the West", is a software library for computing discrete Fourier transforms , developed by Matteo Frigo and Steven G. Johnson at the Massachusetts Institute of Technology....

• FFTPACK
FFTPACK
FFTPACK is a package of Fortran subroutines for the fast Fourier transform. It includes complex, real, sine, cosine, and quarter-wave transforms. It was developed by Paul Swarztrauber of the National Center for Atmospheric Research....