| Notes of the Design of Optimal FIR Filters
John R. Treichler
Applied Signal Technology, Inc. November 1989
1.0 Introduction
A recurring technical task at Applied Signal Technology, Inc. is the
design of FIR digital filters. Fortunately some excellent software packages
exist for the automatic synthesis of impulse responses for such filters,
many of them based on the now-famous Parks-McClellan algorithm[2].
Unfortunately, there is still some mystery about how to use the software
and, equally important, how to estimate impulse response lengths short
of actually designing the filter itself. This technical note primarily
addresses the second problem and indirectly discusses a bit of the first.
We examine here how to convert a typical filter specification in terms
of cutoff frequency, passband ripple, etc., into a reasonably accurate
estimate of the length of the impulse response. Not only does this estimate
suffice for most design tradeoff exercises, it usually allows the Parks-McClellan
routines to be employed only once or twice rather than the multiple times
needed when the “cut-and-try” method is used.
Back to top of page
2.0 Statement of the Optimal Linear Phase FIR Filter Design Problem
2.1 Equal-ripple Design
While other types of filters are often of interest,
this note focuses on the lowpass linear phase filter. Even though it is
not immediately obvious, virtually all of the analytical results developed
in this note apply to the other types as well. This fact is amplified
in Section 4.
It is known that the Parks-McClellan filter synthesis software package
produces “optimal” filters in the sense that the best possible
filter performance is attained for the number of “filter taps”
allowed by the designer. “Optimal” can be defined various ways.
The Parks-McClellan package uses the Remez exchange algorithm to optimize
the filter design by selecting the impulse response of given length, termed
here N, which minimizes the peak ripple in the passband and stopband.
It can be shown, though not here, that minimizing the peak, or maximum,
ripple is equivalent to making all of the local peaks in the ripple equal
to each other. this fact leads to three different names for essentially
the same filter design. They are commonly called “equal-ripple”
filters, because the local peaks are equal in deviation from the desired
filter response. Because the maximum ripple deviation is minimized in
this optimization procedure, they are also termed “minimax”
filters. Finally, since the Russian Chebyshev is usually associated with
minimax designs (1),
these filters are often given his name.
The design template for an equal-ripple lowpass filter is shown in Figure
1. The passband extends from 0 Hz to the cutoff frequency denoted
 . The gain in the passband is assumed
to be unity. Any other gain is attained by scaling the whole impulse response
appropriately. The stopband begins at the frequency denoted  and ends at the so-called Nyquist
or “folding” frequency, denoted by
 ,
