Editing Fourier analysis (section)

==Variants of Fourier analysis==
[[File:Fourier transform, Fourier series, DTFT, DFT.svg|thumb|400px|A Fourier transform and 3 variations caused by periodic sampling (at interval <math>T</math>) and/or periodic summation (at interval <math>P</math>) of the underlying time-domain function. The relative computational ease of the DFT sequence and the insight it gives into <math>S(f)</math> make it a popular analysis tool.]]

===(Continuous) Fourier transform===
{{main|Fourier transform}}

Most often, the unqualified term '''Fourier transform''' refers to the transform of functions of a continuous [[real number|real]] 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 (initial) function is time (<math>t</math>), and the domain of the output (final) function is [[frequency|ordinary frequency]], the transform of function <math>s(t)</math> at frequency <math>f</math> is given by the [[complex number]]''':'''

:<math>S(f) = \int_{-\infty}^{\infty} s(t) \cdot e^{- i2\pi f t} \, dt.</math>

Evaluating this quantity for all values of <math>f</math> produces the ''frequency-domain'' function. Then <math>s(t)</math> can be represented as a recombination of [[complex exponentials]] of all possible frequencies''':'''

:<math>s(t) = \int_{-\infty}^{\infty} S(f) \cdot e^{i2\pi f t} \, df,</math>

which is the inverse transform formula. The complex number, <math>S(f),</math> conveys both amplitude and phase of frequency <math>f.</math>

See [[Fourier transform]] for much 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===
{{Main|Fourier series}}

The Fourier transform of a periodic function, <math>s_{_P}(t),</math> with period <math>P,</math> becomes a [[Dirac comb]] function, modulated by a sequence of complex [[coefficients]]''':'''

:<math>S[k] = \frac{1}{P}\int_{P} s_{_P}(t)\cdot e^{-i2\pi \frac{k}{P} t}\, dt, \quad k\in\Z,</math> &nbsp; &nbsp; (where <math>\int_{P}</math> is the integral over any interval of length <math>P</math>).

The inverse transform, known as '''Fourier series''', is a representation of <math>s_{_P}(t)</math> in terms of a summation of a potentially infinite number of harmonically related sinusoids or [[complex exponentials|complex exponential]] functions, each with an amplitude and phase specified by one of the coefficients''':'''

:<math>s_{_P}(t)\ \ =\ \ \mathcal{F}^{-1}\left\{\sum_{k=-\infty}^{+\infty} S[k]\, \delta \left(f-\frac{k}{P}\right)\right\}\ \ =\ \ \sum_{k=-\infty}^\infty S[k]\cdot e^{i2\pi \frac{k}{P} t}.</math>

Any <math>s_{_P}(t)</math> can be expressed as a [[periodic summation]] of another function, <math>s(t)</math>''':'''

:<math>s_{_P}(t) \,\triangleq\, \sum_{m=-\infty}^\infty s(t-mP),</math>

and the coefficients are proportional to samples of <math>S(f)</math> at discrete intervals of <math>\frac{1}{P}</math>''':'''

:<math>S[k] =\frac{1}{P}\cdot S\left(\frac{k}{P}\right).</math>{{efn-ua
|<math>\int_{P} \left(\sum_{m=-\infty}^{\infty} s(t-mP)\right) \cdot e^{-i2\pi \frac{k}{P} t} \,dt = \underbrace{\int_{-\infty}^{\infty} s(t) \cdot e^{-i2\pi \frac{k}{P} t} \,dt}_{\triangleq\, S\left(\frac{k}{P}\right)}</math>
}}

Note that any <math>s(t)</math> whose transform has the same discrete sample values can be used in the periodic summation.  A sufficient condition for recovering <math>s(t)</math> (and therefore <math>S(f)</math>) from just these samples (i.e. from the Fourier series) is that the non-zero portion of <math>s(t)</math> be confined to a known interval of duration <math>P,</math> which is the frequency domain dual of the [[Nyquist–Shannon sampling theorem]].

See [[Fourier series]] for more information, including the historical development.

===Discrete-time Fourier transform (DTFT)===
{{main|Discrete-time Fourier transform}}

The DTFT is the mathematical dual of the time-domain Fourier series. Thus, a convergent [[periodic summation]] in the frequency domain can be represented by a Fourier series, whose coefficients are samples of a related continuous time function''':'''

