FACTOID # 150: The average person in the United Kingdom drinks as much tea as 23 Italians.
 
 Home   Encyclopedia   Statistics   Countries A-Z   Flags   Maps   Education   Forum   FAQ   About 
 
WHAT'S NEW
RECENT ARTICLES
More Recent Articles »
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Discrete Fourier transform
Fourier transforms
Continuous Fourier transform
Fourier series
Discrete Fourier transform
Discrete-time Fourier transform
Related transforms
edit

In mathematics, the discrete Fourier transform (DFT), 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 sum of sinusoidal components by determining the amplitude and phase of each component. However, the DFT is distinguished by the fact that its input function is discrete and finite: the input to the DFT is a finite sequence of real or complex numbers, which makes the DFT ideal for processing information stored in computers. In particular, the DFT is widely employed in 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 convolutions. The DFT can be computed efficiently in practice using a fast Fourier transform (FFT) algorithm. In mathematics, the Fourier transform is a certain linear operator that maps functions to other functions. ... In mathematics, the Fourier transform is a certain linear operator that maps functions to other functions. ... The Fourier series is a mathematical tool used for analyzing periodic functions by decomposing such a function into a weighted sum of much simpler sinusoidal component functions sometimes referred to as normal Fourier modes, or simply modes for short. ... Given a discrete set of real or complex numbers: (integers), the discrete-time Fourier transform (or DTFT) of is: // Its name implies that the {x[n]} sequence represents the values (aka samples) of a continuous-time function, , at discrete moments in time: , where is the sampling interval (in seconds), and... This is a list of linear transformations of functions related to the Fourier transform. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ... Harmonic analysis is the branch of mathematics which studies the representation of functions or signals as the superposition of basic waves. ... Discrete sampled signal Digital signal A discrete signal or discrete-time signal is a time series, perhaps a signal that has been sampled from a continuous-time signal. ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ... The NASA Columbia Supercomputer. ... Digital signal processing (DSP) is the study of signals in a digital representation and the processing methods of these signals. ... In information theory, a signal is the sequence of states of a communications channel that encodes a message. ... In mathematics, and in particular analysis, a partial differential equation (PDE) is an equation involving partial derivatives of an unknown function. ... In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. ... The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...


Since FFT algorithms are so commonly employed to compute the DFT, the two terms are often used interchangeably in colloquial settings, although there is a clear distinction: "DFT" refers to a mathematical transformation, regardless of how it is computed, while "FFT" refers to any one of several efficient algorithms for the DFT. This distinction is further blurred, however, by the synonym "finite Fourier transform" for the DFT, which apparently predates the term "fast Fourier transform" (Cooley et al., 1969) but has the same initialism. Acronyms and initialisms are abbreviations formed from the initial letter or letters of words, such as NATO and XHTML, and are pronounced in a way that is distinct from the full pronunciation of what the letters stand for. ...

Contents

Definition

The sequence of N complex numbers x0, ..., xN−1 is transformed into the sequence of N complex numbers X0, ..., XN−1 by the DFT according to the formula: In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ...

X_k = sum_{n=0}^{N-1} x_n e^{-frac{2 pi i}{N} k n} quad quad k = 0, dots, N-1

where e is the base of the natural logarithm, i, is the imaginary unit (i2 = − 1), and π is pi. The transform is sometimes denoted by the symbol mathcal{F}, as in mathbf{X} = mathcal{F} left { mathbf{x} right } or mathcal{F} left ( mathbf{x} right ) or mathcal{F} mathbf{x}. e is the unique number such that the value of the derivative (slope of a tangent line) of f (x) = ex (blue curve) at the point x = 0 is exactly 1. ... In mathematics, the imaginary unit (or sometimes the Latin or the Greek iota, see below) allows the real number system to be extended to the complex number system . ... When a circles diameter is 1, its circumference is Ï€. The mathematical constant Ï€ is an irrational real number, approximately equal to 3. ...


The inverse discrete Fourier transform (IDFT) is given by

x_n = frac{1}{N} sum_{k=0}^{N-1} X_k e^{frac{2pi i}{N} k n} quad quad n = 0,dots,N-1.

