Document Type
Article
Department
Mathematics (HMC)
Publication Date
1990
Abstract
A general theory is developed for constructing the shallowest possible circuits and the shortest possible formulas for the carry-save addition of n numbers using any given basic addition unit. More precisely, it is shown that if BA is a basic addition unit with occurrence matrix N, then the shortest multiple carry-save addition formulas that could be obtained by composing BA units are of size n1p+o(1)/, where p is the unique real number for which the Lp norm of the matrix N equals 1. An analogous result connects the delay matrix M of the basic addition unit BA and the minimal q such that multiple carry-save addition circuits of depth (q+o(1)) log n could be constructed by combining BA units. On the basis of these optimal constructions of multiple carry-save adders, the shallowest known multiplication circuits are constructed
Rights Information
© 1990 IEEE
Terms of Use & License Information
DOI
10.1109/FSCS.1990.89586
Recommended Citation
M. Paterson, N. Pippenger, U. Zwick, Faster Circuits and Shorter Formulas for Multiple Addition, Multiplication and Symmetric Boolean Functions, IEEE Symp. on Foundations of Comp. Sci., 31, 642-650 (1990)
