低成本(2n±1)餘數系統乘法器

A Low Cost Modulo (2n±1) RNS Multiplier

楊宇博(Yu-Po Yang)

指導教授 ： 張慶元 ； 羅浩榮

國立清華大學/電機資訊學院/電機工程學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00382

摘要

模數(2n – 1)和(2n + 1)是數位訊號處理(digital signal processor)中的餘數系統(residue number system）和密碼系統(cryptosystem)以及編、解碼系統中的使用頻率甚高，而以此模數為基礎的餘數系統乘法器(RNS multiplier)在數位系統中，使用上也相當的廣泛。在過去的文獻中便提出將(2n – 1)和(2n + 1)餘數乘法器合併，並且使用餘數乘法器再撘配上前看式進位加法器(carry look-ahead adder)，來實現(2n ± 1)餘數系統乘法器，單一電路中擁有兩種運算能力，藉此來節省硬體成本，另有人將自我對偶的特性套用至餘數乘法器來節省電路面積，然而仍然有許多能夠加以改善的空間。
在本篇論文中，除了沿用文獻中所提出之理論與方法，並觀察其電路上之特性，與演算法中限制輸入部分綜合考量，進而將電路做進一步的化簡，實驗用TSMC 0.18μm製程配合Synopsys公司所提供的Design Compiler來進行模擬，並且對面積作最佳化來取得所有模擬數據，電路面積、延遲時間、功率消耗皆能利用所提方法而得到改善，一些對於電路成本具有指標性的數據面積與延遲時間平方的積(AT2)以及延遲時間與電路功率消耗的乘積(Delay-Power)也能夠有大幅的改善，以4-bit為例，可改善面積16.64%，時間延遲節省14.36%，功率消耗減少25.35%，AT2以及Delay-Power分別節省38.87%與36.70%，最後，所提低成本(2n ± 1)餘數系統乘法器，使用Xilinx公司所提供之FPGA電路板實現硬體驗證，經驗證過後確認函數無誤。

關鍵字

餘數系統 ； 乘法器

並列摘要

無資料

並列關鍵字

RNS ； multiplier ； modulo

參考文獻

[1] A.S. Ashur, M.K. Ibrahim, A. Aggoun, ”Novel RNS structures for the moduli set (2n - 1, 2n, 2n + 1) and their application to digital filter implementation,” Signal Processing, vol. 46, pp. 331-343, Oct, 1995.

[2] Y.T. Pai, Y.K. Chen, “The fastest carry lookahead adder,” Proc. IEEE Int’l Workshop on Electronic Design, Test and Applications, pp. 434-436, Jan 2004.

[5] R. Zimmermann, “Efficient VLSI implementation of modulo 2n±1 addition and multiplication,” Proc. 14th Symp. Computer Arithmetic, pp. 158-167, Apr. 1999.

[6] C. Efstathiou, H.T. Vergos, D.Nikolos, “Modified Booth Modulo 2n-1 Multipliers,” IEEE Transactions on Computers, vol. 53, pp. 370-374, Mar. 2004.

[7] L.Sousa, R. Chaves, “A universal architecture for designing efficient modulo 2/sup n/+1 multipliers,” IEEE Transactions on Circuit and Systems, vol. 52, pp. 1166-1178, June 2005.