Fourier transform
Overview
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...
. The subject began with the study of the way general 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...
s may be represented by sums of simpler trigonometric functions. Fourier analysis is named after Joseph Fourier
Joseph Fourier
Jean Baptiste Joseph Fourier was a French mathematician and physicist best known for initiating the investigation of Fourier series and their applications to problems of heat transfer and vibrations. The Fourier transform and Fourier's Law are also named in his honour...
, who showed that representing a function by a trigonometric series greatly simplifies the study of heat propagation.
Today, the subject of Fourier analysis encompasses a vast spectrum of mathematics.
Unanswered Questions
Discussions
Encyclopedia
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 function
s may be represented by sums of simpler trigonometric functions. Fourier analysis is named after Joseph Fourier
, who showed that representing a function by a trigonometric series greatly simplifies the study of heat propagation.
Today, the subject of Fourier analysis encompasses a vast spectrum of mathematics. In the sciences and engineering, the process of decomposing a function into simpler pieces is often called Fourier analysis, while the operation of rebuilding the function from these pieces is known as Fourier synthesis. In mathematics, the term Fourier analysis often refers to the study of both operations.
The decomposition process itself is called a Fourier transform
. The transform is often given a more specific name which depends upon the domain and other properties of the function being transformed. Moreover, the original concept of Fourier analysis has been extended over time to apply to more and more abstract and general situations, and the general field is often known as harmonic analysis
. Each transform used for analysis (see list of Fourierrelated transforms) has a corresponding inverse
transform that can be used for synthesis.
, partial differential equations, number theory
, combinatorics
, signal processing
, imaging, probability theory
, statistics
, option pricing, cryptography
, numerical analysis
, acoustics
, oceanography
, optics
, diffraction
, geometry
, and other areas.
This wide applicability stems from many useful properties of the transforms:
Fourier transformation is also useful as a compact representation of a signal. For example, JPEG
compression uses a variant of the Fourier transformation (discrete cosine transform
) of small square pieces of a digital image. The Fourier components of each square are rounded to lower arithmetic precision
, and weak components are eliminated entirely, so that the remaining components can be stored very compactly. In image reconstruction, each image square is reassembled from the preserved approximate Fouriertransformed components, which are then inversetransformed to produce an approximation of the original image.
, radio wave
s, light waves, seismic waves, and even images, Fourier analysis can isolate individual components of a compound waveform, concentrating them for easier detection and/or removal. A large family of signal processing techniques consist of Fouriertransforming a signal, manipulating the Fouriertransformed data in a simple way, and reversing the transformation.
Some examples include:
argument, and it produces a continuous function of frequency, known as a frequency distribution. One function is transformed into another, and the operation is reversible. When the domain of the input function is time (t), and the domain of the output function is ordinary frequency
, the transform of function s(t) at frequency ƒ is given by the complex number:
Evaluating this quantity for all values of ƒ produces the frequencydomain function. Then s(t) can be represented as a recombination of complex exponentials of all possible frequencies:
which is the inverse transform formula. The complex number, S(ƒ), conveys both amplitude and phase of frequency ƒ.
See Fourier transform
for much more more information, including:
function, modulated by a sequence of complex coefficients:
for all integer values of k,
and where is the integral over any interval of length P.
The inverse transform, known as Fourier series, is a representation of s_{P}(t) in terms of a summation of a potentially infinite number of harmonically related sinusoids or complex exponential functions, each with an amplitude and phase specified by one of the coefficients:
When s_{P}(t), is expressed as a periodic summation of another function, s(t):
the coefficients are proportional to samples of S(ƒ) at discrete intervals of 1/P:
A sufficient condition for recovering s(t) (and therefore S(ƒ)) from just these samples is that the nonzero portion of s(t) be confined to a known interval of duration P, which is the frequency domain dual of the Nyquist–Shannon sampling theorem
.
See Fourier series
for more information, including the historical development.
which is known as the DTFT. Thus the DTFT of the s[n] sequence is also the Fourier transform of the modulated Dirac comb
function.We may also note that:
Consequently, a common practice is to model "sampling" as a multiplication by the Dirac comb
function, which of course is only "possible" in a purely mathematical sense.
The Fourier series coefficients, defined by:
is the inverse transform. And it can be readily shownsee Poisson summation formula
that the coefficients are just samples of s(t) at discrete intervals of T: s[n] = T·s(nT).
Thus we have the important result that when a discrete data sequence, s[n], represents samples of an underlying continuous function, s(t), one can deduce something about its Fourier transform, S(ƒ). That is a cornerstone in the foundation of digital signal processing
. Furthermore, under certain idealized conditions one can theoretically recover S(ƒ) and s(t) exactly. A sufficient condition for perfect recovery is that the nonzero portion of S(ƒ) be confined to a known frequency interval of width 1/T, which is the Nyquist–Shannon sampling theorem
.
Another reason to be interested in S_{1/T}(ƒ) is that it often provides insight into the amount of aliasing
caused by the sampling process.
Applications of the DTFT are not limited to sampled functions. See Discretetime Fourier transform
for more information on this and other topics, including:
function, modulated by the coefficients of a Fourier seriesThe Fourier series represents .. And the integral formula for the coefficients simplifies to a summation:
where is the sum over any nsequence of length N.
The S_{k} sequence is what's customarily known as the DFT of s_{N}. It is also Nperiodic, so it is never necessary to compute more than N coefficients. In terms of S_{k}, the inverse transform is given by:
where is the sum over any ksequence of length N.
When s_{N}[n] is expressed as a periodic summation of another function, s[n] = T·s(nT):
the coefficients are equivalent to samples of S_{1/T}(ƒ) at discrete intervals of 1/P = 1/NT:
In most cases, N is chosen equal to the length of nonzero portion of s[n]. Increasing N, known as zeropadding or interpolation, results in more closely spaced samples of one cycle of S_{1/T}(ƒ). Decreasing N, causes overlap (adding) in the timedomain (analogous to aliasing
), which corresponds to decimation in the frequency domain. (see Sampling the DTFT) In most cases of practical interest, the s[n] sequence represents a longer sequence that was truncated by the application of a finitelength window function
or FIR filter array.
The DFT can be computed using a fast Fourier transform
(FFT) algorithm, which makes it a practical and important transformation on computers.
See Discrete Fourier transform
for much more information, including:
functions. But the same spectral information can be discerned from just one cycle of the periodic function, since all the other cycles are identical. Similarly, finiteduration functions can be represented as a Fourier series, with no actual loss of information except that the periodicity of the inverse transform is a mere artifact. The formulas in the right hand columns below apply to both cases, where in one case is the finite duration function to be analyzed, and in the other case its periodic summation, is the function under analysis. We note in passing that none of the formulas actually require the duration of to be limited to the period, P or N. But that is the most common situation.
topological group
s, which are studied in harmonic analysis
; there, the Fourier transform takes functions on a group to functions on the dual group. This treatment also allows a general formulation of the convolution theorem
, which relates Fourier transforms and convolution
s. See also the Pontryagin duality
for the generalized underpinnings of the Fourier transform.
terms, a function (of time) is a representation of a signal with perfect time resolution, but no frequency information, while the Fourier transform has perfect frequency resolution, but no time information.
As alternatives to the Fourier transform, in time–frequency analysis, one uses time–frequency transforms to represent signals in a form that has some time information and some frequency information – by the uncertainty principle
, there is a tradeoff between these. These can be generalizations of the Fourier transform, such as the shorttime Fourier transform
, the Gabor transform
or fractional Fourier transform
, or can use different functions to represent signals, as in wavelet transforms and chirplet transform
s, with the wavelet analog of the (continuous) Fourier transform being the continuous wavelet transform
.
, where they were used to compute ephemerides (tables of astronomical positions).
In modern times, variants of the discrete Fourier transform were used by Alexis Clairaut in 1754 to compute an orbit,
which has been described as the first formula for the DFT,
and in 1759 by Joseph Louis Lagrange
, in computing the coefficients of a trigonometric series for a vibrating string. Technically, Clairaut's work was a cosineonly series (a form of discrete cosine transform
), while Lagrange's work was a sineonly series (a form of discrete sine transform
); a true cosine+sine DFT was used by Gauss
in 1805 for trigonometric interpolation
of asteroid
orbits.
Euler and Lagrange both discretized the vibrating string problem, using what would today be called samples.
An early modern development toward Fourier analysis was the 1770 paper Réflexions sur la résolution algébrique des équations by Lagrange, which in the method of Lagrange resolvents used a complex Fourier decomposition to study the solution of a cubic:
Lagrange transformed the roots into the resolvents:
where ζ is a cubic root of unity, which is the DFT of order 3.
A number of authors, notably Jean le Rond d'Alembert
,, and Carl Friedrich Gauss
used trigonometric series to study the heat equation
, but the breakthrough development was the 1807 paper
Mémoire sur la propagation de la chaleur dans les corps solides by Joseph Fourier
, whose crucial insight was to model all functions by trigonometric series, introducing the Fourier series.
Historians are divided as to how much to credit Lagrange and others for the development of Fourier theory: Daniel Bernoulli
and Leonhard Euler
had introduced trigonometric representations of functions, and Lagrange had given the Fourier series solution to the wave equation, so Fourier's contribution was mainly the bold claim that an arbitrary function could be represented by a Fourier series.
The subsequent development of the field is known as harmonic analysis
, and is also an early instance of representation theory
.
The first fast Fourier transform (FFT) algorithm for the DFT was discovered around 1805 by Carl Friedrich Gauss when interpolating measurements of the orbit of the asteroids Juno and Pallas, although that particular FFT algorithm is more often attributed to its modern rediscoverers Cooley and Tukey.
, the Fourier transform often takes a time series
or a function of continuous time, and maps it into a frequency spectrum
. That is, it takes a function from the time
domain into the frequency
domain; it is a decomposition of a function into sinusoids of different frequencies; in the case of a Fourier series
or discrete Fourier transform
, the sinusoids are harmonic
s of the fundamental frequency of the function being analyzed.
When the function ƒ is a function of time and represents a physical signal, the transform has a standard interpretation as the frequency spectrum of the signal. The magnitude
of the resulting complexvalued function F at frequency ω represents the amplitude
of a frequency component whose initial phase
is given by the phase of F.
Fourier transforms are not limited to functions of time, and temporal frequencies. They can equally be applied to analyze spatial frequencies, and indeed for nearly any function domain. This justifies their use in branches such diverse as image processing
, heat conduction
and automatic control
.
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...
. The subject began with the study of the way general 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...
s may be represented by sums of simpler trigonometric functions. Fourier analysis is named after Joseph Fourier
Joseph Fourier
Jean Baptiste Joseph Fourier was a French mathematician and physicist best known for initiating the investigation of Fourier series and their applications to problems of heat transfer and vibrations. The Fourier transform and Fourier's Law are also named in his honour...
, who showed that representing a function by a trigonometric series greatly simplifies the study of heat propagation.
Today, the subject of Fourier analysis encompasses a vast spectrum of mathematics. In the sciences and engineering, the process of decomposing a function into simpler pieces is often called Fourier analysis, while the operation of rebuilding the function from these pieces is known as Fourier synthesis. In mathematics, the term Fourier analysis often refers to the study of both operations.
The decomposition process itself is called a 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...
. The transform is often given a more specific name which depends upon the domain and other properties of the function being transformed. Moreover, the original concept of Fourier analysis has been extended over time to apply to more and more abstract and general situations, and the general field is often known as harmonic analysis
Harmonic analysis
Harmonic analysis is the branch of mathematics that studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms...
. Each transform used for analysis (see list of Fourierrelated transforms) has a corresponding inverse
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...
transform that can be used for synthesis.
Applications
Fourier analysis has many scientific applications — in physicsPhysics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
, partial differential equations, number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, signal processing
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
, imaging, probability theory
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of nondeterministic events or measured quantities that may either be single...
, statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
, option pricing, cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, acoustics
Acoustics
Acoustics is the interdisciplinary science that deals with the study of all mechanical waves in gases, liquids, and solids including vibration, sound, ultrasound and infrasound. A scientist who works in the field of acoustics is an acoustician while someone working in the field of acoustics...
, oceanography
Oceanography
Oceanography , also called oceanology or marine science, is the branch of Earth science that studies the ocean...
, optics
Optics
Optics is the branch of physics which involves the behavior and properties of light, including its interactions with matter and the construction of instruments that use or detect it. Optics usually describes the behavior of visible, ultraviolet, and infrared light...
, diffraction
Diffraction
Diffraction refers to various phenomena which occur when a wave encounters an obstacle. Italian scientist Francesco Maria Grimaldi coined the word "diffraction" and was the first to record accurate observations of the phenomenon in 1665...
, geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of premodern mathematics, the other being the study of numbers ....
, and other areas.
This wide applicability stems from many useful properties of the transforms:
 The transforms are linear operators and, with proper normalization, are unitaryUnitary operatorIn 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...
