Digital Signal Processing Reference
In-Depth Information
2.4.1.1 Approximation of the FT Using DFT
The DFT can be used to approximate the original (continuous-time) FT. The
quality of the approximation depends largely on the sampling rate used in the time
domain. As long as the time domain sampling rate is greater than the highest
frequency present in the original analog signal, and the frequency domain sam-
pling rate is F
s
= f
s
/N, the approximation is perfect.
The effectiveness of the DFT for approximating the Fourier Transform derives
from the fact that the DFT is simply a sampled version of the DTFT, which is in
turn a scaled and periodic version of the FT (see
Sect. 2.3.2.2
).
2.4.1.2 Relationship Between the DFT and the DFS Coefficients
A simple comparison between the DFS of a periodic sequence (with period N) and
the DFT of one period of this sequence reveals that the two related by a simple
multiplicative constant:
X
k
;
DFS
¼
X
k
;
DFT
=
N
;
ð
2
:
17
Þ
where X
k,DFS
is the pertinent DFS coefficient and X
k,DFT
is the corresponding DFT
sample. This is reminiscent of a similar relation in the analog domain, where the
FS coefficients of a periodic signal (of period =T
o
) are related to the FT of a single
period of the same signal according to:
X
k
¼
X
1p
ð
f
Þ=
T
o
j
f
¼
kf
o
;
ð
2
:
18
Þ
where X
k
is the pertinent FS coefficient DFS and X
1p
ð
f
Þj
f
¼
kf
o
is the corresponding
FT value.
2.4.1.3 The Fast Fourier Transform
Calculation of the Discrete-Fourier Transform directly according to the definition
in (2.15) requires of the order of N
2
computations, i.e, it requires O(N
2
) arithmetic
operations. These calculations cannot normally be done in real-time, as is required
for many practical applications. For this reason many scientists and engineers have
sought alternative techniques for rapidly calculating the DFT. The first to devise an
efficient algorithm was probably Gauss, but his work went largely un-noticed until
about 1990. In 1965, however, the so-called Fast Fourier Transform (FFT) was re-
invented and popularized. [see J. W. Cooley and J. W. Tukey, ''An algorithm for
the machine calculation of complex Fourier series,'' Mathematics of Computation,
vol. 19, pp. 297-301, 1965]. In contrast to calculation via the direct definition, the
FFT algorithm can be implemented in O(N log(N)) operations. This algorithm
provided not only economy of time in run-time operation, but also economy of
computational and storage elements in hardware for DFT implementation.
Search WWH ::
Custom Search