A simple description of these equations is that the complex numbers Xk represent the amplitude and phase of the different sinusoidal components of the input "signal" xn. The DFT computes the Xk from the xn, while the IDFT shows how to compute the xn as a sum of sinusoidal components Xkexp(2πikn / N) / N with frequency k / N cycles per sample. By writing the equations in this form, we are making extensive use of Euler's formula to express sinusoids in terms of complex exponentials, which are much easier to manipulate. (In the same way, by writing Xk in polar form, we immediately obtain the sinusoid amplitude from | Xk | and the phase from the complex argument.) An important subtlety of this representation, aliasing, is discussed below. FreQuency is a music video game developed by Harmonix and published by SCEI. It was released in November 2001. ... Eulers formula, named after Leonhard Euler, is a mathematical formula in complex analysis that shows a deep relationship between the trigonometric functions and the complex exponential function. ... In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ... Wikibooks Algebra has more about this subject: Complex numbers In mathematics, a complex number is an expression of the form where a and b are real numbers, and i is a specific imaginary number, called the imaginary unit, with the property i 2 = −1. ... Properly sampled image of brick wall. ...


Note that the normalization factor multiplying the DFT and IDFT (here 1 and 1/N) and the signs of the exponents are merely conventions, 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 1/sqrt{N} 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). In mathematics, a unitary matrix is an n by n complex matrix U satisfying the condition where In is the identity matrix and U* is the conjugate transpose (also called the Hermitian adjoint) of U. Note this condition says that a matrix U is unitary if it has an inverse...


(The convention of a negative sign in the exponent is often convenient because it means that Xk is the amplitude of a "positive frequency" 2πk / N. Equivalently, the DFT is often thought of as a matched filter: when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1.) 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. ...


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


Properties

Completeness

The discrete Fourier transform is an invertible, linear transformation In mathematics, a linear transformation (also called linear map or linear operator) is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. ...

mathcal{F}:mathbb{C}^N to mathbb{C}^N

with mathbb{C} denoting the set of complex numbers. 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. In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ...


Orthogonality

The vectors e^{ frac{2pi i}{N} kn} form an orthogonal basis over the set of N-dimensional complex vectors: In mathematics, orthogonal is synonymous with perpendicular when used as a simple adjective that is not part of any longer phrase with a standard definition. ...

sum_{n=0}^{N-1} left(e^{ frac{2pi i}{N} kn}right) left(e^{-frac{2pi i}{N} k'n}right) =N~delta_{kk'}

where ~delta_{kk'} is the Kronecker delta. This orthogonality condition can be used to derive the formula for the IDFT from the definition of the DFT. In mathematics, the Kronecker delta or Kroneckers delta, named after Leopold Kronecker (1823-1891), is a function of two variables, usually integers, which is 1 if they are equal, and 0 otherwise. ...


The Plancherel theorem and Parseval's theorem

If Xk and Yk are the DFTs of xn and yn respectively then Plancherel theorem states: In mathematics, the Plancherel theorem is a result in harmonic analysis, first proved by Michel Plancherel. ...

sum_{n=0}^{N-1} x_n y^*_n = frac{1}{N} sum_{k=0}^{N-1} X_k Y^*_k

where the star denotes complex conjugation. Parseval's theorem is a special case of the Plancherel theorem and states: In mathematics, Parsevals theorem usually refers to the result that the Fourier transform is unitary; loosely, that the sum (or integral) of the square of a function is equal to the sum (or integral) of the square of its transform. ...

sum_{n=0}^{N-1} |x_n|^2 = frac{1}{N} sum_{k=0}^{N-1} |X_k|^2.

Periodicity

If the expression that defines the DFT is evaluated for all integers k instead of just for k = 0, dots, N-1 , 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: X_{k+N} = sum_{n=0}^{N-1} x_n e^{-frac{2pi i}{N} (k+N) n} = sum_{n=0}^{N-1} x_n e^{-frac{2pi i}{N} k n} e^{-2 pi i n} = sum_{n=0}^{N-1} x_n e^{-frac{2pi i}{N} k n} = X_k


where we have used the fact that e − 2πi = 1. In the same way it can be shown that the IDFT formula leads to a periodic extension.


The shift theorem

Multiplying xn by a linear phase e^{frac{2pi i}{N}n m} for some integer m corresponds to a circular shift of the output Xk: Xk is replaced by Xk − m, where the subscript is interpreted modulo N (i.e. periodically). Similarly, a circular shift of the input xn corresponds to multiplying the output Xk by a linear phase. Mathematically, if {xn} represents the vector x then The word modulo (Latin, with respect to a modulus of ___) is the Latin ablative of modulus which itself means a small measure. ...

if mathcal{F}({x_n})_k=X_k
then mathcal{F}({ x_n e^{frac{2pi i}{N}n m} })_k=X_{k-m}
and mathcal{F}({x_{n-m}})_k=X_k e^{-frac{2pi i}{N}k m}

Circular convolution theorem and cross-correlation theorem

The cyclic or circular convolution x*y of the two vectors x = xk  and y = yn  is the vector x*y with components It has been suggested that this article or section be merged into convolution. ...

(mathbf{x*y})_n = sum_{m=0}^{N-1} x_m y_{n-m} quad quad n = 0,dots,N-1

where we continue y cyclically so that

y_{-m} = y_{N-m}quadquad~~~~~~~~~~ m = 0, dots, N-1

The discrete Fourier transform turns cyclic convolutions into component-wise multiplication. That is, if

z_n = (mathbf{x*y})_n

then

Z_k=X_k Y_k quad quad~~~~~~~~~~ k = 0,dots,N-1

where capital letters (X, Y, Z) represent the DFTs of sequences represented by small letters (x, y, z). Note that if a different normalization convention is adopted for the DFT (e.g., the unitary normalization), then there will in general be a constant factor multiplying the above relation.


The direct evaluation of the convolution summation, above, would require O(N2) operations, but the DFT (via an FFT) provides an O(NlogN) method to compute the same thing. Conversely, convolutions can be used to efficiently compute DFTs via Rader's FFT algorithm and Bluestein's FFT algorithm. Raders algorithm (1968) is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution. ... Bluesteins FFT algorithm (1968), commonly called the chirp-z algorithm (1969), is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of arbitrary sizes (including prime sizes) by re-expressing the DFT as a linear convolution. ...


See also: Convolution theorem In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution is the point-wise product of Fourier transforms. ...


In an analogous manner, it can be shown that if zn is the cross-correlation of xn and yn: In statistics, the term cross-correlation is sometimes used to refer to the covariance cov(X, Y) between two random vectors X and Y, in order to distinguish that concept from the covariance of a random vector X, which is understood to be the matrix of covariances between the scalar...

z_n=(mathbf{x * y})_n = sum_{m=0}^{N-1}x_m^*,y_{m+n}

where the sum is again cyclic in m, then the discrete Fourier transform of zn is:

Z_k = X_k^*,Y_k

where capital letters are again used to signify the discrete Fourier transform.


Trigonometric interpolation polynomial

The trigonometric interpolation polynomial In the mathematical subfield of numerical analysis, trigonometric interpolation is a special form of interpolation on the unit circle in the complex plane using trigonometric polynomials. ...

p(t) = frac{X_0}{N} + frac{X_1}{N} e^{it} + cdots + frac{X_{N/2}}{N} cos(Nt/2) + frac{X_{N/2+1}}{N} e^{(-N/2+1)it} + cdots + frac{X_{N-1}}{N} e^{-it} for N even ,
p(t) = frac{X_0}{N} + frac{X_1}{N} e^{it} + cdots + frac{X_{lfloor N/2 rfloor}}{N} e^{lfloor N/2 rfloor it} + frac{X_{lfloor N/2 rfloor+1}}{N} e^{-lfloor N/2 rfloor it} + cdots + frac{X_{N-1}}{N} e^{-it} for N odd,

where the coefficients Xk /N are given by the DFT of xn above, satisfies the interpolation property p(2πn / N) = xn for n=0,ldots,N-1. In mathematics, the parity of an object refers to whether it is even or odd. ...


For even N, notice that the Nyquist component frac{X_{N/2}}{N} cos(Nt/2) is handled specially. The Nyquist frequency, named after Harry Nyquist or the Nyquist–Shannon sampling theorem, is half the sampling frequency of a discrete signal processing system. ...


This interpolation is not unique: aliasing implies that one could add N to any of the complex-sinusoid frequencies (e.g. changing e − it to ei(N − 1)t ) without changing the interpolation property, but giving different values in between the xn 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, and therefore minimizes the mean-square slope int |p'(t)|^2 dt of the interpolating function. Second, if the xn are real numbers, then p(t) is real as well. Look up Slope in Wiktionary, the free dictionary. ...


In contrast, the most obvious trigonometric interpolation polynomial is the one in which the frequencies range from 0 to N − 1 (instead of roughly − N / 2 to + N / 2 as above), similar to the inverse DFT formula. This interpolation does not minimize the slope, and is not generally real-valued for real xn; 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: In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with a geometric progression in each row, i. ...

mathbf{F} = begin{bmatrix} omega_N^{0 cdot 0} & omega_N^{0 cdot 1} & ldots & omega_N^{0 cdot (N-1)} omega_N^{1 cdot 0} & omega_N^{1 cdot 1} & ldots & omega_N^{1 cdot (N-1)} vdots & vdots & ddots & vdots omega_N^{(N-1) cdot 0} & omega_N^{(N-1) cdot 1} & ldots & omega_N^{(N-1) cdot (N-1)} end{bmatrix}

where

omega_N = e^{-2 pi i/N},

is a primitive Nth root of unity. The inverse transform is then given by the inverse of the above matrix: In mathematics, the n-th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 - 1754), are complex numbers located on the unit circle. ...

mathbf{F}^{-1}=frac{1}{N}mathbf{F}^*

With unitary normalization constants 1/sqrt{N}, the DFT becomes a unitary transformation, defined by a unitary matrix: In functional analysis, a unitary operator is a bounded linear operator U on a Hilbert space satisfying U*U=UU*=I where I is the identity operator. ... A unitary transformation is an isomorphism (but not an antiisomorphism; that corresponds to an antiunitary transformation) between two Hilbert spaces or an automorphism of a single Hilbert space. ...

mathbf{U}=mathbf{F}/sqrt{N}
mathbf{U}^{-1}=mathbf{U}^*
|det(mathbf{U})|=1

where det()  is the determinant function. The determinant is the product of the eigenvalues, and therefore (see below) is always pm 1 or pm i. 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. In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ...


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): In linear algebra, two vectors v and w are said to be orthonormal if they are both orthogonal (according to a given inner product) and normalized. ... In mathematics, the nth roots of unity, or de Moivre numbers, are all the complex numbers which yield 1 when raised to a given power n. ...

