Shallow circuits and concise formulae for multiple addition and multiplication |
| |
Authors: | Michael Paterson Uri Zwick |
| |
Affiliation: | (1) Department of Computer Science, University of Warwick, CV4 7AL Coventry, England;(2) Department of Computer Science, Tel Aviv University, 69978 Tel Aviv, Israel |
| |
Abstract: | A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log2n and {, , }-circuits of depth 4.95 log2n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log2n and 5.95 log2n.We also get {, , }-formulae of sizeO (n3.13) and {, }-formulae of sizeO (n4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions. |
| |
Keywords: | Multiplication carry-save addition circuits formulae |
本文献已被 SpringerLink 等数据库收录! |
|