Abstract:
We prove that the complexity of a universal depth-$n$ parallel prefix circuit on $2^n$ inputs with fanout bounded by $2$ is at least $0.75(n-1)2^{n}.$ We also propose a number of simple constructions and upper complexity bounds on fanout-$2$ prefix circuits of depth $n+k.$ Illustr. 4, bibliogr. 14.
Fulltext:
PDF file (418 kB)