常數乘法之演算法與其硬體實現

Efficient Algorithms for Constant Multiplications and Their Hardware Implementation

鞠萍章(Ping-Chang Jui)

指導教授 ： 魏慶隆 ； 薛木添

國立中央大學/資訊電機學院/電機工程學系/博士(2015年)

摘要

整數常數乘法器用於執行整數常數值與輸入數值的相乘，相乘的執行不需乘法器而僅用加法及移位即可。一般而言，移位可以固線(hardwired)方式於板塊間連接，就硬體實現成本而言被視為是免費的；因此所需加法器的數量決定整數常數乘法器硬體實現的成本。
整數常數乘法為數位信號處理演算法最普遍的運算之一，常應用於數字信號處理、影像處理、高精度的算術運算、加密等；整數常數乘法也可應用於信息冗餘設計所需的算術編碼技術如AN碼、乘法布斯編碼技術、高基數的SRT除法等。
常數乘法器的設計已經研究了數十年，其重點在於如何減少單一或多個常數乘法所需的加法器數量，對所需的加法器類型並不關心。本論文著眼於高速常數乘法之高效演算法和硬體實現的研究，並以常數(2^k+-1)的快速乘法為範疇。
(2^k+1)N的運算值可由N值加上2^kN值 (將N值向左移k位元) 而得；另一方面，(2^k-1)N的運算值可由2^kN值減去N值，或加 (-N) 值而得。本論文提出一快速的加法基本單元 (UCA)，並據以建構UCA為主之加法器。UCA與常用的全加器（FA）相比，UCA僅需一個單位的邏輯閘延遲，而FA需要二個單位延遲。模擬結果顯示，所提出的基於UCA的加法器，如漣波進位加法器 (RCA)、超前進位加法器 (CLA)，以及混合RCA/CLA加法器（HyA），相較於基於FA的相同型加法器有較快速的性能及較低的硬體實現成本。所提出的UCA設計理念可很容易的應用於其他不同類型的整數常數乘法。

關鍵字

常數乘法 ； 乘法器 ； 漣波進位加法器 ； 超前進位加法器 ； 混合加法器

並列摘要

Integer constant multiplier performs a multiplication of a data-input with an integer constant value. The multiplication by a fixed-point constant can be done “multiplier-less” using additions and shifts only. Since the shifters are implemented as hard-wired inter-block connections, they are considered “free.” Thus, the number of adders determines the implementation cost.
The integer constant multiplication is a common operation in digital signal processing (DSP) algorithms with the following applications: digital signal processing, image processing, multiple precision arithmetic, cryptography, etc. It can also be applied for the arithmetic coding technique, such as AN code for information redundant design, Booth encoding technique for multiplications, and high-radix SRT division, etc.
Constant multiplier designs have been investigated for several decades. However, the emphasis was placed on minimizing the number of additions required to achieve the multiplications with single constant or multiple constants. Moreover, the types of adders to be implemented are not of concern. This motivates to this study developing efficient algorithms and hardware implementation for fast constant multiplications. This study focuses on the development of fast multiplications of the constants in the form of (2^k+-1).
The value of (2^k+1)N can be computed by adding N to its k-bit left-shifted value 2^kN. On the other hand, the value of (2^k-1)N can be computed by subtracting N from its k-bits left-shifted value 2^kN, or adding (-N) to 2^kN. The fast unit cells for additions (UCAs) are introduced to construct the UCA-based adders. The proposed UCA cells requires only one gate delay, while the conventional full adder (FA) needs two gate delays. Simulation results will show that the proposed UCA-based adders, such as ripple carry adders (RCAs), carry lookahead adders (CLAs), and hybrid RCA/CLA adders (HyAs), achieve faster speed performance with reasonably small hardware cost than the FA-based ones. The UCA design concept is readily applied to the multiplications with the constants in other forms.

並列關鍵字

Constant multiplication ； multiplier ； ripple carry adders ； carry lookahead adders ； hybrid adders

參考文獻

[2] A. K. Oudjida and N. Chaillet, “Radix-2r arithmetic for multiplication by a constant,” IEEE Trans. On Circuits and Systems – II: Express Briefs, Vol. 61, No.5, pp.349-353, May 2014.

[5] N. Gaitanis, “Totally self-checking checker for 3N arithmetic codes,” Electronics Letter, Vol. 17, pp.685-686, 1983.

[6] K. Huang, Computer Arithmetic: Principles, Architecture, and Design, Wiley & Sons, Inc., 1979.

[9] M. D. Ercegovac and T. Lang. Digital Arithmetic. Morgan Kaufmann, 2003.

[11] C. L. Wey, "Built-In Self-Test (BIST) Design of High-Speed Carry-free Dividers," IEEE Trans. on VLSI Systems, Vol. 4, No. 1, pp. 141-145, March 1996.