Let N be a positive integer (for
convenience, N is often a power of 2).
Let w
be a primitive N-th root of unity, like
w = exp ( - 2pi / N ). We have:
|
wN = 1
( and
wk = 1
<=>
N | k )
0 = |
N-1 |
w k |
| å |
| k = 0 |
Two sequences of N complex numbers
(X0 ... XN-1 ) and
(Y0 ... YN-1 )
are Fourier transforms of each other when
the following relation holds:
Discrete
Fourier Transform (as a unitary involution)
|
Ym = |
|
[ |
N-1 |
w km
X k ]* |
| å |
| k = 0 |
|
This definition may not be the simplest one
(see below) but it's
arguably the best theoretical one...
The DFT so defined is an involution
(i.e., it's its own inverse):
|
Xm = |
|
[ |
N-1 |
w km
Yk ]* |
| å |
| k = 0 |
It is also unitary. The counterpart of
Parseval's Theorem is coefficient-free:
å | Yk |2
=
å | X k |2
One popular competing way to define the DFT retains only the square bracket
and forgoes the overall coefficient and the complex conjugation.
This yields a bare finite Fourier transform
(BFFT or barefoot ) which is neither
unitary nor involutive but can be simpler to compute
(especially in a recursive context):
|
Z m = |
N-1 |
w km
X k |
| å |
| k = 0 |
