Discrete Fourier transform - AbsoluteAstronomy.com

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)

This article is about the discrete Fourier transform over any field , commonly called a number-theoretic transform in the case of finite fields...

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

s x₀, ..., x_N−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

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 X_k 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

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

with C denoting the set of complex number

Complex number

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 X_k and Y_k are the DFTs of x_n and y_n 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

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

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

(FFT) to achieve much better performance. Furthermore, convolutions can be used to efficiently compute DFTs via Rader's FFT algorithm

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

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]:...

and overlap-add.

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 X_k are given by the DFT of x_n 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

) 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

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

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

is defined as the unitary DFT of the vector

then

and the Plancherel theorem

Plancherel 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 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

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

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

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 O² 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

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

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

of x(t) into a discrete-time Fourier transform

Discrete-time Fourier transform

(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

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 e^inx, which are eigenfunctions of differentiation: d/dx e^inx = in e^inx. 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

, 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
		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

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

This article is about the discrete Fourier transform over any field , commonly called a number-theoretic transform in the case of finite fields...

Other finite groups

The standard DFT acts on a sequence x₀, x₁, …, x_N−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 G → C 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

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

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Definition

Completeness

Orthogonality

The Plancherel theorem and Parseval's theorem

Periodicity

The shift theorem

Circular convolution theorem and cross-correlation theorem

Convolution theorem duality

Trigonometric interpolation polynomial

The unitary DFT

Expressing the inverse DFT in terms of the DFT

Eigenvalues and eigenvectors

Uncertainty principle

The real-input DFT

Generalized/shifted DFT

Multidimensional DFT

The real-input multidimensional DFT

Applications

Spectral analysis

Data compression

Partial differential equations

Polynomial multiplication

Multiplication of large integers

Some discrete Fourier transform pairs

Representation theory

Other fields

Other finite groups

Alternatives

See also

External links