Optimal Carry Save Networks

Summary

Abstract

A general theory is developed for constructing the asymptotically shallowest networks and the asymptotically smallest networks (with respect to formula size) for the carry save addition of n numbers using any given basic carry save adder as a building block.

Using these optimal carry save addition networks the shallowest known multiplication circuits and the shortest formulae for the majority function (and many other symmetric Boolean functions) are obtained.

In this paper, simple basic carry save adders are described, using which multiplication circuits of depth 3.71 log n (the result of which is given as the sum of two numbers) and majority formulae of size O(n^3.21) are constructed. Using more complicated basic carry save adders, not described here, these results could be further improved. Our best bounds are currently 3.57 log n for depth and O(n^3.13) for formula size.

Introduction

The question ‘How fast can we multiply?’ is one of the fundamental questions in theoretical computer science. Ofman-Karatsuba and Schönhage-Strassen tried to answer it by minimising the number of bit operations required, or equivalently the circuit size. A different approach was pursued by Avizienis, Dadda, Ofman, Wallace and others. They investigated the depth, rather than the size of multiplication circuits.

The main result proved by the above authors in the early 1960's was that, using a process called Carry Save Addition, n numbers (of linear length) could be added in depth O(log n). As a consequence, depth O(log n) circuits for multiplication and polynomial size formulae for all the symmetric Boolean functions are obtained.