Sparse FIR filter design and prediction - Zhao, Heng (2015)
In digital filter design, sparse filters have been suggested as an efficient structure to reduce the implementation and computational cost. In a sparse filter, a considerable number of its coefficients are set to zero; this means its non-zero coefficients are significantly less than traditional non-sparse filters. However, with a given frequency domain specification it is difficult to obtain the most sparse design in polynomial time when the total number of coefficients is large. Many efficient algorithms are proposed to design reasonably sparse filters but not necessarily the most sparse ones. In this research, a genetic algorithm (GA) is proposed to resolve the sparse filter design issue. The position of the filter’s zero coefficients are encoded as chromosomes in GA. Different chromosomes represent different sparse filters, which may be feasible or infeasible solutions according to a given frequency domain specification. This evolutionary algorithm performs an intelligent search among all chromosomes to locate the best feasible solution. While this algorithm gives no guarantee that its solutions are optimal, the possibility to obtain optimal results is good. Test examples are designed and the results show that the proposed method outperforms existing sparse filter design algorithms. Enlightened by the predictability in the order of optimal low-pass filter (e.g. Kaiser’s formula), certain predictability is expected in the minimum number of non-zero coefficients too. It is found that the number of non-zero coefficients for low-pass sparse filters can be predicted using the frequency domain parameters. Formulas to predict the possible minimum number of multipliers required by a sparse filter is proposed based on the data fitting results of experiment data. These formulas may give filter designers some ideas about whether or not an efficient sparse filter can be obtained with a given frequency domain specification before the filter is designed.