as well (a property known as Parseval's theoremParseval's theoremIn 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 MarcAntoine Parseval, which was later...
or, more generally, as the Plancherel theoremPlancherel theoremIn 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....
, and most generally via Pontryagin dualityPontryagin dualityIn mathematics, specifically in harmonic analysis and the theory of topological groups, Pontryagin duality explains the general properties of the Fourier transform on locally compact groups, such as R, the circle or finite cyclic groups.Introduction:...
).  The transforms are usually invertible.
 The exponential functions are eigenfunctions of differentiationDerivativeIn calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...
, which means that this representation transforms linear differential equationDifferential equationA differential equation is a mathematical equation for an unknown function of one or several variables that relates the values of the function itself and its derivatives of various orders...
s with constant coefficientsConstant coefficientsIn mathematics, constant coefficients is a term applied to differential operators, and also some difference operators, to signify that they contain no functions of the independent variables, other than constant functions. In other words, it singles out special operators, within the larger class of...
into ordinary algebraic ones . Therefore, the behavior of a linear timeinvariant system can be analyzed at each frequency independently.  By the convolution theoremConvolution theoremIn 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 pointwise multiplication in the other domain...
, Fourier transforms turn the complicated convolutionConvolutionIn 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 crosscorrelation...
operation into simple multiplication, which means that they provide an efficient way to compute convolutionbased operations such as polynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and nonnegative integer exponents...
multiplication and multiplying large numbers .  The discreteDiscrete Fourier transformIn mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
version of the Fourier transform (see below) can be evaluated quickly on computers using fast Fourier transformFast Fourier transformA 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) algorithms.
Fourier transformation is also useful as a compact representation of a signal. For example, JPEG
JPEG
In computing, JPEG . The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality. JPEG typically achieves 10:1 compression with little perceptible loss in image quality....
compression uses a variant of the Fourier transformation (discrete cosine transform
Discrete cosine transform
A discrete cosine transform expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy compression of audio and images A discrete cosine transform...
) of small square pieces of a digital image. The Fourier components of each square are rounded to lower arithmetic precision
Precision (arithmetic)
The precision of a value describes the number of digits that are used to express that value. In a scientific setting this would be the total number of digits or, less commonly, the number of fractional digits or decimal places...
, and weak components are eliminated entirely, so that the remaining components can be stored very compactly. In image reconstruction, each image square is reassembled from the preserved approximate Fouriertransformed components, which are then inversetransformed to produce an approximation of the original image.
Applications in signal processing
When processing signals, such as audioSound
Sound is a mechanical wave that is an oscillation of pressure transmitted through a solid, liquid, or gas, composed of frequencies within the range of hearing and of a level sufficiently strong to be heard, or the sensation stimulated in organs of hearing by such vibrations.Propagation of...
, radio wave
Radio Wave
Radio Wave may refer to:*Radio frequency*Radio Wave 96.5, a radio station in Blackpool, UK...
s, light waves, seismic waves, and even images, Fourier analysis can isolate individual components of a compound waveform, concentrating them for easier detection and/or removal. A large family of signal processing techniques consist of Fouriertransforming a signal, manipulating the Fouriertransformed data in a simple way, and reversing the transformation.
Some examples include:
 Telephone dialing; the touchtone signals for each telephone key, when pressed, are each a sum of two separate tones (frequencies). Fourier analysis can be used to separate (or analyze) the telephone signal, to reveal the two component tones and therefore which button was pressed.
 Removal of unwanted frequencies from an audio recording (used to eliminate hum from leakage of AC powerAC powerPower in an electric circuit is the rate of flow of energy past a given point of the circuit. In alternating current circuits, energy storage elements such as inductance and capacitance may result in periodic reversals of the direction of energy flow...
into the signal, to eliminate the stereo subcarrier from FM radio recordings);  Noise gating of audio recordings to remove quiet background noise by eliminating Fourier components that do not exceed a preset amplitude;
 EqualizationEqualizationEqualization, is the process of adjusting the balance between frequency components within an electronic signal. The most well known use of equalization is in sound recording and reproduction but there are many other applications in electronics and telecommunications. The circuit or equipment used...
