應用於進位儲存加法器式多常數乘法設計面積最小化之智慧型正負號延伸及精確位元計算技術

Abstract

在眾多用於訊號處理的特殊應用積體電路 (ASIC)中，比如有限脈衝響應濾波器(FIR filter) 、無限脈衝響應濾波器(IIR filter) 、離散餘弦轉換 (DCT)和快速傅立葉轉換(FFT)，多常數乘法是一項廣泛用於取代一般乘法器的做法。只用加法器、減法器和平移的多常數乘法模組可以大幅度減少硬體面積。對高速的應用而言，因為基於進位傳遞加法器 (carry propagation adder)的多常數乘法有著冗長的進位傳遞，所以基於進位儲存加法器(carry save adder)的架構的多常數乘法就發展出來。目前的基於進位儲存加法器的架構的多常數乘法只發展到將進位儲存加法器的數量最佳化，卻忽略了每個進位儲存加法器在實作上的差異。然而，不像進位傳遞加法器，一般的正負號延伸 (sign extension)並不適用於進位儲存加法器。而且，在每個進位儲存加法器之間，字元長度的變異性是很強烈的。在本篇論文中，我們提出一個叫做智慧型正負號延伸的系統化的正負號延伸方法來減少字元長度。將其和精確位元計算技術結合後，再用整數線性規畫(ILP)來做多常數乘法設計的面積最佳化。實驗結果顯示，和傳統的多常數方法比較，面積的改善幅度最高可達30%。

Multiple constant multiplication (MCM) method is widely adopted as a replacement of general purpose multiplier in many ASIC signal processing systems such as FIR filter, IIR filter, DCT and FFT. The MCM block that consists only adders, subtractors and shifters can reduce area cost significantly. For high-speed applications, carry save adder (CSA) based MCM is proposed because the long carry propagation path in traditional carry propagation adder (CPA) is reduced. Currently, all published algorithms of CSA-based MCM problem only count to word level without touching the details of implementation. However, unlike CPA, trivial sign extension is not suitable for CSA. Also, the word length variation in different CSA's is large. In this thesis, we propose a new systematic method called smart sign extension to reduce adder bits and combine it with accurate bit counting while doing MCM area optimization by an ILP (Integer Linear Programming) tool. Experimental results show an area improvement up to 30% compared to the conventional MCM method.