Skip to content Skip to navigation

Connexions

You are here: Home » Content » Introduction to Finite Impulse Response Filters

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Introduction to Finite Impulse Response Filters

Module by: Ricardo Vargas. E-mail the author

This chapter discusses the problem of designing Finite Impulse Response (FIR) digital filters according to the lplp error criterion using Iterative Reweighted Least Squares methods. Section 1 gives an introduction to FIR filter design, including an overview of traditional FIR design methods. For the purposes of this work we are particularly interested in l2l2 and l∞l∞ design methods, and their relation to relevant lplp design problems. (Reference) formally introduces the linear phase problem and presents results that are common to most of the problems considered in this work. Finally, Sections (Reference) through (Reference) present the application of the Iterative Reweighted Least Squares algorithm to other important problems in FIR digital filter design, including the relevant contributions of this work.

Traditional design of FIR filters

(Reference) introduced the notion of digital filters and filter design. In a general sense, an FIR filter design problem has the form

min h ∥ f ( h ) ∥ min h ∥ f ( h ) ∥
(1)

where f(·)f(·) defines an error function that depends on hh, and ∥·∥∥·∥ is an abitrary norm. While one could come up with a number of error formulations for digital filters, this chapter elaborates on the most commonly used, namely the linear phase and complex problems (both satisfy the linear form f(h)=D-Chf(h)=D-Ch as will be shown later in this chapter). As far as norms, typically the l2l2 and l∞l∞ norms are used. One of the contributions of this work is to demonstrate the usefulness of the more general lplp norms and their feasibility by using efficient IRLS-based algorithms.

Traditional design of least squares (l2l2) FIR filters

Typically, FIR filters are designed by discretizing a desired frequency response Hd(ω)Hd(ω) by taking LL frequency samples at {ω0,ω1,...,ωL-1}{ω0,ω1,...,ωL-1}. One could simply take the inverse Fourier transform of these samples and obtain LL filter coefficients; this approach is known as the Frequency Sampling design method
[5], which basically interpolates the frequency spectrum over the samples. However, it is often more desirable to take a large number of samples to design a small filter (large in the sense that L≫NL≫N, where LL is the number of frequency samples and NN is the filter order). The weighted least-squares (l2)(l2) norm (which considers the error energy) is defined by

ε 2 ≜ ∥ ϵ ( ω ) ∥ 2 = 1 π ∫ 0 π W ( ω ) | D ( ω ) - H ( ω ) | 2 d ω 1 2 ε 2 ≜ ∥ ϵ ( ω ) ∥ 2 = 1 π ∫ 0 π W ( ω ) | D ( ω ) - H ( ω ) | 2 d ω 1 2
(2)

where D(ω)D(ω) and H(ω)=F(h)H(ω)=F(h) are the desired and designed amplitude responses respectively. By acknowledging the convexity of Equation 2, one can drop the root term; therefore a discretized form of Equation 2 is given by

ε 2 = ∑ k = 0 L - 1 W ( ω k ) | D ( ω k ) - H ( ω k ) | 2 ε 2 = ∑ k = 0 L - 1 W ( ω k ) | D ( ω k ) - H ( ω k ) | 2
(3)

As discussed in Appendix (Reference), equation Equation 3 takes the form of (Reference), and its solution is given by

h = C T W T W C - 1 C T W T W D h = C T W T W C - 1 C T W T W D
(4)

where W=diag(w)W=diag(w) contains the weighting vector ww. By solving Equation 4 one obtains an optimal l2l2 approximation to the desired frequency response D(ω)D(ω). Further discussion and other variations on least squares FIR design can be found in [5].

Traditional design of minimax (l∞l∞) FIR filters

In contrast to l2l2 design, an l∞l∞ filter minimizes the maximum error across the designed filter's frequency response. A formal formulation of the problem [1], [4] is given by

min h max ω | D ( ω ) - H ( ω ; h ) | min h max ω | D ( ω ) - H ( ω ; h ) |
(5)

A discrete version of Equation 5 is given by

min h max k | D ( ω k ) - C k h | min h max k | D ( ω k ) - C k h |
(6)

Within the scope of filter design, the most commonly approach to solving Equation 6 is the use of the Alternation Theorem
[2], in the context of linear phase filters (to be discussed in (Reference)). In a nutshell the alternation theorem states that for a length-NN FIR linear phase filter there are at least N+1N+1 extrema points (or frequencies). The Remez exchange algorithm [5], [1], [4] aims at finding these extrema frequencies iteratively, and is the most commonly used method for the minimax linear phase FIR design problem. Other approaches use more standard linear programming methods including the Simplex algorithm [3], [7] or interior point methods such as Karmarkar's algorithm [6].

The l∞l∞ problem is fundamental in filter design. While this document is not aimed covering the l∞l∞ problem in depth, portions of this work are devoted to the use of IRLS methods for standard problems as well as some innovative uses of minimax optimization.

References

  1. Antoniou, Andreas. (1993). Digital Filters: Analysis, Design, and Applications. (2nd). McGraw-Hill.
  2. Cheney, E. W. (1966). Intl. Series in Pure and Applied Mathematics: Introduction to Approximation Theory. McGraw-Hill.
  3. Chvatal, Vasek. (1980). Linear Programming. Freeman and Co.
  4. Cunningham, Edward. (1992). Digital Filtering: An Introduction. Houghton-Mifflin.
  5. Parks, T. W. and Burrus, C. S. (1987). Digital Filter Design. John Wiley and Sons.
  6. Ruzinsky, Steven A. (1989, Febr.). and Minimization via a Variant of Karmarkar's Algorithm. IEEE Trans. on Acoustics, Speech and Signal Processing, 37(2), 245-253.
  7. Strang, G. (1986). Introduction to Applied Mathematics. Wellesley-Cambridge Press.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks