117
C H A P T E R 8
Frequency Domain Transforms
Frequency domain transforms are extensively used in signal processing applications. In this
chapter, the Discrete Fourier Transform (DFT) and the Fast Fourier Transform (FFT), which
is the computationally efficient version of the DFT, are covered.
8.1 FOURIER TRANSFORMS
e Fourier transform pair for discrete aperiodic signals is given by:
Fourier transform pairs for
discrete signals
8
ˆ
ˆ
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
ˆ
ˆ
:
X.e
j
/ D
1
X
nD1
xŒne
j n
; D !T
s
xŒn D
1
2
Z
X.e
j
/e
j n
d:
(8.1)
ese two equations allow the transformation of signals from the time to the frequency and
from the frequency back to the time domain.
8.1.1 DISCRETE FOURIER TRANSFORM
Fourier transform of discrete signals is continuous over the frequency range 0 f
s
=2. us, from
the viewpoint of programming, this transform is difficult to implement due to the integration
involved. In practice, DFT is used in place of Fourier transform. DFT is the equivalent of
Fourier series in the analog domain. However, it should be noted that DFT and Fourier series
pairs are defined for periodic signals. ese transform pairs are expressed as:
118 8. FREQUENCY DOMAIN TRANSFORMS
Fourier series for periodic
analog signals
8
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
:
X
k
D
1
T
T =2
Z
T =2
x.t /e
j!
0
kt
dt
x.t/ D
1
X
kD1
X
k
e
j!
0
kt
where T denotes period and
!
0
fundamental frequency:
(8.2)
Discrete Fourier transform
(DFT) for periodic
discrete signals
8
ˆ
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
ˆ
:
XŒk D
N 1
X
nD0
xŒne
j
2
N
nk
; k D 0; 1; : : : ; N 1
xŒn D
1
N
N 1
X
kD0
XŒke
j
2
N
nk
; n D 0; 1; : : : ; N 1:
(8.3)
e equation describing the DFT transformation can be written as:
XŒk D
N 1
X
nD0
xŒn W
nk
N
; k D 0; 1; : : : ; N 1; (8.4)
where W
N
D e
j 2=N
. To compute each term, N complex multiplications and N 1 complex
additions are required. For a frame consisting of N input samples, N
2
complex multiplications
and N
2
N complex additions are thus required. It is easy to see that this method is computa-
tionally inefficient, in particular when N increases. Here is a typical DFT code in C that appears
in [1]:
void DFT(Complex* data) {
int i, j;
int N = data->N;
float arg, wI, wR;
float sumXr[N];
float sumXi[N];
for (i=0; i<N; i++) {
sumXr[i] = 0.0f;
sumXi[i] = 0.0f;
for(j=0; j<N; j++) {
arg = 2*PI*i*j/N;
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.