Digital Signal Processing Reference
In-Depth Information
3.6 DF T-IDF T PAIR
3.6.1 DEFINITION-FORWARD TRANSFORM (TIME TO FREQUENCY )
The complex Discrete Fourier Transform (DFT) may be defined as:
N
−
1
X
[
k
]=
x
[
n
]
(
cos
[
2
πnk/N
]−
j
sin
[
2
πnk/N
]
)
(3.6)
n
=
0
or, using the complex exponential form,
N
−
1
e
−
j
2
πnk/N
X
[
k
]=
x
[
n
]
(3.7)
n
=
0
where
n
is the sample index (running from 0 to
N
−
1)ofan
N
point sequence
x
[
n
]
. Harmonic number
(also called mode, frequency, or bin) is indexed by
k
and runs from 0 to
N
−
1.
Using Eq. (3.7) results in computation by the
Direct Method
, as opposed to much more efficient
algorithms lumped under the umbrella term
FF T (Fast Fourier Transform)
.
3.6.2 DEFINITION-INVERSE TRANSFORM (FREQUENCY TO TIME)
If the DFT is defined as in Eq. (3.6), then the Inverse
Discrete Fourier Transform (IDF T)
is defined
as:
N
−
1
1
N
x
[
n
]=
X
[
k
]
(
cos
[
2
πkn/N
]+
j
sin
[
2
πnk/N
]
)
(3.8)
k
=
0
for
n
=
0 to
N
−
1, or, in complex exponential notation
N
−
1
1
N
e
j
2
πnk/N
x
[
n
]=
X
[
k
]
(3.9)
k
=
0
3.6.3 MAGNITUDE AND PHASE
Since DFT bins are, in general, complex numbers, the magnitude and phase are computed as for any
complex number, i.e.,
Re
(X
)
2
)
2
|
X
[
k
]| =
[
k
]
+
Im
(X
[
k
]
and
X
[
k
]=
arcTan
(
Im
(X
[
k
]
)/
Re
(X
[
k
]
))
3.6.4 N, SCALING CONSTANT, AND DF T VARIANTS
The definitions above are independent of whether
N
is even or odd. An alternate definition of the DFT
for
N
even makes the ranges of
n
and
k
run from
−
N/
2
+
1 to
N/
2. An alternate definition of the DFT
for
N
odd has the ranges of
n
and
k
running from
−
(N
−
1
)/
2 to
(N
−
1
)/
2.