Namespaces
Variants
Actions

Difference between revisions of "Fourier transform, discrete"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
f0411601.png
 +
$#A+1 = 35 n = 0
 +
$#C+1 = 35 : ~/encyclopedia/old_files/data/F041/F.0401160 Fourier transform, discrete
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A transform used for the harmonic analysis of functions given on a discrete set of points.
 
A transform used for the harmonic analysis of functions given on a discrete set of points.
  
If a function is given on the set of points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411601.png" /> by its values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411602.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411603.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411604.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411605.png" /> is the period of the function, then the discrete Fourier transform of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411606.png" /> is the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411607.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411608.png" /> is the matrix with entries
+
If a function is given on the set of points $  t _ {k} = k \Delta t $
 +
by its values $  x _ {k} $,  
 +
$  k = 0 \dots N - 1 $,  
 +
$  \Delta t = T/N $,  
 +
where $  T > 0 $
 +
is the period of the function, then the discrete Fourier transform of the vector $  x = ( x _ {0} \dots x _ {N - 1 }  ) $
 +
is the vector $  \widehat{x}  = Fx $,  
 +
where $  F $
 +
is the matrix with entries
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f0411609.png" /></td> </tr></table>
+
$$
 +
\mathop{\rm exp}  \{ - 2 \pi i \omega _ {m} t _ {k} \} ,
 +
