Faster circuits and shorter formulae for multiple addition,multiplication and symmetric Boolean functions

摘要

A general theory is developed for constructing the shallowestpossible circuits and the shortest possible formulas for the carry-saveaddition of n numbers using any given basic addition unit. Moreprecisely, it is shown that if BA is a basic addition unit withoccurrence matrix N, then the shortest multiple carry-saveaddition formulas that could be obtained by composing BA unitsare of size n¹p+o(1)/, where p is theunique real number for which the L_p norm of thematrix N equals 1. An analogous result connects the delaymatrix M of the basic addition unit BA and the minimalq such that multiple carry-save addition circuits of depth(q+o(1)) log n could be constructed bycombining BA units. On the basis of these optimal constructionsof multiple carry-save adders, the shallowest known multiplicationcircuits are constructed