where  is the sampling
frequency of the data entering the digital filter. In some references,
[1]
for example, the sampling rate
is assumed to be normalized to unity just as the passband gain has here.
The dependence on the sampling frequency is kept explicit in this note,
however, so that its impact on design parameters can be kept visible.
Figure 1. Frequency Response of an Optimal Weighted
Equal-Ripple Linear Phase FIR Filter
The optimal synthesis algorithm is assumed here to produce an impulse
response whose associated frequency response has ripples in both the passband
and the stopband. The peak deviation in the passband is denoted  and the peak deviation in the stopband
is denoted  . It is commonly believed that an “equal-ripple”
design forces to equal
. In fact this is not true. The local ripple peaks in the
passband will all equal
and those in the stopband will all equal . For a given filter specification the two are linked together by
a weight denoted W, so that  . In fact the Parks-McClellan routines insure the design of weighted
equal-ripple filters. The choice of W is discussed shortly.
An important design parameter is the transition band,
denoted  , and defined
as the difference between the stopband edge and the passband edge .
Thus,
In theory the required filter order N is a function
of all of the design parameters defined so far, that is, , , , , and . A central point of this technical note is that under
a large range of practical circumstances the required value of N
can be estimated using only ,
, and the smaller of and . Back to top of page
2.2 Conversion of Specifications
While the parameters defined in the previous section relate directly
to the theory of FIR filter design optimization, some of them differ from
those usually employed to specify the performance of a filter. We discuss
here the conversion of two of those, and , into more traditional
measures.
Passband Ripple: Figure
1 uses the parameter to describe the peak difference between the template lowpass
filter and the magnitude of the filter response actually attained. Traditionally
this passband ripple has been specified in terms of the maximum difference
in the power level transmitted through the filter in the passband. By
this definition, the peak-to-peak passband ripple, abbreviated here as
PBR, is given by
Assuming that the nominal power transmission through the filter is unity,
the numerator is the power gain at a ripple peak and the denominator is
the gain at a trough. It is easily shown (see Appendix
A) that when is small
compared to unity, or, equivalently, when the passband ripple is less
than about 1.5 dB, then (2)
Stopband Ripple: The traditional specification for stopband ripple,
abbreviated here as SBR, is the power difference between the nominal passband
transmission level and the transmission level of the highest ripple in
the stopband. For the equal ripple design shown in Figure
1, all stopband ripples have equal peak values and the nominal passband
transmission is unity, that is, 0 dB. The stopband ripple, or more accurately,
the minimum stopband power rejection, denoted SBR, is given by
Example: Suppose a filter is specified to have a passband
ripple of 0.5 dB and a minimum stopband attenuation of 60 dB. Using
the above equations we find that
= 0.0288,
= .001, and the relative weighting, W, equals 28.8.
In discussing filter specifications it should be noted that the cutoff
frequency shown in Figure
1 differs from the definition typically used in analog filter designs.
The cutoff frequency is commonly defined as the 3 dB point, that
is, that frequency at which the power transfer function falls to a value
3 dB below the nominal passband level. Instead the value of
shown in Figure 1 is the highest frequency
at which the specified passband ripple is still attained. In very few
practical cases do the two definitions result in the same frequency value.
Back to top of page
3.0 Filter Sizing
3.1 The Formula for Estimation of the FIR Filter Length
For many lowpass filter designs the peak passband excursion
exceeds the peak stopband
excursion by a factor
of ten or more. This ratio, earlier denoted as the weight W,
was just evaluted in the previous section to have the value 28.8 for a
typical set of specifications. In this case the stopband attenuation specification
drives the required filter order. In this case, and with a few additional
assumptions which will be enumerated later, the number of coefficients
in the impulse response of a high-order FIR linear phase filter, denoted
N, can be accurately estimated using the formula:
where the design parameter 
is given by the equation:
As before, SBR is the minimum stopband attenuation compared
to the nominal passband power transmission level, measured in decibels.
Continuing Example: Suppose as before that the lowpass filter
of interest is to have a peak-to-peak passband ripple (PBR) of 0.5
dB and a minimum stopband attenuation of 60 dB. Since W
has been evaluated to be approximately 29 in this case, equation
5 applies. Using equation 6,
is evaluated to be 2.42. Thus N is closely approximated
by 2.42 times the reciprocal of the normalized transition bandwidth
 .
To continue the example assume that the sampling rate is 8 kHz,
that the cutoff frequency
is 1530 Hz, and that the stopband edge
is 2330 Hz.
Thus = 800
Hz and
= 0.1,
yielding an estimated filter order N of approximately
24.
Executing the Parks-McClellan design program with these parameters
happens to produce an impulse response which almost perfectly matches
the desired result (e.g., peak stopband ripple of 60.07 dB as opposed
to the stated objective of 60 dB).
Note that the required filter order N as estimated by equations
5 and 6 does not depend on the passband ripple PBR or on the exact values
of the cutoff and stopband frequencies. Thus, when the conditions allowing
the underlying assumptions to be met are true, estimating the required
filter order N becomes very easy.
Table 1 provides the values of the design parameter
from equation 6 for various
degrees of stopband suppression. Given also is the range of the passband
ripple for which the values of
apply. The column marked maximum passband ripple reflects the assumption
that the passband deviation
is small compared to unity; specifically, the stated value of 1.74 dB
corresponds to =
0.1. The rightmost column, denoted minimum passband ripple, is
the limit imposed by the assumption that
> 10 · . Of course
FIR linear phase equal ripple filters can be designed with passband ripple
extending beyond the stated range. However, as the PBR specification approaches
either of these endpoints the validity of equation 6 will degrade. The
predicted filter length will err on the low side for small PBR values
and be overly pessimistic for PBR > 1.74 dB. In such cases, an iteration
on the design might be necessary to obtain the desired filter characteristics.
Table 1. Values of the Design Parameter 
as a Function of the Minimum Stopband Attenuation
| |
Stopband
Attenuation
(in dB)
|
|
Maximum Passband
Ripple (in dB) |
Minimum Passband
Ripple (in dB) |
| |
45 |
1.87 |
1.74 |
1.0 |
| |
50 |
2.05 |
1.74 |
0.55 |
| |
55 |
2.23 |
1.74 |
0.31 |
| |
60 |
2.42 |
1.74 |
0.174 |
| |
65 |
2.60 |
1.74 |
0.098 |
| |
70 |
2.78 |
1.74 |
0.055
|
Back to top of page
3.2 Derivation of the Formula
This section describes the theoretical underpinnings of equations
5 and 6. A clear understanding of this section is not required to
use the Parks-McClellan software routines or to enjoy the remainder of
this technical note.
As discussed in Section 2, the Parks-McClellan
synthesis algorithm uses the Remez exchange algorithm to optimally select
the values of the N impulse response coefficients in such a way
as to minimize the weighted peak difference between the desired magnitude
frequency response and the actual one. Since the solution to this optimization
problem does not have a closed form, it is not easy to generalize its
properties. To learn about its properties and to develop appropriate design
rules, McClellan, Rabiner, and others synthesized thousands of filters
and measured their properties. Curves with this sort of information are
presented in [1],
along with a complicated empirical formula for the filter order N
in terms of all of the parameters specifying the filter. While this work
is not immediately useful for design work, a limiting casewas uncovered
by those workers which does provide some insight into the optimal filter
solutions and leads to the simple rules compressed into equations 5 and
6.
Suppose we desire to design a high-order, FIR, linear phase filter for
which the passband is as narrow as possible. Looking again at Figure
1 with this in mind reveals that all of the ripple behavior for such
a filter will occur in the stopband. Such a filter, or a very close approximation
to it, can be synthesized using another FIR filter design method, that
of multiplying a sampled
function, where
 ,
