Returning to the issue of how to use the DFT to perform
filtering, we can analytically specify the frequency response,
and derive the corresponding
length-NN DFT by sampling the
frequency response.
∀k,k∈0…N-1:Hk=Hⅇⅈ2πkN
k
k
0
…
N
1
H
k
H
2
k
N
(1)
Computing the inverse DFT yields a
length-
NN signal
no
matter what the actual duration of the unit-sample response
might be. If the unit-sample response has a duration
less than or equal to
NN (it's a
FIR filter), computing the inverse DFT of the sampled frequency
response indeed yields the unit-sample response. If, however,
the duration exceeds
NN , errors
are encountered. The nature of these errors is easily explained
by appealing to the Sampling Theorem. By sampling in the
frequency domain, we have the potential for aliasing in the time
domain (sampling in one domain, be it time or frequency, can
result in aliasing in the other) unless we sample fast
enough. Here, the duration of the unit-sample response
determines the minimal sampling rate that prevents aliasing. For
FIR systems — they by definition have finite-duration unit
sample responses — the number of required DFT samples
equals the unit-sample response's duration:
N≥q
N
q
.
Derive the minimal DFT length for a
length-qq unit-sample response
using the Sampling Theorem. Because sampling in the
frequency domain causes repetitions of the unit-sample
response in the time domain, sketch the time-domain result
for various choices of the DFT length
NN.
In sampling a discrete-time signal's Fourier transform
LL times equally over
02π
0
2
to form the DFT, the corresponding signal equals the periodic
repetition of the original signal.
Sk↔∑i=-∞∞sn-iL
↔
S
k
i
s
n
i
L
(2)
To avoid aliasing (in the time domain), the transform length
must equal or exceed the signal's duration.
Express the unit-sample response of a FIR filter in terms of
difference equation coefficients. Note that the
corresponding question for IIR filters is far more difficult
to answer: Consider this example.
The difference equation for an FIR filter has the form
yn=∑m=0q
b
m
xn-m
y
n
m
0
q
b
m
x
n
m
(3)
The unit-sample response equals
hn=∑m=0q
b
m
δn-m
h
n
m
0
q
b
m
δ
n
m
(4)
which corresponds to the representation described in
a problem
of a length
q+1
q
1
For IIR systems, we cannot use the DFT to find the system's
unit-sample response: aliasing of the unit-sample response will
always occur. Consequently, we can only
implement an IIR filter accurately in the time domain with the
system's difference equation. Frequency-domain implementations
are restricted to FIR filters.
Another issue arises in frequency-domain filtering that is
related to time-domain aliasing, this time when we consider the
output. Assume we have an input signal having duration
N
x
N
x
that we pass through a FIR filter having a length-
q+1
q
1
unit-sample response. What is the duration of the output
signal? The difference equation for this filter is
yn=
b
0
xn+…+
b
q
xn-q
y
n
b
0
x
n
…
b
q
x
n
q
(5)
This equation says that the output depends on current and past
input values, with the input value
qq samples previous defining the
extent of the filter's
memoryof past input
values. For example, the output at index
N
x
N
x
depends on
x
N
x
x
N
x
(which equals zero),
x
N
x
-1
x
N
x
1
, through
x
N
x
-q
x
N
x
q
. Thus, the output returns to zero only after the last input
value passes through the filter's memory. As the input signal's
last value occurs at index
N
x
-1
N
x
1
, the last nonzero output value occurs when
n-q=
N
x
-1
n
q
N
x
1
or
nq+
N
x
-1
n
q
N
x
1
. Thus, the output signal's duration equals
q+
N
x
q
N
x
.
In words, we express this result as "The output's duration
equals the input's duration plus the filter's duration minus
one." Demonstrate the accuracy of this statement.
The unit-sample response's duration is
q+1
q
1
and the signal's
N
x
N
x
. Thus the statement is correct.
The main theme of this result is that a filter's output extends
longer than either its input or its unit-sample response. Thus,
to avoid aliasing when we use DFTs, the dominant factor is not
the duration of input or of the unit-sample response, but of the
output. Thus, the number of values at which we must evaluate the
frequency response's DFT must be at least
q+
N
x
q
N
x
and we must compute the same length DFT of the input. To
accommodate a shorter signal than DFT length, we simply
zero-pad the input: Ensure that for indices
extending beyond the signal's duration that the signal is
zero. Frequency-domain filtering, diagrammed in Figure 1, is accomplished by storing the
filter's frequency response as the DFT
Hk
H
k
, computing the input's DFT
Xk
X
k
, multiplying them to create the output's DFT
Yk=HkXk
Y
k
H
k
X
k
, and computing the inverse DFT of the result to yield
yn
y
n
.
