Digital Signal Processing Reference
In-Depth Information
domain representation. We will use the convention “x
i
”to
represent the time-domain version of the signal, and “X
k
”to
represent the frequency-domain representation of the signal.
Both indexes i and k will run from 0 to N
1.
12.1 DFT and IDFT Equations
DFT (time
frequency)
/
N
Þ¼
X
N
1
i
¼
0
x
k
e
j2
p
ki
=
N
X
k
¼ Hð
2
p
k
=
for k
¼f
0
::
N
1
g
IDFT (frequency
time)
/
N
X
N
1
k
¼
0
X
k
e
þ
j2
p
ki
=
N
X
i
¼
1
=
for i
¼f
0
::
N
1
g
These equations do appear very similar. The differences are
the negative sign on the exponent on the DFT equation, and the
factor of 1 / N on the IDFT equation. The DFT equation requires
that every single sample in the frequency domain has a contri-
bution from each and every one of the time domain samples. And
the IDFT equation requires that every single sample in the time
domain has a contribution from each and every one of the
frequency domain samples. To compute a single sample of either
transform requires N complex multiplies and additions. To
compute the entire transform will require computing N samples,
for a total of N
2
multiplies and additions. This can become
a computational problem when N becomes large. As we will see
later, this is the reason the FFT and IFFT were developed.
The values of X
k
represent the amount of signal energy at each
frequency point. Imagine taking a spectrum of 1 MHz which we
divide into N bins. If N
¼
20, then we will have 20 frequency bins,
each 50 kHz wide. The DFT output, X
k
, will represent the signal
energy in each of these bins. For example, X
0
will represent
the signal energy at 0 kHz, or the DC component of the signal.
X
1
will represent the frequency content of the signal at 50 kHz. X
2
will represent the frequency content of the signal at 100 kHz. X
19
will represent the frequency content of the signal at 950 kHz.
A few comments on these transforms might prove helpful.
Firstly, they are reversible. We can take a signal represented by N
samples, and perform the DFT on it. We will get N outputs rep-
resenting the frequency response or spectrum on the signal. If we
take this frequency response and perform the IDFT on it, we will
get back our original signal of N samples back. Secondly, when
the DFT output gives the frequency content of the input signal, it
is assuming that the input signal is periodic in N. To put it another