sum_{m=0}^{N-1}U_{km}U_{mn}^*=delta_{kn}

If mathbf{X} is defined as the unitary DFT of the vector mathbf{x} then

X_k=sum_{n=0}^{N-1} U_{kn}x_n

and the Plancherel theorem is expressed as: In mathematics, the Plancherel theorem is a result in harmonic analysis, first proved by Michel Plancherel. ...

sum_{n=0}^{N-1}x_n y_n^* = sum_{k=0}^{N-1}X_k Y_k^*

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 mathbf{x} = mathbf{y}, this implies that the length of a vector is preserved as well—this is just Parseval's theorem: In mathematics, Parsevals theorem usually refers to the result that the Fourier transform is unitary; loosely, that the sum (or integral) of the square of a function is equal to the sum (or integral) of the square of its transform. ...

sum_{n=0}^{N-1}|x_n|^2 = sum_{k=0}^{N-1}|X_k|^2

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:

mathcal{F}^{-1}({x_n}) = mathcal{F}({x_{N - n}}) / N

(As usual, the subscripts are interpreted modulo N; thus, for n = 0, we have xN − 0 = x0.) The word modulo (Latin, with respect to a modulus of ___) is the Latin ablative of modulus which itself means a small measure. ...


Second, one can also conjugate the inputs and outputs:

mathcal{F}^{-1}(mathbf{x}) = mathcal{F}(mathbf{x}^*)^* / N

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(xn) as xn with its real and imaginary parts swapped—that is, if xn = a + bi then swap(xn) is b + ai. Equivalently, swap(xn) equals . Then It has been suggested that Software pointer be merged into this article or section. ...

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, T(mathbf{x}) = mathcal{F}(mathbf{x}^*) / sqrt{N} is clearly its own inverse: . A closely related involutary transformation (by a factor of (1+i) /√2) is H(mathbf{x}) = mathcal{F}((1+i) mathbf{x}^*) / sqrt{2N}, since the (1 + i) factors in H(H(mathbf{x})) cancel the 2. For real inputs mathbf{x}, the real part of H(mathbf{x}) is none other than the discrete Hartley transform, which is also involutary. In mathematics, an involution, or an involutary function, is a function that is its own inverse, so that f(f(x)) = x for all x in the domain of f. ... A discrete Hartley transform (DHT) is a Fourier-related transform of discrete, periodic data similar to the discrete Fourier transform (DFT), with analogous applications in signal processing and related fields. ...


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. In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ... In linear algebra, the eigenvectors (from the German eigen meaning own) of a linear operator are non-zero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ...


Consider the unitary form mathbf{U} defined above for the DFT of length N, where mathbf{U}_{m,n} = omega_N^{mn}/sqrt{N} = exp(-2pi i mn/N)/sqrt{N}. This matrix satisfies the equation:

