This article is cited in 1 paper

Short notes

Minimal parallel prefix circuits

I. S. Sergeev

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The exact complexity of a minimal prefix circuit of width $m$ and depth $\lceil\log_2 m\rceil$ 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 the circuits of XOR-gates.

Key words: prefix circuits, complexity, depth.

UDC: 519.714

Received: 19.09.2010

Bibliographic databases:

• 
•