EE120 - Fall’19 - Lecture 10 Notes1 1

Licensed under a Creative Commons

Attribution-NonCommercial-ShareAlike
Murat Arcak 4.0 International License.
1 October 2019

FIR Filter Design by Windowing

Ideal Low-Pass Filter: H (e jω )

1
... ...
ωc ω 
c
h[n] = sinc n ←→
π π −2π ωc 2π
To obtain a FIR filter truncate the ideal impulse response:
(
1 |n| ≤ N1
ĥ[n] = h[n]w[n], where w[n] =
0 otherwise.

What is the effect of truncation on the frequency response? From the

multiplication property of DTFT (Lecture 9):

1
Z
Ĥ (e jω ) = H (e jθ )W (e j(ω −θ ) )dθ (1)
2π 2π

and, from Lecture 8 (page 5), the DTFT of the rectangular window w
above is:
sin(ω ( N1 +1/2))
(
jω sin(ω/2)
ω 6= 0,
W (e ) =
2N1 + 1 ω = 0.
main lobe
2N 1 + 1
side lobes

2π 2π
2N 1 + 1

Gibbs Phenomenon and Tapered Windows

The periodic convolution (1) is depicted in the Figure 1 below. Figure

2 shows that Ĥ (e jω ) exhibits oscillations near the discontinuities of
H (e jω ) and their amplitudes do not decrease as N1 is increased. This
is known as the Gibbs Phenomenon.
These oscillations are caused by the sizable side lobes of W (e jω ) (high
frequency components) which are due to the abrupt change from 0 to
1 in the rectangular window function w above.
 ee120 - fall’19 - lecture 10 notes 2

Figure 1: The periodic convolution (1)

of the ideal low-pass filter response and
H (e jθ ) the DTFT of the rectangular window.

W (e j(ω −θ ))
%

Ĥ (e jω )
H (e jω ) %

Figure 2: The effect of increasing

N1 = 1 Ĥ (e jω ) N1 = 2 the window length. Ĥ (e jω ) exhibits
H (e jω ) oscillations near the discontinuities of
H (e jω ) and their amplitudes do not
decrease as N1 is increased. This is
known as the Gibbs Phenomenon.

ω ω
N1 = 3 N1 = 9

ω ω
 ee120 - fall’19 - lecture 10 notes 3

”Tapered” windows mitigate this problem, e.g., the triangular

(Bartlett) window:
|n|
(
1 − N if |n| ≤ N1
w[n] = 1
0 otherwise.
Other tapered windows exist (Hanning, Hamming, Blackman, etc.)
and are depicted in Figure 3. Although the differences between these
windows may not be appreciable in time domain, their Fourier Trans-
forms have significant differences as shown in Figure 4. Note the
tradeoff between main
| lobe
{z width} & side lobe amplitude in Figure 4.
| {z }
must be small for must be small to
sharp transition reduce ripples
from passband to
stopband

Figure 3: Tapered windows of type

1.2 Rectangular
Bartlett Bartlett, Hanning, Hamming, and
Hanning
Hamming Blackman for N1 = 25 superimposed.
Blackman

0.8

w[n]
0.6

0.4

0.2

0
-25 -20 -15 -10 -5 0 5 10 15 20 25
n

Summary: To obtain a FIR filter truncate the ideal filter’s impulse

response h[n] with one of the window functions w[n]:

ĥ[n] = h[n]w[n].

The new impulse response is zero outside of n ∈ {− N1 , · · · , N1 } but

not yet causal. To make it causal, shift to the right by N1 :

ĥ[n − N1 ] ←→ e− jωN1 Ĥ (e jω )

which does not change the magnitude of the frequency response,

only the phase. Finally, ĥ[n] must be scaled by a constant to obtain
∑n ĥ[n] = 1, so the dc gain is Ĥ (e j0 ) = 1.
FIR implementation:

y[n] = b0 x [n] + b1 x [n − 1] + ... + b M x [n − M ]

where b0 , ..., b M are the impulse response coefficients: bn = ĥ[n − N1 ].

 ee120 - fall’19 - lecture 10 notes 4

0
Figure 4: The magnitude of the Fourier
Transform W (e jω ) (in dB) for the rectan-
-10
20 log10 |W (e jω )|, rectangular gular, Bartlett, Hanning, Hamming, and
-20

-30
Blackman windows. Here each window
function in Figure 3 is scaled such that
-40
∑n w[n] = 1, so W (e j0 ) = 1 = 0 dB.
-50
dB Note that the tapered windows progres-
-60
sively reduce the side lobe amplitudes
-70
in the order they are presented. This
-80
has the desired effect of reducing rip-
-90
ples in the frequency response of the
-100
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
truncated filter. However, the main lobe
0
width increases which has a negative
-10
effect: the transition from passband to
Bartlett stopband will be slower for the filter
-20
truncated with the respective window.
-30

-40

dB -50

-60

-70

-80

-90

-100
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-10
Hanning
-20

-30

-40

dB -50

-60

-70

-80

-90

-100
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-10
Hamming
-20

-30

-40

dB -50

-60

-70

-80

-90

-100
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-10

-20
Blackman
-30

-40

dB -50

-60

-70

-80

-90

-100
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

normalized frequency (×π radians)

 ee120 - fall’19 - lecture 10 notes 5

Discrete Fourier Transform (DFT)

The DFT of a sequence x [n] with finite length, say N, is a sequence

X [k ] of the same length in the frequency domain:

N −1 2π
X [k] = ∑ x [n]e− j N kn k = 0, 1, . . . , N − 1 (2)
n =0

As a convention we represent the length-N sequences x [n] and X [k]

with indices n and k running from 0 to N − 1.

Connection to Discrete Fourier Series

If we define a period-N sequence x̃ [n] by adding x [n] end-to-end:

x̃ [n] := x [(n mod N )] (3)

then X [k] = Nak for k = 0, 1, . . . , N − 1:

Nak := X [(k mod N )]. (4)

Synthesis Equation for DFT:

N −1
1 2π
x [n] =
N ∑ X [k ]e j N kn n = 0, 1, . . . , N − 1 (5)
k =0

Example:

x [n]
1
n
0 1 2 3 4 5

Take N = 5 (5-point DFT):

4 2π
X [k] = ∑ e− j N kn , k = 0, 1, 2, 3, 4 (6)
n =0

5 if k = 0
= (7)
0 otherwise.
 ee120 - fall’19 - lecture 10 notes 6

To see why X [k] = 0 for, say k = 1, note that (6) is the sum of the
following complex numbers:

Im

n=1
n=2

Re
n=0
n=3
n=4

What if we take N = 10 (10-point DFT)?

X [k ] = 10ak , k = 0, 1, . . . , 9 where ak are FS coefficients of:

x̃ [n]
... 1 ... n
1 2 3 4 5 9 10

This is a rectangular pulse train similar to the one studied in Lecture

5 with N1 = 2, N = 10, except that the pulse is not centered at
n = 0, but at n = 2. To account for this time shift we multiply the
4π
kth Fourier Series coefficient in Lecture 5 with e− j 10 k (explain why).
Then,
2N1 + 1
X [0] = Na0 = N = 2N1 + 1 = 5
N

π
4π 1 sin( kπ (2N1 + 1) /N ) 4π sin
2 k

X [k ] = Nak = Ne− j 10 k = e− j 10 k
N sin(kπ/N ) sin π
10 k

for k = 1, . . . , 9. From the expression above we compute:

X [0] = 5, X [2] = X [4] = X [6] = X [8] = 0, X [1] = 1 − j3.0777,
X [3] = 1 − j0.7265, X [5] = 1, X [7] = 1 + j0.7265, X [9] = 1 + j3.0777.

Conjugate Symmetry Property of the DFT:

If x [n] is real, then

X ∗ [ N − k] = X [k] k = 1, 2, . . . , N − 1. (8)

This follows from the analogous property of Fourier Series coeffi-

cients.
Example: In the 10-point DFT above, X [1] = X ∗ [9], X [3] = X ∗ [7], . . . .
 ee120 - fall’19 - lecture 10 notes 7

Connection between DFT and DTFT

Recall:
∞ N −1
X (e jω ) = ∑ x [n]e− jωn = ∑ x [n]e− jωn (9)
n=−∞ n =0
N −1 2π
X [k] = ∑ x [n]e− j N kn , k = 0, 1, . . . , N − 1 (10)
n =0

N samples of DTFT at ω = 2π Nk
X [k] = X (e jω ) (11)
w= 2π
N k k = 0, 1, . . . , N − 1.

Note that (11) is valid only if the duration of x is ≤ N, because in (9)

we assumed x [n] = 0 when n ∈ / {0, 1, . . . , N − 1}.
Back to the example:
(
4 5 ω=0
jω
X (e ) = ∑e − jωn
= sin(5ω/2)
e− j2ω sin(ω/2) ω 6= 0
(12)
n =0

| X (e jω )| 10 point DFT
5 point DFT
5

ω
2π 4π 6π 8π 2π
5 5 5 5

DFT Makes Convolution Easy

y[n] = h[n] ∗ x [n] (13)

|{z} |{z}
FIR with input sequence
duration = P with duration = L

Set N ≥ L + P − 1 (duration of y). Pad zeros in h and x to make them

duration = N. Take their N-point DFT to find H [k] and X [k]. Take
inverse DFT of H [k] X [k ] to obtain y[n].