mathbf{U}^4 = mathbf{I}.

This can be seen from the inverse properties above: operating mathbf{U} twice gives the original data in reverse order, so operating mathbf{U} four times gives back the original data and is thus the identity matrix. This means that the eigenvalues λ satisfy a characteristic equation: In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ... In linear algebra, the characteristic equation of a square matrix A is the equation in one variable λ where I is the identity matrix. ...

λ4 = 1.

Therefore, the eigenvalues of mathbf{U} are the fourth roots of unity: λ is +1, −1, +i, or −i. In mathematics, the n-th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 - 1754), are complex numbers located on the unit circle. ...


Since there are only four distinct eigenvalues for this Ntimes N 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; the matrix is not defective.) In linear algebra, a scalar λ is called an eigenvalue (in some older texts, a characteristic value) of a linear mapping A if there exists a nonzero vector x such that Ax=λx. ... In linear algebra, a set of elements of a vector space is linearly independent if none of the vectors in the set can be written as a linear combination of finitely many other vectors in the set. ... In linear algebra, a defective matrix is a square matrix that does not have a complete basis of eigenvectors, and is therefore not diagonizable. ...


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 (Dickinson and Steiglitz, 1982). The multiplicity depends on the value of N modulo 4, and is given by the following table: Johann Carl Friedrich Gauss or Gauß ( ; Latin: ) (30 April 1777 – 23 February 1855) was a German mathematician and scientist of profound genius who contributed significantly to many fields, including number theory, analysis, differential geometry, geodesy, electrostatics, astronomy, and optics. ... The word modulo (Latin, with respect to a modulus of ___) is the Latin ablative of modulus which itself means a small measure. ...

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

Unfortunately, no simple analytical formula for the 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 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). In mathematics, orthogonal is synonymous with perpendicular when used as a simple adjective that is not part of any longer phrase with a standard definition. ...


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—the DFT matrix can be taken to fractional powers by exponentiating the eigenvalues (e.g., Rubio and Santhanam, 2005). For the continuous Fourier transform, 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 (Atakishiyev and Wolf, 1997). The "best" choice of eigenvectors to define a fractional discrete Fourier transform remains an open question, however. The fractional Fourier transform (FRFT) is a linear transformation generalizing the continuous Fourier transform, and 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 intermediate domain between time and... In mathematics, the continuous Fourier transform is a certain linear operator that maps functions to other functions. ... In mathematics, the Hermite polynomials are a classical orthogonal polynomial sequence that arise in probability, such as the Edgeworth series; in combinatorics, as an example of an Appell sequence, obeying the umbral calculus; and in physics, as the eigenstates of the quantum harmonic oscillator. ... Kravchuk polynomials or Krawtchouk polynomials are classical orthogonal polynomials associated with the binomial distribution, introduced by the Ukrainian mathematician Mikhail Kravchuk in 1929. ...


The real-input DFT

If x_0, ldots, x_{N-1} are real numbers, as they often are in practical applications, then the DFT obeys the symmetry: In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ...

X_k = X_{N-k}^* ,

where the star denotes complex conjugation and 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 X_0, ldots, X_{N-1}. In this case, the "DC" element X0 is purely real, and for even N the "Nyquist" element XN / 2 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. This article is about the Eulers formula in complex analysis. ...


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:

X_k = sum_{n=0}^{N-1} x_n e^{-frac{2 pi i}{N} (k+b) (n+a)} quad quad k = 0, dots, N-1

Most often, shifts of 1 / 2 (half a sample) are used. While the ordinary DFT corresponds to a periodic signal in both time and frequency domains, a = 1 / 2 produces a signal that is anti-periodic in frequency domain (Xk + N = − Xk) and vice-versa for b = 1 / 2. Thus, the specific case of a = b = 1 / 2 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 and sine transforms. 2-D DCT compared to the DFT The discrete cosine transform (DCT) is a Fourier-related transform similar to the discrete Fourier transform (DFT), but using only real numbers. ... In mathematics, the discrete sine transform (DST) is a Fourier-related transform similar to the discrete Fourier transform (DFT), but with one additional property: If the input consists of only real numbers, so will the output. ...


Another interesting choice is a = b = − (N − 1) / 2, 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, evaluated on the unit circle in the complex plane; more general z-transforms correspond to complex shifts a and b above. In mathematics and signal processing, the Z-transform converts a discrete time domain signal, which is a sequence of real numbers, into a complex frequency domain representation. ...


