
Rajit Manohar and José A. Tierno
The prefix problem is to compute all the products x1*x2*...*xk, for
1<= k<= n, where * is an associative
binary operation. We start with an asynchronous circuit to solve this
problem with O(log n) latency and O(n log n) circuit size, with
O(n) *operations in the circuit. Our contributions are:

A modification to the circuit that improves its averagecase
latency from O(log n) to O(loglog n) time; and
 A further modification that allows the circuit to run at
fullthroughput i.e., with constant response time.
The construction can be used to obtain a
asynchronous adder with O(log n)
worstcase latency and O(loglog n) averagecase latency.

