Thread View: gwene.acm.algorithms.transactions
1 messages
1 total messages
Started by unknown
Thu, 25 Jul 2019 02:00
Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival Times
Author: unknown
Date: Thu, 25 Jul 2019 02:00
Date: Thu, 25 Jul 2019 02:00
1 lines
895 bytes
895 bytes
Ulrich Brenner, Anna Hermann<br /><br />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 And-Or path, i.e., a formula of type t0 ∧ (t1 ∨ (t2 ∧ (… tm−1) …) or t0 ∨ (t1 ∧ (t2 ∨ (… tm−1) …). We present an algorithm that computes the fastest known Boolean circuit for an And-Or path with given arrival times a(t0), …, a(tm−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 log2 W + log2 log2m + log2 log2 log2 m + 4.3, where W := ∑i = 0m−1 2a(ti). <p><a href="http://dl.acm.org/citation.cfm?id340321">Link</a>
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads