Some Lower Bounds of Cyclic Shift on Boolean Circuits

Tatsuie TSUKIJI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.4   pp.520-523
Publication Date: 1996/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
Boolean circuits,  cyclic shift,  lower bounds,  partitionings,  synchronous circuits,  

Full Text: PDF>>
Buy this Article




Summary: 
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.