of audio recordings with a series of bandpass filters;  Digital radio reception with no superheterodyne circuit, as in a modern cell phone or radio scanner;
 Image processingImage processingIn electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
to remove periodic or anisotropic artifacts such as jaggiesJaggies"Jaggies" is the informal name for artifacts in raster images, most frequently from aliasing, which in turn is often caused by nonlinear mixing effects producing highfrequency components and/or missing or poor antialiasing filtering prior to sampling....
from interlaced video, stripe artifacts from strip aerial photographyStrip aerial photographyStrip aerial photography is a method of aerial photography that uses a highspeed, lowaltitude aircraft to take a continuous picture, rather than using overlapping highaltitude photographs, as in conventional aerial photography...
, or wave patterns from radio frequency interference in a digital camera;  Cross correlation of similar images for coalignment;
 Xray crystallographyXray crystallographyXray crystallography is a method of determining the arrangement of atoms within a crystal, in which a beam of Xrays strikes a crystal and causes the beam of light to spread into many specific directions. From the angles and intensities of these diffracted beams, a crystallographer can produce a...
to reconstruct a crystal structure from its diffraction pattern;  Fourier transform ion cyclotron resonanceFourier transform ion cyclotron resonanceFourier transform ion cyclotron resonance mass spectrometry, also known as Fourier transform mass spectrometry, is a type of mass analyzer for determining the masstocharge ratio of ions based on the cyclotron frequency of the ions in a fixed magnetic field...
mass spectrometry to determine the mass of ions from the frequency of cyclotron motion in a magnetic field.  Many other forms of spectroscopy also rely upon Fourier Transforms to determine the threedimensional structure and/or identity of the sample being analyzed, including Infrared and Nuclear Magnetic Resonance spectroscopies.
 Generation of sound spectrogramSpectrogramA spectrogram is a timevarying 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...
