|
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,
|
