|
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.
Received: 22.07.2003
Citation:
D. A. Zhukov, “On a class of cell circuits”, Diskr. Mat., 18:4 (2006), 84–98; Discrete Math. Appl., 16:5 (2006), 499–512
Linking options:
https://www.mathnet.ru/eng/dm81https://doi.org/10.4213/dm81 https://www.mathnet.ru/eng/dm/v18/i4/p84
|
Statistics & downloads: |
Abstract page: | 549 | Full-text PDF : | 257 | References: | 39 | First page: | 16 |
|