應用設計空間探索於有限脈衝響應濾波器之硬體最佳化

Design Space Exploration for Hardware-Efficient FIR Filter Design

楊創任(Chuang-Ren Yang)

指導教授 ： 周景揚

國立交通大學/電機學院/電子工程系所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00589

摘要

在這篇論文中，我們提出一個演算法，針對線性相位的有限脈衝響應濾波器選擇一組符合規格的濾波器係數，此演算法的主要目的是最小化一個利用多重常數乘法器所實作的有限脈衝響應濾波器中的加法器個數。在傳統的設計中，實作於有限脈衝響應濾波器中的多重常數乘法器只會利用加法和左移(left-shift)這兩種運算，然而，我們的演算法允許使用右移(right-shift)運算來擴展設計空間。我們也發展一個啟發式的分支限界法(branch and bound method)，它可以使我們在擴展的設計空間中有效率的搜尋。實驗數據顯示我們的演算法相較於目前存在最好的方法，在加法器個數上最多可以改善30.6%且平均改善13.8%。

關鍵字

有限脈衝響應濾波器 ； 多重常數乘法器

並列摘要

In this thesis, we propose an algorithm to determine coefficients for a specified linear phase FIR filter design. The target of our algorithm is to minimize the adder cost as the FIR filter is implemented through multiple constant multiplication (MCM). Traditionally, an MCM block in an FIR filter design is implemented using addition and left-shift operations only. Nevertheless, our algorithm allows the use of right-shift operations to further expand the design space. We also develop a heuristic-based approximated branch and bound method to search in broader design space efficiently. Experimental results show that our method can reduce the adder cost by up to 30.6% and 13.8% on average as compared to an existing state-of-the-art technique.

並列關鍵字

FIR filter ； MCM

參考文獻

[1] Y. Voronenko and M. Püschel, “Multiplierless multiple constant multiplication,” in ACM Transactions on Algorithms, 2007, vol. 3, pp. 11.

[2] A. G. Dempster and M. D. Macleod, “Use of minimum-adder multiplier blocks in FIR digital filters,” in IEEE Transactions on Circuits and Systems I, 1995, vol. 42, pp. 569-577.

[3] A. G. Dempster and M. D. Macleod, “Using all signed-digit representations to design single integer multipliers using subexpression elimination,” in International Symposium on Circuits and Systems, 2004, vol. 3, pp. III-165-8.

[4] J. Yli-Kaakinen and T. Saramaki, “A systematic algorithm for the design of multiplierless FIR filters,” in International Symposium on Circuits and Systems, 2001, vol. 2, pp. 185-188.

[5] O. Gustafsson and L. Wanhammar, “Design of linear-phase FIR filters combining subexpression sharing with MILP,” in Midwest Symposium on Circuits and Systems, 2002, vol. 3, pp. III-9-III-12.