by an N-point window function constructed from a Chebyshev polynomial.
The sampled
,
or sinc, function is the inverse z-transform of a perfect lowpass filter.
It cannot be used directly since it extends infinitely far into both forward
and backward time. A finite duration impulse response is obtained by multiplying
the “perfect” response by a finite-duration window function.
The one discussed here uses Chebyshev polynomials as their basis. These
polynomials are discussed in Appendix B.
They all have the property that the polynomials’ peak magnitude is
unity for values of x between –1 and 1, and that for greater
values of  , the magnitude
grows as  where M is the order of the polynomial. One such polynomial is shown in Figure 2.
Figure 2. A Chebyshev Polynomial (drawn from [1])
We desire that the oscillatory portion of the polynomial correspond to
the stopband region of the filter response and the
portion to correspond to the transition from the stopband to the passband.
This is accomplished by invoking a change of variables relating x
to the frequency  . The resulting
equation is then evaluated at the several points to obtain an expression
for the transition bandwidth .
The details of this manipulation are contained in Appendix
C. They result in the following equation:
If is small compared
to unity and N is large compared to unity, as already assumed,
then is closely approximated
by
When the argument of the hyperbolic cosine is large, the function can
be approximated as
With suitable manipulation we find that
Substituting this expression for the inverse hyperbolic cosine yields
a simple formula for :
Rewriting this equation shows that N must equal or exceed:
where is given by
Rewriting equation
4, can be written
as
Substituting this into equation 13 yields
which can be recognized as equation
6.
Back to top of page
3.3 Caveats
The derivation just presented assumes that the filter of interest is
a lowpass design, the filter order is high (> 20 or so), that the
passband ripple is small (that
<<1), and that the filter uses all degrees of freedom except one
in the stopband, that is, that the filter has the lowest possible cutoff
frequency. In fact not all of these conditions have to be met to make
the design equations
5 and 6 useful. An indication of how errors can enter the estimate
of N under other conditions can be seen, however, by examining
Figure 3.
Figure 3. Comparison of the Transition Widths of
Even and Odd Optimal Lowpass Filters (drawn from [1])
This figure shows the smallest value of
attainable with optimal equal-ripple linear phase filters of different
lengths as a function of the cutoff frequency .
Equations 5 and 6 predict that the transition bandwidth is constant as
a function of cutoff frequency and that it always gets smaller as the
filter order N increases. Figure 3 shows that these generalities
are not true. It can be seen that
varies somewhat as a function of
and that there are particular choices of
where a lower value of
is actually attainable with a lower filter order rather than a higher
one. It would appear that, for a given filter order N, some values
of are “hard”
to attain a small transition bandwidth and others are “easy.”
This is in fact true and the reason for it will be discussed in Section
3.7.
While Figure 3 shows that
is not truly independent of the cutoff frequency
and monotonic in the filter order N, the significant variations
appear only for low filter orders. If N is greater than 20 or
so, and the other conditions listed above hold true, as they usually do,
then equations 5 and 6 can be used with impunity, even for highpass and
bandpass filters.
Back to top of page
3.4 Performance Comparison with other FIR Design Methods
A commonly asked question among filter designers is why should the optimal
design methods be used at all, or, equivalently, how much does the use
of an optimal technique buy over some other conventional methods. This
question is conveniently answered using Figure 4,
a figure extracted from [1]
and modified to use the definitions of variables employed in this technical
note. The figure shows the value of the design parameter
needed to attain a specific degree of stopband suppression in lowpass
filters. Since the filter order N and therefore the amount of
computation(3)
 are directly proportional
