There are two types of linear, time-invariant digital filters. We will
investigate digital filters with a finite-duration impulse response
(FIR) in this section and those with an infinite-duration impulse
response (IIR) in another document. FIR filters have characteristics
that make them useful in many applications [3], [2].
- FIR filters can achieve an exactly linear phase frequency response
- FIR filters cannot be unstable.
- FIR filters are generally less
sensitive to coefficient round-off and finite-precision arithmetic than
IIR filters.
- FIR filters design methods are generally linear.
- FIR filters can be efficiently realized on general or special-purpose
hardware.
However, frequency responses that need a rapid transition
between bands and do not require linear phase are often more efficiently
realized with IIR filters.
It is the purpose of this section to examine and
evaluate these characteristics which are important in the design
of the four basic types of linear-phase FIR filters.
Because of the usual methods of implementation, the Finite Impulse
Response (FIR) filter is also called a nonrecursive filter or
a convolution filter. From the time-domain view of this operation,
the FIR filter is sometimes called a moving-average or running-average filter. All of these names represent useful
interpretations that are discussed in this section; however, the
name, FIR, is most commonly seen in filter-design literature and is
used in these notes.
The duration or sequence length of the impulse response of
these filters is by definition finite; therefore, the output can
be written as a finite convolution sum by
y
(
n
)
=
∑
m
=
0
N
-
1
h
(
m
)
x
(
n
-
m
)
y
(
n
)
=
∑
m
=
0
N
-
1
h
(
m
)
x
(
n
-
m
)
(1)
where nn and mm are integers, perhaps representing samples in time,
and where x(n)x(n) is the input sequence, y(n)y(n) the output sequence,
and h(n)h(n) is the length-N impulse response of the filter.
With a change of index variables, this can also be written as
y
(
n
)
=
∑
m
=
n
n
-
N
+
1
h
(
n
-
m
)
x
(
m
)
.
y
(
n
)
=
∑
m
=
n
n
-
N
+
1
h
(
n
-
m
)
x
(
m
)
.
(2)
If the FIR filter is interpreted as an extension of a
moving sum or as a weighted moving average, some of its properties
can easily be seen. If one has a
sequence of numbers, e.g., prices from the daily stock market
for a particular stock, and would like to remove the erratic
variations in order to discover longer term trends, each number could
be replaced by the average of itself and the preceding three
numbers, i.e., the variations within a four-day period would be
“averaged out" while the longer-term variations would remain. To
illustrate how this happens, consider an artificial signal
x(n)x(n) containing a linear term, K1nK1n, and an undesired oscillating
term added to it, such that
x
(
n
)
=
K
1
n
+
K
2
cos
(
π
n
)
x
(
n
)
=
K
1
n
+
K
2
cos
(
π
n
)
(3)
If a length-2 averaging filter is used with
h
(
n
)
=
1
/
2
for
n
=
0
,
1
0
otherwise
h
(
n
)
=
1
/
2
for
n
=
0
,
1
0
otherwise
(4)
it can be verified that, after two outputs, the output y(n)y(n) is
exactly the linear term x(n)x(n) with a delay of one half sample interval
and no oscillation.
This example illustrates the basic FIR filter-design
problem: determine N, the number of terms for h(n)h(n), and the
values of h(n)h(n) for achieving a desired effect on the signal.
The reader should examine simple examples to obtain an intuitive idea
of the FIR filter as a moving average; however, this simple
time-domain interpretation
will not suffice for complicated problems where the concept of
frequency becomes more valuable.
The output of a length-N FIR filter can be calculated from the input using
convolution.
y
(
n
)
=
∑
k
=
0
N
-
1
h
(
k
)
x
(
n
-
k
)
y
(
n
)
=
∑
k
=
0
N
-
1
h
(
k
)
x
(
n
-
k
)
(5)
and the transfer function of an FIR filter is given by the z-transform
of the finite length impulse response h(n)h(n) as
H
(
z
)
=
∑
n
=
0
N
-
1
h
(
n
)
z
-
n
.
H
(
z
)
=
∑
n
=
0
N
-
1
h
(
n
)
z
-
n
.
(6)
The frequency response of a filter, is found by setting
z=ejωz=ejω, which is the same as the discrete-time Fourier
transform (DTFT) of h(n)h(n),
which gives
H
(
ω
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
ω
n
H
(
ω
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
ω
n
(7)
with ωω being frequency in radians per second.
Strictly speaking, the exponent should be -jωTn-jωTn where TT is the
time interval between the integer steps of nn (the sampling interval).
But to simplify notation, it will be assumed that T=1T=1 until later in the
notes where the relation between nn and time is more important. Also to
simplify notation, H(ω)H(ω) is used to represent the frequency response
rather that H(ejω)H(ejω). It should always be clear from the context
whether HH is a function of zz or ωω.
This frequency-response function is complex-valued and
consists of a magnitude and a phase. Even though the impulse
response is a function of the discrete variable nn, the
frequency response is a function of the continuous-frequency
variable ωω and is periodic with period 2π2π. This periodicity is
easily shown by
H
(
w
+
2
π
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
(
w
+
2
π
)
n
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
ω
n
e
-
j
2
π
n
=
H
(
ω
)
H
(
w
+
2
π
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
(
w
+
2
π
)
n
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
ω
n
e
-
j
2
π
n
=
H
(
ω
)
(8)
with frequency denoted by ωω in radians per second or by ff in Hz
(hertz or cycles per second). These are related by
ω
=
2
π
f
ω
=
2
π
f
(9)
An example of a length-5 filter might be
h
(
n
)
=
2
,
3
,
4
,
3
,
2
h
(
n
)
=
2
,
3
,
4
,
3
,
2
(10)
with a frequency-response plot shown over the base
frequency band (0<ω<π0<ω<π or 0<f<10<f<1 in Figure 1.
To illustrate the periodic nature of the total frequency response,
Figure 2 shows the response over a wider set of frequencies.
The Discrete Fourier Transform (DFT) can be used to evaluate the
frequency response at certain frequencies. The DFT [1] of the
length-N impulse response h(n)h(n) is defined as
C
(
k
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
2
π
n
k
/
N
k
=
0
,
1
,
.
.
.
,
N
-
1
C
(
k
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
2
π
n
k
/
N
k
=
0
,
1
,
.
.
.
,
N
-
1
(11)
which, when compared to (Equation 7), gives
C
(
k
)
=
H
(
ω
k
)
=
H
(
2
π
k
/
N
)
k
=
0
,
1
,
.
.
.
,
N
-
1
C
(
k
)
=
H
(
ω
k
)
=
H
(
2
π
k
/
N
)
k
=
0
,
1
,
.
.
.
,
N
-
1
(12)
for ωk=2πk/Nωk=2πk/N.
This states that the DFT of h(n)h(n) gives NN samples of the
frequency-response function H(ω)H(ω). This sampling at NN points
may not give enough detail, and, therefore, more samples are
needed. Any number of equally spaced samples can be found with
the DFT by simply appending L-NL-N zeros to h(n)h(n) and taking an
L-length DFT. This is often useful when an accurate picture of
all of H(ω)H(ω) is required. Indeed, when the number of appended
zeros goes to infinity, the DFT becomes the discrete-time Fourier transform of
h(n)h(n).
The fact that the DFT of h(n)h(n) is a set of NN samples of the
frequency response suggests a method of designing FIR filters in
which the inverse DFT of NN samples of a desired frequency
response gives the filter coefficients h(n)h(n). That approach is
called frequency sampling and is developed in another section.
A particular property of FIR filters that has proven to be very powerful
is that a linear phase shift for the frequency response is possible. This
is especially important to time domain details of a signal. The spectrum
of a signal contains the individual frequency domain components separated
in frequency. The process of filtering usually involves passing some of
these components and rejecting others. This is done by multiplying the
desired ones by one and the undesired ones by zero. When they are
recombined, it is important that the components have the same time domain
alignment as they originally did. That is exactly what linear phase
insures. A phase response that is linear with frequency keeps all of the
frequency components properly registered with each other. That is
especially important in seismic, radar, and sonar signal analysis as well
as for many medical signals where the relative time locations of events
contains the information of interest.
To develop the theory for linear phase FIR filters, a careful definition
of phase shift is necessary. If the real and imaginary parts of
H(ω)H(ω) are given by
H
(
ω
)
=
R
(
ω
)
+
j
I
(
ω
)
H
(
ω
)
=
R
(
ω
)
+
j
I
(
ω
)
(13)
where j=-1j=-1 and the magnitude is defined
by
|
H
(
ω
)
|
=
R
2
+
I
2
|
H
(
ω
)
|
=
R
2
+
I
2
(14)
and the phase by
Φ
(
ω
)
=
arctan
(
I
/
R
)
Φ
(
ω
)
=
arctan
(
I
/
R
)
(15)
which gives
H
(
ω
)
=
|
H
(
ω
)
|
e
j
Φ
(
ω
)
H
(
ω
)
=
|
H
(
ω
)
|
e
j
Φ
(
ω
)
(16)
in terms of the magnitude and phase. Using the real and imaginary parts is
using a rectangular coordinate system and using the magnitude and phase is
using a polar coordinate system. Often, the polar system is easier to
interpret.
Mathematical problems arise from using |H(ω)||H(ω)| and Φ(ω)Φ(ω),
because |H(ω)||H(ω)| is not analytic and Φ(ω)Φ(ω) not continuous.
This problem is solved by introducing an amplitude function A(ω)A(ω)
that is real valued and may be positive or negative. The frequency
response is written as
H
(
ω
)
=
A
(
ω
)
e
j
Θ
(
ω
)
H
(
ω
)
=
A
(
ω
)
e
j
Θ
(
ω
)
(17)
where A(ω)A(ω) is called the amplitude in order to
distinguish it from the magnitude |H(ω)||H(ω)|, and Θ(ω)Θ(ω) is
the continuous version of Φ(ω)Φ(ω). A(ω)A(ω) is a real, analytic
function that is related to the magnitude by
A
(
ω
)
=
±
|
H
(
ω
)
|
A
(
ω
)
=
±
|
H
(
ω
)
|
(18)
or
|
A
(
ω
)
|
=
|
H
(
ω
)
|
|
A
(
ω
)
|
=
|
H
(
ω
)
|
(19)
With this definition, A(ω)A(ω) can be made analytic and
Θ(ω)Θ(ω) continuous. These are much easier to work with than
|H(ω)||H(ω)| and Φ(ω)Φ(ω). The relationship of A(ω)A(ω) and
|H(ω)||H(ω)|, and of Θ(ω)Θ(ω) and Φ(ω)Φ(ω) are shown in
Figure 3.
To develop the characteristics and properties of linear-phase
filters, assume a general linear plus constant form for the phase
function as
Θ
(
ω
)
=
K
1
+
K
2
ω
Θ
(
ω
)
=
K
1
+
K
2
ω
(20)
This gives the frequency response function of a length-N FIR
filter as
H
(
ω
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
ω
n
=
e
-
j
ω
M
∑
n
=
0
N
-
1
h
(
n
)
e
j
ω
(
M
-
n
)
H
(
ω
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
ω
n
=
e
-
j
ω
M
∑
n
=
0
N
-
1
h
(
n
)
e
j
ω
(
M
-
n
)
(21)
and
H
(
ω
)
=
e
-
j
ω
M
[
h
0
e
j
ω
M
+
h
1
e
j
ω
(
M
-
1
)
+
⋯
+
h
N
-
1
e
j
ω
(
M
-
N
+
1
)
]
H
(
ω
)
=
e
-
j
ω
M
[
h
0
e
j
ω
M
+
h
1
e
j
ω
(
M
-
1
)
+
⋯
+
h
N
-
1
e
j
ω
(
M
-
N
+
1
)
]
(22)
Equation 22 can be put in the form of
H
(
ω
)
=
A
(
ω
)
e
j
(
K
1
+
K
2
ω
)
H
(
ω
)
=
A
(
ω
)
e
j
(
K
1
+
K
2
ω
)
(23)
if MM (not necessarily an integer) is defined by
M
=
N
-
1
2
M
=
N
-
1
2
(24)
or equivalently,
M
=
N
-
M
-
1
M
=
N
-
M
-
1
(25)
Equation 22 then becomes
H
(
ω
)
=
e
-
j
ω
M
[
(
h
0
+
h
N
-
1
)
cos
(
ω
M
)
+
j
(
h
0
-
h
N
-
1
)
sin
(
ω
M
)
+
(
h
1
+
h
N
-
2
)
cos
(
ω
(
M
-
1
)
)
+
j
(
h
1
-
h
N
-
2
)
sin
(
w
(
M
-
1
)
)
+
⋯
]
H
(
ω
)
=
e
-
j
ω
M
[
(
h
0
+
h
N
-
1
)
cos
(
ω
M
)
+
j
(
h
0
-
h
N
-
1
)
sin
(
ω
M
)
+
(
h
1
+
h
N
-
2
)
cos
(
ω
(
M
-
1
)
)
+
j
(
h
1
-
h
N
-
2
)
sin
(
w
(
M
-
1
)
)
+
⋯
]
(26)
There are two possibilities for putting this in the form of
(Equation 23) where A(ω)A(ω) is real: K1=0K1=0 or K1=π/2K1=π/2. The first case
requires a special even symmetry in h(n)h(n) of the form
h
(
n
)
=
h
(
N
-
n
-
1
)
h
(
n
)
=
h
(
N
-
n
-
1
)
(27)
which gives
H
(
ω
)
=
A
(
ω
)
e
-
j
M
ω
H
(
ω
)
=
A
(
ω
)
e
-
j
M
ω
(28)
where A(ω)A(ω) is the amplitude, a real-valued function of ωω and
e-jMωe-jMω gives the linear phase with MM being the group delay.
For the case where NN is odd, using
(Equation 26), (Equation 27), and (Equation 28), we have
A
(
ω
)
=
∑
n
=
0
M
-
1
2
h
(
n
)
cos
ω
(
M
-
n
)
+
h
(
M
)
A
(
ω
)
=
∑
n
=
0
M
-
1
2
h
(
n
)
cos
ω
(
M
-
n
)
+
h
(
M
)
(29)
or with a change of variables,
A
(
ω
)
=
∑
n
=
1
M
2
h
(
M
-
n
)
cos
(
ω
n
)
+
h
(
M
)
A
(
ω
)
=
∑
n
=
1
M
2
h
(
M
-
n
)
cos
(
ω
n
)
+
h
(
M
)
(30)
which becomes
A
(
ω
)
=
∑
n
=
1
M
2
h
^
(
n
)
cos
(
ω
n
)
+
h
(
M
)
A
(
ω
)
=
∑
n
=
1
M
2
h
^
(
n
)
cos
(
ω
n
)
+
h
(
M
)
(31)
where h^(n)=h(M-n)h^(n)=h(M-n) is a shifted h(n)h(n).
These formulas can be made simpler by defining new coefficients so that
(Equation 29) becomes
A
(
ω
)
=
∑
n
=
0
M
a
(
n
)
cos
(
ω
(
M
-
n
)
)
A
(
ω
)
=
∑
n
=
0
M
a
(
n
)
cos
(
ω
(
M
-
n
)
)
(32)
where
a
(
n
)
=
{
h(M)
0
2h(n)
for n = M
otherwise
for
0
≤
n
≤
M
-
1
a(n)={
h(M)
0
2h(n)
for n = M
otherwise
for
0
n
M
-
1
(33)
and Equation 31 becomes
A
(
ω
)
=
∑
n
=
0
M
a
(
n
)
cos
(
ω
n
)
A
(
ω
)
=
∑
n
=
0
M
a
(
n
)
cos
(
ω
n
)
(34)
with
a
(
n
)
=
{
2h(M+n)
0
h(M)
for
0
≤
n
≤
M
-
1
otherwise
for
n
=
0
a(n)={
2h(M+n)
0
h(M)
for
0
n
M
-
1
otherwise
for
n
=
0
(35)
Notice from (Equation 34) for NN odd, A(ω)A(ω) is an even function around
ω=0ω=0 and ω=πω=π, and is periodic with period 2π2π.
For the case where NN is even,
A
(
ω
)
=
∑
n
=
0
N
/
2
-
1
2
h
(
n
)
cos
ω
(
M
-
n
)
A
(
ω
)
=
∑
n
=
0
N
/
2
-
1
2
h
(
n
)
cos
ω
(
M
-
n
)
(36)
or with a change of variables,
A
(
ω
)
=
∑
n
=
1
N
/
2
2
h
(
N
/
2
-
n
)
cos
ω
(
n
-
1
/
2
)
A
(
ω
)
=
∑
n
=
1
N
/
2
2
h
(
N
/
2
-
n
)
cos
ω
(
n
-
1
/
2
)
(37)
These formulas can also be made simpler by defining new coefficients so that
(Equation 36) becomes
A
(
ω
)
=
∑
n
=
0
N
/
2
-
1
a
(
n
)
cos
(
ω
(
M
-
n
)
)
A
(
ω
)
=
∑
n
=
0
N
/
2
-
1
a
(
n
)
cos
(
ω
(
M
-
n
)
)
(38)
where
a
(
n
)
=
{
0 otherwise
2
h
(
n
)
for
0
≤
n
≤
N
/
2
-
1
a(n)=
{
0 otherwise
2
h
(
n
)
for
0
n
N
/
2
-
1
(39)
and (Equation 37) becomes
A
(
ω
)
=
∑
n
=
1
N
/
2
a
(
n
)
cos
(
ω
(
n
-
1
/
2
)
)
A
(
ω
)
=
∑
n
=
1
N
/
2
a
(
n
)
cos
(
ω
(
n
-
1
/
2
)
)
(40)
with
a
(
n
)
=
{
0 otherwise
2
h
(
N
/
2
-
n
)
for
1
≤
n
≤
N
/
2
a(n)=
{
0 otherwise
2
h
(
N
/
2
-
n
)
for
1
≤
n
≤
N
/
2
(41)
Notice from Equation 40 for NN even, A(ω)A(ω) is an even function around ω=0ω=0, an odd function around ω=πω=π, and is periodic with period 4π4π. This requires A(π)=0A(π)=0.
For the case in (Equation 23) where K1=π/2K1=π/2, an odd symmetry is
required of the form
h
(
n
)
=
-
h
(
N
-
n
-
1
)
h
(
n
)
=
-
h
(
N
-
n
-
1
)
(42)
which, for NN odd, gives
H
(
ω
)
=
j
A
(
ω
)
e
j
M
ω
H
(
ω
)
=
j
A
(
ω
)
e
j
M
ω
(43)
with
A
(
ω
)
=
∑
n
=
0
M
-
1
2
h
(
n
)
sin
ω
(
M
-
n
)
A
(
ω
)
=
∑
n
=
0
M
-
1
2
h
(
n
)
sin
ω
(
M
-
n
)
(44)
and for NN even
A
(
ω
)
=
∑
n
=
0
N
/
2
-
1
2
h
(
n
)
sin
ω
(
M
-
n
)
A
(
ω
)
=
∑
n
=
0
N
/
2
-
1
2
h
(
n
)
sin
ω
(
M
-
n
)
(45)
To calculate the frequency or amplitude response numerically, one must
consider samples of the continuous frequency response function above.
LL samples of the general complex frequency response H(ω)H(ω) in
Equation 21 are calculated from
H
(
ω
k
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
ω
k
n
.
H
(
ω
k
)
=
∑
n
=
0
N
-
1
h
(
n
)
e
-
j
ω
k
n
.
(46)
for k=0,1,2,⋯,L-1k=0,1,2,⋯,L-1.
This can be written with matrix notation as
H
=
F
h
H
=
F
h
(47)
where HH is an LL by 1 vector of the samples of the complex
frequency response, FF is the LL by NN matrix of complex exponentials
from (Equation 46), and hh is the NN by 1 vector of real filter
coefficients.
These equations are possibly redundant for equally spaced samples since
A(ω)A(ω)
is an even function and, if the phase response is linear, h(n)h(n) is
symmetric. These redundancies are removed by sampling (Equation 32) over 0≤ωk≤π0≤ωk≤π and by using aa defined in (Equation 33) rather than
hh. This can be written
A
=
C
a
A
=
C
a
(48)
where AA is an LL by 1 vector of the samples of the real valued
amplitude frequency response, CC is the LL by MM real matrix of
cosines from (Equation 32), and aa is the MM by 1 vector of filter
coefficients related to the impulse response by (Equation 33). A similar set
of equations can be written from (Equation 44) for NN odd or from
(Equation 45) for NN even.
This formulation becomes a filter design method by giving the samples of a
desired amplitude response as Ad(k)Ad(k) and solving (Equation 48) for the
filter coefficients a(n)a(n). If the number of independent frequency
samples is equal to the number of independent filter coefficients and if
CC is not singular, this is the frequency sampling filter design method
and the frequency response of the designed filter will interpolate the
specified samples. If the number of frequency samples LL is larger than
the number of filter coefficients NN, (Equation 48) may be solved
approximately by minimizing the norm ∥A(ω)-Ad(ω)∥∥A(ω)-Ad(ω)∥.
The discrete time Fourier transform of the impulse response of a digital
filter is its frequency response, therefore, it is an important tool.
When the symmetry conditions of linear phase are incorporated into the
DTFT, it becomes similar to the discrete cosine or sine transform
(DCT or DST). It also has an arbitrary normalization possible for
the odd length that needs to be understood.
The discrete time Fourier transform (DTFT) is defined in (Equation 7)
which, with the conditions of an odd length-N symmetrical signal,
becomes
A
(
ω
)
=
∑
n
=
1
M
a
(
n
)
cos
(
ω
n
)
+
K
a
(
0
)
A
(
ω
)
=
∑
n
=
1
M
a
(
n
)
cos
(
ω
n
)
+
K
a
(
0
)
(49)
where M=(N-1)/2M=(N-1)/2. Its inverse as
a
(
n
)
=
2
π
∫
0
π
A
(
ω
)
cos
(
ω
n
)
d
ω
a
(
n
)
=
2
π
∫
0
π
A
(
ω
)
cos
(
ω
n
)
d
ω
(50)
for n=1,2,⋯,Mn=1,2,⋯,M and
a
(
0
)
=
1
K
π
∫
0
π
A
(
ω
)
d
ω
a
(
0
)
=
1
K
π
∫
0
π
A
(
ω
)
d
ω
(51)
where KK is a parameter of normalization for the
a(0)a(0) term with 0<K<∞0<K<∞. If K=1K=1, the expansion equation
(Equation 49) is one summation and doesn't have to have the separate
term for a(0)a(0). If K=1/2K=1/2, the equation for the coefficients
(Equation 50) will also calculate the a(0)a(0) term and the separate
equation (Equation 51) is not needed. If K=1/2K=1/2, a symmetry
results which simplifies equations later in the notes.
From the previous discussion, it is seen that there are four
possible types of FIR filters [1] that lead to the linear phase
of (Equation 20). These are summarized in Table 1.
Table 1: The Four Types of Linear Phase FIR Filters
| Type 1. |
The impulse response has an odd length and is even symmetric |
| |
about its midpoint of n=M=(N-1)/2n=M=(N-1)/2 which requires |
| |
h(n)=h(N-n-1)h(n)=h(N-n-1) and gives (Equation 29) and (Equation 30). |
| Type 2. |
The impulse response has an even length and is even symmetric |
| |
about MM, but MM is not an integer. Therefore, there is no |
| |
h(n)h(n) at the point of symmetry, but it satisfies (Equation 36) and (Equation 37). |
| Type 3. |
The impulse response has an odd length as for Type 1 and has |
| |
the odd symmetry of (Equation 42), giving an imaginary multiplier |
| |
for the linear-phase form in (Equation 43) with amplitude (Equation 44). |
| Type 4. |
The impulse response has an even length as for Type 2 and the |
| |
odd symmetry of Type 3 in (Equation 42) and (Equation 43) with amplitude (Equation 45). |
Examples of the four types of linear-phase FIR filters with
the symmetries for odd and even length are shown in Figure 4.
Note that for NN odd and h(n)h(n) odd symmetric, h(M)=0h(M)=0.
For the analysis or design of linear-phase FIR filters, it
is necessary to know the characteristics of A(ω)A(ω). The most
important characteristics are shown in Table 2.
Table 2: Characteristics of A(ω)A(ω) for Linear Phase
| 0.0pt7.11317pt12.80374pt
TYPE 1. |
Odd length, even symmetric h(n)h(n) |
|
| |
A(ω)A(ω) is even about ω=0ω=0 |
A
(
ω
)
=
A
(
-
ω
)
A
(
ω
)
=
A
(
-
ω
)
|
| |
A(ω)A(ω) is even about ω=πω=π |
A
(
π
+
ω
)
=
A
(
π
-
ω
)
A
(
π
+
ω
)
=
A
(
π
-
ω
)
|
| |
A(ω)A(ω) is periodic with period = 2π2π |
A
(
ω
+
2
π
)
=
A
(
ω
)
A
(
ω
+
2
π
)
=
A
(
ω
)
|
| 0.0pt7.11317pt12.80374pt
TYPE 2. |
Even length, even symmetric h(n)h(n) |
|
| |
A(ω)A(ω) is even about ω=0ω=0 |
A
(
ω
)
=
A
(
-
ω
)
A
(
ω
)
=
A
(
-
ω
)
|
| |
A(ω)A(ω) is odd about ω=πω=π |
A
(
π
+
ω
)
=
-
A
(
π
-
ω
)
A
(
π
+
ω
)
=
-
A
(
π
-
ω
)
|
| |
A(ω)A(ω) is periodic with period 4π4π |
A
(
ω
+
4
π
)
=
A
(
ω
)
A
(
ω
+
4
π
)
=
A
(
ω
)
|
| 0.0pt7.11317pt12.80374pt
TYPE 3. |
Odd length, odd symmetric h(n)h(n) |
|
| |
A(ω)A(ω) is odd about ω=0ω=0 |
A
(
ω
)
=
-
A
(
-
ω
)
A
(
ω
)
=
-
A
(
-
ω
)
|
| |
A(ω)A(ω) is odd about ω=πω=π |
A
(
π
+
ω
)
=
-
A
(
π
-
ω
)
A
(
π
+
ω
)
=
-
A
(
π
-
ω
)
|
| |
A(ω)A(ω) is periodic with period =2π=2π |
A
(
ω
+
2
π
)
=
A
(
ω
)
A
(
ω
+
2
π
)
=
A
(
ω
)
|
| 0.0pt7.11317pt12.80374pt
TYPE 4. |
Even length, odd symmetric h(n)h(n) |
|
| |
A(ω)A(ω) is odd about ω=0ω=0 |
A
(
ω
)
=
-
A
(
-
ω
)
A
(
ω
)
=
-
A
(
-
ω
)
|
| |
A(ω)A(ω) is even about ω=πω=π |
A
(
π
+
ω
)
=
A
(
π
-
ω
)
A
(
π
+
ω
)
=
A
(
π
-
ω
)
|
| |
A(ω)A(ω) is periodic with period =4π=4π |
A
(
ω
+
4
π
)
=
A
(
ω
)
A
(
ω
+
4
π
)
=
A
(
ω
)
|
Examples of the amplitude function for odd and even length
linear-phase filter A(ω)A(ω) are shown in Figure 5.
These characteristics reveal several inherent features that
are extremely important to filter design. For Types 3 and 4,
A(0)=0A(0)=0 for any choice of filter coefficients h(n)h(n). This would
not be desirable for a lowpass filter. Types 2 and 3 always
have A(π)=0A(π)=0 which is not desirable for a highpass filter. In
addition to the linear-phase characteristic that represents a
time shift, Types 3 and 4 give a constant 90-degree phase shift,
desirable for a differentiator or Hilbert transformer. The first
step in the design of a linear-phase FIR filter is the choice of
the type most compatible with the specifications.
It is possible to uses the formulas to express the frequency response
of a general complex or non-linear phase FIR filter by taking the
even and odd parts of h(n)h(n) and calculating a real and imaginary
“amplitude" that would be added to give the actual frequency response.
As shown earlier, LL equally spaced samples of H(ω)H(ω)
are easily calculated for L>NL>N by appending L-NL-N zeros to
h(n)h(n) for a length-L DFT. This appears as
H
(
2
π
k
/
L
)
=
DFT
{
h
(
n
)
}
for
k
=
0
,
1
,
⋯
,
L
-
1
H
(
2
π
k
/
L
)
=
DFT
{
h
(
n
)
}
for
k
=
0
,
1
,
⋯
,
L
-
1
(52)
This direct method of calculation is a straightforward and
flexible approach. Only the samples of H(ω)H(ω) that are of
interest need to be calculated. In fact, even nonuniform spacing
of the frequency samples can be achieved by sampling the DTFT
defined in (Equation 7). The direct use of the DFT can be inefficient,
and for linear-phase filters, it is A(ω)A(ω), not H(ω)H(ω), that is the
most informative. In addition to the direct application of the
DFT, special formulas are developed in ((Reference)) for evaluating
samples of A(ω)A(ω) that exploit the fact that h(n)h(n) is real and
has certain symmetries. For long filters, even these formulas
are too inefficient, so the DFT is used, but implemented by a
Fast Fourier Transform (FFT) algorithm.
In the special case of Type 1 filters with LL equally spaced
sample points, the samples of the frequency response are of the
form
A
k
=
A
(
2
π
k
/
L
)
=
∑
n
=
0
M
-
1
2
h
(
n
)
cos
(
2
π
(
M
-
n
)
k
/
L
)
+
h
(
M
)
A
k
=
A
(
2
π
k
/
L
)
=
∑
n
=
0
M
-
1
2
h
(
n
)
cos
(
2
π
(
M
-
n
)
k
/
L
)
+
h
(
M
)
(53)
For Type 2 filters,
A
k
=
A
(
2
π
k
/
L
)
=
∑
n
=
0
N
/
2
-
1
2
h
(
n
)
cos
(
2
π
(
M
-
n
)
k
/
L
)
A
k
=
A
(
2
π
k
/
L
)
=
∑
n
=
0
N
/
2
-
1
2
h
(
n
)
cos
(
2
π
(
M
-
n
)
k
/
L
)
(54)
For Type 3 filters,
A
k
=
A
(
2
π
k
/
L
)
=
∑
n
=
0
M
-
1
2
h
(
n
)
sin
(
2
π
(
M
-
n
)
k
/
L
)
A
k
=
A
(
2
π
k
/
L
)
=
∑
n
=
0
M
-
1
2
h
(
n
)
sin
(
2
π
(
M
-
n
)
k
/
L
)
(55)
For Type 4 filters,
A
k
=
A
(
2
π
k
/
L
)
=
∑
n
=
0
N
-
1
2
h
(
n
)
sin
(
2
π
(
M
-
n
)
k
/
L
)
A
k
=
A
(
2
π
k
/
L
)
=
∑
n
=
0
N
-
1
2
h
(
n
)
sin
(
2
π
(
M
-
n
)
k
/
L
)
(56)
Although this section has primarily concentrated on linear-phase
filters by taking their symmetries into account, the
method of taking the DFT of h(n)h(n) to obtain samples of the
frequency response of an FIR filter also holds for general
arbitrary linear phase filters.
A qualitative understanding of the filter characteristics
can be obtained from an examination of the location of the N-1N-1
zeros of an FIR filter's transfer function. This transfer
function is given by the z-transform of the length-N impulse
response
H
(
z
)
=
∑
n
=
0
N
-
1
h
(
n
)
z
-
n
H
(
z
)
=
∑
n
=
0
N
-
1
h
(
n
)
z
-
n
(57)
which can be rewritten as
H
(
z
)
=
z
-
N
+
1
(
h
0
z
N
-
1
+
h
1
z
N
-
2
+
.
.
.
+
h
N
-
1
)
H
(
z
)
=
z
-
N
+
1
(
h
0
z
N
-
1
+
h
1
z
N
-
2
+
.
.
.
+
h
N
-
1
)
(58)
or as
H
(
z
)
=
z
-
N
+
1
D
(
z
)
H
(
z
)
=
z
-
N
+
1
D
(
z
)
(59)
where D(z)D(z) is an N-1N-1 order polynomial that is multiplied by an
N-1N-1 order pole located at the origin of the complex z-plane. D(z)D(z)
is defined in order to have a simple polynomial in positive powers
of zz.
The fact that h(n) is real valued requires the zeros to all
be real or occur in complex conjugate pairs. If the FIR filter is
linear phase, there are further restrictions on the possible zero
locations. From (Equation 27), it is seen that linear phase implies a
symmetry in the impulse response and, therefore, in the
coefficients of the polynomial D(z)D(z) in (Equation 59). Let the complex
zero z1z1 be expressed in polar form by
z
1
=
r
1
e
j
x
z
1
=
r
1
e
j
x
(60)
where r1r1 is the radial distance of z1z1 from the origin in the
complex z-plane, and xx is the angle from the real axis as
shown in Figure 6.
Using the definition of H(z)H(z) and D(z)D(z) in (Equation 57) and
(Equation 58) and the linear-phase even symmetry requirement of
h
(
n
)
=
h
(
N
-
1
-
n
)
h
(
n
)
=
h
(
N
-
1
-
n
)
(61)
gives
H
(
1
/
z
)
=
D
(
z
)
H
(
1
/
z
)
=
D
(
z
)
(62)
which implies that if z1z1 is a zero of H(z)H(z), then 1/z11/z1 is also
a zero of H(z)H(z). In other words, if
H
(
z
1
)
=
0
,
then
H
(
1
/
z
1
)
=
0
.
H
(
z
1
)
=
0
,
then
H
(
1
/
z
1
)
=
0
.
(63)
This means that if a zero exists at a radius of r1r1, then one
also exists at a radius of 1/r11/r1, thus giving a special type of
symmetry of the zeros about the unit circle. Another possibility
is that the zero lies on the unit circle with r1=1/r1=1r1=1/r1=1.
There are four essentially different cases [4] of even
symmetric filters that have the lowest possible order. All higher
order symmetric filters have transfer functions that can be
factored into products of these lowest order transfer functions.
These are illustrated by four basic filters of lowest order that
satisfy these conditions: one length-2, two length-3, and one
length-5.
The only length-2 even-symmetric linear-phase FIR filter has
the form
D
(
z
)
=
(
z
+
1
)
K
D
(
z
)
=
(
z
+
1
)
K
(64)
which, for any constant KK, has a single zero at z1=-1z1=-1.
The even symmetric length-3 filter has a form
D
(
z
)
=
(
z
2
+
a
z
+
1
)
K
D
(
z
)
=
(
z
2
+
a
z
+
1
)
K
(65)
There are two possible cases. For |a|>2|a|>2, two real zeros can
satisfy (Equation 63) with z1=rz1=r and 1/r1/r. This gives
D
(
z
)
=
(
z
2
+
(
r
+
1
/
r
)
z
+
1
)
K
D
(
z
)
=
(
z
2
+
(
r
+
1
/
r
)
z
+
1
)
K
(66)
The other length-3 case for |a|<2|a|<2 has two complex conjugate
zeros on the unit circle and is of the form
D
(
z
)
=
(
z
2
+
(
2
cos
x
)
z
+
1
)
K
D
(
z
)
=
(
z
2
+
(
2
cos
x
)
z
+
1
)
K
(67)
The special case for a=2a=2 is not of lowest order. It can be
factored into (Equation 64) squared.
Any length-4 even-symmetric filter can be factored into
products of terms of the form of (Equation 64) and (Equation 65).
The fourth case is of an even-symmetric length-5 filter of
the form
D
(
z
)
=
z
4
+
a
z
3
+
b
z
2
+
a
z
+
1
D
(
z
)
=
z
4
+
a
z
3
+
b
z
2
+
a
z
+
1
(68)
For a2<4(b-2)a2<4(b-2) and b>2b>2, the zeros are neither real nor
on the unit circle; therefore, they must have complex conjugates
and have images about the unit circle. The form of the transfer
function is
D
(
z
)
=
{
z
4
+
[
(
2
(
r
2
+
1
)
/
r
)
cos
x
]
z
3
+
[
r
2
+
1
/
r
2
+
4
cos
2
x
]
z
2
+
[
(
2
(
r
2
+
1
)
/
r
)
cos
x
]
z
+
1
}
K
D
(
z
)
=
{
z
4
+
[
(
2
(
r
2
+
1
)
/
r
)
cos
x
]
z
3
+
[
r
2
+
1
/
r
2
+
4
cos
2
x
]
z
2
+
[
(
2
(
r
2
+
1
)
/
r
)
cos
x
]
z
+
1
}
K
(69)
If one of the zeros of a length-5 filter is on the real axis or
on the unit circle, D(z)D(z) can be factored into a product of lower
order terms of the forms in (Equation 64), (Equation 66), and
(Equation 67) and, therefore, is not of lowest order.
The odd symmetric filters of (Equation 42) are described by the
above factors plus the basic length-2 filter described by
D
(
z
)
=
(
z
-
1
)
K
D
(
z
)
=
(
z
-
1
)
K
(70)
The zero locations for the four basic cases of Type 1 and 2 FIR
filters are shown in Figure 7. The locations for the Type 3 and
4 odd-symmetric cases of (Equation 42) are the same, plus the zero at
one from (Equation 69).
From this analysis, it can be concluded that all linear-phase
FIR filters have zeros either on the unit circle or in the
reciprocal symmetry of (Equation 66) or (Equation 69) about the unit circle,
and their transfer functions can always be factored into products
of terms with these four basic forms. This factored form can be
used in implementing a filter by cascading short filters to
realize a long filter. Knowledge of the locations of the transfer
function zeros helps in developing filter design and analysis
programs. Notice how these zero locations are consistent with
the amplitude responses illustrated in Table 2 and Figure 5.
In this section the basic characteristics of the FIR filter
have been derived. For the linear-phase case, the frequency
response can be calculated very easily. The effects of the linear
phase can be separated so that the amplitude can be approximated
as a real-valued function. This is a very useful property for
filter design. It was shown that there are four basic types of
linear-phase FIR filters, each with characteristics that are also
important for design. The frequency response can be calculated
by application of the DFT to the filter coefficients or, for
greater resolution, to the NN filter coefficients with zeros added
to increase the length. A very efficient calculation of the DFT
uses the Fast Fourier Transform (FFT). The frequency response can
also be calculated by special formulas that include the effects
of linear phase.
Because of the linear-phase requirements, the zeros of the
transfer function must lie on the unit circle in the z plane or
occur in reciprocal pairs around the unit circle. This gives
insight into the effects of the zero locations on the frequency
response and can be used in the implementation of the filter.
The FIR filter is very attractive from several points of
view. It alone can achieve exactly linear phase. It is easily
designed using methods that are linear. The filter cannot be
unstable. The implementation or realization in hardware or on a
computer is basically the calculation of an inner product, which
can be accomplished very efficiently. On the negative side, the
FIR filter may require a rather long length to achieve certain
frequency responses. This means a large number of arithmetic
operations per output value and a large number of coefficients
that have to be stored. The linear-phase characteristic makes the
time delay of the filter equal to half its length, which may be
large.
How the FIR filter is implemented and whether it is chosen over
alternatives depends strongly on the hardware or computer to be
used. If an array processor is used, an FFT implementation [3] would
probably be selected. If a fixed point TMS320 signal processor is
used, a direct calculation of the inner product is probably best. If
a floating point DSP or microprocessor with floating-point
arithmetic is used, an IIR filter may be chosen over the FIR, or the
implementation of the FIR might take into account the symmetries of
the filter coefficients to reduce arithmetic. To make these choices,
the characteristics developed in this chapter, together with the
results developed later in these notes, must be considered.
A central characteristic of engineering is design. Basic to DSP is
the design of digital filters. In many cases, the specifications of
a design is given in the frequency domain and the evaluation of the
design is often done in the frequency domain. A typical sequence of
steps in design might be:
- From an application, choose a desired ideal response,
typically described in the frequency domain.
- From the available hardware and software, choose an allowed
class of filters (e.g. a length-N FIR digital filter).
- From the application, set a measure or criterion of
“goodness" for the response of an allowed filter compared to the
desired response.
- Develop a method to find (or directly generate) the best member of
the allowed class of linear phase FIR filters as measured by the criterion
of goodness.
This approach is often used iteratively. After the best filter is
designed and evaluated, the desired response and/or the allowed
class and/or the measure of quality might be changed; then the
filter would be redesigned and reevaluated.
The ideal response of a lowpass filter is given in
Figure 8.
Figure 8a is the basic lowpass response that exactly
passes frequencies from zero up to a certain frequency, then rejects
(multiplies those frequency components by zero)the frequencies above
that. Figure 8b introduces a “transitionband" between
the pass and stopband to make the design easier and more efficient.
Figure 8c introducess a transitionband which is not used
in the approximation of the actual to the ideal responses. Each of
these ideal responses (or other similar ones) will fit a particular
application best.
-
Burrus, C. S. and Parks, T. W. (1985). DFT/FFT and Convolution Algorithms. New York: John Wiley & Sons.
-
Mitra, Sanjit K. (2006). Digital Signal Processing, A Computer-Based Approach. (Third). [First edition in 1998, second in 2001]. New York: McGraw-Hill.
-
Oppenheim, A. V. and Schafer, R. W. (1999). Discrete-Time Signal Processing. (Second). [Earlier editions in 1975 and 1989]. Englewood Cliffs, NJ: Prentice-Hall.
-
Parks, T. W. and Burrus, C. S. (1987). Digital Filter Design. New York: John Wiley & Sons.
