Fast and Stable Least-Squares Approach For The Design of Linear Phase FIR Filters
Fast and Stable Least-Squares Approach For The Design of Linear Phase FIR Filters
Fast and Stable Least-Squares Approach For The Design of Linear Phase FIR Filters
6, JUNE 1998
1485
ON
ON
I. INTRODUCTION
(1)
where
1486
TABLE I
MAGNITUDE RESPONSE OF LINEAR PHASE FIR FILTERS
(9)
In this case,
and
(10)
(3)
..
.
..
.
(11)
..
..
..
.
(4)
OKUDA et al.: FAST AND STABLE LEAST-SQUARES APPROACH FOR THE DESIGN OF LINEAR PHASE FIR FILTERS
1487
where
(18)
(19)
are orthonormal functions, the optimal soWhen
lution is given by
(20)
and
(21)
is
Thus, if the system of orthonormal functions
constructed, we can obtain an optimal solution without the
need for extra computations.
Therefore, the problem of solving linear equations (3) is
converted into the problem of constructing the system of orthonormal functions
. In order to solve this problem, for example, we can in principle apply GramSchmidts
orthogonalization; however, it requires the iterative computation of integrals, and it is difficult to reduce the computation
time compared with solving a normal equation with Gaussian
elimination. In the next section, we propose a fast and stable
algorithm for constructing orthonormal functions, which is
based on the Chebyshev polynomial and a recurrence relation.
B. Design Algorithm
The th order Chebyshev polynomial
(12)
The cost function in (9) is rewritten as
is defined as
(13)
where
(22)
where
(14)
Using
basis function
, (22) is rewritten as
(23)
(16)
Then, the optimal closed-form solution
given by
(24)
of (3) is
which satisfies
(17)
(25)
1488
Then
1) For
: The second and third terms
in (32) are identically zero due to the supposition of the
in the first term
mathematical induction. Since
is a polynomial whose order is smaller than , this term
,
can be expressed by the linear combination of
. Therefore, the first term is zero under the
supposition of the mathematical induction. In this case, (32)
and
.
is necessarily satisfied independent of
: The second term in (32) is zero; there2) For
fore
(26)
composes a system of orthogonal functions
If
in , we can design FIR digital filters analytically. This
function satisfies the following important theorem [13].
Theorem 1Recurrence Relation: If
is an orthogonal function that satisfies (27) and
is an orthonormal function of
, then a
thon , which satisfies
order orthonormal function
(27) with the appropriate constant values
and
, exists.
(27)
(28)
Here
(33)
must hold to satisfy (32). Then, we express
as
and
(34)
and
.
Proof: In the case of
(35)
(29)
of (33) is
satisfies
(36)
(30)
Since
is normalized,
is determined as
(31)
Next, we assume that
orthonormal condition
satisfies the
, it
(37)
Equation (33) is rewritten as
(16)
where
denotes Kroneckers delta and is expressed by the
recurrence relation in (27).
expressed by (27) into (16)
Substituting
(38)
According to (27)
(39)
(32)
must be satisfied. We now prove the existence of
and satisfy (32).
and
OKUDA et al.: FAST AND STABLE LEAST-SQUARES APPROACH FOR THE DESIGN OF LINEAR PHASE FIR FILTERS
1489
satisfies
(41)
3) For
(42)
is obtained.
Therefore, with
of (41) and
of (42), the orthogonal
defined by (27) can be obtained.
function
By using the above recurrence relation, we can construct
a system of orthonormal functions very easily. Then, the frequency response is given by (20) and (21). It should be noted
that orthogonal functions can be derived using the recurrence
relation (27). However, when the orthogonal functions are used
in
instead of orthonormal functions, optimal coefficients
(17) increase exponentially, and numerical errors sometimes
arise, especially for
. In practice, this algorithm using
the orthonormal functions is more numerically stable, and an
optimal solution is obtained with little numerical error.
The flowgraph of this algorithm is shown in Fig. 2. In this
algorithm, each iteration includes six steps, and each step
computations. Since is generally selected in
requires
proportion to , this algorithm requires
computations.
A MATLAB program for designing a linear-phase FIR filter
is shown in Table II.
,
, and
already have
Note that
been derived in the main algorithm.
The computational complexity of the above steps is
. Since
is much smaller than , the computation
time required for these steps is very short compared with the
main algorithm. If is small, it is also possible to obtain the
filter coefficients easily by the IDFT.
Table III and Fig. 3 show a MATLAB program and a
flowgraph for obtaining filter coefficients (Algorithm 2), respectively.
V. EXAMPLES
AND
COMPARISON
1490
TABLE II
MATLAB PROGRAM OF MAIN ALGORITHM
OKUDA et al.: FAST AND STABLE LEAST-SQUARES APPROACH FOR THE DESIGN OF LINEAR PHASE FIR FILTERS
1491
TABLE III
MATLAB PROGRAM OF ALGORITHM 2
Fig. 6.
grid density of
was used. This specification is the
same as in the case of Fig. 1 in Section IV. Fig. 6 illustrates
the results of the proposed algorithm. The magnitude response
obtained using CLS2 is almost the same as that of CLS1. As is
pointed out in Section IV, CLS1 and CLS2 have a numerical
and the width of the transition band
problem when both
are large. However, the proposed method can achieve a better
magnitude response than the conventional methods.
Fig. 7 shows the plots of approximation error versus .
This error corresponds to the log of mean squared error, that is,
. Although the errors arising in CLS1 and Gaussian
plots.
1492
N . : Proposed algorithm,
OKUDA et al.: FAST AND STABLE LEAST-SQUARES APPROACH FOR THE DESIGN OF LINEAR PHASE FIR FILTERS
1493