s used to analyze sounds.
(Continuous) Fourier transform
Most often, the unqualified term Fourier transform refers to the transform of functions of a continuous realReal 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 π...
argument, and it produces a continuous function of frequency, known as a frequency distribution. One function is transformed into another, and the operation is reversible. When the domain of the input function is time (t), and the domain of the output function is ordinary 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...
, the transform of function s(t) at frequency ƒ is given by the complex number:
Evaluating this quantity for all values of ƒ produces the frequencydomain function. Then s(t) can be represented as a recombination of complex exponentials of all possible frequencies:
which is the inverse transform formula. The complex number, S(ƒ), conveys both amplitude and phase of frequency ƒ.
See 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...
for much more more information, including:
 conventions for amplitude normalization and frequency scaling/units
 transform properties
 tabulated transforms of specific functions
 an extension/generalization for functions of multiple dimensions, such as images.
Fourier series
The Fourier transform of a periodic function, s_{P}(t), with period P, becomes a Dirac combDirac comb
In mathematics, a Dirac comb is a periodic Schwartz distribution constructed from Dirac delta functions...
function, modulated by a sequence of complex coefficients:
for all integer values of k,
and where is the integral over any interval of length P.
The inverse transform, known as Fourier series, is a representation of s_{P}(t) in terms of a summation of a potentially infinite number of harmonically related sinusoids or complex exponential functions, each with an amplitude and phase specified by one of the coefficients:
When s_{P}(t), is expressed as a periodic summation of another function, s(t):
the coefficients are proportional to samples of S(ƒ) at discrete intervals of 1/P:
A sufficient condition for recovering s(t) (and therefore S(ƒ)) from just these samples is that the nonzero portion of s(t) be confined to a known interval of duration P, which is the frequency domain dual of the Nyquist–Shannon sampling theorem
Nyquist–Shannon sampling theorem
The Nyquist–Shannon sampling theorem, after Harry Nyquist and Claude Shannon, is a fundamental result in the field of information theory, in particular telecommunications and signal processing. Sampling is the process of converting a signal into a numeric sequence...
.
See 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...
for more information, including the historical development.
Discretetime Fourier transform (DTFT)
The DTFT is the mathematical dual of the timedomain Fourier series. Thus, any periodic summation in the frequency domain can be represented by a Fourier series, whose coefficients are samples of a related continuous time function:which is known as the DTFT. Thus the DTFT of the s[n] sequence is also the Fourier transform of the modulated Dirac comb
Dirac comb
In mathematics, a Dirac comb is a periodic Schwartz distribution constructed from Dirac delta functions...
function.We may also note that:
Consequently, a common practice is to model "sampling" as a multiplication by the Dirac comb
Dirac comb
In mathematics, a Dirac comb is a periodic Schwartz distribution constructed from Dirac delta functions...
function, which of course is only "possible" in a purely mathematical sense.
The Fourier series coefficients, defined by:
is the inverse transform. And it can be readily shownsee Poisson summation formula
Poisson summation formula
In mathematics, the Poisson summation formula is an equation that relates the Fourier series coefficients of the periodic summation of a function to values of the function's continuous Fourier transform. Consequently, the periodic summation of a function is completely defined by discrete samples...
that the coefficients are just samples of s(t) at discrete intervals of T: s[n] = T·s(nT).
Thus we have the important result that when a discrete data sequence, s[n], represents samples of an underlying continuous function, s(t), one can deduce something about its Fourier transform, S(ƒ). That is a cornerstone in the foundation of digital 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...
. Furthermore, under certain idealized conditions one can theoretically recover S(ƒ) and s(t) exactly. A sufficient condition for perfect recovery is that the nonzero portion of S(ƒ) be confined to a known frequency interval of width 1/T, which is the Nyquist–Shannon sampling theorem
Nyquist–Shannon sampling theorem
The Nyquist–Shannon sampling theorem, after Harry Nyquist and Claude Shannon, is a fundamental result in the field of information theory, in particular telecommunications and signal processing. Sampling is the process of converting a signal into a numeric sequence...
.
Another reason to be interested in S_{1/T}(ƒ) is that it often provides insight into the amount of aliasing
Aliasing
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...
caused by the sampling process.
Applications of the DTFT are not limited to sampled functions. See Discretetime Fourier transform
Discretetime Fourier transform
In mathematics, the discretetime 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...
for more information on this and other topics, including:
 normalized frequency units
 windowing (finitelength sequences)
 transform properties
 tabulated transforms of specific functions
Discrete Fourier transform (DFT)
The DTFT of a periodic sequence, s_{N}[n], with period N, becomes another Dirac combDirac comb
In mathematics, a Dirac comb is a periodic Schwartz distribution constructed from Dirac delta functions...
function, modulated by the coefficients of a Fourier seriesThe Fourier series represents .. And the integral formula for the coefficients simplifies to a summation:
where is the sum over any nsequence of length N.
The S_{k} sequence is what's customarily known as the DFT of s_{N}. It is also Nperiodic, so it is never necessary to compute more than N coefficients. In terms of S_{k}, the inverse transform is given by:
where is the sum over any ksequence of length N.
When s_{N}[n] is expressed as a periodic summation of another function, s[n] = T·s(nT):
the coefficients are equivalent to samples of S_{1/T}(ƒ) at discrete intervals of 1/P = 1/NT:
In most cases, N is chosen equal to the length of nonzero portion of s[n]. Increasing N, known as zeropadding or interpolation, results in more closely spaced samples of one cycle of S_{1/T}(ƒ). Decreasing N, causes overlap (adding) in the timedomain (analogous to aliasing
Aliasing
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...
), which corresponds to decimation in the frequency domain. (see Sampling the DTFT) In most cases of practical interest, the s[n] sequence represents a longer sequence that was truncated by the application of a finitelength window function
Window function
In signal processing, a window function is a mathematical function that is zerovalued 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...
or FIR filter array.
The DFT can be computed 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, which makes it a practical and important transformation on computers.
See Discrete Fourier transform
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
for much more information, including:
 transform properties
 applications
 tabulated transforms of specific functions
