Fast Signed-Digit Multi-operand Decimal Adders

Jeff Rebacz, Erdal Oruklu, Jafar Saniie
DOI: 10.4236/cs.2011.23032                

Abstract

Decimal arithmetic is desirable for high precision requirements of many financial, industrial and scientific applications. Furthermore, hardware support for decimal arithmetic has gained momentum with IEEE 754-2008, which standardized decimal floating-point. This paper presents a new architecture for two operand and multi-operand signed-digit decimal addition. Signed-digit architectures are advantageous because there are no carry-propagate chains. The proposed signed-digit adder reduces the critical path delay by parallelizing the correction stage inherent to decimal addition. For performance evaluation, we synthesize and compare multiple unsigned and signed-digit multi-operand decimal adder architectures on 0.18μm CMOS VLSI technology. Synthesis results for 2, 4, 8, and 16 operands with 8 decimal digits provide critical data in determining each adder's performance and scalability.

Keywords

Computer Arithmetic, Decimal Arithmetic, Signed-Digit, Multi-operand Adder, BCD

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	BigDecimal, 2008. http://java.sun.com/products.
[2]	DecNumber, AlphaWorks, 2008. http://www.alphaworks.ibm.com/tech/decnumber.
[3]	L. Eisen, et al., “IBM POWER6 Accelerators: VMX and DFU,” IBM Journal of Research and Development, Vol. 51, No. 6, 2007, pp. 663-683. doi:10.1147/rd.516.0663
[4]	C. Webb, “IBM z10: The Next-Generation Mainframe Microprocessor,” IEEE Micro, Vol. 28, No. 2, 2008, pp. 19-29. doi:10.1109/MM.2008.26
[5]	A. Tsang and M. Olschanowsky, “A Study of Database 2 Customer Queries,” Technical Report TR-03.413, IBM Santa Teresa Laboratory, San Jose, USA, 1991.
[6]	L.-K. Wang, C. Tsen, M. Schulte and D. Jhalani, “Benchmarks and Performance Analysis of Decimal Floating-Point Applications,” 5th International Conference on Computer Design, Lake Tahoe, 7-10 October 2007, pp. 164-170. doi:10.1109/ICCD.2007.4601896
[7]	R. Kenney and M. Schulte, “High-Speed Multioperand Decimal Adders,” IEEE Transactions on Computers, Vol. 54, No. 8, 2005, pp. 953-963. doi:10.1109/TC.2005.129
[8]	I. D. Castellanos and J. E. Stine, “Compressor Trees for Decimal Partial Product Reduction,” GLSVLSI’08: Proceedings of the 18th ACM Great Lakes Symposium on VLSI, ACM, Orlando, 4-6 May 2008, pp. 107-110.
[9]	I. S. Hwang, “High Speed Binary and Decimal Arithmetic Unit,” USA Patent No. 4,866,656.
[10]	A. Bayrakci and A. Akkas, “Reduced Delay BCD Adder,” IEEE International Conference on Application Specific Systems, Architectures and Processors, Montreal, 9-11 July 2007, pp. 266-271.
[11]	Y. You, Y. D. Kim and J. H. Choi, “Dynamic Decimal Adder Circuit Design by Using the Carry Lookahead,” IEEE Design and Diagnostics of Electronic Circuits and Systems, Prague, 18-21 April 2006, pp. 242-244. doi:10.1109/DDECS.2006.1649627
[12]	L.-K. Wang and M. Schulte, “A Decimal Floating-Point Adder with Decoded Operands and a Decimal Leading-Zero Anticipator,” 19th IEEE Symposium on Computer Arithmetic, Portland, 8-10 June 2009, pp. 125-134.
[13]	A. Vazquez and E. Antelo, “A High-Performance Significand BCD Adder with IEEE 754-2008 Decimal Rounding,” 19th IEEE Symposium on Computer Arithmetic, Portland, 8-10 June 2009, pp. 135-144.
[14]	L.-K. Wang and M. Schulte, “Decimal Floating-Point Adder and Multifunction Unit with Injection-Based Rounding,” 18th IEEE Symposium on Computer Arithmetic, Montpellier, 25-27 June 2007, pp. 56-68.
[15]	M. Erle, E. Schwarz and M. Schulte, “Decimal Multiplication with Efficient Partial Product Generation,” 17th IEEE Symposium on Computer Arithmetic, Cape Cod, 27-29 June 2005, pp. 21-28.
[16]	M. Erle, M. Schulte and B. Hickmann, “Decimal Floating-Point Multiplication via Carry-Save Addition,” 18th IEEE Symposium on Computer Arithmetic, Montpellier, 25-27 June 2007, pp. 46-55.
[17]	A. Vazquez, E. Antelo and P. Montuschi, “A New Family of High-Performance Parallel Decimal Multipliers,” 18th IEEE Symposium on Computer Arithmetic, Montpellier, 25-27 June 2007, pp. 195-204.
[18]	G. Jaberipur and A. Kaivani, “Improving the Speed of Parallel Decimal Multipliers,” IEEE Transactions on Computers, Vol. 58, No. 11, 2009, pp. 1539-1552. doi:10.1109/TC.2009.110
[19]	T. Lang and A. Nannarelli, “A Radix-10 Digit-Recurrence Division Unit: Algorithm and Architecture,” IEEE Transactions on Computers, Vol. 56, No. 6, 2007, pp. 727-739. doi:10.1109/TC.2007.1038
[20]	A. Vazquez, E. Antelo and P. Montuschi, “A Radix-10 SRT Divider Based on Alternative BCD Codings,” 25th International Conference on Computer Design, Lake Tahoe, 7-10 October 2007, pp. 280-287.
[21]	H. Nikmehr, B. Phillips and C. Lim, “Fast Decimal Floating-Point Division,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 14, No. 9, 2006, pp. 951-961.
[22]	A. Kaivani and G. Jaberipur, “Fully Redundant Decimal Addition and Subtraction Using Stored-Unibit Encoding,” Integration, the VLSI journal, Vol. 43, No. 1, 2010, pp. 34-41.
[23]	L. Dadda, “Multioperand Parallel Decimal Adder: A Mixed Binary and BCD Approach,” IEEE Transactions on Computers, Vol. 56, No. 10, 2007, pp. 1320-1328. doi:10.1109/TC.2007.1067
[24]	A. Svoboda, “Decimal Adder with Signed Digit Arithmetic,” IEEE Transactions on Computers, Vol. C-18, No. 3, 1969, pp. 212-215. doi:10.1109/T-C.1969.222633
[25]	J. Moskal, E. Oruklu and J. Saniie, “Design and Synthesis of a Carry-Free Signed-Digit Decimal Adder,” IEEE International Symposium on Circuits and Systems, New Orleans, 27-30 May 2007, pp. 1089-1092.
[26]	H. Nikmehr, B. Phillips and C. Lim, “A Decimal Carry-Free Adder,” Smart Structures, Devices, and Systems-II, Sydney, 13 December 2005, pp. 786-797.
[27]	B. Shirazi, D. Yun and C. Zhang, “RBCD: Redundant Binary Coded Decimal Adder,” IEE Proceedings on Computers and Digital Techniques, Vol. 136, No. 2, 1989, pp. 156-160. doi:10.1049/ip-e.1989.0021
[28]	B. Shirazi, D. Yun and C. Zhang, “VLSI Designs for redundant Binary-Coded Decimal Addition,” 7th Annual International Phoenix Conference on Computers and Communications, Scottsdale, 16-18 March 1988, pp. 52-56. doi:10.1109/PCCC.1988.10042
[29]	R. Kenney, M. Schulte and M. Erle, “A High-Frequency Decimal Multiplier,” IEEE International Conference on Computer Design: VLSI in Computers and Processors, San Jose, 11-13 October 2004, pp. 26-29. doi:10.1109/ICCD.2004.1347893
[30]	A. Avizienis, “Signed Digit Number Representations for Fast Parallel Arithmetic,” IRE Transactions on Electronic Computers, Vol. EC-10, No. 3, 1961, pp. 389-400. doi:10.1109/TEC.1961.5219227
[31]	B. Parhami, “Generalized Signed-Digit Number Systems: A Unifying Framework for Redundant Number Representations,” IEEE Transactions on Computers, Vol. 39, No. 1, 1990, pp. 89-98. doi:10.1109/12.46283
[32]	J. Rebacz, E. Oruklu and J. Saniie, “High Performance Signed-Digit Decimal Adders,” IEEE International Conference on Electro/Information Technology, Windsor, 7-9 June 2009, pp. 251-255. doi:10.1109/EIT.2009.5189621
[33]	V. Dave, E. Oruklu and J. Saniie, “Design and Synthesis of a Three Input Flagged Prefix Adder,” IEEE International Symposium on Circuits and Systems, New Orleans, 27-30 May 2007, pp. 1081-1084. doi:10.1109/ISCAS.2007.378197
[34]	D. Phatak and I. Koren, “Hybrid Signed-Digit Number Systems: A United Framework for Redundant Number Representations with Bounded Carry Propagation Chains,” IEEE Transactions on Computers, Vol. 43, No. 8, 1994, pp. 880-891. doi:10.1109/12.295850
[35]	J. Rebacz, E. Oruklu and J. Saniie, “Performance Evaluation of Multi-Operand Fast Decimal Adders,” 52nd IEEE International Midwest Symposium on Circuits and Systems, Cancun, 2-5 August 2009, pp. 535-538. doi:10.1109/MWSCAS.2009.5236036