| 1 |
Let f be in 1D a typical function defined on a grid and labeled with index m= 0 ... N-1
|
| 2 |
Let i = sqrt(-1) and index matrices and vectors from 0.
|
| 3 |
The Discrete Fourier Transform G(f) of an N-element vector f is another vector of length N given by Matrix Vector Multiplication ? f
|
| 4 |
Where ? is the N*N matrix with matrix elements:
|
| 5 |
?km = v (-k*m)
|
| 6 |
and v is:
|
| 7 |
v = e (2pi/N) = cos(2p/N) + i*sin(2p/N)
|
| 8 |
This is a complex number with whose Nth power is 1 and is therefore called the Nth root of unity
|
| 9 |
E.g., for N = 4:
|
| 10 |
v = 0+1*i, v2 = -1+0*i, v3 = 0-1*i, v4 = 1+0*i,
|
