Abstract: The minimax optimization is widely used in wireless communications to design the equiripple lowpass filter, such as the Linear Programming (LP) method. However, the conventional LP method suffered from its large computation loads. Hence, this study investigates an iterative LP method, in which constraints are iteratively thrown on the non-uniformly distributed frequency grid to reduce the problem scale as much as possible, resulting in much lower computations. Moreover, since the non-uniform frequency grid allows us to precisely control the ripple, the proposed method also yields a better equiripple result compared to the conventional LP method and the Particle Swarm Optimization (PSO) algorithm.
INTRODUCTION
Digital filters have been widely used in digital signal process, such as the speech coding, the image processing and the matched filter in digital communications (Lyons, 2004; Lee and Miller, 1998; Oppenheim et al., 1999). There are two kinds of filters, namely the Finite Impulse Response (FIR) filter and the Infinite Impulse Response (IIR) filter (Hua et al., 2012; Lai and Lin, 2010; Jiang and Kwan, 2010). Since, the linear phase property is important in wireless communication systems (Proakis, 2000; Ruan et al., 2012), the authors pay attention to the linear phase FIR filter in this study. Moreover, because the Low-Pass Filter (LPF) is widely used in wireless communications, only the LPF design is studied in this study.
There are many FIR LPF design algorithms including the window method, the frequency sampling method, the Least Squares (LS) method (Selesnick et al., 1996; Zhang and Wu, 2011), PM algorithm (Antoniou, 1982) and the linear programming method (LP) (Rabiner, 1972) (Samueli, 1988). Among these methods, the window method and the frequency sampling method are simple but difficult to produce the equiripple filter. Moreover, previous work indicated that the LPF of wireless systems requests very rigorous performance specification (Lee and Miller, 1998) and these strict requirements make the LS method yields only the coarse equiripple filter. Even though the original PM algorithm is very efficient, it cannot take into account some special frequency domain constraints directly. Thus, by utilizing complicated iterative techniques (Lai, 2002; Lai and Zhao, 2006) proposed constrained Chebyshev methods for equality and inequality constraints which usually required more than ten iterations.
Another optional minimax method in LPF design is the non-iterative LP (NILP) method (Rabiner, 1972) which can make use of both the weight W and the variable frequency domain constraints. However, the NILP method uniformly discretizes the frequency range ([0, ωp]∪[ωs, π]) into G discrete points, denoting as vector ωD. These operations cause two drawbacks. First, the obtained passband (stopband) ripple would be larger than the desired ripple slightly and the deviation is proportional to 1/G approximately. Second, the number of constraints must be as twice larger as the discrete frequency number (G) which increases the scale of the optimization problem. Aside from the NILP method, Samueli (1988) had exploited non-uniform ωD and the exchange algorithm in his LP based Nyquist filter design, where he mainly focused on the Inter-Symbol-Interference (ISI). However, the ordinary LPF is quite different from the Nyquist filter, where people care for another three performance specifications instead of the ISI: ripples, transition band and stopband attenuations. Hence, Samuelis method cannot be applied to design the LPF directly.
In this study, after constructing a W-driven optimization model analogous to the previous literature (Rabiner, 1972; Samueli, 1988), an iterative LP (ILP) method is presented to design the linear phase LPF, where constraints on the non-uniformly distributed frequency grid are employed to relieve the requirement of discrete frequency number G. In each iteration, the nonlinear root-finding method, i.e., Newton method (Yang et al., 2005), is employed to refine the discrete frequency in the local peak of zero-phase responses which improves the precision of frequency vector ωD and helps to accelerate convergence. In addition, it had been well-known that the stop criterion was important for an iterative algorithm, thus, a comparative study on some stop criteria are also presented in this study in terms of the convergence and the equiripple error. Moreover, in order to provide engineers more flexible alter-natives to confront real-world requirements, another two optimization models are introduced with the above iterative technique, where the proposed algorithm suppress δp (δs) directly while minimize δs (δp) thereafter.
Of course, all the methods mentioned above are deterministic in nature. With the rapid development of computation algorithms, the heuristic algorithm had been applied in filter design, such as the particle swarm (PSO) algorithm (Kennedy and Eberhart, 1995; Zhan et al., 2009). These heuristic algorithms are non-deterministic and capable of dealing with both convex and non-convex optimization problems. A comparison between the ILP and PSO algorithm is also provided in our study.
CONVENTIONAL LP METHOD
Linear phase FIR filters: For linear phase FIR filters, the filter coefficient vector h must satisfy:
| (1) |
where N denotes the filter length and the symmetric coefficient ensures the linear phase (Oppenheim et al., 1999). Without loss of generality, the authors focus on the type I lowpass filters, whose zero phase response can be found as:
| (2) |
where ωε[0, π]. Equation 2 can be written in matrix form:
| (3) |
where, [.]T represents the transposing operation:
and
Performance specifications and constraints: Given the filter length N, the filter performance specification includes the stopband attenuation As, the ripples (δp, δs) and the transition width B (that defined by two cutoff frequencies ωp and ωs). Their relationships are analogous to three angles in triangle (Losada, 2004), i.e., one can at most select the values of two of the above specifications while the third specification will be determined by the optimization algorithm.
According to Losada (2004), when N and δp are fixed, improving δs or As equivalently will lead to the increase of the transition band width. The following constraints can be used to limit the transition band width:
| (4) |
which is a part of constraints in conventional LP (CLP) methods. It is equivalent to enforce the actual passband cut-off frequency to be no less than the specification ωp and the actual stopband start frequency to be no more than the specification ωS.
The CLP method in LPF design: Generally, the weighted approximation error obeys:
| (5) |
When the error curve of E(ω) has equal peaks in the passband, the filter is known as the equiripple filter. In Eq. 5, the weighting function:
and the desired zero-phase response:
Similar to PM algorithm, the CLP optimization model Eq. 6 aims to minimize the weighted ripple both in passband and stopband while ωp, ωS and the weight value W (equals to δp, δS) satisfying the specification:
| (6) |
where, the ripple δ is regarded as the optimizing variable and ωk is an element of the frequency vector ωD.
ILP METHOD DERIVATION
Evaluating the extreme frequencies: Before detail discussions, a frequency vector ΩM, corresponding to the extremum of the zero-phase response, should be defined according to the equation:
| (7) |
The actual passband and stopband ripple are determined by approximation errors on the frequency ΩM and the boundary frequency {0, π}. As for the equiripple LPF, the specification ωp and ωS must be the alternate points (Oppenheim et al., 1999). Hence, people must take into consideration the frequency vector Ωextrm comprised by ΩM and the boundary frequencies {0, ωp, ωS, π}. Now Ωextrm can be obtained by solving Eq. 7 by the Newton root-finding method and an acceptable solution can be obtained in about 4~5 iterations with absolute error less than 10-12.
ILP method: Similar to Samueli (1988), Ωextrm is not the subset of ωD which means that the frequency domain constraints havent been imposed on Ωextrm. Therefore, the absolute approximation error on frequency Ωextrm tends to be slightly larger than δp, δS in model Eq. 6, i.e., the real-world ripple value would be larger than the desired value and the deviation is determined by the difference of Ωextrm and the closest element in ωD. In fact, the above deviation indicates that the filter designed by the CLP method is not the optimum filter in the sense of minimax approximation due to the coarse conversion from the Semi-Infinite Linear Programming (SILP) to Finite Linear Programming (FLP). The conclusion is supported by simulations given in section 4.
Scrutinizing in Eq. 6, people explicitly see that the constraint number is twice times as the element number of ωD, viz., 2G. The countermeasure to reduce the above deviation is to increase G which leads to the constraint number grows rapidly and results in heavy computation loads. Therefore, the compromise has to be made between the desired performance specification and the computation efficiency which is the bottleneck of the CLP method in the FIR filter design.
One can imagine that if all constraints are imposed on Ωextrm, the ripple in discretized model Eq. 6 can be suppressed precisely. In fact, provided with constraints on Ωextrm, people dont need to import any other frequency constraints. Therefore, its enough to impose only one constraint on each element of Ωextrm while the CLP method requires two. According to Oppenheim et al. (1999), there are no more than (N+5)/2 elements (alternate points) in Ωextrm, resulting in small constraint amounts. This strategy avoids the degeneration of constraints in the conversion from the SILP and to FLP and ensures that the filter coefficient vector h produced by the ILP method is equivalent to solution of the semi-infinite programming model.
In essence, the ILP method is a kind of exchange algorithms which is similar to the Remez exchange algorithm in (Antoniou, 1982) and Multi-exchange algorithm in (Adams, 1991; Selesnick et al., 1996). Moreover, the proposed algorithm absorbs the exchange idea and extends CLP method to more general cases. The iterative algorithm is given as follows:
| Step 1: | Initializing the frequency vector ωD, i.e., discretizing [0, ωp]∪[ωS, π] into G points |
| Step 2: | Substituting ωD into a discretized model, such as Eq. 6 or other models to be presented in the next and calculating the filter coefficient vector h |
| Step 3: | Calculating the new frequency vector Ωextrm |
| Step 4: | Checking the stop criterion. If the stop criterion to be discussed in the next is satisfied, go to (step 7). Otherwise, go to (step 5) |
| Step 5: | Substituting the frequency vector Ωextrm into discretized model. To be specific, the elements corresponding to the local maximum in the zero-phase response use the first or the third inequality constraint in the selected LP model while the elements corresponding to the local minimum in the zero-phase response use the second or the fourth inequality constraint |
| Step 6: | Solving the LP problem and update the filter coefficient vector h. Go to (step 3) |
| Step 7: | Stop |
The initial frequency is generated in passband and stopband uniformly, where the passband includes:
points and the stopband includes:
points (
Stop criteria applications: Several stop criteria can be applied in the proposed ILP methods. The first is:
| (8) |
where, Ωkextrm, ||x|| and εΩ represent the Ωextrm of the kth iteration, the vector length and a small positive threshold, respectively. The second criteria is similar as that in (Antoniou, 1982), i.e.:
| (9) |
where, max (x) and min (x) represent the maximum and the minimum of vector x. Note that E (x) is defined in Eq. 5. The cost ΛW characterizes the equiripple condition by taking into account the dynamic range of the weighted approximation error in Ωextrm.
There had been a conclusion on the one-point exchange in by Powell (1981), viz., the exchange algorithm produced a bounded equiripple error (formula 8.16) and the error tends to be the same for adjacent iterations (formula 8.24). Then, the following criterion can be derived:
| (10) |
where, Ask and |x| denotes the stop attenuation at the kth iteration and the absolute value of x.
According to Cetin et al. (1997), the iteration terminates when there is no significance change in the filter coefficient vector h, such as:
| (11) |
where, hk means the filter coefficient vector at the kth iteration. All above stop criteria are suitable for the proposed ILP method and which one produces the fastest convergence speed and the best equiripple performance, will be deeply investigated in the next section.
Additional optimization models: In order to enrich the optimization option, another two optimization models can be as follows:
| (12) |
where, both the filter coefficient vector h and the stopband ripple δS are regarded as decision variable. The other is to minimize the passband ripple with fixed transition band and stopband ripple δS:
| (13) |
where, the decision variables are the filter coefficient vector h and the passband ripple δp.
Since, all three models are convex in nature, no matter which model is used, the resulting tradeoff is the fundamental tradeoff (Davidson, 2010) and cannot be outperformed by any other models (Powell, 1981) which implies that once the specification is given, all three models could yield the same results. This pleasing conclusion gives engineer more flexibility of model choice in practical designs.
EXAMPLES AND ANALYSIS
Here, all frequencies are normalized by the sampling frequency.
Example 1: Stop criterion discussion:
| • | Specification A: N = {49, 75}, ωp = 0.24π, ωS = 0.30π the logarithmic ripple Rp = 2 dB, where: |
| • | Specification B: N = 49, ωp = 0.24π, ωS = 0.30π, Rp = {0.2, 2} dB |
| • | Target: Comparing the cost functions with the ILP method for model (12) |
From Fig. 1, all four cost functions (stop conditions) yield similar curves and after six iterations, there exist no significant variations for ΛΩ, ΛW, Λs and Λh which indicates that the proposed ILP algorithm can converged in about six iteration, i.e., the convergence speed is fast and acceptable. Moreover, according to the turning points in Fig. 1, people clearly see that reasonable thresholds {εΩ, εW, εs, εh} can be {10-16, 10-6, 10-6, 10-16}, respectively.
| Fig. 1: | Stop condition comparisons in example 1 |
| Fig. 2: | Magnitude response in example 2: x-axis is the digital frequency and y-axis is the response amplitude |
Since, the cost function εW depicts the equiripple degree directly, this study chooses εW = 10-6 as the stop criterion in the next and other three stop criteria can be analyzed similarly.
Example 2: Comparisons of three optimization models:
| • | Specification: N = 49, ωp = 0.24 π, ωS = 0.30π, Rp = 2 dB |
| • | Target: Comparing the ILP method for model 6, 12 and 13 |
Test result is shown in Fig. 2 which supports the conclusion that specifications achieved by three different models are the same. It is this equivalence that provides engineers more optimal model alternatives in real-world applications.
| Table 1: | Test result of example 3 |
| CLP: Conventional LP method, ILP: Iterative LP method | |
Example 3: the LPF design in the GMC wireless systems:
| • | Specification: The prototype LPF in the Generalized Multi-Carrier (GMC) system (Hua et al. 2004), where, N = 217, ωc = 1/18π, Rp = 0.2 dB, roll-off factor α equals 0.20 |
| • | Target: Minimizing the stopband attenuation As |
Here only inequality constraints are imposed on the passband and stopband. Examples with transition constraints, i.e., the constraint on ωc, are to be given in Example 4.
In the CLP method, there are:
frequency points uniformly distributed in [0, ωp] ([ωS, π]). G may equal 2 N or 8 N for different precisions. Test results are shown in Table 1 and Fig. 3, where CLP and ILP represent the CLP method and the proposed ILP method. Note I.t. denotes the iteration times and dB is the logarithmic unit.
From Fig. 3 and Table 1, people explicitly see that the CLP method produces frequencies (ωp, ωS) slightly deviated from the desired specification and the deviation decreases as G increases.
| Fig. 3: | Magnitude response in example 3: x-axis is the digital frequency and y-axis is the response amplitude |
However, the proposed ILP method produces accurate frequencies (ωp, ωS) exactly equal to the desired specification. Moreover, the proposed method fixed the passband ripple to 0.2 dB precisely while the conventional method yields a slightly larger passband ripple due to that the constraint condition doesnt impose on Ωextrm. In addition, the computation load of the CLP method increases drastically as G increases. For example, in the case that G equals 8 N, it takes about ten seconds, whereas the ILP method only takes about four seconds which once again suggests its superiority to the CLP method.
Example 4: The bandwidth constraint.
In wireless communications, sometimes people care for the signal bandwidth, generally the -3 dB bandwidth denoted by ωc. if ωc is constrained, what happens?
| • | Specification: The same as example 3 |
| • | Target: Investigating the influence of ωc constraint |
Table 2 illustrates the influence of constraint on ωc. Compared with Table 2, ωS and Rp are remains unchanged while As degrades significantly. If one fixes ωc = 1/18π precisely, the worst case is presented. Relaxing the constraint ωc, i.e., allowing ωc ranges from ωc (1-ζ) to ωc (1+ζ), better As can be achieved. On the other hand, the constraint on ωc results in larger Rp which reduces the transition band width and brings benefits in some sense.
| Table 2: | Test results of example 4 |
To sum up, if one has to constrain ωc, he had better throw a range constraint and increase the filter length to ensure As≥40 dB.
Example 5: Comparison with the PSO algorithm:
| • | Specification: The same as example 2 |
| • | Target: Comparing the PSO method with the ILP method |
| • | Optimization model: Model 6 |
PSO algorithm is one of the most important heuristic algorithms. It was first introduced by Kennedy and Eberhart (1995) and was further refined by many researchers. Among them, the Adaptive Particle Swarm Algorithm (APSO) (Zhan et al., 2009) exhibits good performance. Thus, we exploited the APSO algorithm and the canonical PSO algorithm as the optimization tools for FIR filters design.
There are two methods to obtain the filter coefficient by PSO algorithm. The first one is to exploit the PSO algorithm to search h directly (Ababneh and Bataineh, 2008), named the direct-search approach here. The other approach is frequency sampling method, i.e., exploiting the PSO algorithm to search samples in the frequency domain and the filter coefficient h can be obtained by solving a linear matrix equation (Lim, 1990; Gu et al., 2012), named the indirect-search approach here.
The simulation results can be found in Table 3 and Fig. 4. As for the direct-search approach, all the elements of h are clamped at 0.5 (Ababneh and Bataineh, 2008). On the other hand, the non-uniformly sampling is exploited for the indirect-search approach, where the passband (stopband) is equivalently divided into:
points and the passband (stopband) samples are clamped within [0.7, 1.3] ([-0.3, 0.3]).
The result shows that the indirect-search approach outperforms the direct-search method and the APSO algorithm outperforms the canonical PSO algorithm. However, even the performance of the best APSOF algorithm is inferior to that of ILP and the former even takes significant large computation times.
| Table 3: | Test results of example 5 |
| D: Direct search method, F: Frequency sampling method | |
| Fig. 4: | Magnitude response in example 5: x-axis is the digital frequency and y-axis is the response amplitude |
Accordingly, we can draw a conclusion that in our study, the ILP algorithm is superior to the PSO algorithm.
CONCLUSION
An iterative linear programming method for equiripple LPF designing is proposed in this study which exploits the non-uniform frequency sampling and exchange algorithm to reduce the constrain number (the discrete frequency number) and overcomes drawbacks of the conventional method. Numerical computations also show that the proposed method achieves better performance than conventional linear programming method and the modern heuristic algorithms.
ACKNOWLEDGMENTS
This study was supported by Zhejiang provincial NSF under grant No. Y1090645, the key project of Chinese Ministry of Education under grant No. 210087 and in part by the open research fund of National Mobile Communications Research Laboratory, Southeast University (No. 2010D06).