Parallel Prefix Computation
Richard E. Ladner, Michael J. Fischer · Journal of the ACM · 1980
The prefix problem is to compute all the products x t o x2 .... o xk for i ~ k .~n, where o is an associative operation A recurstve construction IS used to obtain a product circuit for solving the prefix problem which has depth exactly [log:n] and size bounded by 4n An application yields fast, small Boolean ctrcmts to simulate fimte-state transducers.By simulating a sequentml adder, a Boolean clrcmt which has depth 2[Iog2n] + 2 and size bounded by 14n Is obtained for n-bit binary addmon The size can be decreased significantly by permitting the depth to increase by an addmve constant KEY WORDS AND PHRASES automaton, binary addmon, clrcmt, combinational complexity, depth, fanout, parallehsm, size, transducer CR CATEGORIES 5.22, 5 25, 6 1, 6 32 X3 o X2.