Minimal Parallel Prefix Circuits / Sergeev I.S. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2011. № 5. P. 48-51 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 0].
The exact complexity of the minimal prefix circuit of width m and depth [log2 m] + 1 is obtained in the case when m is a power of two. New upper bounds for the complexity of prefix circuits are obtained under various depth restrictions and separately for circuits of XOR-gates.
Key words:
prefix circuits, complexity, depth.