Discrete Fourier Transform

• Let f be in 1D a typical function defined on a grid and labeled with index m= 0 … N-1

• Let i = sqrt(-1) and index matrices and vectors from 0.

• The Discrete Fourier Transform G(f) of an N-element vector f is another vector of length N given by Matrix Vector Multiplication ? f

• Where ? is the N*N matrix with matrix elements:

• ?km = v (-k*m)

• and v is:

• v = e (2pi/N) = cos(2p/N) + i*sin(2p/N)

• This is a complex number with whose Nth power is 1 and is therefore called the Nth root of unity

• E.g., for N = 4:

• v = 0+1*i, v2 = -1+0*i, v3 = 0-1*i, v4 = 1+0*i,

Previous slide

Next slide

Back to first slide

View graphic version