to , it serves as an excellent
indicator for comparisons. Curves for three design methods are shown,
windowing techniques, so-called “frequency sampling” techniques,
and the optimal, equal-ripple design produced by the Parks-McClellan program.
In each case there are some variations depending on the choice of design
parameters other than stopband ripple. For example, the optimal technique
shows a band of results indexed by the amount of passband ripple (hence
) specified. The figure
shows that, for modest degrees of stopband suppression, all of the methods
work about equally well. For high degrees of suppression, however, the
optimal technique allows values of
to be attained which are on the order of half of those attainable with
the windowing methods and about 60 to 70% of the frequency sampling
method. Since computation is directly proportional to ,
these saving are directly translatable into hardware and/or runtime improvements.
Figure 4. Comparisons among Windowed, Frequency
Sampling, and Optimal Lowpass Filters (drawn from [1])
Why, one might ask, is the optimal method significantly better than, say,
the window method? A fuller answer is presented shortly, but a simple
one is that the optimal methods allow the designer to avoid overdesigning
portions of the frequency response about which he or she needn’t
exert as much control. For example, recall the design example discussed
in Section 2.2. In that case a set of reasonable
specifications was developed which allowed the magnitude of the passband
ripple to be almost 29 times larger than the stopband ripple. Since the
Parks-McClellan design package allows the design of weighted
equal-ripple filters this disparity can be accommodated. Window-designed
filters, however, are constrained to have exactly the same passband ripple
as stopband ripple .
Effectively the optimal design methods allow the degrees of freedom in
the impulse response to be focused on the most stressing parts of the
frequency response design while the window method treats all parts equally.
The frequency-sampling method falls in between.
Back to top of page
3.5 The Meaning of the Design Parameter
More insight into the meaning of the design parameter
can be gained by examining all three aforementioned design methods in
terms of the inverse discrete Fourier transform. Suppose that our objective,
as it is, is to synthesize an N-point FIR filter. Suppose further that
we use the approach of specifying the frequency response we desire with
equally spaced samples in the frequency domain and then use the inverse
discrete Fourier transform (DFT) to transform the frequency specification
into a time-domain impulse response. This approach is shown in graphical
form in Figure 5.
Figure 5. Using the Discrete Fourier Transform
(DFT) as the Basis of FIR Filter Desig
Analytically there is a one-to-one relationship between the N points of
an FIR impulse response and the frequency response of the filter measured
at N equally-spaced frequencies between 0 and
Hertz. Specifically it is straight-forward to show that the impulse response
h(k) and the complex gains  ,
for 0  n
N –
1,
are invertibly related, where the filter’s frequency response is
given by
Thus, choosing the complex gains
is equivalent to choosing the impulse response h(k), 0
k
N – 1, and, through equation 16, to the filter frequency
response at all values of
between 0 and Hertz.
By examining Figure 5 it can be seen that choosing a frequency response
(and hence an impulse response) can be intuitively viewed as adjusting
the gain levers on a graphic equalizer of the type now used on home stereos.
Each lever sets the gain, denoted here as ,
of a filter given by
By setting these N gain values optimally the best possible frequency
response is attained.
The analogy of the graphic equalizer can be followed somewhat further.
equation 16 suggests that the FIR design problem can be thought in the
terms of the structure shown in Figure 6. The input
signal is applied to all N of what we’ll call the basis
filters, where the frequency response of the n-th filter is given
by equation 17. As noted earlier these basis filters, so called because
they form the linearly independent set of filters used to construct H(),
are frequency-shifted versions of the same fairly sloppy bandpass filter.
These filter outputs are then scaled by the complex coefficients
and then added together to produce the observable filter output. Thus
the basis filters are fixed and the
control the frequency and hence impulse response of the digital filter.
It should be noted that the filter is not usually actually constructed(4)
as shown in Figure 6 but it is a very convenient analogy when trying to
understand the relationships between the various filter synthesis methods.
Figure 6. The FIR Filter Design Problem Modeled
as a Bank of Bandpass Filters
Now we shall use the model. In our quest for the true meaning of ,
consider first the design of a simple lowpass filter. We desire the cutoff
frequency and the stopband
edge to be as low as
possible and allow the peak stopband ripple to be quite large. Using the
graphic equalizer model just discussed yields the design shown in Figure
7. Only one filter, the one centered at DC, is used. Its gain is set
to unity and that of all others is set to zero. The peak stopband ripple
is determined by the first sidelobe of the only active filter. It can
be computed to be about 13 dB below the maximum passband power level (measured
at DC).
Figure 7. A Simple Lowpass Filter Designed Using
the Graphic Equalizer Analogy
What is in this case?
Graphically it can be seen to be somewhat less than than the frequency
interval between DC and the first transmission zero of .gif)
which occurs at  .
Suppose that we now rewrite equation 5 as
Thus we see that in the simple filter designed in Figure 7 the associated
value of is slightly less
than one.
Now suppose that we attempt to design a better filter, again using the
graphic equalizer method. Our first objective is to reduce the size of
the stopband ripple.
To do this we leave 
set to unity and increase the values of 
and  slightly so that
their positive mainlobe values cancel the negative-going first sidelobe
of .
All other filter gain levels will remain set to zero. The effects of
this strategy are seen in Figure 8.
Figure 8. Lowpass Filter Obtained Using the Second
and Third DFT Basis Functions
The first objective, that of reducing the peak stopband ripple, is achieved.
By choosing and
just right, the first sidelobe of
can be effectively cancelled, leaving the other sidelobes to compete for
the peak value. The second effect is less desirable, however. From graphical
inspection it is clear that ,
the frequency interval between
and , has grown. It now
exceeds
 ,