Summary
For periodic functions, both the Fourier transform and the DTFT comprise only a discrete set of frequency components (Fourier series), and the transforms diverge at those frequencies. One common practice is to handle that divergence via Dirac delta and Dirac combDirac comb
In mathematics, a Dirac comb is a periodic Schwartz distribution constructed from Dirac delta functions...
functions. But the same spectral information can be discerned from just one cycle of the periodic function, since all the other cycles are identical. Similarly, finiteduration functions can be represented as a Fourier series, with no actual loss of information except that the periodicity of the inverse transform is a mere artifact. The formulas in the right hand columns below apply to both cases, where in one case is the finite duration function to be analyzed, and in the other case its periodic summation, is the function under analysis. We note in passing that none of the formulas actually require the duration of to be limited to the period, P or N. But that is the most common situation.
Continuoustime transforms  
Any duration (continuous frequency)  Finite duration or periodic (discrete frequencies)  

Transform  
Inverse 
Discretetime transforms  
Any duration (continuous frequency)  Finite duration or periodic (discrete frequencies)  

Transform  
Inverse  

Fourier transforms on arbitrary locally compact abelian topological groups
The Fourier variants can also be generalized to Fourier transforms on arbitrary locally compact abelianAbelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
topological group
Topological group
In mathematics, a topological group is a group G together with a topology on G such that the group's binary operation and the group's inverse function are continuous functions with respect to the topology. A topological group is a mathematical object with both an algebraic structure and a...
s, which are studied in harmonic analysis
Harmonic analysis
Harmonic analysis is the branch of mathematics that studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms...
; there, the Fourier transform takes functions on a group to functions on the dual group. This treatment also allows a general formulation of 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 pointwise multiplication in the other domain...
, which relates Fourier transforms and 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 crosscorrelation...
s. See also the Pontryagin duality
Pontryagin duality
In mathematics, specifically in harmonic analysis and the theory of topological groups, Pontryagin duality explains the general properties of the Fourier transform on locally compact groups, such as R, the circle or finite cyclic groups.Introduction:...
for the generalized underpinnings of the Fourier transform.
Time–frequency transforms
In signal processingSignal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
terms, a function (of time) is a representation of a signal with perfect time resolution, but no frequency information, while the Fourier transform has perfect frequency resolution, but no time information.
As alternatives to the Fourier transform, in time–frequency analysis, one uses time–frequency transforms to represent signals in a form that has some time information and some frequency information – by the uncertainty principle
Uncertainty principle
In quantum mechanics, the Heisenberg uncertainty principle states a fundamental limit on the accuracy with which certain pairs of physical properties of a particle, such as position and momentum, can be simultaneously known...
, there is a tradeoff between these. These can be generalizations of the Fourier transform, such as the shorttime Fourier transform
Shorttime Fourier transform
The shorttime Fourier transform , or alternatively shortterm Fourier transform, is a Fourierrelated transform used to determine the sinusoidal frequency and phase content of local sections of a signal as it changes over time....
, the Gabor transform
Gabor transform
The Gabor transform, named after Dennis Gabor, is a special case of the shorttime Fourier transform. It is used to determine the sinusoidal frequency and phase content of local sections of a signal as it changes over time...
or 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 nth power where n need not be an integer — thus, it can transform a function to an...
, or can use different functions to represent signals, as in wavelet transforms and chirplet transform
Chirplet transform
In signal processing, the chirplet transform is an inner product of an input signal with a family of analysis primitives called chirplets.Similarity to other transforms:...
s, with the wavelet analog of the (continuous) Fourier transform being the continuous wavelet transform
Continuous wavelet transform
A continuous wavelet transform is used to divide a continuoustime function into wavelets. Unlike Fourier transform, the continuous wavelet transform possesses the ability to construct a timefrequency representation of a signal that offers very good time and frequency localization...
.
History
A primitive form of harmonic series dates back to ancient Babylonian mathematicsBabylonian mathematics
Babylonian mathematics refers to any mathematics of the people of Mesopotamia, from the days of the early Sumerians to the fall of Babylon in 539 BC. Babylonian mathematical texts are plentiful and well edited...
, where they were used to compute ephemerides (tables of astronomical positions).
In modern times, variants of the discrete Fourier transform were used by Alexis Clairaut in 1754 to compute an orbit,
which has been described as the first formula for the DFT,
and in 1759 by Joseph Louis Lagrange
Joseph Louis Lagrange
JosephLouis Lagrange , born Giuseppe Lodovico Lagrangia, was a mathematician and astronomer, who was born in Turin, Piedmont, lived part of his life in Prussia and part in France, making significant contributions to all fields of analysis, to number theory, and to classical and celestial mechanics...
, in computing the coefficients of a trigonometric series for a vibrating string. Technically, Clairaut's work was a cosineonly series (a form of discrete cosine transform
Discrete cosine transform
A discrete cosine transform expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy compression of audio and images A discrete cosine transform...
), while Lagrange's work was a sineonly series (a form of discrete sine transform
Discrete sine transform
In mathematics, the discrete sine transform is a Fourierrelated transform similar to the discrete Fourier transform , but using a purely real matrix...
); a true cosine+sine DFT was used 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...
in 1805 for trigonometric interpolation
Trigonometric interpolation
In mathematics, trigonometric interpolation is interpolation with trigonometric polynomials. Interpolation is the process of finding a function which goes through some given data points. For trigonometric interpolation, this function has to be a trigonometric polynomial, that is, a sum of sines and...
of asteroid
Asteroid
Asteroids are a class of small Solar System bodies in orbit around the Sun. They have also been called planetoids, especially the larger ones...
orbits.
Euler and Lagrange both discretized the vibrating string problem, using what would today be called samples.
An early modern development toward Fourier analysis was the 1770 paper Réflexions sur la résolution algébrique des équations by Lagrange, which in the method of Lagrange resolvents used a complex Fourier decomposition to study the solution of a cubic:
Lagrange transformed the roots into the resolvents:
where ζ is a cubic root of unity, which is the DFT of order 3.
A number of authors, notably Jean le Rond d'Alembert
Jean le Rond d'Alembert
JeanBaptiste le Rond d'Alembert was a French mathematician, mechanician, physicist, philosopher, and music theorist. He was also coeditor with Denis Diderot of the Encyclopédie...
,, and Carl Friedrich 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...
used trigonometric series to study the heat equation
Heat equation
The heat equation is an important partial differential equation which describes the distribution of heat in a given region over time...
, but the breakthrough development was the 1807 paper
Mémoire sur la propagation de la chaleur dans les corps solides by Joseph Fourier
Joseph Fourier
Jean Baptiste Joseph Fourier was a French mathematician and physicist best known for initiating the investigation of Fourier series and their applications to problems of heat transfer and vibrations. The Fourier transform and Fourier's Law are also named in his honour...
, whose crucial insight was to model all functions by trigonometric series, introducing the Fourier series.
Historians are divided as to how much to credit Lagrange and others for the development of Fourier theory: Daniel Bernoulli
Daniel Bernoulli
Daniel Bernoulli was a DutchSwiss mathematician and was one of the many prominent mathematicians in the Bernoulli family. He is particularly remembered for his applications of mathematics to mechanics, especially fluid mechanics, and for his pioneering work in probability and statistics...
and Leonhard Euler
Leonhard Euler
Leonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
had introduced trigonometric representations of functions, and Lagrange had given the Fourier series solution to the wave equation, so Fourier's contribution was mainly the bold claim that an arbitrary function could be represented by a Fourier series.
The subsequent development of the field is known as harmonic analysis
Harmonic analysis
Harmonic analysis is the branch of mathematics that studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms...
, and is also an early instance of 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...
.
The first fast Fourier transform (FFT) algorithm for the DFT was discovered around 1805 by Carl Friedrich Gauss when interpolating measurements of the orbit of the asteroids Juno and Pallas, although that particular FFT algorithm is more often attributed to its modern rediscoverers Cooley and Tukey.
Interpretation in terms of time and frequency
In signal processingSignal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
, the Fourier transform often takes a time series
Time series
In statistics, signal processing, econometrics and mathematical finance, a time series is a sequence of data points, measured typically at successive times spaced at uniform time intervals. Examples of time series are the daily closing value of the Dow Jones index or the annual flow volume of the...
or a function of continuous time, and maps it into a frequency spectrum
Frequency spectrum
The frequency spectrum of a timedomain signal is a representation of that signal in the frequency domain. The frequency spectrum can be generated via a Fourier transform of the signal, and the resulting values are usually presented as amplitude and phase, both plotted versus frequency.Any signal...
. That is, it takes a function from the time
Time
Time is a part of the measuring system used to sequence events, to compare the durations of events and the intervals between them, and to quantify rates of change such as the motions of objects....
domain into the 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...
domain; it is a decomposition of a function into sinusoids of different frequencies; in the case of a 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...
or discrete Fourier transform
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
, the sinusoids are harmonic
Harmonic
A harmonic of a wave is a component frequency of the signal that is an integer multiple of the fundamental frequency, i.e. if the fundamental frequency is f, the harmonics have frequencies 2f, 3f, 4f, . . . etc. The harmonics have the property that they are all periodic at the fundamental...
s of the fundamental frequency of the function being analyzed.
When the function ƒ is a function of time and represents a physical signal, the transform has a standard interpretation as the frequency spectrum of the signal. The magnitude
Magnitude (mathematics)
The magnitude of an object in mathematics is its size: a property by which it can be compared as larger or smaller than other objects of the same kind; in technical terms, an ordering of the class of objects to which it belongs....
of the resulting complexvalued function F at frequency ω represents the amplitude
Amplitude
Amplitude is the magnitude of change in the oscillating variable with each oscillation within an oscillating system. For example, sound waves in air are oscillations in atmospheric pressure and their amplitudes are proportional to the change in pressure during one oscillation...
of a frequency component whose initial phase
Phase (waves)
Phase in waves is the fraction of a wave cycle which has elapsed relative to an arbitrary point.Formula:The phase of an oscillation or wave refers to a sinusoidal function such as the following:...
is given by the phase of F.
Fourier transforms are not limited to functions of time, and temporal frequencies. They can equally be applied to analyze spatial frequencies, and indeed for nearly any function domain. This justifies their use in branches such diverse as image processing
Image processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
, heat conduction
Heat conduction
In heat transfer, conduction is a mode of transfer of energy within and between bodies of matter, due to a temperature gradient. Conduction means collisional and diffusive transfer of kinetic energy of particles of ponderable matter . Conduction takes place in all forms of ponderable matter, viz....
and automatic control
Automatic control
Automatic control is the application of concepts derived from the research area of modern control theory. Automatic control is also a technology for application of control strategies. The implementing requires prior of analyzing and modeling of the subject to be controlled...
.
See also
 Fourierrelated transforms
 Laplace transform (LT)
 Twosided Laplace transformTwosided Laplace transformIn mathematics, the twosided Laplace transform or bilateral Laplace transform is an integral transform closely related to the Fourier transform, the Mellin transform, and the ordinary or onesided Laplace transform...
 Mellin transformMellin transformIn mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the twosided Laplace transform...
 Fast Fourier transformFast Fourier transformA 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)  Nonuniform discrete Fourier transformNonuniform discrete Fourier transformIn applied mathematics, the nonuniform discrete Fourier transform of a signal is a type of Fourier transform, related to a discrete Fourier transform or discretetime Fourier transform, but in which the input signal is not sampled at equallyspaced intervals. As a result of this, the computed...
