Digital Signal Processing Reference
In-Depth Information
M
M
M
order
using 2 ×
additions and 2 ×
multiplications, that is
M
additions
4
2
2
and
M
multiplications. This process can be iterated log
2
M
times, until the
calculation of
M
discrete Fourier transforms of the 1
st
order, which requires no
operations. Finally, this calculation thus requires
M
log
2
M
additions and
M
log
2
M
multiplications.
If the fact that
M
is a power of 2 seems very restrictive, it is possible to develop
the FFT algorithms in the case where
M
can be factorized in the form of a product of
integer numbers
M = M
1
M
2
,…M
p
.
Thus we are talking of algorithms in a multiple
base, which require
(
)
(
)
O
MM
++
"
M
operations [BRI 74].
1
p
These fast algorithms require the calculation of the discrete Fourier transform in
its entirety. It is often preferable to return to a direct calculation if we do not need to
calculate this transform only in low frequencies known
a priori.
2.3. Windows
Consider a continuous time signal
x
(
t
)
with an unlimited support which we
recorded during the time interval [0,
T
]
.
Thus it is natural to approximate its Fourier
transform
()
x
f
, that is:
+∞
=
∫
()
2
−
j
π
f t
()
x
ˆ
f
x t e
dt
−∞
by the finite integral:
T
∫
()
−
j
2
π
f t
x te
dt
0
This amounts to approximating
()
x
by the Fourier transform of the signal
x
(
t
)
f
, Let us observe
l
()
()
multiplied by the rectangular window
1
x f
the result
of this approximation in the case where the signal
x
(
t
)
is a cisoid of frequency
f
0
,
,
amplitude
a
and initial phase
φ
:
0
1
T
t
0,
(
)
j
2
πφ
f t
+
()
()
j
φ
δ
(
)
x t
=
e
0
xv
ˆ
=
e
f
−
f
0
The product is transformed by the Fourier transform into a convolution sum.
This convolution along with the Dirac delta function shifted to
F
0
thus shifts the
Fourier transform of the window to
f
0
. We thus obtain:
Search WWH ::
Custom Search