thus making greater than
unity.
These trends continue as more and more filter gains
are allowed to become non-zero in the quest of further reducing the peak
stopband ripple. The peak is reduced, the ripple structure begins to approach
the Chebyshev equal-ripple form seen in Figure
1, and the transition band stretches out as more filters are used
to try to constrain the stopband frequency response to meet the stopband
ripple goals. The design parameter
is just a measure of the number of filters, or, equivalently, the number
of equalizer levers, needed to transit from one gain level (e.g., the
passband) to another (e.g., the stopband) while achieving the desired
passband and stopband ripple performance. Since
is the spacing between the bins of an N-point DFT, the term
can also be thought of as the number of DFT bins needed to make a gain
transition. This interpretation is explored next.
Back to top of page
3.6 Three Methods of Designing FIR Filters
Section 3.4 alluded to the fact that three
basic methods have traditionally been used for the design of FIR digital
filters. Figure 4 in fact
compares their relative performance in terms of the value of
(which was shown to be proportional to the filter’s required run-time
computation rate) implied. Given the background of the previous subsection
it is now possible to understand each of the methods and to gain some
insight into the differences between their performance.
Back to top of page
3.6.1 Window-based Filters
One of the earliest class of FIR filters are those based on the use of
a “smoothing window.” This window, constructed to have only
N non-zero points, is multiplied point-by-point by an impulse response
of infinite duration which has the “perfect” frequency response.
This multiplication or windowing has the effect of making the
filter impulse response finite in duration (hence FIR), but also has the
effect of smearing the desired frequency response.
The stopband ripple specification is obtained by using a window capable
of suppressing all sidelobes to the desired degree. This can be seen in
Figure 9. The windowed filter basis function has substantially
lower sidelobes than the original
filter basis function, in trade for substantial widening of the main lobe.
This widening means growth in the equivalent design parameter
and is monotonic with the degree of sidelobe suppression attained.
Figure 9. The Effect of a Window Function on the Basis
Filter
It should also be observed that the sidelobe reduction has the effect
of reducing the ripple in the passband as well as in the stopband. Thus,
some of the filter’s degrees of freedom are given up in perhaps overdesigning
the passband response rather than focusing them on the stopband performance.
Back to top of page
3.6.2 Frequency Sampling Design
In the simplest DFT-based FIR filter design method, the desired frequency
response is sampled at frequency intervals of
Hertz and the filter gains
are set to those values. This is in essence the method used for the simple
lowpass filter shown in Figure
7. The big advantages of this method are its simplicity and the fact
that any desired response, no matter how complicated, can be approximated.
The big disadvantage is its uncontrolled ripple performance in both the
stopband and passband. The traditional cures for this are the use of a
window function to suppress the ripple and the expansion of the filter
order N to compensate for the window’s smearing of the desired response.
Increasing N, of course, increases the filter’s run-time
computation rate.
Relatively early in the development of FIR design techniques it was discovered
that much better adherence to the desired frequency response could be
attained by allowing some of the basis filter gains
to vary slightly from the exact sampled values (e.g., 1 and 0 for a lowpass
filter). This idea is shown in Figure 10. A simple
lowpass filter is the desired response. Solid dots show the frequency
samples of this desired response taken every
Hertz. These samples have values of 1 and 0 for
in the passband and stopband respectively. Now suppose that the values
of for n in
the vicinity of the cutoff frequency
are allowed to be modified slightly with the goal of minimizing the peak
stopband ripple. These values of n are denoted with small circles
instead of solid dots in Figure 10. Rabiner and his coworkers [4]
showed in 1970 that it was possible to use the linear programming optimization
technique to manipulate two or three of the filter gains to obtain great
improvement in stopband ripple performance. The computational complexity
of the linear programming method, however, limited the number of the
which could be so chosen.
Figure 10. Comparison of “Frequency Sampling”
and Equal-Ripple Design
Back to top of page
3.6.3 Equiripple Design
It was generally known in 1971 that equal-ripple passband and stopband
behavior would lead to the best filter performance, where “best”
means the smallest transition band (and hence )
for a given set of peak passband and stopband ripple specifications. In
fact a great deal was known about the properties of such filters. What
was lacking was a computationally satisfactory method of designing such
optimal filters. As just noted, the linear programming technique provided
a big step but still fell short. The breakthrough came in two parts. Several
workers, but principally Parks, McClellan (Parks’ graduate student),
and Rabiner showed that four different variants of FIR linear phase filters
could all be represented by the same set of equations (5)
and could therefore be solved the same way. The second part was Parks’
suggestion of using the Remez exchange algorithm for doing the actual
optimization. The Remez exchange algorithm effectively allows all degrees
of freedom in the filter impulse response to be adjusted simultaneously
while the linear programming technique allows the adjustment of only one
at a time. For high order filters this distinction makes a tremendous
difference in the number of computations needed to iteratively optimize
a design. Refering again to Figure 10, the Remez algorithm allows all
of the frequency samples to be modified, even for filter orders as high
as N= 1000, thus permitting the best possible filter performance
to be achieved. McClellan also proved that the linear phase FIR filter
design problem satisfied the conditions needed to guarantee convergence
of the Remez algorithm.
Back to top of page
3.7 Why Does Depend on the Cutoff Frequency ?
The formulas presented in equations
5 and 6 imply that and
hence the required filter order N are independent of the cutoff
frequency . The supporting
analysis showed that this is only true in the limit of high order filters,
i.e. when N is large. The dependence for shorter filters is shown
in Figure 3. Why should this occur?
Consider the filter design problem shown in Figure 11.
Again the goal is a simple lowpass filter with cutoff frequency .
The frequency sampling points at frequency multiples of
are also shown as solid dots. Instead of fixing the gains we presume that
the filter gains , or,
equivalently, the graphic equalizer levers, are optimized, by whatever
means, to yield the best stopband ripple performance.
Figure 11. Visualizing the Effects of Cutoff Frequency
on Design Difficulty
Figure 11(a) shows the combination of gains
needed to constrain the peak stopband ripple to a given level, say  .
The frequency at which this equal ripple band starts is of course
and the difference between
and is .
Now suppose that is increased
slightly, as shown in Figure 11(b). Now a different set of the
are needed to make the peak ripple equal
and these result in different values of
and . Pursuing this graphical
analysis we find that:
- Cutoff frequencies near multiples of
result in smaller transition bands, and hence smaller values of ,
than those near the center of two bins. This occurs, to first order,
since two or more stopband basis filters are needed to cancel the
first sidelobe of the last basis passband filter when the passband
stops between two bins, while one is needs if the passband stops near
a bin.
- Because these “hard” and “easy” frequency ranges
occur for every bin, the number of the ranges, counting both positive
and negative frequencies, is about the same as the filter order(6)
N.
- The variation in the transition band
is more pronounced as N decreases since there are fewer basis
filters to use in optimizing the response.
As an aside, one might observe from Figure
4 that all three methods perform about equally for high levels of
stopband ripple. Intuitively the reason for this should now be clear.
Window-based methods need not use much shaping if high levels of ripple
are tolerable. Similarly, frequency sampling need not use many adjustable
coefficients. Since this is true, the equal-ripple techniques will not
perform much better since their only advantage is that of adjusting all
of the filter gains. The underlying point is that, for high-ripple designs,
all of the methods produce designs closely resembling the sum of simple,
shifted
functions and produce a transition band
of about the order of
,
hence an of about unity.
Only as the stopband ripple specification grows tighter does the method
and accuracy of adjusting the coefficients and the number of them available
for adjustment begin to affect the transition band performance.
Back to top of page
4.0 Extension to Non-lowpass Filters
All of the dicussion to this point has focused on lowpass filters. Practical
applications require other types, of course, including highpass, bandpass,
and bandstop designs. In fact, the analysis presented in the previous
sections applies to all of these design criteria and the rules for filter
length estimation can be used almost directly. In general, equations
5 and 6 apply when one of the equal ripple specifications dominates
all others and when one of the transition band specifications dominates
all others. As a practical matter this means that 
dominates if it is less than one-tenth of all other ripple specifications
and that  dominates if
it is simply less than all others. Suppose we define 
and by the equations:
If so, then equation 5 can be used directly and the equation for
becomes
A final hint – Watch out for the implicit boundary conditions present
in the design of linear phase FIR digital filters in two cases: even order,
symmetric response and odd order, antisymmetrical response. In both of
these cases the underlying equations for the filter’s frequency response
constrain it to equal exactly zero at .
This is obviously not a problem for lowpass filters, since the desired
gain at is zero already.
However, in the design of multiband and highpass filters an inordinate
amount of engineering time has been wasted trying to design even-order
filters when in fact it is impossible to do so. The Parks-McClellan algorithm
will gamely try, but will fail. As a rule, use odd values of N
for highpass and multiband filters requiring nonzero response at
and use even-order filters for differentiators.
Back to top of page
References
- L. R. Rabiner and B. Gold, Theory and Application
of Digital Signal Processing, Prentice-Hall, 1975.
- J. H. McClellan, et al, “A Computer Program for
Designing Optimal FIR Linear Phase Digital Filters,” IEEE Transactions
on Audio and Electroacoustics, Vol. AU-21, No. 6, December, 1973, pp. 506–526
- R.E. Crochiere and L.R. Rabiner, “Multirate Digital Signal Processing”, Prentice-hall, 1983.
- L. R. Rabiner, et al., “An Approach to the Approximation
Problem for Nonrecursive Digital Filters,” IEEE Trans. Audio Electroacoustics,
Vol. AU–18, pp. 83–106, June 1970.
Back to top of page
Appendix A: The Formula for Convering between  and Passband Ripple
From equation
2, the peak-to-peak passband ripple, measured in decibels, is given
by
where is the peak amplitude
deviation in the passband. Suppose now that
If so, then the passband ripple PBR is closely approximated by
Now recall that  ,
when x is small compared to unity, and that  .
Combining these facts, leads to the equation
This formula holds as long as
is small compared to unity. Using
= 0.1 as a benchmark, the formula holds for values of passband ripple
less than 1.74 dB, the range in which most filter design falls.
Back to top of page
Appendix B: Some Notes on Chebyshev Polynomials
Section 3.2 used some of the properties
of the Chebyshev polynomials to develop the key formulas used for FIR
filter sizing. This appendix provides a very brief review of these polynomials
and the equations used to generate them.
Figure 12 shows a set of polynomials which have the
property that, for values of x between –1 and 1, the polynomial
has peak magnitude of unity. A footnote in Section 3.2 pointed out that
the Russian engineer Chebyshev developed these polynomials as part of
design effort which required minimizing the maximum lateral excursion
of a locomotive drive rod. For each polynomial order, say M,
the objective is to choose the polynomial’s coefficients so that
it “ripples” between x= –1 and x=
1 and then proceeds off proportional to 
for values of  . Not only
did Chebyshev find such polynomials, he found that one exists for each
positive integer value of M, and that they are related through
a recursion equation, that is, the polynomial for M can be directly
obtained from the polynomials for M–1 and M–2.
Figure 12. Graphs of Chebyshev Polynomials of Orders
0 through 4
Consider the following recursion expression:
with initial conditions of
and
Note that both of these initial conditions meet (if trivially) the stated
criteria for being Chebyshev polynomials.
Using this recursion expression we find, for M from 0 to 5,
that:
These polynomials are plotted in Figure 12 and it may be confirmed by
inspection that they meet the stated criteria.
A surprising result is that there is yet another way to present these
polynomials. This method is given by the following equations:
Analytically it can be confirmed that these equations satisfy the recursion
seen in equation 26. To see that they describe the same polynomials as
seen in Figure 12, consider equation 35 for values of
between –1 and 1. For such values 
ranges between  and 0.
Thus  ranges between
 and 0, and 
