请输入您要查询的字词:

 

单词 DiscreteFourierTransform
释义

discrete Fourier transform


The discrete Fourier transform (DFT) is an invertiblePlanetmathPlanetmath transform widely employed in signal processing and analysis. It can be computed using stable efficient algorithms known as Fast Fourier Transform (FFT) algorithms.

1 Definition

Given a sequence {fn}n=0N-1 of N complex numbersPlanetmathPlanetmath, the DFT is defined as a sequence {Fk}k=0N-1 of N complex numbers according to the equation

Fk=1N(1-p)/2n=0N-1fnWN-k,n  k=0,1,2,,N-1

where WNk,n=e2πiqkn/N are the basis functions, p is an arbitrary real number and q is either 1 or -1.

Similarly, we can reconstruct {fn}n=0N-1 from {Fk}k=0N-1 via the inverse discrete Fourier transform (IDFT):

fn=1N(1+p)/2k=0N-1FkWNk,n  n=0,1,2,,N-1

2 Explanation

Generically, if we have some vector 𝐯=(v1,v2,,vn) that we wish to project on to a set of unit basis vectors 𝐁^1,𝐁^2,,𝐁^m, we find that the kth componentMathworldPlanetmathPlanetmath of the projection 𝐯 is given by

vk=𝐯,𝐁^k

where 𝐮,𝐯 is an inner productMathworldPlanetmath. Using the standard dot productMathworldPlanetmath of complex vectors, we have

vk=j=0mvjB¯k,j

(where z¯ represents the complex conjugateMathworldPlanetmath of z).

We may use a procedure to project a function onto basis functions. Here, the components of our vectors are the functions sampled at certain time intervals.

The idea of the Fourier transformMathworldPlanetmath is to project our discrete function {fn} onto a basis made up of sinusoidal functions of varying frequency.

We know from Euler’s relationPlanetmathPlanetmath that

eix=cosx+isinx

so we can construct a sinusoidal function of any frequency k:

WNk,n=e2πiqkn/N=cos(2πiqkn/N)+isin(2πiqkn/N)

By Nyquist’s theorem, any frequency components of {fn} above the Nyquist frequency N2 will be aliased into lower frequencies, so we will only concern ourselves with the frequency components -N2kN2.

Now we substitute these results into the standard formula for projection to reveal that

Fk=n=0N-1fnWN-k,n  k=0,1,2,,N-1

3 Group theoretic interpretation and generalization

This procedure may be interpreted in terms of group theory as follows: The basis functions χk(j)e-2πνkij/f are the charactersMathworldPlanetmathPlanetmath of the irreducible representations of the group M. The orthogonality relation χm,χn=δmn which was used to obtain the transform as a projection is the orthogonality relation for characters.

Once we view the discrete Fourier transform in this fashion, it is not hard to generalize it by replacing M with any discrete group G. As it turns out, there are two versions of the generalization which turn out to coincide exactly in the case of commutative groups (such as M).

First generalization: Let f:G be conjugationMathworldPlanetmath invariant, which means that, for every yG, it is the case that f(yxy-1)=f(x). Then one has

f(x)=k1dkf,χkχk(x)

where the index k runs over all irreducible representations and dk is the dimensionPlanetmathPlanetmathPlanetmathPlanetmath of the representation k. The inner product on vectors is the usual one:

𝐮,𝐯=gG𝐮(g)𝐯¯(g)

The justification for this comes from the fact that the set of irreducible characters spans the space of conjugation invariant functions and the orthogonality of these characters.

Second generalization: If f:G is any function on a group (not necessarily conjugation invariant), then we have the transform

f(x)=ki,j=1dkf,ρmnkρmnk(x)

where k and dk are as before and ρmnk are the matrix elements of the representation k. The justification for this comes from the fact that the set of matrix elements of representations spans the space of functions on the group and the orthogonality relation for matrix elements.

Remarks:DFT is also generalized by two-dimensional Fourier transforms (2D-FT), Fourier-Stieltjes transforms, and via groupoid representationPlanetmathPlanetmathPlanetmathPlanetmath to anharmonic analysis that can also be numerically computed by utilizing FFT, but tend tobe very much slower that the one-dimensional FFT because many series of sequential one-dimensional FFTs and also additional matrix transformations are involved in 2D-FT, or 2D-FFT.

References:Paul Bourke, http://astronomy.swin.edu.au/ pbourke/analysis/dft/”Discrete Fourier Transform”

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 11:06:23