Multidimensional DFT

The ordinary DFT computes the transform of a "one-dimensional" dataset: a sequence (or array) xn that is a function of one discrete variable n. More generally, one can define the multidimensional DFT of a multidimensional array x_{n_1, n_2, dots, n_d} that is a function of d discrete variables n_ell = 0, 1, dots, N_ell-1 for ell in 1, 2, dots, d: This article does not cite any references or sources. ...

X_{k_1, k_2, dots, k_d} = sum_{n_1=0}^{N_1-1} left(omega_{N_1}^{~k_1 n_1} sum_{n_2=0}^{N_2-1} left( omega_{N_2}^{~k_2 n_2} cdots sum_{n_d=0}^{N_d-1} omega_{N_d}^{~k_d n_d}cdot x_{n_1, n_2, dots, n_d} right) cdots right) , ,

where omega_{N_ell} = exp(-2pi i/N_ell) as above and the d output indices run from k_ell = 0, 1, dots, N_ell-1. This is more compactly expressed in vector notation, where we define mathbf{n} = (n_1, n_2, dots, n_d) and mathbf{k} = (k_1, k_2, dots, k_d) as d-dimensional vectors of indices from 0 to mathbf{N} - 1, which we define as mathbf{N} - 1 = (N_1 - 1, N_2 - 1, dots, N_d - 1): 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. ...

X_mathbf{k} = sum_{mathbf{n}=0}^{mathbf{N}-1} e^{-2pi i mathbf{k} cdot (mathbf{n} / mathbf{N})} x_mathbf{n} , ,

where the division mathbf{n} / mathbf{N} is defined as mathbf{n} / mathbf{N} = (n_1/N_1, dots, n_d/N_d) 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:

x_mathbf{n} = frac{1}{prod_{ell=1}^d N_ell} sum_{mathbf{k}=0}^{mathbf{N}-1} e^{2pi i mathbf{n} cdot (mathbf{k} / mathbf{N})} X_mathbf{k} , .

The multidimensional DFT has a simple interpretation. Just as the one-dimensional DFT expresses the input xn as a superposition of sinusoids, the multidimensional DFT expresses the input as a superposition of plane waves, or sinusoids oscillating along the direction mathbf{k} / mathbf{N} in space and having amplitude X_mathbf{k}. Such a decomposition is of great importance for everything from digital image processing (d = 2) to solving partial differential equations in three dimensions (d = 3) by breaking the solution up into plane waves. In the physics of wave propagation (especially electromagnetic waves), a plane wave (also spelled planewave) is a constant-frequency wave whose wavefronts (surfaces of constant amplitude and phase) are infinite parallel planes normal to the propagation direction. ... Digital image processing is the use of computer algorithms to perform image processing on digital images. ... In mathematics, and in particular analysis, a partial differential equation (PDE) is an equation involving partial derivatives of an unknown function. ...


Computationally, the multidimensional DFT is simply the composition of a sequence of one-dimensional DFTs along each dimension. For example, in the two-dimensional case x_{n_1,n_2} one can first compute the N1 independent DFTs of the rows (i.e., along n2) to form a new array y_{n_1,k_2}, and then compute the N2 independent DFTs of y along the columns (along n1) to form the final result X_{k_1,k_2}. Or, one can transform the columns and then the rows—the order is immaterial because the nested summations above commute. In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... Mathematical meaning A map or binary operation is said to be commutative when, for any x in A and any y in B . ...


Because of this, given a way to compute a one-dimensional DFT (e.g. an ordinary one-dimensional FFT algorithm), one immediately has a way to efficiently compute the multidimensional DFT. This is known as a row-column algorithm, although there are also intrinsically multidimensional FFT algorithms. The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...


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. The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...


Spectral analysis

When the DFT is used for spectral analysis, the {x_n}, sequence usually represents a finite set of uniformly-spaced time-samples of some signal x(t),, where t represents time. The conversion from continuous time to samples (discrete-time) changes the underlying Fourier transform of x(t) into a discrete-time Fourier transform (DTFT), which generally entails a type of distortion called aliasing. Choice of an appropriate sample-rate (see Nyquist frequency) 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, 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. 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 of the spectrum (also called a periodogram in this context); two examples of such techniques are the Welch method and the Bartlett method. Familiar concepts associated with a frequency are colors, musical notes, radio/TV channels, and even the regular rotation of the earth. ... In mathematics, the continuous Fourier transform is a certain linear operator that maps functions to other functions. ... Given a discrete set of real or complex numbers: (integers), the discrete-time Fourier transform (or DTFT) of is: // Its name implies that the {x[n]} sequence represents the values (aka samples) of a continuous-time function, , at discrete moments in time: , where is the sampling interval (in seconds), and... Properly sampled image of brick wall. ... The Nyquist frequency, named after Harry Nyquist or the Nyquist–Shannon sampling theorem, is half the sampling frequency of a discrete signal processing system. ... In signal processing, a window function (or apodization function) is a function that is zero-valued outside of some chosen interval. ... It has been suggested that this article or section be merged with periodogram. ... In probability theory and statistics, the variance of a random variable (or somewhat more precisely, of a probability distribution) is a measure of its statistical dispersion, indicating how its possible values are spread around the expected value. ... The term periodogram appears often in the context of power spectral density calculations. ... In 1967 P.D. Welch wrote a paper titled The Use of Fast Fourier Transform for the Estimation of Power Spectra: A Method Based on Time Averaging Over Short, Modified Periodograms that appeared in IEEE Trans. ...


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. Given a discrete set of real or complex numbers: (integers), the discrete-time Fourier transform (or DTFT) of is: // Its name implies that the {x[n]} sequence represents the values (aka samples) of a continuous-time function, , at discrete moments in time: , where is the sampling interval (in seconds), and...

  • The procedure is sometimes referred to as zero-padding, which is a particular implementation used in conjunction with the fast Fourier transform (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.

The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...

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 or sometimes the modified discrete cosine transform). A lossy data compression method is one where compressing a file and then decompressing it retrieves a file that may well be different to the original, but is close enough to be useful in some way. ... 2-D DCT compared to the DFT The discrete cosine transform (DCT) is a Fourier-related transform similar to the discrete Fourier transform (DFT), but using only real numbers. ... modified discrete cosine transform (MDCT) is a Fourier-related transform based on the type-IV discrete cosine transform (DCT-IV), with the additional property of being lapped: it is designed to be performed on consecutive blocks of a larger dataset, where subsequent blocks are overlapped so that the last half...


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 (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. A linear differential equation with constant coefficients is transformed into an easily solvable algebraic equation. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called a spectral method. In mathematics, and in particular analysis, a partial differential equation (PDE) is an equation involving partial derivatives of an unknown function. ... The Fourier series is a mathematical tool used for analyzing periodic functions by decomposing such a function into a weighted sum of much simpler sinusoidal component functions sometimes referred to as normal Fourier modes, or simply modes for short. ... In applied mathematics, Spectral methods are algorithms to solve certain kinds of partial differential equations numerically using some sort of Fast Fourier Transform. ...


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,

mathbf{c} = mathbf{a} * mathbf{b}

Where c is the vector of coefficients for c(x), and the convolution operator *, is defined so

c_n = sum_{m=0}^{d-1}a_m b_{n-m mathrm{mod} d} qquadqquadqquad n=0,1,...,d-1

But convolution becomes multiplication under the DFT:

mathcal{F}(mathbf{c}) = mathcal{F}(mathbf{a})mathcal{F}(mathbf{b})

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

mathbf{c} = mathcal{F}^{-1}(mathcal{F}(mathbf{a})mathcal{F}(mathbf{b})).

With a 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 sizes, is often chosen for the transform operation. In this case, d should be chosen as the smallest integer greater than the sum of the input polynomial degrees that is factorizable into small prime factors (e.g. 2, 3, and 5, depending upon the FFT implementation). The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ... The Cooley-Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. ... A composite number is a positive integer which has a positive divisor other than one or itself. ...


Multiplication of large integers

The fastest known algorithms for the multiplication of very large integers use the polynomial multiplication method outlined above. Integers can be treated as the coefficients of polynomials, evaluated specifically at the number base. After polynomial multiplication, a relatively low-complexity carry-propagation step completes the multiplication. A multiplication algorithm is an algorithm (or method) to multiply two numbers. ... The integers are commonly denoted by the above symbol. ...


Some discrete Fourier transform pairs

Some DFT pairs
x_n = frac{1}{N}sum_{k=0}^{N-1}X_k cdot e^{i 2 pi kn/N} X_k = sum_{n=0}^{N-1}x_n cdot e^{-i 2 pi kn/N} Note
x_n cdot e^{i 2 pi nl/N} , X_{k-l}, Shift theorem
x_{n-l}, X_k cdot e^{-i 2 pi kl/N}
x_n in mathbb{R} X_k=X_{N-k}^*, Real DFT
a^n,
{N-1 choose n}, left(1+e^{-i 2 pi k/N} right)^{N-1},

Derivation as Fourier series

Main article: A derivation of the discrete Fourier transform

The DFT can be derived as a truncation of the Fourier series of a periodic sequence of impulses. The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... The Fourier series is a mathematical tool used for analyzing periodic functions by decomposing such a function into a weighted sum of much simpler sinusoidal component functions sometimes referred to as normal Fourier modes, or simply modes for short. ... The Dirac delta function, often referred to as the unit impulse function and introduced by the British theoretical physicist Paul Dirac, can usually be informally thought of as a function δ(x) that has the value of infinity for x = 0, the value zero elsewhere. ...


See also

The N-point discrete Fourier transform (DFT) can be expressed as a matrix multiplication with an N-by-N matrix, as follows: where x is the original input signal, and X is the DFT of the signal. ...

References

  • Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 0-13-307505-2. 
  • Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R. (1999). Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. ISBN 0-13-754920-2. 
  • Smith, Steven W. (1997). The Scientist and Engineer's Guide to Digital Signal Processing. San Diego, Calif.: California Technical Publishing. ISBN 0-9660176-3-3. 
  • Cormen, Thomas H.; Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). "Chapter 30: Polynomials and the FFT", Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, pp.822–848. ISBN 0-262-03293-7.  esp. section 30.2: The DFT and FFT, pp.830–838.
  • P. Duhamel, B. Piron, and J. M. Etcheto (1988). "On computing the inverse DFT". IEEE Trans. Acoust., Speech and Sig. Processing 36 (2): 285–286. 
  • J. H. McClellan and T. W. Parks (1972). "Eigenvalues and eigenvectors of the discrete Fourier transformation". IEEE Trans. Audio Electroacoust. 20 (1): 66-74. 
  • Bradley W. Dickinson and Kenneth Steiglitz (1982). "Eigenvectors and functions of the discrete Fourier transform". IEEE Trans. Acoust., Speech and Sig. Processing 30 (1): 25-31. 
  • F. A. Grünbaum (1982). "The eigenvectors of the discrete Fourier transform". J. Math. Anal. Appl. 88 (2): 355-363. 
  • Natig M. Atakishiyev and Kurt Bernardo Wolf (1997). "Fractional Fourier-Kravchuk transform". J. Opt. Soc. Am. A 14 (7): 1467-1477. 
  • C. Candan, M. A. Kutay and H. M.Ozaktas (2000). "The discrete fractional Fourier transform". IEEE Trans. On Signal Processing 48 (5): 1329-1337. 
  • Magdy Tawfik Hanna, Nabila Philip Attalla Seif, and Waleed Abd El Maguid Ahmed (2004). "Hermite-Gaussian-like eigenvectors of the discrete Fourier transform matrix based on the singular-value decomposition of its orthogonal projection matrices". IEEE Trans. Circ. Syst. I 51 (11): 2245-2254. 
  • Juan G. Vargas-Rubio and Balu Santhanam (2005). "On the multiangle centered discrete fractional Fourier transform". IEEE Sig. Proc. Lett. 12 (4): 273-276. 
  • J. Cooley, P. Lewis, and P. Welch (1969). "The finite Fourier transform". IEEE Trans. Audio Electroacoustics 17 (2): 77-85. 

Professor Alan V. Oppenheim Alan V. Oppenheim is a Ford Professor of Engineering at the MITs Department of Electrical Engineering and Computer Science. ... Ronald Schafer (born February 17, 1938 in Tecumseh, Nebraska) is an electrical engineer notable for his contributions to digital signal processing. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ... Dr. James Cooley (born 1926) is an American mathematician. ...

External links

Digital signal processing
Theory — Nyquist–Shannon sampling theorem, estimation theory, detection theory
Sub-fields — audio signal processing | control engineering | digital image processing | speech processing | statistical signal processing
Techniques — Discrete Fourier transform (DFT) | Discrete-time Fourier transform (DTFT) | bilinear transform | Z-transform, advanced Z-transform
Sampling — oversampling | undersampling | downsampling | upsampling | aliasing | anti-aliasing filter | sampling rate | Nyquist rate/frequency
This box: view • talk • edit


 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments
Please enter the 5-letter protection code

Want to know more?
Search encyclopedia, statistics and forums:
 


Lesson Plans | Student Area | Student FAQ | Reviews | Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.