$$
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116010.png" /> is the imaginary unit, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116013.png" />. The components of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116014.png" /> are analogues of the Fourier coefficients in the usual trigonometric expansions. The discrete Fourier transform is used to calculate approximately these coefficients, spectra, auto- and mutual-correlation functions, etc. A direct computation of the discrete Fourier transform requires about <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116015.png" /> arithmetic operations and a great expenditure of machine time. The method of the fast Fourier transform (see [[#References|[1]]]) enables one to reduce the number of operations considerably. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116016.png" />, this method carries out the discrete Fourier transform approximately in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116017.png" /> operations, increasing the accuracy of the calculation. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116018.png" /> there are algorithms which are particularly convenient in practice. There is a considerable number of programs realizing or using the fast Fourier transform to solve applied problems. The method of the fast Fourier transform includes widely known efficient methods for computing the discrete Fourier transform, for example, the Runge method (see [[#References|[2]]] and [[Runge–Kutta method|Runge–Kutta method]]).
+
$  i $
 +
is the imaginary unit, $  \omega _ {m} = m \Delta \omega $,  
 +
$  m = 0 \dots N - 1 $,  
 +
$  \Delta \omega = 1/T $.  
 +
The components of the vector $  \widehat{x}  $
 +
are analogues of the Fourier coefficients in the usual trigonometric expansions. The discrete Fourier transform is used to calculate approximately these coefficients, spectra, auto- and mutual-correlation functions, etc. A direct computation of the discrete Fourier transform requires about $  N  ^ {2} $
 +
arithmetic operations and a great expenditure of machine time. The method of the fast Fourier transform (see [[#References|[1]]]) enables one to reduce the number of operations considerably. When $  N = n _ {1} \dots n _ {m} $,  
 +
this method carries out the discrete Fourier transform approximately in $  N ( n _ {1} + \dots + n _ {m} ) $
 +
operations, increasing the accuracy of the calculation. When $  N = 2  ^ {m} $
 +
there are algorithms which are particularly convenient in practice. There is a considerable number of programs realizing or using the fast Fourier transform to solve applied problems. The method of the fast Fourier transform includes widely known efficient methods for computing the discrete Fourier transform, for example, the Runge method (see [[#References|[2]]] and [[Runge–Kutta method|Runge–Kutta method]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J. Cooley,  J. Tukey,  "An algorithm for the machine calculation of complex Fourier series"  ''Math. Comp.'' , '''19'''  (1965)  pp. 297–301</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  C.Z. Runge,  ''Math. Phys.'' , '''48'''  (1903)  pp. 443</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J. Cooley,  J. Tukey,  "An algorithm for the machine calculation of complex Fourier series"  ''Math. Comp.'' , '''19'''  (1965)  pp. 297–301</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  C.Z. Runge,  ''Math. Phys.'' , '''48'''  (1903)  pp. 443</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
The fast Fourier transform of J. Cooley and J. Tukey exploits the special structure of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116019.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116020.png" /> it turns out that the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116021.png" /> can be factorized into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116022.png" /> matrices the rows of which contain only a few non-zero entries, the non-zero entries being equal or having opposite signs. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116023.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116024.png" /> where the rows of the factor matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116027.png" /> each contain only 2 non-zero elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116029.png" /> such that either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116030.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116031.png" /> (written out formulas for the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116032.png" /> can be found in [[#References|[a1]]], p. 255). Thus, the computation of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116033.png" /> requires only <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116034.png" /> instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041160/f04116035.png" />  "operations" . A detailed theoretical treatment of the fast Fourier transform as well as algorithmic information is provided by the monograph [[#References|[a2]]].
+
The fast Fourier transform of J. Cooley and J. Tukey exploits the special structure of the matrix $  F $.  
 +
For $  N = 2  ^ {n} $
 +
it turns out that the matrix $  F $
 +
can be factorized into $  n $
 +
matrices the rows of which contain only a few non-zero entries, the non-zero entries being equal or having opposite signs. For example, if $  N = 8 $,  
 +
then $  F = A B C $
 +
where the rows of the factor matrices $  A $,  
 +
$  B $
 +
and $  C $
 +
each contain only 2 non-zero elements $  a $
 +
and $  b $
 +
such that either $  a = b $
 +
or $  a = - b $(
 +
written out formulas for the case $  N = 8 $
 +
can be found in [[#References|[a1]]], p. 255). Thus, the computation of the vector $  F x = A B C x $
 +
requires only $  n \cdot N = 24 $
 +
instead of $  N  ^ {2} = 64 $"
 +
operations" . A detailed theoretical treatment of the fast Fourier transform as well as algorithmic information is provided by the monograph [[#References|[a2]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C.E. Fröberg,  "Introduction to numerical analysis, theory and applications" , Benjamin/Cummings  (1985)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.D. Brigham,  "The fast Fourier transform" , Prentice-Hall  (1974)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.W. Ramirez,  "The FFT fundamentals and concepts" , Prentice-Hall  (1985)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.F. Elliot,  K.R. Rao,  "Fast transforms: algorithms, analysis, applications" , Acad. Press  (1982)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C.E. Fröberg,  "Introduction to numerical analysis, theory and applications" , Benjamin/Cummings  (1985)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.D. Brigham,  "The fast Fourier transform" , Prentice-Hall  (1974)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.W. Ramirez,  "The FFT fundamentals and concepts" , Prentice-Hall  (1985)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.F. Elliot,  K.R. Rao,  "Fast transforms: algorithms, analysis, applications" , Acad. Press  (1982)</TD></TR></table>

Latest revision as of 19:39, 5 June 2020


A transform used for the harmonic analysis of functions given on a discrete set of points.

If a function is given on the set of points $ t _ {k} = k \Delta t $ by its values $ x _ {k} $, $ k = 0 \dots N - 1 $, $ \Delta t = T/N $, where $ T > 0 $ is the period of the function, then the discrete Fourier transform of the vector $ x = ( x _ {0} \dots x _ {N - 1 } ) $ is the vector $ \widehat{x} = Fx $, where $ F $ is the matrix with entries

$$ \mathop{\rm exp} \{ - 2 \pi i \omega _ {m} t _ {k} \} , $$

$ i $ is the imaginary unit, $ \omega _ {m} = m \Delta \omega $, $ m = 0 \dots N - 1 $, $ \Delta \omega = 1/T $. The components of the vector $ \widehat{x} $ are analogues of the Fourier coefficients in the usual trigonometric expansions. The discrete Fourier transform is used to calculate approximately these coefficients, spectra, auto- and mutual-correlation functions, etc. A direct computation of the discrete Fourier transform requires about $ N ^ {2} $ arithmetic operations and a great expenditure of machine time. The method of the fast Fourier transform (see [1]) enables one to reduce the number of operations considerably. When $ N = n _ {1} \dots n _ {m} $, this method carries out the discrete Fourier transform approximately in $ N ( n _ {1} + \dots + n _ {m} ) $ operations, increasing the accuracy of the calculation. When $ N = 2 ^ {m} $ there are algorithms which are particularly convenient in practice. There is a considerable number of programs realizing or using the fast Fourier transform to solve applied problems. The method of the fast Fourier transform includes widely known efficient methods for computing the discrete Fourier transform, for example, the Runge method (see [2] and Runge–Kutta method).

References

[1] J. Cooley, J. Tukey, "An algorithm for the machine calculation of complex Fourier series" Math. Comp. , 19 (1965) pp. 297–301
[2] C.Z. Runge, Math. Phys. , 48 (1903) pp. 443

Comments

The fast Fourier transform of J. Cooley and J. Tukey exploits the special structure of the matrix $ F $. For $ N = 2 ^ {n} $ it turns out that the matrix $ F $ can be factorized into $ n $ matrices the rows of which contain only a few non-zero entries, the non-zero entries being equal or having opposite signs. For example, if $ N = 8 $, then $ F = A B C $ where the rows of the factor matrices $ A $, $ B $ and $ C $ each contain only 2 non-zero elements $ a $ and $ b $ such that either $ a = b $ or $ a = - b $( written out formulas for the case $ N = 8 $ can be found in [a1], p. 255). Thus, the computation of the vector $ F x = A B C x $ requires only $ n \cdot N = 24 $ instead of $ N ^ {2} = 64 $" operations" . A detailed theoretical treatment of the fast Fourier transform as well as algorithmic information is provided by the monograph [a2].

References

[a1] C.E. Fröberg, "Introduction to numerical analysis, theory and applications" , Benjamin/Cummings (1985)
[a2] E.D. Brigham, "The fast Fourier transform" , Prentice-Hall (1974)
[a3] R.W. Ramirez, "The FFT fundamentals and concepts" , Prentice-Hall (1985)
[a4] D.F. Elliot, K.R. Rao, "Fast transforms: algorithms, analysis, applications" , Acad. Press (1982)
How to Cite This Entry:
Fourier transform, discrete. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fourier_transform,_discrete&oldid=46965
This article was adapted from an original article by V.A. Morozov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article