(NDFT)  Fractional Fourier transformFractional Fourier transformIn 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 nth power where n need not be an integer — thus, it can transform a function to an...
(FRFT)  Quantum Fourier transformQuantum Fourier transformIn quantum computing, the quantum Fourier transform is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform...
(QFT)  Numbertheoretic transform
 Leastsquares spectral analysisLeastsquares spectral analysisLeastsquares spectral analysis is a method of estimating a frequency spectrum, based on a least squares fit of sinusoids to data samples, similar to Fourier analysis...
 Basis vectors
 BispectrumBispectrumIn mathematics, in the area of statistical analysis, the bispectrum is a statistic used to search for nonlinear interactions. The Fourier transform of the secondorder cumulant, i.e., the autocorrelation function, is the traditional power spectrum...
 Characteristic function (probability theory)Characteristic function (probability theory)In probability theory and statistics, the characteristic function of any random variable completely defines its probability distribution. Thus it provides the basis of an alternative route to analytical results compared with working directly with probability density functions or cumulative...
 Orthogonal functionsOrthogonal functionsIn mathematics, two functions f and g are called orthogonal if their inner product \langle f,g\rangle is zero for f ≠ g. Whether or not two particular functions are orthogonal depends on how their inner product has been defined. A typical definition of an inner product for functions is...
 Pontryagin dualityPontryagin dualityIn mathematics, specifically in harmonic analysis and the theory of topological groups, Pontryagin duality explains the general properties of the Fourier transform on locally compact groups, such as R, the circle or finite cyclic groups.Introduction:...
 Schwartz space
 Spectral densitySpectral densityIn statistical signal processing and physics, the spectral density, power spectral density , or energy spectral density , is a positive real function of a frequency variable associated with a stationary stochastic process, or a deterministic function of time, which has dimensions of power per hertz...
 Spectral density estimationSpectral density estimationIn statistical signal processing, the goal of spectral density estimation is to estimate the spectral density of a random signal from a sequence of time samples of the signal. Intuitively speaking, the spectral density characterizes the frequency content of the signal...
 WaveletWaveletA wavelet is a wavelike oscillation with an amplitude that starts out at zero, increases, and then decreases back to zero. It can typically be visualized as a "brief oscillation" like one might see recorded by a seismograph or heart monitor. Generally, wavelets are purposefully crafted to have...
External links
 Tables of Integral Transforms at EqWorld: The World of Mathematical Equations.
 An Intuitive Explanation of Fourier Theory by Steven Lehar.
 Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lecture 6 is on the 1 and 2D Fourier Transform. Lectures 715 make use of it., by Alan Peters