0.5 Introduction to finite impulse response filters

This chapter discusses the problem of designing Finite Impulse Response (FIR) digital filters according to the $l_p$ error criterion using Iterative Reweighted Least Squares methods. [link] 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 $l_2$ and $l_{\infty }$ design methods, and their relation to relevant $l_p$ design problems. [link] formally introduces the linear phase problem and presents results that are common to most of the problems considered in this work. Finally, Sections [link] through [link] 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

[link] introduced the notion of digital filters and filter design. In a general sense, an FIR filter design problem has the form

where $f(·)$ defines an error function that depends on $h$ , and $\parallel ·\parallel$ 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\left(h\right)=D-\mathbf{C}h$ as will be shown later in this chapter). As far as norms, typically the $l_2$ and $l_{\infty }$ norms are used. One of the contributions of this work is to demonstrate the usefulness of the more general $l_p$ norms and their feasibility by using efficient IRLS-based algorithms.

Traditional design of least squares ( $l_2$ ) fir filters

Typically, FIR filters are designed by discretizing a desired frequency response $H_d\left(\omega \right)$ by taking $L$ frequency samples at $\{{\omega }_0,{\omega }_1,...,{\omega }_{L-1}\}$ . One could simply take the inverse Fourier transform of these samples and obtain $L$ filter coefficients; this approach is known as the Frequency Sampling design method [link] , 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\gg N$ , where $L$ is the number of frequency samples and $N$ is the filter order). The weighted least-squares $\left(l_2\right)$ norm (which considers the error energy) is defined by

where $D\left(\omega \right)$ and $H\left(\omega \right)=\mathcal{F}\left(h\right)$ are the desired and designed amplitude responses respectively. By acknowledging the convexity of [link] , one can drop the root term; therefore a discretized form of [link] is given by

As discussed in Appendix [link] , equation [link] takes the form of [link] , and its solution is given by

where $\mathbf{W}=\text{diag}\left(\sqrt{w}\right)$ contains the weighting vector $w$ . By solving [link] one obtains an optimal $l_2$ approximation to the desired frequency response $D\left(\omega \right)$ . Further discussion and other variations on least squares FIR design can be found in [link] .

Traditional design of minimax ( $l_{\infty }$ ) fir filters

In contrast to $l_2$ design, an $l_{\infty }$ filter minimizes the maximum error across the designed filter's frequency response. A formal formulation of the problem [link] , [link] is given by

A discrete version of [link] is given by

Within the scope of filter design, the most commonly approach to solving [link] is the use of the Alternation Theorem [link] , in the context of linear phase filters (to be discussed in [link] ). In a nutshell the alternation theorem states that for a length- $N$ FIR linear phase filter there are at least $N+1$ extrema points (or frequencies). The Remez exchange algorithm [link] , [link] , [link] 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 [link] , [link] or interior point methods such as Karmarkar's algorithm [link] .

The $l_{\infty }$ problem is fundamental in filter design. While this document is not aimed covering the $l_{\infty }$ 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.