cycles between –1 or 1 and 1, hitting M + 1 extrema
on the way, counting the endpoints. Similar analysis shows that equation
36 grows monotonically in magnitude as
does. In fact it is easy to show that 
assymptotically approaches
as gets much greater than
one.
This second form of the definition for Chebyshev polynomials is very
useful since it is a closed form and because it involves cosines, a functional
form appearing frequently in frequency-domain representations of filters.
In light of this a final twist might be noted. Equation 36 is in fact
superfluous given equation 35. To see this, consider evaluating equation
35 for = 2. It initially
appears that this won’t work, since arccosine cannot be evaluated
for arguments greater than unity. In fact it can, it’s just that
the result is purely imaginary. It is easy, using Euler’s definition
of the cosine, to see that the cosine of jx is the same as the
hyberbolic cosine of x. Thus, the arccosine of 2 is j times
the inverse hyperbolic cosine of 2, that is, j ·
1.31. Multiplying by M and taking the cosine of the product yields the
cosine of jMx, which is the hyperbolic cosine of Mx.
Thus, if imaginary arguments are permitted, then equation 35 suffices
to describe all of the Chebyshev polynomials. Back to top of page
Appendix C: Using a Chebyshev Polynomial to Estimate 
We desire that the oscillatory portion of the polynomial shown in Figure
2 correspond to the stopband region of the filter response and the
portion to correspond
to the transition from the stopband to the passband. This is achieved
by employing a change of variables from frequency
to the polynomial argument x
While many different types of variable changes could be employed, this
one matches the boundary conditions (an obvious requirement) but happens
to employ the cosine function, a member of the same family used to define
the Chebyshev polynomials.
With this change of variables we see that the transition band
is defined by the difference between 
and  . Using the closed,
but nonintuitive form of the K-th order Chebyshev polynomial, valid for
, we have then
To synthesize the desired impulse response using this windowing technique
we multiply the resulting window function by the sampled sinc function.
In this case, however, we desire that the cutoff frequency be as low as
possible, limiting at zero Hz. The associated sinc function equals unity
for all non-zero coefficients of the impulse response. Since the final
impulse response is the point-by-point product of the window and the sampled
sinc function, in this case the window itself is the resulting impulse
response. It suffices then to examine the properties of the N-th order
Chebyshev polynomial to see how the N-point optimal filter will behave.
To find the relationship between the required filter order N
and the attainable transition band ,
we first determine the proper value of K and then evaluate equation
38 at the known combinations of x and  .
To select K we note that all but one of the ripples in the polynomial’s
response are used in the stopband and these are split evenly between the
positive and negative frequencies. Thus a filter and window of order N
implies a Chebyshev polynomial of order
With this resolved we observe from Figure 2 that
These equations are manipulated to yield an expression for  .
Equation 37 is then used to obtain values for ,
corresponding to ,
and , corresponding to
. Their difference,
defined earlier to be the transition band ,
is then given by
Under suitable conditions this equation can be simplified considerably.
For example, in the limits of small
and large N, equation 43 reduces to equation
8.
Back to top of page
Footnotes
- He developed the concept of minimax design and a set of polynomials
which carry his name, not from filter design, but from the optimal design of piston
drive rods for steam locomotives. The polynomials are discussed more in Section
3.2 and Appendix B.
- Strictly speaking, the peak ripple excursions are equal in
magnitude, not in decibels. This subtlety is completely negligible for small values
of .
- The actual amount of computation depends on whether the data
is real- or complex-valued, whether the impulse response symmetry is exploited,
and whether interpolation or decimation is used. In all cases, however, R
is proportional to and ,
and therefore Figure 4 provides an accurate indication of the relative computational
complexity of the filters resulting from the different design methods.
- Frequency-domain filters are, of course, the counterexample.
- The variants are odd and even filter order and symmetric and
antisymmetric impulse responses.
- Various boundary conditions can make the actual number one
less or one more than the filter order.
| 