:<math>S_\tfrac{1}{T}(f)\ \triangleq\ \underbrace{\sum_{k=-\infty}^{\infty} S\left(f - \frac{k}{T}\right) \equiv \overbrace{\sum_{n=-\infty}^{\infty} s[n] \cdot e^{-i2\pi f n T}}^{\text{Fourier series (DTFT)}}}_{\text{Poisson summation formula}} = \mathcal{F} \left \{ \sum_{n=-\infty}^{\infty} s[n]\ \delta(t-nT)\right \},\,</math>

which is known as the DTFT. Thus the '''DTFT''' of the <math>s[n]</math> sequence is also the '''Fourier transform''' of the modulated [[Dirac comb]] function.{{efn-ua|
We may also note that''':'''
:<math>\begin{align} \sum_{n=-\infty}^{+\infty} T\cdot s(nT) \delta(t-nT) &= \sum_{n=-\infty}^{+\infty} T\cdot s(t) \delta(t-nT) \\ &= s(t)\cdot T \sum_{n=-\infty}^{+\infty} \delta(t-nT). \end{align}</math>
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 (and inverse transform), are defined by''':'''

:<math>s[n]\ \triangleq\ T \int_\frac{1}{T} S_\tfrac{1}{T}(f)\cdot e^{i2\pi f nT} \,df = T \underbrace{\int_{-\infty}^{\infty} S(f)\cdot e^{i2\pi f nT} \,df}_{\triangleq\, s(nT)}.</math>

Parameter <math>T</math> corresponds to the sampling interval, and this Fourier series can now be recognized as a form of the [[Poisson summation formula]].&nbsp; Thus we have the important result that when a discrete data sequence, <math>s[n],</math> is proportional to samples of an underlying continuous function, <math>s(t),</math> one can observe a periodic summation of the continuous Fourier transform, <math>S(f).</math> Note that any <math>s(t)</math> with the same discrete sample values produces the same DTFT.&nbsp; But under certain idealized conditions one can theoretically recover <math>S(f)</math> and <math>s(t)</math> exactly. A sufficient condition for perfect recovery is that the non-zero portion of <math>S(f)</math> be confined to a known frequency interval of width <math>\tfrac{1}{T}.</math>&nbsp; When that interval is <math>\left[-\tfrac{1}{2T}, \tfrac{1}{2T}\right],</math> the applicable reconstruction formula is the [[Whittaker–Shannon interpolation formula]].  This is a cornerstone in the foundation of [[digital signal processing]].

Another reason to be interested in <math>S_\tfrac{1}{T}(f)</math> 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 [[Discrete-time Fourier transform]] for more information on this and other topics, including''':'''
* normalized frequency units
* windowing (finite-length sequences)
* transform properties
* tabulated transforms of specific functions

===Discrete Fourier transform (DFT)===
{{main|Discrete Fourier transform}}

Similar to a Fourier series, the DTFT of a periodic sequence, <math>s_{_N}[n],</math> with period <math>N</math>, becomes a Dirac comb function, modulated by a sequence of complex coefficients (see {{slink|DTFT|Periodic data}})''':'''

:<math>S[k] = \sum_n s_{_N}[n]\cdot e^{-i2\pi \frac{k}{N} n}, \quad k\in\Z,</math> &nbsp; &nbsp; (where <math>\sum_{n}</math> is the sum over any sequence of length <math>N.</math>)

The <math>S[k]</math> sequence is customarily known as the '''DFT''' of one cycle of <math>s_{_N}.</math> It is also <math>N</math>-periodic, so it is never necessary to compute more than <math>N</math> coefficients. The inverse transform, also known as a [[discrete Fourier series]], is given by''':'''

:<math>s_{_N}[n] = \frac{1}{N} \sum_{k} S[k]\cdot e^{i2\pi \frac{n}{N}k},</math> &nbsp; where <math>\sum_{k}</math> is the sum over any sequence of length <math>N.</math>

When <math>s_{_N}[n]</math> is expressed as a [[periodic summation]] of another function''':'''

:<math>s_{_N}[n]\, \triangleq\, \sum_{m=-\infty}^{\infty} s[n-mN],</math> &nbsp; and &nbsp; <math>s[n]\, \triangleq\, T\cdot s(nT),</math>

the coefficients are samples of <math>S_\tfrac{1}{T}(f)</math> at discrete intervals of <math>\tfrac{1}{P} = \tfrac{1}{NT}</math>''':'''

:<math>S[k] = S_\tfrac{1}{T}\left(\frac{k}{P}\right).</math>

Conversely, when one wants to compute an arbitrary number <math>(N)</math> of discrete samples of one cycle of a continuous DTFT, <math>S_\tfrac{1}{T}(f),</math> it can be done by computing the relatively simple DFT of <math>s_{_N}[n],</math> as defined above. In most cases, <math>N</math> is chosen equal to the length of the non-zero portion of <math>s[n].</math> Increasing <math>N,</math> known as ''zero-padding'' or ''interpolation'', results in more closely spaced samples of one cycle of <math>S_\tfrac{1}{T}(f).</math> Decreasing <math>N,</math> causes overlap (adding) in the time-domain (analogous to [[aliasing]]), which corresponds to decimation in the frequency domain. (see {{slink|Discrete-time Fourier transform|2=L=N×I}}) In most cases of practical interest, the <math>s[n]</math> sequence represents a longer sequence that was truncated by the application of a finite-length [[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''':'''
* 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 (not discussed above) is to handle that divergence via [[Dirac delta]] and [[Dirac comb]] 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, finite-duration 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.

It is common in practice for the duration of ''s''(•) to be limited to the period, {{mvar|P}} or {{mvar|N}}.&nbsp; But these formulas do not require that condition.
{| class="wikitable" style="text-align:left"
|+ <math>s(t)</math> transforms (continuous-time)
|-
! !! Continuous frequency !! Discrete frequencies
|-
! Transform
| <math>S(f)\, \triangleq\, \int_{-\infty}^{\infty} s(t) \cdot e^{-i2\pi f t} \,dt</math>
|| <math>\underbrace{\frac{1}{P}\cdot S\left(\frac{k}{P}\right)}_ {S[k]}\, \triangleq\, \frac{1}{P} \int_{-\infty}^{\infty} s(t) \cdot e^{-i2\pi \frac{k}{P} t}\,dt \equiv \frac{1}{P} \int_P s_{_P}(t) \cdot e^{-i2\pi \frac{k}{P} t} \,dt</math>
|-
! Inverse
| <math>s(t) = \int_{-\infty}^{\infty} S(f) \cdot e^{ i2\pi f t}\, df</math>
||<math>\underbrace{s_{_P}(t) = \sum_{k=-\infty}^{\infty} S[k] \cdot e^{i2\pi \frac{k}{P} t}}_{\text{Poisson summation formula (Fourier series)}}\,</math>
|}

{| class="wikitable" style="text-align:left"
|+ <math>s(nT)</math> transforms (discrete-time)
|-
! !! Continuous frequency !! Discrete frequencies
|-
! Transform
| <math>\underbrace{S_\tfrac{1}{T}(f)\, \triangleq\, \sum_{n=-\infty}^{\infty} s[n]\cdot e^{-i2\pi f nT}}_{\text{Poisson summation formula (DTFT)}}</math>
||
<math>
\begin{align}
\underbrace{S_\tfrac{1}{T}\left(\frac{k}{NT}\right)}_ {S[k]}\, &\triangleq\, \sum_{n=-\infty}^{\infty} s[n]\cdot e^{-i2\pi \frac{kn}{N}}\\
&\equiv \underbrace{\sum_{N} s_{_N}[n]\cdot e^{-i2\pi \frac{kn}{N}}}_{\text{DFT}}\,
\end{align}
</math>
|-
! Inverse
| <math>s[n] = \underbrace{T \int_\frac{1}{T} S_\tfrac{1}{T}(f)\cdot e^{i2\pi f nT} \,df}_{\text{Fourier series coefficient}}</math>
<math>\sum_{n=-\infty}^{\infty} s[n]\cdot \delta(t-nT) = \underbrace{\int_{-\infty}^{\infty} S_\tfrac{1}{T}(f)\cdot e^{i2\pi f t}\,df}_{\text{inverse Fourier transform}}\,</math>
||
<math>
s_{_N}[n] = \underbrace{\frac{1}{N} \sum_{N} S[k]\cdot e^{i2\pi \frac{kn}{N}}}_{\text{inverse DFT}}
</math>
|}