<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-166

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

M.S. Paterson, N. Pippenger and U. Zwick, Optimal Carry Save Networks (October 1, 1990).

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 the optimal carry save additional 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 (n3.13) 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 (n3.13) for formula size.

<%@ include file="cited.html" %>

M.S. Paterson, N. Pippenger and Uri Zwick, "Optimal Carry Save Networks" Boolean Functional Complexity, London Mathematical Society Lecture Note Series 169, Cambridge University Press, pp. 174-201 (1992)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>