On a class of cell circuits

D. A. Zhukov


Abstract: We introduce a class of cell circuits, $T$-circuits, and describe a connection between the lower bound for the area and the depth of the circuits of this class: the less the depth the greater the area of a circuit. We give examples of $T$-circuits with logarithmic depth in the problem of calculation of $n$ prefix sums and also of sums and differences of two $n$-digit numbers. It is shown that the area of these circuits is $O(n\log n)$ and has the optimal order.

UDC: 519.7

Received: 22.07.2003

DOI: 10.4213/dm81

 English version: Discrete Mathematics and Applications, 2006, 16:5, 499–512

Bibliographic databases:

• 
• 
• 
•