Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival Times

Ulrich Brenner; Anna Hermann

doi:10.1145/3340321

paper

Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival Times

arXiv:1710.08267 · doi:10.1145/3340321

Abstract

We consider the fundamental problem of constructing fast circuits for the carry bit computation in binary addition. Up to a small additive constant, the carry bit computation reduces to computing an \aop, i.e., a formula of type $t_{0} \land (t_{1} \lor (t_{2} \land (\dots t_{m - 1}) \dots)$ or $t_{0} \lor (t_{1} \land (t_{2} \lor (\dots t_{m - 1}) \dots)$ . We present an algorithm that computes the fastest known Boolean circuit for an \aop~ with given arrival times $a (t_{0}), \dots, a (t_{m - 1})$ for the input signals. Our objective function is delay, a natural generalization of depth with respect to arrival times. The maximum delay of the circuit we compute is $lo g_{2} W + lo g_{2} lo g_{2} m + lo g_{2} lo g_{2} lo g_{2} m + 4.3$ , where $W := \sum_{i = 0}^{m - 1} 2^{a (t_{i})}$ . Note that $⌈ lo g_{2} W ⌉$ is a lower bound on the delay of any circuit depending on inputs $t_{0}, \dots, t_{m - 1}$ with prescribed arrival times. Our method yields the fastest circuits for \aop s, carry bit computation and adders in terms of delay known so far.