Optimal carry save networks
Optimal carry save networks
复制标题
最佳进位保存网络
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
M. Paterson;N. Pippenger;Uri Zwick
本文给出了一个一般性的理论，以任意给定的基本保留进位加法器为构造块，构造n个数保留进位加法的渐近最浅网络和渐近最小网络（相对于公式大小）。利用最佳进位保留附加网络，得到了已知的最浅乘法电路和多数函数（以及许多其它对称布尔函数）的最短公式。本文描述了一种简单的基本进位保存加法器，用它构造了深度为3.71logn的乘法电路（其结果为两个数之和）和大小为O（n3.13）的多数公式。使用这里没有描述的更复杂的基本进位保存加法器，可以进一步改进这些结果。目前，我们的深度最佳界限为3.57 log n，公式大小最佳界限为O（n3.13）。
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.