The Library
Optimal carry save networks
Tools
Tools
Tools
Paterson, Michael S., Pippenger, Nicholas and Zwick, Uri (1990) Optimal carry save networks. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-166.pdf - Requires a PDF viewer. Download (18Mb) | Preview |
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.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Network processors | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | October 1990 | ||||
| Dates: |
|
||||
| Number: | Number 166 | ||||
| Number of Pages: | 19 | ||||
| DOI: | CS-RR-166 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | M.S. Paterson, N. Pippenger and Uri Zwick, “Optimal Carry Save Networks” <i>Boolean Functional Complexity</i>, London Mathematical Society Lecture Note Series <b>169</b>, Cambridge University Press, pp. 174-201 (1992) | ||||
| Funder: | Science and Engineering Research Council (Great Britain) (SERC), Natural Sciences and Engineering Research Council of Canada (NSERC), European Commission (EC), Universiṭat Tel-Aviv | ||||
| Grant number: | 3075 (ALCOM) (EC) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
