For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Some Lower Bounds of Cyclic Shift on Boolean Circuits
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Boolean circuits, cyclic shift, lower bounds, partitionings, synchronous circuits,
Full Text: PDF>>
We define two restricted classes of Boolean circuits by assuming the following conditions on underlying graphs of circuits, and prove, for each class, nonlinear lower bounds on size of circuits computing cyclic shifts: ・ for any two paths from the same input to the same output node, the sequences of depths of nodes along these paths are the same. ・ A circuit is partitioned into subcircuits such that each subcircuit has at most o(log n) output gates and the multivalued circuit obtained from the partition is directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.