Faster Circuits and Shorter Formulae for Multiple Addition, Multiplcation and Symmetric Boolean Functions
Document Type
Conference Proceeding
Department
Mathematics (HMC)
Publication Date
10-1990
Abstract
A general theory is developed for constructing the shallowest possible circuits and the shortest possible formulae for the carry save addition of n numbers using any given basic addition unit. (A carry save addition produces two numbers whose sum is equal to the sum of the n input numbers).
More precisely, it is shown that if BA is a basic addition unit with occurrence matrix N then the shortest multiple carry save addition formulae that could be obtained by composing BA units are of size n1/p+o(1) where p is the unique real number for which ||N||p = 1. (Here ||N||p is the usual Lp norm of the matrix N). 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(q))log n could be constructed by combining BA units.
Based on these optimal constructions of multiple carry save adders we construct the shallowest known multiplication circuits. The depth of the obtained n x n bit multiplication circuit, which uses only dyadic gates, is 3.71 log n. As for carry save addition, the result of the multiplication is given as a sum of two numbres. This construction improves previous results of Ofmen, Wallace, Khrapchenko and others.
Mutiple carry save adders can also be used to construct formulae for symmetric Boolean functions. Here we are able to construct Boolean formulae of size O(n3.16) for many symmetric Boolean functions, including the majority of Boolean formulae of size O(n3.30) for all symmetric Boolean functions. This improves previous results of Khrapchenko, Pippenger, Paterson and Peterson.
Rights Information
© 1990 IEEE
DOI
10.1109/FSCS.1990.89586
Recommended Citation
Patterson, Michael S., Nicholas Pippenger and Uri Zwick. "Faster Circuits and Shorter Formulae for Multiple Addition, Multiplcation and Symmetric Boolean Functions." IEEE Symp. on Foundations of Comp. Sci., 31 (1990), 642-650.
