An iterative minimax approximation technique, based on the Lawson's algorithm coupled with the weighted least square approximation, is proposed for the design of linear phase FIR discrete filters. The Lawson's algorithm is an iterative approximation technique which minimizes a Chebychev error norm. For each iteration, the weight is adjusted according to the approximation errors of the previous iteration and the weighted least square approximation using the adjusted weight is made. The technique is quiet general and can be applied to the design of various types of FIR discrete filters including one and two dimensional FIR digital filters, non-uniformaly sampled discrete filters and two-dimensional hexagonally sampled FIR digital filters. New design technique is especially useful for the design of two-dimensional FIR digital filters and two dimensional hexagonally sampled FIR digital filters, for which there are only a few design techniques proposed thus far. The existing techniques are computationally very complex and it is difficult to visualize the design processes. The efficiency of the new design technique based on the Lawson's iteration is directly related to an efficient implimentation of the weighted least square approximation using FFT and vector Toeplitz inversion.
To demonstrate the capabilities of the new technique, several cicular symmetric two-dimensional FIR digital filters are designed. The results are comparable to the filters designed using the ascent exchange algorithm. The new design technique allows design of filters of size as large as 25 * 25 without exponential increase in computation time. Besides the ability of large size filter design, another advantage of the new technique is that it can be directly applicable to the design of non-rectangularly sampled FIR filters such as hexagonally sampeld FIR digital filters. Several examples of hexagonally sampled FIR digital filters are also shown.
As an alternative to Lawson's iteration, Bandler's nonlinear minimax optimization algorithm is also considered for FIR digital filter design. Since the basis function for 2-D FIR digital filters does not satisfy the Harr condition, many convensional techniques such as ascent algorithm and Lawson's iteration do not guarantee convergencies. Thus it is important to note that, the convergency of the Bandler's algorithm has been proved without any constraints on the basis functions, and the algorithm can be used as a basis for the comparison of various design techniques.
본 논문에서는 FIR discrete filter의 design에 유용한 Frequency weighted least square design technique를 Lawson 의 algorithm에 적용하여 minimax sense에서 최적인 FIR digital filter를 design 하는 방법을 제안 하였다. 1 차원의 경우, 적당한 가속화 방법에 의하여 빠른 시간 내에 최적인 filter를 design 할 수 있었고, 2 차원의 경우에서는 그 filter의 basis function들의 집합이 Harr condition을 만족하지 않으므로 Lawson 의 algorithm은 원만하게 수렴하지 못하여 그 algorithm을 약간 수정하여 최적인 2 차원의 FIR digital filter 를 얻을 수 있었다. 그리고, 이 방법을 minimax sense에서 최적인 Hexagonally sampled FIR digital filter를 design 할 수 있도록 연장하였다.
또한, 2 차원의 경우 FIR digital filter 의 basis function들의 성질에 아무런 제약이 필요없는 Bandler의 nonlinear minimax optimization algorithm 을 새로운 방법으로서 제안 하였다.