應用二進位共用項分享之延遲且面積最佳化的有限脈衝響應濾波器合成技術

Delay and Area Optimal FIR Filter Synthesis using binary subexpression sharing

許耀中(Yao-Chung Hsu)

指導教授 ： 周景揚

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

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

摘要

摘 要
多重常數乘法器(MCM)被廣泛的使用在數位訊號處理的應用上，如濾波器。它將輸入資料乘上一組常數係數。由於常數乘法運算能利用加法和二進位的位移來實現，而不需使用傳統的乘法運算，大多數的無乘法(multiplier-less)多重常數乘法器演算法著重在減少加法運算的次數。當設計一個高速的多重常數乘法器時，最長路徑延遲的最佳化會被考慮到設計中。在本篇論文，我們用整數線性規畫法(ILP)和二進位共用項分享技術來達到多重常數乘法器的延遲和面積最佳化，並且同時地利用進位前瞻加法器(CLA)與進位儲存加法器(CSA)來實現加法架構。且我們的方法會找出所有可能的二進位共用項來與目標配對。在實驗部分，我們的方法與前人的作法相比，在面積與延遲上都有更好的表現。

關鍵字

共通項 ； 多重常數乘法器 ； 共通項簡化法 ； 二進位共通項簡化法 ； 整數線性規畫法

並列摘要

The multiple constant multiplication (MCM) is extensively used in digital signal processing (DSP) applications, such as filters. It multiplies the input data with a set of constant coefficients. Since constant multiplication can be implemented by adders and binary shifters instead of generic multipliers, many multiplier-less MCM algorithm are proposed to minimize the total number of adders. While designing a high-speed MCM, the adder architecture should be taken into consideration to further minimize the critical path delay. In this thesis, we present an ILP-based approach for delay and area-optimal binary subexpression sharing for MCM design which uses different adder architectures (i.e., carry look-ahead adder and carry save adder) simultaneously. The proposed method exploits patterns acquired from all possible symbols (also known as subexpressions) to match the target MCM design optimally. The experimental results show that the proposed algorithm can achieve significant performance improvement as compared with the prior art.

並列關鍵字

common subexpression ； MCM ； CSE ； BSE ； ILP

參考文獻

[1] K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementation. New York: Wiley, 1999.

[4] H.-J. Kang and I.-C. Park, “FIR filter synthesis algorithms for minimizing the delay and the number of adders,” IEEE Transactions on Circuits and Systems. II, Analog Digital Signal Process, vol. 48, no. 8, pp. 770–777, Aug. 2001.

[5] A. Dempster et al., “Designing multiplier blocks with low logic depth,” IEEE international symposium on Circuits and Systems, May 2002, vol. 5, pp. 773–776.

[6] Y. Takahashi and M. Yokoyama, “New cost-effective VLSI implementation of multiplierless FIR filter using common subexpression elimination," IEEE international symposium on Circuits and Systems, May 2005, vol. 2, pp. 1445–1448.

[7] C. Yao, H. Chen, T. Lin, C. Chien and C. Hsu, “A novel common subexpression elimination method for synthesizing fixed-point FIR filters,” IEEE Transactions on Circuits and Systems I, pp. 2211–2215, Nov. 2004.