INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS, VOL. 25, 179—197 (1997) THE SIMULTANEOUS APPROXIMATION OF MAGNITUDE AND PHASE BY FIR DIGITAL FILTERS. II: METHODS AND EXAMPLES ALEXANDER W. POTCHINKOV1 AND REMBERT M. REEMTSEN2* 1 IFP N12/21 (Ref. IIIC Forschungsförderung TU Berlin), Institut für Elektronik, TU Berlin, Sekr. EN3, D-10587 Berlin, Germany 2 Lehrstuhl für Ingenieurmathematik, Fakultät I, TU Cottbus, Postfach 101344, D-03013 Cottbus, Germany SUMMARY In the present second part of this paper the relations between earlier approaches, the new approach in part I of the paper and the problem of simultaneous approximation of magnitude and phase are discussed. In particular, we begin by reconsidering the methods of Cuthbert and Holt et al., Steiglitz, and Chen and Parks which are predecessors of our method. Afterwards, results of numerical experiments are presented. We especially design filters considered previously by other authors and compare the results obtained by our approach with others. These filters are obtained by the solution of unconstrained approximation problems. We finally demonstrate the abilities of our approach by presenting two filters, especially one of length 1000, where the requirements lead to additional constraints in the design problem. ( 1997 by John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) (No. of Figures: 17; No. of Tables: 2; No. of Refs: 15) 1. DISCUSSION OF DESIGN METHODS In the first part of the paper we investigated in particular the quality of an FIR filter obtained by the solution of the complex Chebyshev approximation problem CA with regard to a solution of the magnitude/phase problem MPA. (Both problems are given in Section 1 of part I.) Besides the mentioned approaches for the direct solution of the unconstrained problem CA in References 1—3 and the possibly constrained problem (SIP)CA of the authors in References 4—6, especially three earlier ways of approximately solving CA or MPA are known. These are the approaches of Cuthbert7 and Holt et al.,8 Steiglitz9, and Chen and Parks.10 These three approaches can be related to the error function e (h, u)"D(u)!H(h, u) (1) C of problem CA, which enables us to discuss the historical development of FIR filter design and the differences between the diverse approaches, including our own in Section 3 of part I. It is our first goal here and topic of Section 1.1 to describe the methods of Cuthbert and Holt et al., Steiglitz, and Chen and Parks in a unifying way. While Chen and Parks start from e (h, u) directly, Cuthbert C and Holt et al., and Steiglitz use complex-valued error functions which, for fixed h and u, evolve from e (h, u) C by a plane rotation around the origin. The particular design problem of the different authors can then be derived in such a way that e (h, u) in problem CA is replaced by the (rotated) error of the respective approach C and the so-obtained problem is linearized by a special type of linearization which geometrically means replacing a circle (l -norm in R2) by a rectangle or, as in the case ofthe methods of Steiglitz, and Chen and 2 Parks, by the smallest square enclosing this circle (maximum norm in R2). While a plane rotation of e (h, u) C * Correspondence to: R. M. Reemtsen, Lehrstuhl für Ingenieurmathematik, Fakultät I, TU Cottbus, Postfach 101344, D-03013 Cottbus, Germany. CCC 0098—9886/97/030179—19$17.50 ( 1997 by John Wiley & Sons, Ltd Received 28 April 1995 Revised 31 May 1996 180 A. W. POTCHINKOV AND R. M. REEMTSEN itself obviously does not change the solution of the correspondingly altered design problem (SIP)CA, the considerably differing results for the mentioned methods are due to the different effects of the linearizations of the respective error function. Since the methods of Cuthbert and Holt, Steiglitz, and Chen and Parks can be related to problem CA via the exchange of a norm, it is easy to get error estimates for the filters obtained by these methods with respect to the solution of problem CA. From these estimates it further follows immediately with Theorem 1 of part I that, like the minimal values of problems MPA and CA, the minimal values of the approximation problems of these earlier methods also tend to zero for NPR when Assumption 1 of part I is satisfied. The magnitude and phase errors for the filters obtained by the various approaches, including our own in Section 3 of part I, are studied in Section 1.2. It is argued that normally our approach leads to the smallest magnitude and phase errors, with the superiority of our approach becoming most evident in the design of filters for which BOBP is given. The arguments are confirmed by the numerical experiments given in Section 2. For the sake of simplicity we renounce again a weight function ¼(u) in the following discussion. 1.1. Earlier approaches We begin by considering the approach of Cuthbert7 and Holt et al.8 from 1974 and 1976 where for simplicity we assume N to be even. Application of the time-shifting property of the Fourier transform for the time interval of the filter half-length or, differently expressed, plane rotation of the complex error e (h, u) at (h u) C by the angle 0 (u)"u(N!1)/2 around the origin allows the splitting of the unit impulse response and its Fourier transform into their even and odd parts. If a (n) is the even and b (n) is the odd part of the unit h h impulse response h(n), n"0,1, 2 , N!1, the error function e (h, u) (equation (1)) of the complex Chebyshev C approximation problem CA can be written as e (h, u)"ReMe (h, u)N#jIm Me (h, u)N"e!ju(N!1)/2 (e (a , u)#je (b , u)) C C C CHE h CHO h with obvious definitions of e (a , u) and e (b , u).7,8 Hence, letting e (h, u) " : e (a , u)#je (b , u), CHE h CHO h CH CHE h CHO h one arrives at e (h, u)"e ju(N!1)/2e (h, u) (2) CH C expressing that e (h, u) is obtained by rotation of e (h, u) around the origin by the angle 0 (u). One can now CH C formulate the complex approximation problem for M " : N/2!1 CACH: o* " : min max D e (h, u)D" min max De (a , u)#je (b ,u)D CACH CH CHE h CHO h h3RN u3B a , b 3RM u3B h h which, because of the linearity of e (a , u) and e (b , u) with respect to a and b , can be written as CHE h CHO h h h a convex SIP problem analogously to problem CA and which, since De (h, u)D"De (h, u)D, has the same CH C solution as this. Instead of problem CACH (the actual solution of problems of type CA was not possible until the end of the 1980s), Cuthbert and Holt et al. solve the following two real linear Chebyshev approximation problems using the algorithm of McClellan and Parks:11 : min max D e (a , u)D LCACHE: o* " CHE a 3RM u3B CHE h h : min max D e (b , u)D LCACHO: o* " CHO b 3RM u3B CHO h h In general the minimal values o* and o* of LCACHE and LCACHO are not identical, as the numerical CHO CHE experiments by Schulist3 and the authors showed. The method of Cuthbert7 and Holt et al.8 was also published by Pei und Shyu12 in 1992 without reference to the earlier work. The work of Pei and Shyu is also extensively discussed in the thesis of Schulist.3 Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. 181 FIR DIGITAL FILTERS. II In order to demonstrate the analogy to the approaches of Steiglitz, and Chen and Parks considered next, we finally mention that the solution of the problems LCACHE and LCACHO is obviously identical with the solution of the weighted approximation problem A : min max w max D e (a , u)D, w max De LCACH: o* " (b , u)D CH a , b 3RM 1 u3B CHE h 2 u3B CHO h h h A B "min max w max DReMe (h, u)ND, w max D ImMe (h, u)ND 1 u3B CH 2 u3B CH h 3Rn B with weights w " : 1/o* and w " : 1/o* . The practical solution of problem LCACH would of course CHO 1 2 CHE require the a priori knowledge of the weights w and w . 1 2 ¹he approach of Steiglitz9 from 1981 starts from the complex error e (h, u), where for an allpass with C DD(u)D"1, u3B " : BP, Steiglitz introduced a complex-valued error function e (h, u) " : e!jbD (u) e (h, u)"DD(u)D!e!jbD(u) H(h, u), u3B (3) S C which is derived from e (h, u) by rotation of e (h, u) around the origin by the angle !b (u). Consequently, C C D the problem : min max De (h, u)D CAS: o* " CAS S h3RN u3B is also of the same type as problem CA when Dexp (!jb (u))D"1 is extracted from the problem, and it has D the same solution as this. Steiglitz then considers the generalized real linear Chebyshev approximation problem A : min max max DReMe (h, u)ND, max DImMe (h, u)ND LCAS: o* " S S S h3Rn u3B u3B B "min max max (DReMe (h, u)ND, DImMe (h, u)ND) S S h3RN u3B In order to obtain an approximate solution of this continuous problem, which can be written equivalently as a linear SIP problem, he proceeded in a way that was common at the beginning of the 1980s. He replaced the infinite set B in problem LCAS by a finite subset BI of frequencies, converted the so-discretized approximation problem into a finite linear optimization problem and solved that problem by the Simplex algorithm. Noting that the modulus DzD of a complex number z can be interpreted as the l -norm of the vector (ReMzN, 2 ImMzN)T in R2 and that the maximum norm of this vector is max (ReMzN, ImMzN), one can see that, similarly as LCACH from CACH, problem LCAS originates from problem CAS by linearizing CAS in such a way that the l -norm of (ReMe (h, u)N, ImMe (h, u)N)T is exchanged for the maximum norm. Hence, with respect to 2 S S the optimization problems corresponding to CAS and LCAS, a convex constraint J[(ReMe (h, u)N)2# S (ImMe (h, u)N)2])o is replaced by the constraint max (DReMe (h, u)ND, DImMe (h, u)ND))o or by the four S S S equivalent linear constraints $ReMe (h, u)N)o and $ImMe (h, u)N)o respectively. Hence, from a geoS S metric viewpoint, the requirement ‘h is such that (ReMe (h, u)N, ImMe (h, u)N)T lies in the disc with radius o’ for S S u3B is exchanged for the requirement ‘h is such that (ReMe (h, u)N, ImMe (h, u)N)T lies in the smallest square S S enclosing the disc’. ¹he approach of Chen and Parks10 from 1987 starts from the complex error e (h, u) directly and not from C a rotation of e (h, u). For our discussion we first relate to the normally used case ‘p"2’ in Reference 10, in C which case one arrives at the continuous linear approximation problem A : min max max DReMe (h, u)ND, max DImMe (h, u)ND LCA: o* " CP C C h3Rn u3B u3B ( 1997 by John Wiley & Sons, Ltd. B Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) 182 A. W. POTCHINKOV AND R. M. REEMTSEN Clearly, LCA is obtained from problem CA by the same kind of linearization which, as we showed, was also used by Steiglitz and, with additional weights, by Cuthbert and Holt et al. before. Like Steiglitz, Chen and Parks solved this problem in a discretized form as a finite linear optimization problem by the Simplex algorithm. The methods discussed up to now evolve from problem CA (with possibly rotated error) by exchange of the real l -norm for the real maximum norm, which, for (ReMzN, ImMzN)T3R2, with z3C, are related by 2 max (DReMzND, DImMzND))J[(ReMzN)2#(ImMzN)2]"DzD)J2 max (DReMzND, DIm MzND) (4) Therefore, applying (4) to e (h, u), e (h, u) and e (h, u) (equations (2), (3) and (1) respectively) and recalling CH S C that De (h, u)D"De (h, u)D"De (h, u)D, we deduce the following relationships between the minimal values of CH S C the linear programmes LCACH, LCAS and LCA and that of the Chebyshev problem CA: (5) o* )o* )J2 o* max (o* , o* ))o* )J2 max (o* , o* ), o*)o* )J2 o* , CP CA CP S CA S CHE CHO CA CHE CHO Together with Theorem 1 of part I, these estimates in turn lead to the following theorem in which we again denote the dependence of the respective minimal values on the coefficient number N. ¹heorem 1 Under Assumption 1 of part I we have lim o* (N)" lim o* (N)" lim o*(N)" lim o* (N)"0 N?= CHE N?= CHO N?= S N?= CP If, instead of by the square (case p"2), a disc in R2 is approximated by the smallest enclosing regular polygon with 2p edges for p'2, a better approximation of the disc and, when this idea is applied to problem CA, a more accurate linearization of CA is obtained, but at the price of 2p'4 constraints per frequency in the corresponding linear optimization problem instead of only four constraints. The latter explains the geometrical meaning and the effect of the variable ‘p’ in the paper of Chen and Parks. Thus obviously a linearization of CA as used by Chen and Parks for p'2 could likewise be performed for problem CAS and naturally would lead to a better approximate solution of CAS than that obtained from problem LCAS of Steiglitz. Eventually a disc can also be expressed exactly by infinitely many linear constraints given by the tangents of the disc. Application of this idea to problem CA or CAS results in infinitely many linear constraints per frequency in the corresponding optimization problem, which is just the approach of Alkhairy et al.,1, Schulist3, and Burnside and Parks.2 Since problem CAS is equivalent to problem CA, which in turn is equivalent to the above-mentioned completely linearized version of CA, application of the latter idea to CAS would result in the same problem that the authors of References 1—3 obtain for CA. It will, however, become obvious in the following sections that the solution of improved linearizations of CA or CAS, in comparison with LCA and LCAS, or even the direct solution of problems CA or CAS, does not necessarily yield a better approximate solution of problem MPA, since CA and CAS themselves only describe MPA approximately. 1.2. Comparative discussion We do not discuss the approach of Cuthbert and Holt et al. here further, since it does not have any advantages over the methods of Steiglitz, and Chen and Parks. In particular, fast methods for solving the linear SIP problems LCAS and LCA are available today and these methods in addition allow linear constraints for the requested filter,4 while it is not obvious how constraints on H(h,u) should be treated by the two real Chebyshev problems LCACHE and LCACHO above. In the following we therefore concentrate on filters which are designed by the solution of the linear problems LCAS and LCA of Steiglitz, and Chen Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. 183 FIR DIGITAL FILTERS. II and Parks on one hand and by solutions of the Chebyshev problem CA and problem CSIPMPA in Section 3 of part I on the other hand, where the effect of the discretization used by Steiglitz, and Chen and Parks is not respected. We mention that, except for problem MPA, all problems discussed up to now can be written as linear or non-linear convex SIP problems (analogously to the derivation of SIPMPA from MPA in Section 1 of part I). They could therefore be solved directly by our methods in References 4 and 6 in their continuous form, i.e. without use of a discretization. In order to illuminate the relationships between the diverse methods, we consider the respective ‘tolerance regions’ for the error o of the requested filter, assuming that o is sufficiently small (similarly as is required by Assumptions 2 and 3 in Section 2 of part I). With e!jbD(u)D(u)"DD(u)D and H (h, u) " : e!jbD(u)H(h, u) S (equation (3)), these are given by the following sets where u3BP is fixed: the set R(o):"MH(h, u)3CDmax (D DD(u)D!DH(h, u)D D, Darg(D(u))!arg(H(h, u))D))oN which belongs to problem (SIP)MPA and represents part of a circular ring in the complex plane with central angle 2o, inner radius DD(u)D!o and outer radius DD(u)D#o, and the corresponding set R*(o) " : MH (h, u)3CDmax(D DD(u)D!DH (h, u)D D, Darg(H (h, u))D))oN S S S related to the equivalent problem (2) of part I (see the left diagram of Figure 1); the sets R (o) " : MH(h, u)3CD DD(u)D!H(h, u)D)oN C and R (o) " : MH (h, u)3CD D DD(u)D!H (h, u)D)oN CS S S which concern the Chebyshev problems (SIP)CA and CAS and geometrically represent a disc with radius o around D(u) and DD(u)D respectively (see the right diagram of Figure 1); the sets R (o) " : MH (h, u)3C D max (D DD(u)D!ReMH (h, u)ND, DIm MH (h, u)ND))oN S S S S and R (o) " : MH(h, u)3C D max (DReMD(u)!H(h, u)ND, DIm MD(u)!H(h, u)ND))oN CP Figure 1. Tolerance regions for (rotated) problems MPA and CA ( 1997 by John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) 184 A. W. POTCHINKOV AND R. M. REEMTSEN concerning the linear problems LCAS and LCA of Steiglitz, and Chen and Parks respectively, which both represent squares in the complex plane with side lengths 2o and centers DD(u)D and D(u) respectively (see the left diagram of Figure 2); and, with o " : Jd, eventually the set R (o) " : MH (h, u)3C D max (D DD(u)D!ReMH (h, u)ND, DH (h, u)D!DD(u)D, DImMH (h, u)ND))oN PR S S S S for problem CSIPMPA from Sections 3 of part I which has the geometrical representation exhibited by the right diagram of Figure 2. We first deduce now a result on the minimal values of problem CA, problem CSIPMPA and the problem of Steiglitz. Relating to the sets R (o), R (o) and R*(o) for u3BP, we obviously have S PR max(D DD(u)D!ReMH (h, u)ND, DImMH (h, u)ND))max (D DD(u)D!ReMH (h, u)ND, DH (h, u)D!DD(u)D, DImMH (h, u)ND) S S S S S )D DD(u)D!H (h, u)D, u3BP S Together with max (DReMH (h, u)ND, DImMH (h, u)ND))DH (h, u)D, u3BS S S S for the stopbands, we arrive at (6) o*)o* )o* S PR CA : (o* )2 is the minimal value of problem CSIPMPA. In combination with Theorem for all filters, where d* " PR PR 1 of part I, the latter yields the subsequent result in which again the dependence of the respective values on N is denoted. ¹heorem 2 Under Assumption 1 of part I we have lim o* (N)" lim d* (N)"0 N?= PR N?= PR The relationships (5) and (6) between the minimal values of the diverse problems themselves do not provide information about the value of solutions of the respective problems with regard to the solution of the Figure 2. Tolerance regions for problems LCA, LCAS and CSIPMPA Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. 185 FIR DIGITAL FILTERS. II magnitude/phase problem. In order to get an idea about the size of these errors, we next make use of the geometrical representation of the tolerance regions in Figures 1 and 2. For that we define : max De (h, u)D, e.!9 (h) " M M u3B : sup De (h, u)D e.!9 (h) " b u3BP b (7) where we first consider the magnitude error only in passbands, i.e. we first set B"BP in (7). The tolerance regions of problems CA and CAS are circular, where the disc representing R (o) is obtained CS from the disc R (o) by rotation by the angle !b (u) around the origin. Therefore, the set of all h such that C D H(h, u) is in R (o) is identical with the set of all h such that H (h, u) is in R (o). Hence both problems CA and C S CS CAS have the same solution h* , as was already pointed out above. Further, when o* is the minimal value of CA CA problem CA, then H(h* , u) lies in R (o* ) for each u3BP, so that from Figure 1 one deduces the following CA C CA bound for the maximal magnitude and phase error at h* (see also Theorem 2 of part I): CA (8) max (e.!9 (h* ), e.!9 (h* )))max (o* , tan~1 (o* /(D !o* ))) CA CA .*/ CA CA CA b M When, instead of CA and CAS, the related linearized problems LCA and LCAS are considered, rotation of the square representing the tolerance region R (o) by the angle !b (u) around the origin does not yield the CP D square R (o). By a similar argument to that lending to (8), corresponding upper bounds for the maximal S magnitude/phase error can be derived from Figure 2 as follows. One has max (e.!9 (h* ), e.!9 (h* )))max (J2 o* , tan~1 (J2 o* /D )) CP .*/ CP CP M CP b for the solution h* and minimal value o* of problem LCA of Chen and Parks and CP CP A max (e.!9 (h*), e.!9 (h*)))max max (J[(DD(u)D#o*)2# o*2]!DD(u)D), tan~1 [o* /(D !o*)] M S b S S S S .*/ S u3BP (9) B (10) for the solution h* and minimal value o* of problem LCAS of Steiglitz. Finally, if h* solves problem PR S S : Jd* is given, where d* is the minimal value of CSIPMPA, one obtains CSIPMPA and o* " PR PR PR (11) max (e.!9(h* ), e.!9 (h* )))max (o* , tan~1 [o* /(D !o* )]) PR PR .*/ PR PR M PR b The maximal magnitude error in stopbands is obviously )o* and )o* for problems (SIP)CA PR CA and CSIPMPA respectively, where it is )J2 o* and )J2 o* in the case of problems LCAS and CP S LCA respectively. Hence for BOBP in (7) the estimates (8), (9) and (11) remain true, while (10) has to be replaced by (12) max (e.!9 (h*), e.!9 (h*)))max (J2o* , tan~1 [o* /(D !o* )]) S S .*/ S S M S b In all cases the maximal magnitude/phase error at the respective solution is obviously an upper bound for the minimal value o* of the magnitude/phase problem MPA. It is further easily concluded that the bounds MPA in (8)—(12) are the smallest possible ones in the sense that there can exist a filter for which the maximal magnitude or phase errors are identical with the given bounds. Evidently, these bounds depend on the minimal value of the respective problem, where the size of this minimal value is unpredictable. Except for the estimates (8) and (9) (by (5) the bound in (9) normally is larger than the one in (8)), the relationships (5) and (6) between the minimal values do not seem to be helpful in order to get an idea of the size of the bounds in (8)—(12) in relation to each other. A result like that, however, would also say little about the actual size of the errors for a particular design problem, since the estimates (8)—(12) only provide the worst possible errors. Thus each of the methods may turn out to be the best with respect to the maximal magnitude/phase error for a particular design problem. However, there are some indications, which are explained in the following and supported by our numerical results, that problem CSIPMPA normally yields the best solution among all discussed approaches. ( 1997 by John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) 186 A. W. POTCHINKOV AND R. M. REEMTSEN The problems LCAS and LCA of Steiglitz, and Chen and Parks evolve from the Chebyshev problem CA by a linearization of the same type. Thus it is likely that the minimal values of these problems have about the same magnitude (which is confirmed by the results in Table I below). When this is assumed, the bound in (10) (for BP"B) for the problem of Steiglitz turns out to be more favourable than the one in (9) for the method of Chen and Parks, while the bounds in (9) and (12), related to general filters, are about the same. This is seen also from Figures 1 and 2. The position of the square belonging to Steiglitz’s method seems to be more favourable with respect to the magnitude/phase error than that related to the method of Chen and Parks. Thus it may be expected (and indeed happens, as the following section shows) that for allpass filters the method of Steiglitz yields better approximate solutions of (SIP)MPA than does the method of Chen and Parks. When stopbands are involved, however, both methods, briefly speaking, replace the circle by the square and hence can lead to magnitude errors of the same size. Considering the solution of problem CA, similar statements are difficult to make. However, it can be observed at least that in problem CA the magnitude approximation in stopbands is identical with that in problem MPA and hence optimally stated with respect to this problem. The same is true for problem CSIPMPA in Section 3 of part I, which, at the occurrence of stopbands, is clearly superior to the methods of Steiglitz, and Chen and Parks. Comparing problems LCAS of Steiglitz and CSIPMPA further, we observe that, owing to the identity e8 (h, u)"ImMe (h, u)N for u3BP (equation (5) of part I), each constraint b CS DImMe (h, u)ND!o)0 in the SIP version of problem LCAS of Steiglitz is tantamount to the constraint CS e82 (h, u)!d)0 used in CSIPMPA for the control of the phase error. (In problem CSIPMPA, d stands for b o2.) Moreover, as also the geometrical representations of the corresponding tolerance regions R (o) and S R (o) exhibit, for BP"B problem CSIPMPA differs from the continuous problem LCAS in such way that PR for DH(h, u)D'DD(u)D the approximation of the magnitude is performed in the same way as in problem MPA and not by a linearization of the magnitude function as in LCAS. These arguments indicate that, on average, our approach should be somewhat better than the one of Steiglitz in the case BP"B and considerably better if BPOB. Also, since problem CSIPMPA is derived by a more careful treatment of the constraints in the SIP version of MPA (as also the forms of the respective tolerance regions show), one can expect the solution of CSIPMPA generally to provide a better approximate solution of the magnitude/phase problem MPA than does the solution of the Chebyshev problem CA. 2. NUMERICAL EXPERIMENTS In Section 2.1 we begin by discussing the design of three FIR allpass approximations, denoted briefly as allpass filters in the following. The respective problems provide examples of unconstrained filter design. Afterwards, in Section 2.2, we present two lowpass filters where bounds are set for the approximation errors of magnitude and phase in the passband and hence a constrained filter design problem has to be solved. 2.1. ¹hree examples of unconstrained approximation The three allpass filters of length N"61 given by Steiglitz9 were designed by four different methods and compared. In particular, the SIP problems SIPCA and CSIPMPA and discretized versions of problems LCA and LCAS suggested by Chen and Parks, and Steiglitz respectively were solved. For the solution of LCA and CAS, as in Reference 9, a grid B3 of 610 equidistantly chosen frequencies in [0, n] was selected. The corresponding linear optimization problems with 610]4"2440 linear constraints were then solved by the programme ‘LP’ of the MATLAB software.13 At the solution of these finite linear optimization problems, in the case of Steiglitz’s problem, stability problems occurred, as typical for such optimization problems (see Section 2.6 of Reference 4), and solution was only possible after o was factored by the weight 10~3. Problems SIPCA and CSIPMPA were solved with the method of Reference 6. Table I lists the definitions of the allpass filters and the results of the numerical experiments. The listed maximal modulus errors of the magnitude, the phase, the delay and the complex error (1) in the columns of Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. 187 FIR DIGITAL FILTERS. II Table I. Characteristics of designed allpass filters e.!9, M magnitude error e.!9, b phase error e.!9, q delay error e.!9, C complex error o*, defect Allpass no. 1 (Chirp allpass): N"61, D(u)"e jbD(u), b (u)"!30 u#(8/(2n)) (u!n/2)2, u3BP"[0, n] D SIPCA 4·42213]10~4 4·44592]10~4 4·35211]10~2 4·44593]10~4 4·44593]10~4 CSIPMPA 3·80126]10~4 3·80271]10~4 4·03802]10~2 5·37630]10~4 3·80126]10~4 LCAS 3·80727]10~4 3·81081]10~4 4·03747]10~2 5·38391]10~4 3·79835]10~4 LCA 4·33861]10~4 4·28589]10~4 4·63339]10~2 5·10236]10~2 3·80392]10~4 Allpass no. 2 (Twin-delay allpass): N"61, D(u)"e!j34u, u3BP1"[0, n/2]; D(u)"e!j26u, u3BP2"(n/2, n] SIPCA CSIPMPA LCAS LCA LCACHE/LCACHO 3·87304]10~2 3·46794]10~2 3·20045]10~2 3·85018]10~2 — 3·88056]10~2 3·59580]10~2 4·24513]10~2 4·23475]10~2 — 4·0000033 4·0000045 4·0 4·018987 — 3·88251]10~2 4·95034]10~2 5·20191]10~2 4.23475]10~2 3·87792]10~2 3·88251]10~2 3·46794]10~2 3·14978]10~2 3·21793]10~2 — Allpass no. 3 (Sine-delay allpass): N"61, D(u)"e jbD(u), b (u)"!30 u#2n (1!cosu), u3BP"[0, n] D SIPCA 9·70321]10~4 9·71318]10~4 1·01426]10~1 9·71320]10~4 9·71320]10~4 CSIPMPA 9·32917]10~4 9·33776]10~4 9·94399]10~2 1·31747]10~3 9·32917]10~4 LCAS 9·34819]10~4 9·34696]10~4 9·93923]10~2 1·31528]10~3 9·31624]10~4 LCA 9·43940]10~4 1·02171]10~3 1·03872]10~1 1·02656]10~3 8·09811]10~4 Figure 3. Allpass no. 1, error plots via SIPCA ( 1997 by John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) 188 A. W. POTCHINKOV AND R. M. REEMTSEN Figure 4. Allpass no. 1, error plots via CSIPMPA the table were computed on 216"65,536 equidistant frequencies in [0, n] for the obtained solution of the problem given in the respective row of Table I. The value of o* refers to the minimal value of the problem in the case of problems LCA and LCAS and equals Jd* in the case of problems SIPCA and CSIPMPA, where d* is the minimal value of these problems. For each of the filters obtained by solution of SIPCA and CSIPMPA, four graphs are presented, where Figure 3 and 4 refer to allpass no. 1, Figures 5 and 6 to allpass no. 2 and Figure 7 and 8 to allpass no. 3. These four graphs represent the modulus of the complex error function (1) (‘complex error’) and the error functions of the magnitude (‘magnitude error’), the phase (‘phase error’) and the group delay (‘delay error’) on BP. The corresponding graphs for the solution of problem LCAS do not differ seriously from the respective ones for CSIPMPA, so they are not given here. For allpass no. 2, the result in Table I for the complex approximation error of the method of Cuthbert and Holt et al. is taken from the thesis of Schulist.3 Since this error is smaller than the smallest possible error obtained by the solution of the (continuous) problem SIPCA, it may be concluded that Schulist used a rather coarse finite sample set of frequencies in BP in order to compute the error. In this connection it has to be noted that the desired phase b (u) is discontinuous at u"n/2 for allpass D no. 2. However, the prescription D(u) itself is continuous at u"n/2 in that case and hence this discontinuity does not have any obvious effects for the diverse methods, except for the method of Cuthbert and Holt et al. which, according to Schulist, leads to significant errors in such a case. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. 189 FIR DIGITAL FILTERS. II Figure 5. Allpass no. 2, error plots via SIPCA Figure 6. Allpass no. 2, error plots via CSIPMPA ( 1997 by John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) 190 A. W. POTCHINKOV AND R. M. REEMTSEN Figure 7. Allpass no. 2, error plots via SIPCA Figure 8. Allpass no. 3, error plots via CSIPMPA Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. 191 FIR DIGITAL FILTERS. II For all three allpass filters the maximum of both ‘magnitude error’ and ‘phase error’ turns out to be significantly larger for the filters obtained by the solution of LCA and SIPCA than for the filter obtained from CSIPMPA. The improvement by solution of CSIPMPA is especially seen from the envelope curves of magnitude and phase for the filter obtained from SIPCA. It is remarkable that the results for these allpass filters obtained by the approach of Steiglitz partially have the same quality as those reached by solution of CSIPMPA. We conclude with some remarks referring to the work of Pei and Shyu.12 In Reference 12, allpass filters obtained from the solution of ¸ -approximation problems are compared with the allpass filters of Steiglitz.9 2 (See also Reference 14 in this context.) Pei and Shyu point out the small computing times of about 20 s on a VAX 11/780 and remark that the results of their ¸ -approximation are ‘better in most of the frequency 2 band except near the zero and folding frequencies’ (Reference 12, p. 144). To us, however, it does not seem appropriate to compare the results of ¸ -approximation with those of ¸ -approximation, since it is well 2 = known that in the case of ¸ -approximation the error can increase in the neighbourhood of the interval 2 boundaries which, for example, can be seen at Gibbs’ phenomenon in connection with Fourier series.15 The avoidance such increases just required the use of ¸ -approximation and, as our computing times of 10—20 = seconds on an IBM RS6000-350, for example, for the design of the allpass filters above show, ¸ = approximation does not necessarily mean large computing times. It has further to be noted that ¸ 2 approximation over the total interval [0, n] as in the case of allpass filters simply results in a Fourier sum for which the coefficients defined by integrals can be taken from any mathematical handbook. Thus application of the ‘eigenfilter’ method is not necessary in such a case. 2.2. Examples of constrained approximation We designed two nearly linear phase lowpass filters with bounds on the magnitude and phase error according to problem (7) of part I. The first filter was designed twice, first by solution of our SIP problem CSIPMPA and secondly by solution of the Steiglitz problem LCAS, where for LCAS a discretization of 710 equidistant frequencies in the passband and stopband was chosen. The characteristics of the obtained filters h* are summarized in Table II analogously to Table I. In contrast with the CSIPMPA filter, the LCAS filter violates the prescribed magnitude and phase bounds in the passband by 13% and 9% respectively. The stopband magnitude error differs significantly from the defect o*, which clearly is an effect of the above-described linearization used by Steiglitz. We note that in the case of problem CSIPMPA, o* also gives the maximal magnitude error in the stopband. Figures 9—12 illustrate the CSIPMPA and LCAS filters. For the passband, Figure 9 shows the magnitude and phase errors of the LCAS filter and Figure 10 those obtained by solution of CSIPMPA. Figure 11 and 12 present the stopband magnitudes of the LCAS and CSIPMPA filters respectively. Table II. Characteristics of designed lowpass filters Magnitude error passband Magnitude error stopband e.!9 b phase error e.!9 q delay error e.!9 C complex error o* defect ¸owpass no. 1: N"70, D(u)"exp (!ju20), º (u)"º (u)"1]10~3 for u3BP:"[0, 0·12n] and D(u)"0 for M b u3BS:"[0·24n,n] CSIPMPA LCAS 1]10~3 2·36660]10~4 1]10~3 1·84341]10~1 1·38374]10~3 2·36660]10~4 1·13134]10~3 2·70868]10~4 1·09031]10~3 2·03305]10~1 1·54957]10~3 1·92412]10~4 ¸owpass no. 2: N"1000, D(u)"exp (!ju400), º (u)"º (u)"1]10~3 for u3BP:"[0, 0·12n] and D(u)"0 for M b u3BS:"[0·128n,n] CSIPMPA 1]10~3 ( 1997 by John Wiley & Sons, Ltd. 8·08504]10~4 1]10~3 8·53216]10~1 1·41289]10~3 8·08504]10~4 Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) 192 A. W. POTCHINKOV AND R. M. REEMTSEN Figure 9. Lowpass no. 1, passband magnitude and phase errors via LCAS Fig. 10. Lowpass no. 1, passband magnitude and phase errors via CSIPMPA Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. 193 FIR DIGITAL FILTERS. II Figure 11. Lowpass no. 1, stopband magnitude error via LCAS Figure 12. Lowpass no. 1, stopband magnitude error via CSIPMPA ( 1997 by John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) 194 A. W. POTCHINKOV AND R. M. REEMTSEN Figure 13. Lowpass no. 2, magnitude Figure 14. Lowpass no. 2, modulus of complex error Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. 195 FIR DIGITAL FILTERS. II Figure 15. Lowpass no. 2, passband magnitude error Figure 16. Lowpass no. 2, passband phase error ( 1997 by John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) 196 A. W. POTCHINKOV AND R. M. REEMTSEN Figure 17. Lowpass no. 2, passband delay error In order to demonstrate the capabilities of our approach via CSIPMPA and of the method in Reference 6, we designed a second lowpass filter of the same type with length N"1000. The characteristics of the obtained filter are likewise summarized in Table II. The filter is illustrated by Figures 13—17. For the passband and stopband in each case, Figures 13 and 14 show the magnitude and the modulus of the complex error function respectively. For the passband alone the error functions of magnitude, phase and group delay are given in Figures 15—17. 3. CONCLUSIONS If the aim of FIR filter design is the simultaneous approximation of prescriptions for magnitude and phase, then solution of the complex Chebyshev approximation problem (SIP)CA or problem LCA of Chen and Parks leads to significantly worse results than the solution of problem CSIPMPA, as examples of allpass filters showed. The numerical behaviour, i.e. the number of iterations and hence the total computing time of the method in Reference 6, however, may vary considerably when applied to SIPCA and CSIPMPA and may be more favourable for the first or the second one depending on the problem. For allpass filters also the approach of Steiglitz showed excellent results, but not for problems involving stopbands, as could be expected. Our approach via formulation of an SIP problem allows the addition of finitely many linear equality and arbitrarily many convex (and hence especially linear) inequality constraints in problems MPA and CA respectively (‘constrained filter design’), since such additional constraints do not cause any particular difficulties in the then still convex programmes SIPCA and CSIPMPA respectively. The potential for solving constrained problems, for example, opens the possibility of controlling the approximation error of the group Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997) ( 1997 by John Wiley & Sons, Ltd. FIR DIGITAL FILTERS. II 197 delay advantageously. Further, the use of the method in Reference 6 not only allows high filter degrees but also yields an accuracy which presently is not reached by any other method. REFERENCES 1. A. S. Alkhairy, A. F. Christian and J. S. Lim, ‘Design and characterization of optimal FIR filters with arbitrary phase’, IEEE ¹rans. Signal Process. 41, 559—572 (1993). 2. D. Burnside and T. W. Parks, ‘Accelerated design of FIR filters in the complex domain’, Proc ICASSP, IEEE, New York, 1993, pp. III-81—III-84. 3. M. Schulist, ‘Ein Beitrag zum Entwurf nichtrekursiver Filter’, Ph.D. ¹hesis, University of Erlangen-Nürnberg, 1992. 4. A. Potchinkov and R. Reemtsen, ‘FIR filter design in the complex domain by a semi-infinite programming technique. I. The method’, AEº® , 48, 135—144 (1994). 5. A. Potchinkov and R. Reemtsen, ‘FIR filter design in the complex domain by a semi-infinite programming technique. II. Examples’, AEº® , 48, 200—209 (1994). 6. A. Potchinkov and R. Reemtsen, ‘The design of FIR filters in the complex plane by convex optimization’, Signal Proc. 46, 127—146 (1995). 7. L. G. Cuthbert, ‘Optimizing non-recursive digital filters to non-linear phase characteristics’, Radio Electron. Eng. 44, 645—651 (1974). 8. A. G. Holt, J. Attikiouzel and R. Bennett, ‘Iterative technique for designing non-recursive digital filter non-linear phase characteristics’, Radio Electron. Eng., 46, 589—592 (1976). 9. K. Steiglitz, ‘Design of FIR digital phase networks’, IEEE ¹rans. Acoust., Speech, Signal Process., ASSP-29, 171—176 (1981). 10. X. Chen and T. W. Parks, ‘Design of FIR filters in the complex domain’, IEEE ¹rans. Acoust., Speech, Signal Process., ASSP-35, 144—153 (1987). 11. J. H. McClellan and T. W. Parks, ‘A unified approach to the design of optimal FIR linear-phase digital filters’, IEEE ¹rans. Circuit ¹heory, CT-20, 697—701 (19973). 12. S.-C. Pei and J.-J. Shyu, ‘Design of real FIR filters with arbitrary complex frequency responses by two real Chebyshev approximations’, Signal Process. 26, 119—129 (1992). 13. MA¹¸AB, The MathWorks, Inc.’, Natick, MA, 1922. 14. T. Q. Nguyen, ‘The design of arbitrary FIR digital filters using the eigenfilter method’, IEEE ¹rans. Signal Process., SP-41, 1128—1139 (1993). 15. R. W. Hamming, Digital Filters, 2nd edn, Prentice-Hall, Englewood Cliffs, NJ, 1983. . ( 1997 by John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl., Vol. 25, 179—197 (1997)

1/--страниц